Fixed point square root

Don''t have the solution right at hand, but recommend this book:

"Math Toolkit for Real-Time Programming" by Jack W. Crenshaw, ISBN 1929629095, 2000.

Wouldn''t be surprised if he covers fixed point math.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

There is an easy formula for calculating square root

# = number to calculate square root of
G = Current guess (explained below)

New G = (G + #/G)/2

First make an initial guess of the answer. The value isnt important. If we can get it close to the expected square root it will help us find the result quicker, but its not a big deal.

Now plug our guess (G) into the formula and we calculate New G, our revised (more accurate) guess. Now repeat the process over and over until the change in G is below some tolerable error, like:
abs(G - New G) < 0.01

When we get withing our tolerance level, we have the square root.

Need an example? Lets calc the square root of 87. If we use a calculator we see the answer is approx: 9.3274. Now lets figure it with this formula. Lets use an initial guess of 3.

Guess 1 = 3
Guess 2 = (3 + 87/3)/2 = 16
Guess 3 = (16 + 87/16)/2 = 10.7188
Guess 4 = (10.7188 + 87/10.7188)/2 = 9.4177
Guess 5 = (9.4177 + 87/9.4177)/2 = 9.3278
Guess 6 = (9.3278 + 87/9.3278)/2 = 9.3274

Now we see the difference between Guess 5 and Guess 6 is less than 0.01, so we stop (or you can go on if you need more accuracy). And low and behold, we have calculated the square root of 87 (to the nearest 10000th) exactly. And it only took 6 steps, and only 5 calculations. In total it took 5 additions and 10 divisions (although 5 of those divisions are division by 2, which can be simplified to a bitshift, which can be done extremely quickly).

Hope this helps

--
Ron Frazier

Edited by - LordKronos on October 22, 2001 12:27:06 PM

/me saves this method to hard disk...

Very nice.

Also, as I mentioned it helps if your initial guess is reasonably close. I said it really didnt matter, but it can speed thing up with really large numbers. For example if you try to find the square root of 1000000 and your first guess is 2, then it will take you roughly 10 tries before you even get your error to < 100.0

But there are tricks you can use to get to the result faster. There might be a better way than this, but this has worked reasonably good for me. To pick your starting guess, use the most significant 1/2 of the bits of your number. For example, if you number is 908, in binary this is 1110001100. thats 10 digits, so use the most significant 5, which is 11100, or 28 which is pretty close to the actual answer of 30.13 In the case of a large number like 1234567890, this technique reduces the number of guesses (until error < 0.01) from 19 down to 4. Pretty good, and easily worth the effort.

And its relatively simple to implement:
--------------------
tmp = (int) num;
initguess = (int) num;
while (tmp > 0)
{
tmp = tmp >> 2;
initguess = initguess >> 1;
};
--------------------

I think the above code is how I did it, but I typed it from memory so there may be an error there, but you should get the general concept.

---
Ron Frazier

Thank you very very much LordKronos. Your method is ideal and suits my needs exactly.

Much appreciated.

henry

There''s a very good C implementation given in Graphics Gems V, whic uses only elementary integer operations (+, -, shifts) and a fixed number of loop iterations.