Help Implementing Newton-Raphson Division
I've been working on functions which can perform arithmetic on arbitrarily large unsigned integers for sometime now. I've got add, subtract, multiply, and division with remainder all working but the division function is too slow. I would like to implement Newton-Raphson division but am having a hard time finding example code that would show me how to do it with arbitrarily large unsigned integers. The algorithm involves using the reciprocal of the denominator but these are not floating point numbers that I'm working with. Wikipedia showed an example of how to divide by three with the Newton-Raphson algorithm using integers but I am unable to figure out how to apply it to all denominators. The way I'm representing my large numbers is basically with an array of 32-bit unsigned integers with bits starting at the end of the array and going to the left and a pointer keeps up with where the number begins in the array. So, 2^32, which is too large for a 32-bit unsigned integer to represent by one, would be represented in the array as
startPtr->[00000000000000000000000000000001][00000000000000000000000000000000]
in binary. I don't know if that's big-endian or little-endian. Anyhow, if anyone out there can help me figure this out I'd appreciate it.
ps) I know that there are libraries out there like GMP which I could use for this stuff but I really want to learn how to do it myself.
Re: Help Implementing Newton-Raphson Division
Quote:
Originally Posted by
vindy1099
ps) I know that there are libraries out there like GMP which I could use for this stuff but I really want to learn how to do it myself.
So why not learn how GMP and other libraries implement these constructs? Isn't the first thing you should do is to see an implementation of what you want to achieve, and then learn how this implementation achieves the goal?
For example, GMP comes with full source code. What I would have done is to write a small program using GMP that performs the results you're looking for. If it performs them fast, then I would debug and look at the source to see how this is achieved (in addition to getting a general background on how GMP stores arbitrary numbers).
Regards,
Paul McKenzie
Re: Help Implementing Newton-Raphson Division
I'm not entirely sure on this. but I would imagine that calculating the reciprocal and then multiplying is slower than the straightforward divide. Unless there's some magic method i'm not aware off to calculate a reciprocal.
so unless you plan on doing a lot of divides by the same divisor... This probably isn't worth investigating. It would probably be worthwhile to precalculate reciprocals for division by 10 (or chunks of 10^x) to convert from your long format to decimal (=displaying values). that is, assuming you store the large integers in binary format and not in BCD format. But for the special case of displaying to decimal there's other tricks you can use to convert binary to decimal that would probably end up being faster than the reciprocal.
if you are using BCD, then that is part of your problem. Bcd divides are slow by nature. binary divides will be faster (but still the slowest by far of the 3 operations) but converting to decimal/display is harder. if you need to do a lot of calculations and few displays, then binary will be a clear winner, if you need to do simple/few calculations and lots of display, then BCD will be a better fit. If you are using binary divides, then you could be loosing a lot of performance setting up the divides (if you're using C++ code fir this).