function FastSqrt ( X : Integer ) : Integer;

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

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...

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.

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 Ronkanen <ronka...@cc.helsinki.fi> wrote in article
<7901jv$...@kruuna.Helsinki.FI>...