mpMul

多倍長整数の乗算

関数名

mpMul  多倍長整数同士の乗算

形式

void mpMul(int *ret, int *a, int *b);

引数

ret   （出力）多倍長整数同士の乗算の結果（a * b）
a, b  （入力）多倍長整数

関数値

なし

注意事項

配列の各要素 a_i（i は 1 以上）は1語を表し、 1語で表し得る最大の整数は 9999 とする。語の長さは a₀ の値で表す。すなわち、多倍長整数は
a_nK^n-1+ a_n-1K^n-2+...+a₂K+ a₁
で表現する。ただし、K=10000、n=a₀。

用例（mpMul-test.c）

プログラム（mpMul.c）

#define N 10000

void mpMul(int *ret, int *a, int *b)
{
    int  i, j;
    int  la, lb;
    int  *aa;
    int  ca = 1;
    long x;

    la = *a;
    lb = *b;

    for (i = la + lb; i > 0; i--) *(ret + i) = 0;

    for (j = 1; j <= lb; j++) {
        ca = 0;
        for (i = 1, aa = a; i <= la; i++) {
            x = *++aa;
            x = x * *++b + *(ret + i + j - 1) + ca;
            *(ret + i + j - 1) = x % N;
            ca = x / N;
        }
        *(ret + i + j - 1) = ca;
    }
    
    *ret = (ca != 0) ? la + lb : la + lb - 1;
}

説明

乗算は加減算ほど単純でなく、いろいろ工夫の余地がある。実用上または理論上の観点から興味深い方法がいくつも考えられている。
乗算について考えよう。a、bをそれぞれm、n語とすると、積c=a*bはm+n 語以下となる。通常の筆算と同様の方法で、乗数bの１語ごとをaに掛け、それらの和は積cとなる。

この方法では、bのn語をそれぞれaのm語に掛けるので、m*n回の繰り返しとなる。したがって、計算に必要な時間はO(mn)である。