円周率.jp (http://xn--w6q13e505b.jp/method/school.html)

筆算

多倍長乗算の基本は小学校で習ってきた筆算のままの方法である. 各桁の値同士を掛け合わせ,対象となる桁の部分に加える. $n$ 桁同士の掛け算における計算量は $O(n^2)$ となり, 桁が大きくなる時に実質的に使いものにならなくなる. しかし,逆に極端に桁数が小さい場合,特に アセンブリ言語のように特殊な計算を行えるときには有効な方法となる.

なお,「桁」では説明が面倒になることがあるので, コンピュータが一度に扱うことができるサイズ(32 bit 計算機だと 0〜232−1,64 bit 計算機だと 0〜264−1) を「ワード」と呼び,これを計算対象と見なす.

1 ワード× 1 ワード

多倍長乗算の基本となる筆算方式だが,その基本はやはり 1 ワード同士の掛け算である. 人間は掛け算九九を覚えてそれに従って計算するだけであるが, 計算機でも実質的に同様のことを行う. (勿論,CPU の中の電気信号レベルで見れば AND 演算と SHIFT と加算で行われているが,プログラムのレベルではそれは考慮しない.)

この 1 ワード同士の掛け算は C 言語などの高級言語で見ると ワード外に溢れた部分の値を読み出せないため 途中でオーバーフローが起きないように一旦分割したり, 繰り上がりを確認するなど,かなり面倒な作業が必要になる.

1 ワードが符号なし 64 ビット整数の例:
void MultWords(uint64 a, uint64 b, uint64* cl, uint64* ch) {
  uint64 ah = a >> 32, al = a & 0xffffffff;
  uint64 bh = b >> 32, bl = b & 0xffffffff;
  uint64 chh = ah * bh, cll = al * bl;
  uint64 clh = al * bh, chl = ah * bl;
  uint64 cm = clh + chl;
  if (cm < clh)
    chh += 1ULL << 32;
  *ch = chh + (cm >> 32);
  *cl = cll + (cm << 32);
  if (*cl < cll)
    ++(*ch);
}

一方,アセンブリ言語を用いる場合, この様な演算を行う命令があるので1〜2命令で終わる. メジャーな CPU アーキテクチャの例として, x64 ならば IMULMUL が, POWER ならば mulhdmulhdumulld などが,ARM ならば UMULLSMULL が使える.

n ワード × n ワード

ワード数が増えた場合,上記の 1 ワード× 1 ワードの演算を繰り返し適用させることになるが, それと同時に繰り上がりを考慮する必要がある. 筆算では他の乗算アルゴリズムとは違い, 毎回繰り上がりを計算することができるため, ワードいっぱいまで数を詰めることができる.