仕事上, 時折マイコンのような低性能なコンピュータのプログラムを組んでます. この手のコンピュータは基本すべての演算を整数型で行わなくてはいけません. 整数型の方が圧倒的に速いわけですから…
そのためアルゴリズムはメモリ操作と条件分岐, 和算, 差算, 積算, そしてたまに除算を使って作り上げます. しかしたまにどうしても平方根を求めたい時があります. 一番簡単な方法はテーブル作って参照させることですが, 求めたい範囲が 32bit 整数の正の範囲 (0〜2147483647) になると現実的ではありません. 正攻法は例えば次のようなニュートン法を使うことでしょう.
|
int Sqrt(int a){ // 本題でないので a<=1 の例外処理は略 int x = a >> 1; // ここで適当に初期値を設定 int y; do{ y = x; x = (x + a/x) >> 1; } while (x !=y); return x; } |
要は一行目の初期値です. これを適当に近い値にすればいいのです. というわけで以下のようなコードをあみだしました.
|
int Sqrt(int a){ if (a<=0) return 0; if (a==1) return 1; int x; if (a <= 38408) x = (a >> 7)+11; else if (a<=1411319) x = (a >> 10)+210; else if (a<=70459124) x = (a >> 13)+1414; else if (a<=794112116) x = (a >> 15)+7863; else x = (a>>17)+26038; x = (x +a/x) >> 1; x = (x +a/x) >> 1; return x; } |
条件分岐は少々分かりにくいですが, 32bit 整数の正の範囲 (0〜2147483647) すべてで真値との誤差が 1 以下に なるよう調整した結果です. 当然分岐を増やせば 0.5 以下になるのでしょうが, そこまでの精度は普通要りません (1 以下でもオーバースペックです).