11/01/24 20:10:09
超亀レスだが前スレ#772へ
開平法というアルゴリズムがある。いわゆる平方根の筆算方法だ。
URLﾘﾝｸ(yosshy.sansu.org) とか紹介してるところは多い。
これを2進化するとビットシフトと加算と比較だけで10行ぐらいで作れる。
対象が何ビットだろうとビット数の半分のループで平方根が出るし、
最後のあまりが０かどうかで2乗ちょうどかの判定もできる。
今の PC は浮動小数点計算が速いので double 以内なら mathlib の sqrt() 使った法が早いが、
sqrt()が遅い環境やビット数の多い環境ならこのアルゴリズムを試す価値はある。
32bit用ならこんな感じ
int isqrt(unsigned int base, unsigned int* root)
{
unsigned int bits=16;
unsigned int answer=0;
unsigned int side=0;
unsigned int rest=0;
while (bits>0) {
bits--;
rest <<= 2;
rest |= (base>>(bits<<1))&3;
answer <<= 1;
side <<= 1;
if (rest>side) {
side++;
rest -= side;
side++;
answer++;
}
}
*root=answer;
return (rest==0);
}