Path: utzoo!attcan!uunet!samsung!usc!apple!motcsd!xdos!doug
From: doug@xdos.UUCP (Doug Merritt)
Newsgroups: comp.graphics
Subject: Re: Approximating Square Root
Summary: A note on initial guess in binary search
Keywords: Square root, source code, Newton's method
Message-ID: <541@xdos.UUCP>
Date: 26 Nov 89 16:29:58 GMT
References: <21322@adm.BRL.MIL>
Reply-To: doug@xdos.UUCP (Doug Merritt)
Organization: Hunter Systems, Mountain View CA (Silicon Valley)
Lines: 24

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