筆算
多倍長乗算の基本は小学校で習ってきた筆算のままの方法で、 各桁の値同士を掛け合わせ対象となる桁の部分に加えることを繰り返す。 $n$ 桁同士の掛け算における計算量は $O(n^2)$ となり 桁数が大きくなるにつれ他のアルゴリズムの方が高速になるが、 逆に桁数が小さい場合は最速の方法である。
ちなみに「桁」では説明が面倒になることがあるので、 コンピュータが一度に扱うことができるサイズ （現在主に使われている 64 bit 計算機だと 0〜264−1） を「ワード」と呼び、この単位で計算するものとする。
1 ワード× 1 ワード
多倍長乗算の基本となる筆算方式だが、 その基本はやはり 1 ワード同士の掛け算である。 人間は掛け算九九を覚えてそれに従って計算するだけであるが コンピュータでも実質的に同様のことを行う。
ただこの 1 ワード同士の掛け算は C 言語などの高級言語で見ると ワード外に溢れた部分の値を読み出せないため 途中でオーバーフローが起きないように一旦分割したり、 繰り上がりを確認するなど、かなり面倒な作業が必要になる。 (gcc や clang など一部の処理系では符号なし 128 bit 整数 の演算が built-in で実装されているので下記のようなコードを 書かなくても済む。)
符号なし 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);
}
一方、アセンブリ言語を用いる場合、
この様な演算を行う命令があるので１〜２命令で終わる。
メジャーな CPU アーキテクチャの例として、
x64 ならば IMUL や MUL が、
POWER ならば mulhd、mulhdu、
mulld などが、ARM ならば
UMULL や SMULL が使える。
$n$ ワード $\times n$ ワード
ワード数が増えた場合、上記の 1 ワード× 1 ワードの演算を繰り返し適用させることになるが、 それと同時に繰り上がりを考慮する必要がある。 筆算では他の乗算アルゴリズムとは違い、 毎回繰り上がりを計算することができるため、 ワードいっぱいまで数を詰めることができる。