CompuServe Messages

The classic way is the Newton iteration approach. Given a number A and an estimate R of its root, the next estimate is given by R' = 1/2 (R + A / R). You can use some kind of test on the difference, to decide when to quit, but it's usually easier to just loop a fixed number of times. Depending on the initial guess, the method converges in about 5-10 iterations. The initial guess is the trick. The worst you can do is to use some fixed value like 1. Next best is to use some kind of table lookup, based upon the value of the input. Of course, that takes time too. Someone else suggested a table lookup for the whole thing, if you only need an 8-bit answer. Taking this a little farther, you could do a lookup on only the first few bits in the input value, and then do one or two Newton iterations to finish. If you're doing it in floating point (doubtful, since you're doing it in assember), I've had good look by just halving the exponent. In other words, the starting value is always 1.0E to the something. Crude but it works. There is also a closed-form algorithm for the square root, which works a lot like an integer divide. If you go back to your old grade school math books, you'll find the decimal version of it. But usually that can take longer than the iterative approach. Jack