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

タイトルを変えた。

10進変換（1）

計算は2進数で行い、表示するときに10進数に直す。

2¹⁰⁰⁰⁰⁰を10進数にするのに、1を10万回2倍すると非常に簡単に実装できる。適当な桁で区切って（下のコードは4桁）、ビットにしたがって、2倍とインクリメントを繰り返す。使い方は、引数に100000と指定する。
数秒かかる。

999 0020 9301 4384 5079 4403 … 8310 9376

しかし、これでは遅いだろうし、なによりGPUが使えない。

#include 

#include 

#include 
typedef unsigned int    uint;
const int   max_bit = 32;   // 配列の要素当たりのビット数

const int   max_dec = 10000;
void twice(uint *ary, int& n);

void increment(uint *ary, int& n);
int main(int argc, char **argv) {

    int     nexp;

    try {

        if(argc != 2)

            throw(1);

        nexp = atoi(argv[1]);

        if(nexp <= 0)

            throw(1);

    }

    catch(...) {

        fprintf(stderr, "usage : bin n.\n");

        fprintf(stderr, "        n : natural number\n");

    }

    

    uint    *ary_bin;

    uint    *ary_dec;

    

    uint    nbin = nexp / max_bit + 1;

    int     ibin = nexp % max_bit;

    ary_bin = new uint[nbin];

    for(int i = 0; i < nbin - 1; i++)

        ary_bin[i] = 0;

    ary_bin[nbin-1] = 1 << ibin;

    

    // 10進で1を用意

    uint    ndec = (int)(nexp / (log((double)max_dec) - log(2.0))) + 1;

    ary_dec = new uint[ndec];

    int     max_dec_elem = 0;

    ary_dec[0] = 1;

    

    twice(ary_dec, max_dec_elem);

    int     i = nbin - 1;

    int     k = ibin - 2;

    if(k < 0) {

        i--;

        k += max_bit;

    }

    for( ; i >= 0; i--) {

        for( ; k >= 0; k--) {

            twice(ary_dec, max_dec_elem);

            if(ary_bin[i] & (1 << k))

                increment(ary_dec, max_dec_elem);

        }

        k = max_bit - 1;

    }

    

    printf("%4d", ary_dec[max_dec_elem]);

    for(int i = max_dec_elem - 1; i >= 0; i--)

        printf(" %04d", ary_dec[i]);

    printf("\n");

    

    delete ary_bin;

    delete ary_dec;

    

    return 0;

}
void twice(uint *ary, int& n) {

    int     carry = 0;

    for(int i = 0; i <= n; i++) {

        ary[i] <<= 1;

        ary[i] += carry;

        if(ary[i] >= max_dec) {

            ary[i] -= max_dec;

            carry = 1;

        }

        else {

            carry = 0;

        }

    }

    

    if(carry == 1) {

        n++;

        ary[n] = 1;

    }

}
void increment(uint *ary, int& n) {

    bool    carry = true;

    for(int i = 0; i <= n; i++) {

        ary[i]++;

        if(ary[i] >= max_dec)

            ary[i] = 0;

        else

            break;

    }

    

    if(carry) {

        n++;

        ary[n] = 1;

    }

}