Previous: , Up: Multiplication Algorithms   [Index]


15.1.8 不均衡乗算

乗算する2数の長さが異なる場合, MUL_TOOM22_THRESHOLD以下であれば,筆算アルゴリズムを使います(see Basecase Multiplication)。

もっと長い桁であれば,FFTを直接使います。

この中間のサイズの場合は,Alberto Zanoni と Marco Bodratoが提唱したToom-Cookに似たアルゴリズムを使います。 考え方としては,2数を分割して異なる次数の多項式を作ります。GMPの現在の実装では,小さい方の引数を2つの係数,即ち,1次多項式に変換し,大きい方の引数は2~4つの係数,即ち,1~3次多項式に変換します。