Subj : Re: sqrt algo
To   : comp.programming
From : Jean-Claude Arbaut
Date : Thu Jul 14 2005 12:48 am




Le 13/07/05 15:53, dans 3jkkn2Fi2cgtU1@individual.net, « osmium »
<r124c4u102@comcast.net> a écrit :

> "himanshu bafna" writes:
> 
>> Can anyone shed light on an Algorithm for finding out the square root of a
>> number? to make it simple lets only consider integers.
> 
> Look up Newton-Raphson.  There are lots of different write ups, look at
> different ones until you find one you like.  It will make more sense to you
> if you have some calculus in your background.  A constraint to integers is,
> in general, a red herring.

Not necessarily, there algorithms for integers as well.
There is one to compute square roots "by hand", like multiplications and
divisions. There is also another simple one, but not very fast:
To find sqrt(N), Find largest n such that 4^n <= N, then highest bit of
sqrt(N) will be 2^n. Then try 2^n+2^(n-1) and compare its square with N,
etc. You don't need to really compute squares, only shifts and additions.

.