RSS Twitter Facebook

2018/09/18 (2018年09月 のアーカイブ)

整数の平方根(切り捨て)

シェア

FPU を使えない環境でたま～に使いたくなって、どうやってたっけ? と毎回昔のコードを掘り返したりしているので、メモ。

バビロニアンメソッドと呼ばれる奴で、16bit値くらいなら割り算10回分程度。
真の値は戻り値と戻り値 +1 の間になるように多少気を使っている。 

unsigned int sqrint(unsigned int x){
  unsigned int y1 = x, y2 = (x + 1) >> 1;
  while(y2 < y1)
    y1 = y2, y2 = (y1 + x / y1) >> 1;
  return y1;
}
9.21 追記-----
これだと初期値が適当すぎて収束が遅いので、@xevixeviさんが、もうちょっと改善する案をツイートしてくれましたので、追記しておきます。

有効ビット数まで切り詰めて初期値とするので必要な反復計算がかなり減ります。速度重視ならこっち。また最初の例だと、UINT_MAX を入力した時に例外が起こるのを回避できてます。 

unsigned int sqrint(unsigned int x){
  unsigned int y1 = x, y2 = 1, x2 = x;
  while(x2 >>= 2)
    y2 = (y2 << 1) + 1;
  while(y2 < y1)
    y1 = y2, y2 = (y1 + x / y1) >> 1;
  return y1;
}
ついでに...
処理時間に占める除算の割合が高そうなので、ループの終了条件の確認で1回余計に回るのを避けるために毎回乗算するパターン。これが割に合うかどうかは CPU 次第だけど、除算に比べて乗算が充分に速ければこっちの方が速くなる可能性があります。 

unsigned int sqrint(unsigned int x){
  unsigned int y = 1, x2 = x;
  while(x2 >>= 2)
    y = (y << 1) + 1;
  while(y * y > x)
    y = (y + x / y) >> 1;
  return y;
}

Posted by g200kg : 2018/09/18 12:20:55