Board index » delphi » Fast Sqrt

Fast Sqrt

        Can anyone tell me an algorithm of calculating integer square root
of integer fast;
        i.e i need

        function FastSqrt ( X : Integer ) : Integer;

        with only integer calculations [ Round ( Sqrt ( X ) ) won't do].

            Thanx in advance,
                            NAD

 

Re:Fast Sqrt


Quote
Nickolai Delegnan wrote:

>         Can anyone tell me an algorithm of calculating integer square root
> of integer fast;
>         i.e i need

>         function FastSqrt ( X : Integer ) : Integer;

>         with only integer calculations [ Round ( Sqrt ( X ) ) won't do].

This is not an evaluated method, but only an idea:

1) estimate by collecting the bits, eg.
   Est := 0;
   if (X and $0003) <> 0 then Est := Est+1;
   if (X and $000C) <> 0 then Est := Est+2;
   if (X and $0030) <> 0 then Est := Est+4;
   ....
   if (X and $C000) <> 0 then Est := Est+128;

could be made quicker with some sort of lookup table?

2) Est := (Est + X/Est) shr 1;
   Est := (Est + X/Est) shr 1;

In ASM surely a bit faster.

As said before: an idea only...

Franz Glaser

Re:Fast Sqrt


Quote
Ing. Franz Glaser wrote in message <36B0F127.8068E...@eunet.at>...
>Nickolai Delegnan wrote:

>>         Can anyone tell me an algorithm of calculating integer
square root
>> of integer fast;
>...
>1) estimate by collecting the bits, eg.
>...
>could be made quicker with some sort of lookup table?

If he actually wants the square roots of 16-bit integers rather than
LongInts, he could do the whole thing with a lookup table. Since
256*256=65536 each entry would fit in one byte and the whole table
would fit in a quarter KB. That's small enough for a lookup table, and
it would be fast.

FP

Re:Fast Sqrt


JRS:  In article <36b091d...@news.ptt.ru> of Thu, 28 Jan 1999 19:31:54
in news:comp.lang.pascal.borland, Nickolai Delegnan <n...@dialup.ptt.ru>
wrote:

Quote
>        Can anyone tell me an algorithm of calculating integer square root
>of integer fast;
>        i.e i need

>        function FastSqrt ( X : Integer ) : Integer;

You need to decide whether to round to nearest or truncate : is Sqrt(8)
to be 2 or 3, or don't-care ?

If you mean integer, and are not going to need longint, the fastest way
must be with a precalculated lookup table.  Each entry only needs a
byte.  Something like the following will fill it.  In practice, you will
probably want to put A on the heap.

var J, JP : byte ; K, J2 : word ;
A : array [0..maxint] of byte ;
begin
K := 0 ; JP := 0 ;
for J := 0 to 181 {Trunc(Sqrt(MaxInt))} do begin J2 := J*J ;
  while K<J2 do begin A[K] := JP ; Inc(K) end ;
  JP := J end ;
for K := K to MaxInt do A[K] := JP ;
{ check: }
for K := 0 to 100 do write(A[K]:4) ;
Writeln ;
for K := 180*180 to Maxint do write(A[K]:4) ;
end.

If you can't afford the memory, use shifting to generate a rough square
root (shift the input right until it is 1 or 0, shift 1 left half as
many times) then use Newton-Raphson iteration as often as necessary -
X := (X + Sq/X)/2 - if it works OK with integers.

But it may not be possible to root much faster than with Sqrt, providing
that you are using the FPU.  A small asm..end might beat what the
compiler gives.

If the job is such that you will often call repeatedly with the same
argument, maybe cache the answer.

procedure Srt(const J : integer) : integer (untested} ;
const XJ : integer = 0 ; XR : integer = 0 ;
begin if J=XJ then Srt := XR else begin
  XJ := J ; XR := Sqrt(J) ; Srt := XR end end.

--
John Stockton, Surrey, UK.    j...@merlyn.demon.co.uk    Turnpike v4.00    MIME.
  Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
  Correct 4-line sig. separator is as above, a line precisely "-- " (SoRFC1036)
  Do not Mail News to me.    Before a reply, quote with ">" or "> " (SoRFC1036)

Re:Fast Sqrt


In article <78s37k$3n...@ezekiel.eunet.ie>,

Quote
Frank Peelo <fpe...@indigo.ie> wrote:

>If he actually wants the square roots of 16-bit integers rather than
>LongInts, he could do the whole thing with a lookup table. Since
>256*256=65536 each entry would fit in one byte and the whole table
>would fit in a quarter KB. That's small enough for a lookup table, and
>it would be fast.

Pardon, wouldn't one need 32KB for direct lookup table.  Of course you
could use the high word as index and then check the that the result is
actually OK.

That is something like:

z:=lut[hi(x)]
y:=lut[hi(x)+1]
while (z<y) and (sqr(z+1)<=x) do inc(z);

The lut would be like

0,16,22,27,32,35,39,42,45,48,..

trunc(sqrt(256*i)).

Where in the end the numbers are adjacent ones or even same. Or it
could be enough to do:

z:=lut[hi(x)]
while (sqr(z+1)<=x) do inc(z);

Some consideration should be put to very large numbers though.

Osmo

Re:Fast Sqrt


Osmo Ronkanen <ronka...@cc.helsinki.fi> wrote in article
<7901jv$...@kruuna.Helsinki.FI>...

Quote
> In article <78s37k$3n...@ezekiel.eunet.ie>,
> Frank Peelo <fpe...@indigo.ie> wrote:

> >If he actually wants the square roots of 16-bit integers rather than
> >LongInts, he could do the whole thing with a lookup table. Since
> >256*256=65536 each entry would fit in one byte and the whole table
> >would fit in a quarter KB. That's small enough for a lookup table, and
> >it would be fast.

> Pardon, wouldn't one need 32KB for direct lookup table.  Of course you
> could use the high word as index and then check the that the result is
> actually OK.

You're right. Th'auld brain is in worse condition than usual. And Dr. John
has posted it right so good night.

FP

Other Threads