Newsgroups: comp.lang.c
Path: utzoo!henry
From: henry@zoo.toronto.edu (Henry Spencer)
Subject: Re: # to the nth power
Message-ID: <1990Nov3.220554.19404@zoo.toronto.edu>
Organization: U of Toronto Zoology
References: <9750@helios.TAMU.EDU> <1990Nov1.232830.17131@NCoast.ORG> <2730D2C2.13524@maccs.dcss.mcmaster.ca> <3809@idunno.Princeton.EDU>
Date: Sat, 3 Nov 90 22:05:54 GMT

In article <3809@idunno.Princeton.EDU> pfalstad@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@zoo.toronto.edu   utzoo!henry