15.1 乗算アルゴリズム

NxNリムの乗算と2乗は下記の7つのアルゴリズムのうち1つを使って実行されます。Nが増えるごとに7つのアルゴリズムに順次移行していきます。

アルゴリズム	下限閾値マクロ
筆算(Basecase)	(なし)
Karatsuba	MUL_TOOM22_THRESHOLD
Toom-3	MUL_TOOM33_THRESHOLD
Toom-4	MUL_TOOM44_THRESHOLD
Toom-6.5	MUL_TOOM6H_THRESHOLD
Toom-8.5	MUL_TOOM8H_THRESHOLD
FFT	MUL_FFT_THRESHOLD

2乗の場合もSQRを接頭詞とする下限閾値マクロを使ってアルゴリズムを切り替えます。

NxM乗算，即ち，被乗数のサイズが異なる場合，MUL_TOOM22_THRESHOLDを越えていると，サイズによりますが，Toom-cookに似たアルゴリズムかFFTを使って計算が行われます（see Unbalanced Multiplication)。