doug@xdos.UUCP (Doug Merritt) (11/27/89)
Quick note on binary-search approximations to e.g. square root:
if you pick an initial guess badly, binary search will converge
very slowly on the real answer, about 1 iteration per bit of precision.
For IEEE floating point with 55 bits of mantissa, this means 55 iterations.
A good initial guess will dramatically increase the speed.
For most simple functions like square root, cube root, etc, you can get
an excellent order-of-magnitude first guess by manipulating the exponent.
E.g. for a number == X * 2^10 (floating point is typically implemented
using base two exponents), a good first guess would be 2 ^ (10/2) ==
2^5. The exponent is approximately the logarithm (base two) of the
number, so dividing the exponent by two approximates taking the square root.
Similarly for cube root: divide exponent by three.
In theory, what this should do is eliminate the iterations normally
required for finding the correct exponent in the course of binary search,
which might save 8 iterations, a significant percentage. That's worst
case. Average case is even better, cutting an average of 50 to 60 iterations
down to around 20.
Doug
--
Doug Merritt {pyramid,apple}!xdos!doug
Member, Crusaders for a Better Tomorrow Professional Wildeyed Visionary