Menu
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.
937
Division Algorithm for Integers. The division algorithm for integers states that given any two integers a and b, with b > 0, we can find integers q and r such that 0 < r < b and a = bq + r. The numbers q and r should be thought of as the quotient and remainder that result when b is divided into a.
The division algorithm formula is: Dividend = (Divisor × Quotient) + Remainder. This can also be written as: p(x) = q(x) × g(x) + r(x), where, p(x) is the dividend. q(x) is the quotient.
When an integer is divided by a positive integer, there is a quotient and a remainder. This is traditionally called the “Division Algorithm”, but it is really a theorem. Theorem. If a is an integer and d a positive integer, then there are unique. integers q and r, with 0 ≤ r < d, such that a = dq + r.
The standard algorithm for long division is a series of steps repeated in this order: divide, multiply, subtract, bring down. With the standard algorithm, we solve division problems one place value at a time.
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.
21
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.
129
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
