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.
-
2Something like Java's BigInteger?Bernhard Barker– Bernhard Barker2013-06-26 14:00:43 +00:00Commented Jun 26, 2013 at 14:00
-
1Barrett reduction calculates a modulus, not a quotient.Tyler Durden– Tyler Durden2013-06-26 14:00:48 +00:00Commented Jun 26, 2013 at 14:00
-
3For generic questions like this you should be using the Wikipedia and coming here AFTER you have read the wikipedia and tried something.Tyler Durden– Tyler Durden2013-06-26 14:18:31 +00:00Commented Jun 26, 2013 at 14:18
-
1wikipedia doesn't answer on questions what the fastest one. I no need divisions that should be running for a days.Kosmo零– Kosmo零2013-06-26 14:32:20 +00:00Commented Jun 26, 2013 at 14:32
-
1@Tyler: ... and it obtains the remainder by first computing the quotient, and then subtracting off the appropriate multiple of the divisor.user1084944– user10849442015-10-05 07:50:11 +00:00Commented Oct 5, 2015 at 7:50
|
Show 6 more comments
2 Answers
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.
3 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.
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.
1 Comment
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)).