What is the fastest algorithm for division of crazy large integers?

Question

I need to divide numbers represented as digits in byte arrays with non standard amount of bytes. It maybe 5 bytes or 1 GB or more. Division should be done with numbers represented as byte arrays, without any conversions to numbers.

Solution 1

Divide-and-conquer division winds up being a whole lot faster than the schoolbook method for really big integers.

GMP is a state-of-the-art big-number library. For just about everything, it has several implementations of different algorithms that are each tuned for specific operand sizes.

Here is GMP's "division algorithms" documentation. The algorithm descriptions are a little bit terse, but they at least give you something to google when you want to know more.

Brent and Zimmermann's Modern Computer Arithmetic is a good book on the theory and implementation of big-number arithmetic. Probably worth a read if you want to know what's known.

Solution 2

The standard long division algorithm, which is similar to grade school long division is Algorithm D described in Knuth 4.3.1. Knuth has an extensive discussion of division in that section of his book. The upshot of this that there are faster methods than Algorithm D but they are not a whole lot faster and they are a lot more complicated than Algorithm D.

If you determined to get the fastest possible algorithm, you can resort to what is known as the SRT algorithm.

All of this and more is covered by the way on the Wikipedia Division Algorithm.

Comments

[Tyler Durden]

Yes, but... as I said these algorithms are a LOT more complicated than Algorithm D. The main reason for doing divide and conquer is so that you can use the Karatsuba algorithm, and let me tell you writing all this plus a Karatsuba implementation will be a LOT of work, and I mean a LOTTA LOTTA work. I don't know how good a programmer the OP is, but even a very good programmer could spend MONTHS writing a correct implementation using divide and conquer.

[tmyklebu]

@TylerDurden: Well, he asked about "crazy large numbers." Karatsuba isn't bad on its own, since you don't run into power-of-two issues. It starts becoming a lot of work when you start wanting to implement Toom-Cook and the various FFT-based methods, then figuring out the crossover points. This is why you use GMP for that :)

[tmyklebu]

@TylerDurden: And divide-and-conquer division isn't too bad at all once you have a fast multiplication black-box. Take the high half of the numerator and denominator, recursively divide, and then do a little cleanup afterward. Again, tuning and finding the crossover point between schoolbook and divide-and-conquer is a fair bit of work.

[Python Cheese]

Of the algorithms listed on the wikipedia link, you'll probably find long division to be the most useful. Be careful of the notation though. D(0) indicates the least significant value in the number, while the left shift suggests that the numbers are stored big endian wise (which means the LSD should be at D(n-1)).