# Teach me a simple, efficient division algorithm

I want to implement arbitrary-precision arithmetic in JavaScript for non-negative integer numbers. Long division isn't efficient if instead of the usual 10 digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) there are 226 digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G, ...). Any pointers? You don't have to explain it in a programming language. In fact, I'd prefer if you didn't.

PS: 26 = ⌊53 / 2⌋. 53 bits is the precision of a float. 15 = ⌊31 / 2⌋. 31 bits is the precision of an int.

Here's what I have. It's in the public domain. It still needs fixing.

function divide(a, b)
{
var i, q, r;
q = create_empty();
r = create_empty();
for (i = get_length(a) - 1; i >= 0; --i) {
q = shift_left(q, 1);
r = prepend(r, get_digit(a, i));
while (!is_less(r, b)) {
q = increment(q);
r = subtract(r, b);
} }
return {quotient: q, remainder: r};
}
-
$2^{16}$ digits? What practical purpose would such an accurate number have? Do you know how to multiply to such accuracy? and how long does multiplication take? – picakhu Jul 25 '11 at 14:52
The arithmetic for numbers that small is already implemented in the computer. If I use those fixed-precision non-negative integer numbers as digits I can write an unfixed-precision non-negative integer number library. – Fox Jul 25 '11 at 14:57
There seems to be a mixup here. picakhu was talking about numbers with $2^{16}$ digits, whereas when you say that these numbers are small and the arithmetic for them is already implemented in the computer, I presume you're talking about numbers up to $2^{16}$, i.e. with $16$ (binary) digits? – joriki Jul 25 '11 at 15:10
Quite a few years ago, I used the division procedure described in Knuth's Art of Computer Programming to write such a program. Knuth's procedure was even then well short of state of the art for theoretical efficiency, but it was simple to code, and, best of all, worked. – André Nicolas Jul 25 '11 at 15:30
Take the long division algorithm as given in Knuth: The Art of Computer Programming, Vol. 2. In the 3rd edition this is Algorithm D in section 4.3.1 on page 272. Googling for the terms knuth "algorithm d" site:books.google.com I got as top link "Hacker's delight" where a C-version of that algorithm is given. – j.p. Jul 25 '11 at 15:45