# to the nth power
Henry Spencer
henry at zoo.toronto.edu
Sun Nov 4 09:05:54 AEST 1990
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
More information about the Comp.lang.c
mailing list