Embedded.com - Integer Square Roots (Programmer's Toolbox)

Description

by Jack W. Crenshaw

Functions that execute an unpredictable number of iterations are frowned upon in real-time systems.

Editor's note: We have updated the listings, figures, and tables are updated in this article to make them easier to read. --sr, 10/27/08.

Ask any math-smart programmer how to find a square root of a number, and five will get you ten, he'll tell you about Newton's method, which is an iterative approach. The general idea is this: given a number a for which we want to find the square root, we begin with an estimate x for that root. We then refine the estimate using the formula:

(1)

This method does work, and works very well. With any kind of reasonable initial estimate, it converges very rapidly. But it is, after all, an iterative method, and the number of iterations it requires to converge depends on the accuracy of our initial guess. In the vicinity of the correct root, the method converges exponentially, meaning that it gives twice as many digits of accuracy at each step. However, if our initial guess is lousy, we only creep up on the solution by halving the error at each step. Everything depends on how well we make that initial guess. I wrote an article on this way back in 1991 ("Square Roots are Simple?" November 1991, p. 30)--my first column for ESP , in fact--where I discussed the intimate details of this method and how to optimize the guessing process.

Even with the best estimates, however, we can't predict in advance how many iterations the method will take to converge to suitable accuracy. In general, functions that execute an unpredictable number of iterations are frowned upon in real-time systems, for the obvious reason that they make the total time per task unpredictable, and introduce jitter, not ...

Original URL

http://www.embedded.com/98/9802fe2.htm

http://www.embedded.com/98/9802fe2.htm