【タイトル】整数の平方根を浮動小数点演算を使わずに計算します


【使用上の注意】
　最近のＣＰＵの浮動小数点演算ユニットは十分に速いのでこのサンプル
コードを使用して速くなる場合はめったにありません。
　限定された用途にだけ使うか、参考・話の種くらいにしましょう（^^;。


【サンプルコード】

// Cardinal 型の平方根を返します（２の１６乗値で返します）
function CardinalSqrt(Value: Cardinal): Cardinal;
var
  i: Integer;
begin
  if Value > $40000000 then
  begin
    Result := 1;
    Dec(Value, $40000000);
  end
  else
    Result := 0;
  for i := 30 downto 0 do
  begin
    if(
        (value shr i) > Result
      )or(
        (
          (Value shr i) = Result
        )and(
          (Value shr (i - 2))and 3 > 0
        )
      )then
    begin
      Dec(Value, Result shl i);
      Value := Value shl 1;
      Dec(Value, 1 shl (i - 1));

      Result := Result shl 1;
      Inc(Result);
    end
    else
    begin
      Result := Result shl 1;
      Value := Value shl 1;
    end;
  end;
end;

// Edit1OnKeyDown イベントの例です。
// Edit1 に数字を打ち込み、[Enter] で平方根を表示します。
procedure TForm1.Edit1KeyDown(Sender: TObject; var Key: Word;
  Shift: TShiftState);
var
  Value: Cardinal;
begin
  if Key = VK_RETURN then
  begin
    Value := CardinalSqrt(Abs(StrToIntDef(Edit1.Text, 100)));
    ShowMessage(FloatToStr(Value / $10000));
    Key := 0;
  end;
end;


【動作速度の検証】
　ある画像処理ルーチンの中で

    value: Cardinal;
    ...
    value := Round(Sqrt(value / 6));
    ...

の代わりに

    value := CardinalSqrt(value * 43) shr (16 + 4);

を入れたら、トータルの処理時間が約1.7倍に遅くなりました(;_;)。
　テスト機は Cerlon300A（定格使用）と Pentium120MHz です。

    value := CardinalSqrt(value * 2731);

で済むように CardinalSqrt を Optimize（ループ数を -23、downto 23）
してもまだ 1.09〜1.07倍くらい遅いままでした。でもこの条件ならば、
整数演算が相対的に得意な AMD-K6系のＣＰＵで逆転できそうです。
　もともと、ハードウェアで実行している平方根の演算をソフトウェアで
エミュレートしているので、平方根演算そのものが遅くなるのは覚悟して
いましたが、

    [整数 >> 浮動小数点] ＆ [浮動小数点 >> 整数]

の変換が無く、固定小数点なのでトータルで速くならないかなぁ...
と期待していたのですが、読みが甘かったです。
　最近のＣＰＵの浮動小数点演算ユニットって速いんですね。


【アルゴリズムについて】
　上記の関数（CardinalSqrt）で実行している平方根の計算方法ですが、
短いコードですからゆっくり読んでみてください。
　ヒントは、高校の教科書に出てきそうな「平方根の手計算」です。あの、
割り算の手計算に似ていて、それの左側にカラムが付加した様なやつです。
あの計算手順を２進法に変換して Object Pascal にすると上記の関数が
できあがります。


                1999/02/12、河邦 正（GCC02240@nifty.ne.jp）

Original document by 河邦 正         氏 ID:(GCC02240)

ここにあるドキュメントは NIFTY SERVEの Delphi Users' Forum の16番会議室「玉石混淆みんなで作るSample蔵」に投稿されたサンプルです。これらのサンプルはボーランド株式会社がサポートする公式のものではありません。また、必ずしも動作が検証されているものではありません。これらのサンプルを使用したことに起因するいかなる損害も投稿者、およびフォーラムスタッフはその責めを負いません。使用者のリスクの範疇でご使用下さい。