GPGPUで多倍長整数計算(2)

10進変換(2)

前回は1ビットずつ計算していたが、さすがにそれでは遅いので16ビットずつに区切って10進計算を行ったところ、0.1秒くらいになった。
しかし、これでもGPUは使えない。



#include
#include
#include

typedef unsigned int uint;

const int max_bit = 32; // 配列の要素当たりのビット数
const int max_dec_exp = 4;
const int max_dec = 10000;
const int multi_exp = 16;

int trim(uint a, int k);
void multiple(uint *ary, int& n);
void add(int a, 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 l = 0; l < nbin - 1; l++)
ary_bin[l] = 0;
ary_bin[nbin-1] = 1 << ibin;

uint ndec = (int)(nexp / (log((double)max_dec) - log(2.0))) + 1;
ary_dec = new uint[ndec];
int max_dec_elem = 0;

int i = nbin - 1;
int k = ibin / multi_exp;
ary_dec[0] = trim(ary_bin[i], k);
if(ary_dec[0] >= max_dec) {
ary_dec[1] = ary_dec[0] / max_dec;
ary_dec[0] -= ary_dec[1] * max_dec;
max_dec_elem = 1;
}

k--;
for( ; i >= 0; i--) {
for( ; k >= 0; k--) {
multiple(ary_dec, max_dec_elem);
int n = trim(ary_bin[i], k);
add(n, ary_dec, max_dec_elem);
}
k = max_bit / multi_exp - 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;
}

int trim(uint a, int k) {
int l = multi_exp * k;
return (a >> l) & ((1 << multi_exp) - 1);
}

void multiple(uint *ary, int& n) {
int carry = 0;
for(int i = 0; i <= n; i++) {
ary[i] <<= multi_exp;
ary[i] += carry;
carry = ary[i] / max_dec;
ary[i] -= carry * max_dec;
}

if(carry != 0) {
if(carry >= max_dec) {
n += 2;
ary[n] = carry / max_dec;
ary[n-1] = carry - ary[n] * max_dec;
}
else {
n++;
ary[n] = carry;
}
}
}

void add(int a, uint *ary, int& n) {
int carry = a;
for(int i = 0; i <= n; i++) {
ary[i] += carry;
carry = ary[i] / max_dec;
if(carry != 0)
ary[i] -= carry * max_dec;
else
break;
}

if(carry) {
n++;
ary[n] = 1;
}
}