March 30th, 2013, 10:13 AM
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
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.
Click Here to Expand Forum to Full Width