Next: Karatsuba Multiplication, Previous: Multiplication Algorithms, Up: Multiplication Algorithms [Index]
NxM を実行する筆算アルゴリズムは互いの積を計算し，長方形の枠に入れて和の計算をするというもので，手計算で長い桁の乗算を行う手法と同一のものです。そのため，スクールブック(schoolbook)法，グラマースクール(grammar school)法とも称されます。O(N*M)の手間のかかるアルゴリズムで，詳細はKnuth本(see References)の4.3.1節のアルゴリズムMを参照するか，mpn/generic/mul_basecase.cに記述したものを参考にして下さい。
mpn_mul_basecase関数をアセンブラで実装したものは汎用のCのコードと本質的に何ら変わるところはなく，相違点は普通のアセンブラの技法を使い，速度向上のための分かりづらいコーディングを行っているというところです。
2乗の計算は，正方形の枠の上三角部分と下三角部分の積が同一のものとなるため，普通の乗算の約半分程度の時間で実行できます。対角成分以下の三角部分の積を作れば，その2倍（1bit左シフト)を求め，対角成分の積を加えます。この2乗のアルゴリズムはmpn/generic/sqr_basecase.cで見ることができます。アセンブラによる実装も同様に行っており，本質的にはこの汎用Cコードと同一のものです。
u0 u1 u2 u3 u4 +---+---+---+---+---+ u0 | d | | | | | +---+---+---+---+---+ u1 | | d | | | | +---+---+---+---+---+ u2 | | | d | | | +---+---+---+---+---+ u3 | | | | d | | +---+---+---+---+---+ u4 | | | | | d | +---+---+---+---+---+
実際の2乗計算は乗算より2倍速くはならず，せいぜい1.5倍程度の高速化にとどまります。1.5倍にもならないというのであれば，そのCPU向きのmpn_sqr_basecase関数の改良を要するということになります。
幾つかのCPU上では，小さいサイズの値に対しては，mpn_mul_basecase関数の方が，汎用Cコードであるmpn_sqr_basecase関数より高速になることもあります。SQR_BASECASE_THRESHOLDの値は，mpn_sqr_basecase関数を使うサイズを示しており，これがゼロに設定されていると，常にこの乗算関数を使うことを意味します。