多倍長整数の計算(4)

繰り上がりの処理が楽になると、
繰り上がり計算を毎回しなくても済むようになる。
1万以上になると、すなわち加算すると、
ほぼ毎回繰り上がり計算をしていたが、
整数は21億ちょっとまであるはずなので(確かめていない)、
20億以上になってはじめて繰り上がり計算をするようにした。
すると、16秒となった。



var NFIGURE = 4;
var INT_MAX = Math.round(Math.pow(10, NFIGURE));
var COUNT_MAX = INT_MAX * INT_MAX * 2;

function multiple(x, y) {
var x_length = x.length;
var y_length = y.length;
var z_length = x_length + y_length;
var z = [ ]; // 返り値
for(var i = 0; i < z_length; i++)
z[i] = 0;

for(var m = 0; m < z_length - 1; m++) {
var x0, x1;
if(x_length < y_length) {
if(m < x_length) {
x0 = 0; x1 = m;
}
else if(m < y_length) {
x0 = 0; x1 = x_length - 1;
}
else {
x0 = m - y_length + 1; x1 = x_length - 1;
}
}
else {
if(m < y_length) {
x0 = 0; x1 = m;
}
else if(m < x_length) {
x0 = m - y_length + 1; x1 = m;
}
else {
x0 = m - x_length + 1; x1 = x_length - 1;
}
}

var z_m = z[m];
for(var k = x0; k <= x1; k++) {
z_m += x[k] * y[m-k];
if(z_m >= COUNT_MAX) {
var mod = z_m % INT_MAX;
var div = (z_m - mod) / INT_MAX;
z_m = mod;
var z_n;
for(var n = m + 1; div != 0; n++) {
z_n = z[n] + div;
mod = z_n % INT_MAX;
div = (z_n - mod) / INT_MAX;
z[n] = mod;
}
}
}

var n = m;
while(true) {
var mod = z_m % INT_MAX;
var div = (z_m - mod) / INT_MAX;
z[n] = mod;
if(div == 0)
break;
z_m = z[n+1] + div;
n++;
}
}

if(z[z_length-1] == 0)
z.length--;

return z;
}