How to implement (fast) bigint division?

Question

I'm currently making my own BigInt class, by splitting numbers by 7 digits. (i.e. in base 10,000,000)

I implemented addition, subtraction, and multiplication, and now I'm implementing division and mod. I wrote a code that performs division by long division (estimating numbers by dividing most-significant digits), and it works.

However, it is too slow. When I test operations on a 108-digit number and a 67-digit number, it takes 1.9ms to calculate division, much slower than other operations(0.007~0.008ms to calculate addition/subtraction, 0.1ms to calculate multiplication).

Like Karatsuba and FFT algorithm for fast multiplication, what algorithm exists for calculating division? Wikipedia demonstrates some division algorithms (which calculates multiplicative inverse of divisor and multiplies it with dividend), but I think that doesn't help me much implementing division. I read 'Large integer methods' sections too but that doesn't help me too... :(

Answer 1

The standard reference for big-integer arithmetic is Donald Knuth's book Art of Computer Programming, Volume 2, Section 4.3. His division algorithm is basically the grade-school algorithm, with some small improvements.

By the way, most people that implement big-integer arithmetic use a power of two rather than a power of ten as the radix of their number system.

Answer 2

I'd suggest you have a look at the source code of the GMP library and port the functionality you need to JavaScript, or get an idea of how it's done.

If there is a good algorithm out there, this library will most likely have it; and it is distributed under the LGPL.