# to the nth power

[Richard Harter]

In article <1990Nov3.220554.19404 at zoo.toronto.edu>, henry at zoo.toronto.edu (Henry Spencer) writes:
> In article <3809 at idunno.Princeton.EDU> pfalstad at phoenix.Princeton.EDU (Paul John Falstad) writes:
> >Just out of curiosity, is there an efficient algorithm for finding
> >square root of an integer (or the integral part of the square root, if
> >the number is not a perfect square) using only integer arithmetic?

> It's not difficult using Newton's Method, i.e. successive approximations,
> if you have good integer division.  Like this:

 	sqrtx = ( sqrtx + x/sqrtx ) / 2

> although you'll have to watch roundoff effects to avoid the possibility
> of an infinite loop when the square root isn't exact.  You also need an
> initial approximation, although just x/2 is a good start.

Actually x/2 is not a good start -- the problem is that the convergence
will be geometric with power .5 (i.e. you only gain one bit in each
iteration) until you get close to the actual root.  Once you are sufficiently
close the convergence rate does become quadratic.  What you want to do is
(in effect) get the nearest power of four and take the square root of that.
A reasonably good way to get a starting value (given the integer arithmetic
restriction) is:

	for (y=x,sqrtx=1;y>0;) {ysave = y;y =/ 16;sqrtx =* 4;}
	if (ysave > 4) sqrtx *= 2;

One can fiddle with this (and the Newton formula) to get maximal efficiency
if there is a real need; however a good starting point should suffice for
all but the most cycle hungry.


-- 
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398 
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb.  This sentence short.  This signature done.