What's The Algorithm For Square Root Of Binary Fixed-point Number?

1 Answers

Oddman Profile
Oddman answered
As with a lot of math functions, a variety of algorithms will get you there.

You can do the algorithm for decimal numbers, except do the math in base 2.

Or, you can use an iteration method, such as Newton's method. For such a method, you need an approximation (r) of the root to start with. One approximation I've seen used for 32-bit numbers is
for numbers > 65535, r = n/17916 + 662
for numbers > 255, r = n/70 + 3
for numbers < 256, r = n/11 + 2

Each iteration is computed as r' = (r + n/r)/2.

For some values of n, this may cycle between the two integers on either side of the actual root, so some means needs to be used to determine when convergence on the answer has occurred. Usually, no more than 5 iterations are required for 32-bit numbers.

Answer Question