Path: chuka.playstation.co.uk!news
From: Charlie <charlie@livemedia.co.uk>
Newsgroups: scee.yaroze.freetalk.english
Subject: Re: Square Root
Date: Fri, 21 Aug 1998 18:11:57 +0000
Organization: PlayStation Net Yaroze (SCEE)
Lines: 56
Message-ID: <35DDB86D.64EF@livemedia.co.uk>
References: <35DD914A.BBA25235@ndirect.co.uk>
Reply-To: charlie@livemedia.co.uk
NNTP-Posting-Host: livemedia.easynet.co.uk
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01 (Win95; I)

I use a lookup table from 0-65535, and for values over that, a
combination of shifts and un-shifts. Its very quick, and the loss in
accuracy (for numbers>65535) isn't as much as you'd think. If you didn't
want to waste so much memory you could always adjust it for 0-4095 or
0-8191 etc. again with a further loss of accuracy for bigger numbers.

code below

cheers

Charlie
---------------------------------------------------------------

u_long cc_calcsqrt(u_long a) {

  // if bigger than 65535
  if(a & 0xffff0000) {
    u_long cnt=0;

    do {
      a = a >> 2;
      cnt++;
    } while(a & 0xffff0000);
    
    return(cc_sqrt[a] << cnt);
  } else {
    return(cc_sqrt[a]);
  }

}

Alex Herbert wrote:
> 
> OK, I know that using square roots is best avoided, and in most cases
> they can be.  But sometimes they just can't be avoided.  I decided that
> using floating point was not the way to go, but I've never seen a square
> root algorithm before, so this is what I came up with.
> 
> u_short sq_root(u_long n) {
>     u_short a=0x8000;
>     u_short b=0;
>     u_short c;
> 
>     while(a) {
>         c=a|b;
>         if(c*c<=n)
>             b=c;
>         a=a>>1;
>     }
>     return(b);
> }
> 
> It works fine, but does anyone know a better way to find the sqaure root
> of any u_long?
> 
> Herbs