開平(1)
開平の方法はたぶん中学で習ったと思うが、割り算と似たようなやり方がある。あれをコード化するとこんな感じだろうか。
#includeusing namespace std;
void sqrt(int a, int& b, int& c);
int get_bit_num(int a);int main() {
for(int i = 0; i < 17; i++) {
int b, c;
sqrt(i, b, c); // i = b^2 + c
fprintf(stdout, "%d %d %d\n", i, b, c);
}
}void sqrt(int a, int& b, int& c) {
b = c = 0;
if(a == 0)
return;
int n = get_bit_num(a);
for(int i = (n - 1) / 2; i >= 0; i--) {
c <<= 2;
c += (a >> i * 2) & 3;
b <<= 1;
if(c > b) {
b++;
c -= b;
b++;
}
}
b >>= 1;
}int get_bit_num(int a) {
int n;
for(n = 0; a; n++)
a >>= 1;
return n;
}