多倍長整数の計算（3）

前回の関数は、改良して、70秒→48秒となった。

前回は、被乗数を下の桁から順に計算したが、
今回は積を下の桁から計算する。
そうすると、場合わけが少しややこしいが、
繰り上がりの処理が少し楽になる。
42秒となった。

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 >= INT_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;

                }

            }

        }

        z[m] = z_m;

    }

    

    if(z[z_length-1] == 0)

        z.length--;

    

    return z;

}