square roots (was:Re: RE: # TO THE NTH POWER)

[Jan Christiaan van Winkel]

>From article <18729 at ultima.socs.uts.edu.au>, by robbie.matthews at f1701.n7802.fido.oz.au (Robbie Matthews):
> Original to: blambert at 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 at atcmp.nl
   |       AT Computing   P.O. Box 1428   6501 BK Nijmegen    The Netherlands
__/ \__/ ____________________________________________________________________