Menu
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.
Newton's method is particularly efficient in scenarios where one must divide by the same divisor many times, since after the initial Newton inversion only one (truncated) multiplication is needed for each division.
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. Of the algorithms listed on the wikipedia link, you'll probably find long division to be the most useful.
Long Division StepsStep 1: Take the first digit of the dividend from the left. Check if this digit is greater than or equal to the divisor. Step 2: Then divide it by the divisor and write the answer on top as the quotient. Step 3: Subtract the result from the digit and write the difference below.
I am encoding large integers into an array of size_t. I already have the other operations working (add, subtract, multiply); as well as division by a single digit. But I would like match the time complexity of my multiplication algorithms if possible (currently Toom-Cook).
I gather there are linear time algorithms for taking various notions of multiplicative inverse of my dividend. This means I could theoretically achieve division in the same time complexity as my multiplication, because the linear-time operation is "insignificant" by comparison anyway.
My question is, how do I actually do that? What type of multiplicative inverse is best in practice? Modulo 64^digitcount? When I multiply the multiplicative inverse by my divisor, can I shirk computing the part of the data that would be thrown away due to integer truncation? Can anyone provide C or C++ pseudocode or give a precise explanation of how this should be done?
Or is there a dedicated division algorithm that is even better than the inverse-based approach?
Edit: I dug up where I was getting "inverse" approach mentioned above. On page 312 of "Art of Computer Programming, Volume 2: Seminumerical Algorithms", Knuth provides "Algorithm R" which is a high-precision reciprocal. He says its time complexity is less than that of multiplication. It is, however, nontrivial to convert it to C and test it out, and unclear how much overhead memory, etc, will be consumed until I code this up, which would take a while. I'll post it if no one beats me to it.
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