乗算アルゴリズムの改良の提案

2023年6月に高知で開催された電子情報通信学会RECONF研究会にて，乗算アルゴリズムKaratsuba(カラツバ)法の改良提案を発表しました．

タイトル

被乗数と乗数のビット幅が異なる場合のKaratsuba法の拡張

An Extension of the Karatsuba Algorithm in Case that the Bit Widths of the Multiplicand and Multiplier are Different

Xilinx FPGAに内蔵されるDSPスライスは，被乗数25ビット乗数18ビットという構成をしています．被乗数とは，かけられる数のことで，乗数とは，かける数のことです．乗算結果＝被乗数 × 乗数ということになります．

Xilinx FPGAで一般的に用いられるVivadoの乗算回路生成は，被乗数と乗数が等しい前提で，乗算回路を組んでいるように見えます．すなわち，18ビット×18ビットの乗算を単位として，より大きなビット数の乗算回路を組んでいるようなのです．これは，いかにも資源利用効率が悪そうです．

また，多倍長整数演算は，古くから会計処理で用いられる他，暗号処理でも用いられています．多倍長整数乗算の基本アルゴリズムであり，現在もなお実用的で広く用いられるKaratsuba(カラツバ)法を，被乗数と乗数が異なる条件でも適用できるように拡張してみようというのが，本研究の動機となります．

被乗数と乗数のビット幅が等しい時(たとえば，64ビット×64ビット)の多倍長整数乗算で，提案手法は従来手法(Karatsuba法)と比べて乗算回数をおおよそ4％削減できました．

また，提案手法が原理上，最も効率よく乗算できる被乗数と乗数のビット幅の組合せの時(被乗数と乗数の組み合わせが，(41, 34), (73, 66), (137, 130), (265, 258), …の時)には，提案手法は従来手法(Karatsuba法)と比べて乗算回数を約半分にできました．

より詳細には，論文を参照ください．有償ですが，下記からダウンロードできます．