GPGPUで多倍長整数計算（5）

開平（1）

開平の方法はたぶん中学で習ったと思うが、割り算と似たようなやり方がある。あれをコード化するとこんな感じだろうか。

#include 
using 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;

}