Re: How does a divide operation work?

Hello Roger,

You asked a very good question - how do calculators and computer processors do precise floating-point division? As you pointed out, repeated subtraction of one number from the other would be reasonable for integer arithmetic, but it would not be the best option if we want the answer to a certain number of decimal points. How then do calculators do it, you asked, without floating point systems?

In fact, modern calculators and computers do have floating point systems, i.e. they can manipulate numbers in the floating-point format. Until the eighties, every hardware designer was free to choose their own floating point format. As a result, you might pick up two different computers from that era, have them perform the same calculation and get two different results, either of which (or both!) might be incorrect. The problem was that the number formats used by hardware designers were inconsistent and some were even outright flawed.

Processor designers nowadays have to conform to what is called the IEEE 754 Standard for Floating Point Arithmetic. You can read more about this standard on the web by following one of the links at the bottom of this message.

Now to answer your question about division - one commonly used way to calculate a/b is to first quickly estimate 1/b and then simply multiply that by a, getting a * 1/b = a/b. The multiplication, as you can imagine, can be done using addition (with a number of tricks to make it faster). So the only problem is to estimate 1/b. This is often done using what is called the Newton-Raphson method. It is actually a very old method that can be used in general to find solutions (roots) of any equation f(x)=0. A root of such an equation is a value for x that makes the left side, f(x), equal to 0. In our case, we can approximate 1/b by solving the equation

b - 1/x = 0

As you can see, for x=1/b, the left side of the equation will be equal to 0. The Newton-Raphson method first guesses a value for x and then improves upon that value using the following formula:

x_new = x_old - f(x_old}/f'(x_old)

Here f(x) is the left side of our equation, x_old is our previous guess for x and x_new is the new guess. f'(x) is the derivative of f(x) at x (if you don't know what this means, don't worry). For our equation, we will get the following:

x_new = 2*x_old - b*(x_old)^2

So if we were to use the Newton-Raphson method to compute 1/b, we would first make an initial guess, and then use the above equation repeatedly to make improvements on that guess until we are satisfied that we have come close enough to the actual number 1/b. I should mention that the Newton method is not always guaranteed to get us closer to the actual answer given an arbitrary guess. However, for a "good" initial guess, it will work. A computer processor can actually look up such a first guess in a table, which is very fast, and then use the above equation to make the guess better. Finally, it calculates x * a, getting a pretty good guess for a/b. The guess will be accurate to a certain number of significant digits. Just how accurate it will be depends on a lot of design issues, which would take us a long time to talk about in this email.

Finally, here are some useful references:

About the Newton-Raphson method (this is very technical): Wolfram's MathWorld: Newton's Method
About the IEEE 754 Standard for Binary Floating-Point Arithmetic: IEEE 754 Website
A nice set of slides describing how the Newton-Raphson method can be used in a processor: click here
About floating-point arithmetic in the Intel IA-64 architecture: Follow this link and then click on "IA-64 Floating-Point Divide and Remainder" on the left.

I hope this helped! Feel free to ask further questions and the Mad Scientists will be glad to answer them =)

Tomas

--
Tomas Izo
MIT Artificial Intelligence Lab
http://www.ai.mit.edu/people/ tomas