Есть ли у Delphi isqrt?

Question

Я много работаю над большими целыми числами в значениях UInt64, и мне было интересно, есть ли у Delphi функция целочисленный квадратный корень .Теперь я использую Trunc(Sqrt(x*1.0)), но я думаю, что должен быть более производительный способ, возможно с фрагментом встроенного ассемблера?(Sqrt(x) с x:UInt64 выдает ошибку компилятора недопустимого типа в D7, следовательно, бит *1.0.)

Answer 1

Я очень далек от специалиста по сборке, поэтому этот ответ просто дурачит меня.

Однако, похоже, это работает:

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

до тех пор, пока вы установите для параметра округления слова управления FPU значение "усечь" до вызова isqrt Самым простым способом может быть определение вспомогательной функции

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

и тогда вы можете сделать

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;

Тест

Это действительно улучшает производительность? Ну я тестировал

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;

и получил результат

371802
371774.

Следовательно, это просто не стоит. Наивный подход trunc(sqrt(x)) гораздо легче читать и поддерживать, он имеет превосходную будущую и обратную совместимость и менее подвержен ошибкам.

Answer 2

Это код, который я в итоге использую, основываясь на одном из алгоритмов, перечисленных в википедии

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;

Answer 3

Я считаю, что ответ - нет, у него нет целочисленной функции квадратного корня и что ваше решение разумно.

Я немного удивлен необходимостью умножения на 1,0 для преобразования в значение с плавающей запятой. Я думаю, что это должно быть ошибка Delphi, и более поздние версии, безусловно, ведут себя так, как вы хотели бы.