Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!emory!gatech!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!sci.kun.nl!atcmpe!jc
From: jc@atcmp.nl (Jan Christiaan van Winkel)
Newsgroups: comp.lang.c
Subject: square roots (was:Re: RE: # TO THE NTH POWER)
Message-ID: <817@atcmpe.atcmp.nl>
Date: 6 Dec 90 15:29:20 GMT
References: <18729@ultima.socs.uts.edu.au>
Organization: AT Computing, Nijmegen, The Netherlands
Lines: 28

From article <18729@ultima.socs.uts.edu.au>, by robbie.matthews@f1701.n7802.fido.oz.au (Robbie Matthews):
> Original to: blambert@lotus.com
> OK. Here is a way of getting an integer root that I haven't seen yet:
>  
>  for (sqrtx=1, j=1, k=1; j<x; sqrtx+=1, k+=2, j+=k );
>  
How about this as an approximation:
input:n 
output:sqrt

  sqrt=1;
  while (n>>=2) sqrt<<=1;    /* expecting nonnegative numbers, so >> is OK */

  Number of loops taken: #of_bits_in_a_word/2

This gets an approximation within an order of a magnitude (magnitudes of 2,
that is...)
You will now only a few steps of newtons method:

sqrt=(sqrt + n/sqrt)/2

JC

-- 
___  __  ____________________________________________________________________
   |/  \   Jan Christiaan van Winkel      Tel: +31 80 566880  jc@atcmp.nl
   |       AT Computing   P.O. Box 1428   6501 BK Nijmegen    The Netherlands
__/ \__/ ____________________________________________________________________