Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!att!bu.edu!purdue!mentor.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: comp.lang.c
Subject: Re: # to the nth power
Summary: Roots with integer arithmetic
Message-ID: <2724@l.cc.purdue.edu>
Date: 8 Nov 90 13:36:28 GMT
References: <9750@helios.TAMU.EDU> <1990Nov1.232830.17131@NCoast.ORG> <1990Nov3.220554.19404@zoo.toronto.edu>
Organization: Purdue University Statistics Department
Lines: 28

In article <1990Nov3.220554.19404@zoo.toronto.edu>, henry@zoo.toronto.edu (Henry Spencer) writes:
> 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.

Assuming this is done in integer arithmetic, there is only one case of an
infinite loop.  Using real arithmetic (of course impossible on a computer),
the iteration is always too large.  Thus it should be rounded down.  Now
it is possible that this makes it so small that the next iteration is
larger.  If one starts with something too large, this can only happen
if x = n(n+2), and this can be detected by the iterate being larger than
the previous value, so that a stopping rule when the iterate does not
decrease, and taking the previous value, is always right, if the initial
value is too large.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet)   {purdue,pur-ee}!l.cc!hrubin(UUCP)