# to the nth power

[Henry Spencer]

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.

>How about the cube root?

	curtx = ( 2*curtx + x/(curtx*curtx) ) / 3

if I'm not mistaken.  Same caveat about roundoff error and infinite loops.
-- 
"I don't *want* to be normal!"         | Henry Spencer at U of Toronto Zoology
"Not to worry."                        |  henry at zoo.toronto.edu   utzoo!henry