I'm doing some heavy work on large integer num开发者_如何转开发bers in UInt64 values, and was wondering if Delphi has an integer square root function. Fow now I'm using Trunc(Sqrt(x*1.0)) but I guess there must be a more performant way, perhaps with a snippet of inline assembler? (Sqrt(x)with x:UInt64 throws an invalid type compiler error in D7, hence the *1.0 bit.)

---

I am very far from an expert on assembly, so this answer is just me fooling around.

However, this seems to work:

function isqrt(const X: Extended): integer;
asm
  fld X
  fsqrt
  fistp @Result
  fwait
end;

as long as you set the FPU control word's rounding setting to "truncate" prior to calling isqrt. The easiest way might be to define the helper function

function SetupRoundModeForSqrti: word;
begin
  result := Get8087CW;
  Set8087CW(result or $600);
end;

and then you can do

procedure TForm1.FormCreate(Sender: TObject);
var
  oldCW: word;
begin
  oldCW := SetupRoundModeForSqrti; // setup CW
  // Compute a few million integer square roots using isqrt here
  Set8087CW(oldCW); // restore CW
end;

Test

Does this really improve performance? Well, I tested

procedure TForm1.FormCreate(Sender: TObject);
var
  oldCW: word;
  p1, p2: Int64;
  i: Integer;
  s1, s2: string;
const
  N = 10000000;
begin
  oldCW := SetupRoundModeForSqrti;

  QueryPerformanceCounter(p1);
  for i := 0 to N do
    Tag := isqrt(i);
  QueryPerformanceCounter(p2);
  s1 := inttostr(p2-p1);

  QueryPerformanceCounter(p1);
  for i := 0 to N do
    Tag := trunc(Sqrt(i));
  QueryPerformanceCounter(p2);
  s2 := inttostr(p2-p1);

  Set8087CW(oldCW);

  ShowMessage(s1 + #13#10 + s2);
end;

and got the result

371802
371774.

Hence, it is simply not worth it. The naive approach trunc(sqrt(x)) is far easier to read and maintain, has superior future and backward compatibility, and is less prone to errors.

---

I believe that the answer is no it does not have an integer square root function and that your solution is reasonable.

I'm a bit surprised at the need to multiple by 1.0 to convert to a floating point value. I think that must be a Delphi bug and more recent versions certainly behave as you would wish.

---

This is the code I end up using, based on one of the algorhythms listed on wikipedia

type
  baseint=UInt64;//or cardinal for the 32-bit version
function isqrt(x:baseint):baseint;
var
  p,q:baseint;
begin
  //get highest power of four
  p:=0;
  q:=4;
  while (q<>0) and (q<=x) do
   begin
    p:=q;
    q:=q shl 2;
   end;
  //
  q:=0;
  while p<>0 do
   begin
    if x>=p+q then
     begin
      dec(x,p);
      dec(x,q);
      q:=(q shr 1)+p;
     end
    else
      q:=q shr 1;
    p:=p shr 2;
   end;
  Result:=q;
end;