高速整数乗算アルゴリズムSchönhage Strassen Algorithmを雑に実装した話
そういえばIS Advent Calendarに投稿しようと思ってずっと放置していたのがあったのに、登録するのを忘れていたことを思い出したので、雑に供養します。
だいぶ昔の話なんですが、大学の演習IIIとかいう授業で、なんかSchönhage Strassen Algorithmというのを実装したくなったので実装させてもらいました。
当時のスライドから面白くないものを削除したスライドです。それなりにイメージは伝わると思っています。
実装は公開しています。見るに堪えないかもわかりませんが。
github.com
Schönhage Strassen Algorithmは、整数乗算アルゴリズムで、まあもちろん速いわけなんですが、速いと言っても定数倍がかなり重くて日常的な乗算にはむしろ不利なやつです。
日本語WikipediaにはGMPでは「10進法で33 000 - 150 000桁の大きさ」でSSAを初めて用いるようになるとあります。
ソースに当たると、MUL_FFT_THRESHOLDというのが関係してくるらしくって、その値はx86_64で11520らしいんですが、limbってなんだかわからないしこれがなんなのかはわかりません。
実装するときは、スライドにもありますが、「Multiplying large numbers and the Schönhage-Strassen Algorithm - Theo Kortekaas」とか参考にするといいです。オンラインで見つかるPDFです。
今終わってみるとGMP manualとかも参考になったのかもしれないと思いますが、当時は見つけられなかったのでしかたない。
今回の実装では、スライドのpage 22を見ると、10^6 bit同士の乗算あたりからKaratsuba法を上回ったようです。
まあ圧倒的にGMPには劣るわけですが（スライドpage 23）。
そんなちゃんと実装したわけじゃないので、同じbit数同士の乗算しかできなかったり（当然0埋めすれば違ってもできるが、計算量的に劣る）、詳しくは書きませんが計算途中に特別な条件を満たすと続行不可能になってエラー返したりします*1。
以上、供養でした。
*1:参考PDFでも触れられているのと、「続行不可能」でスライド検索すればなんとなく分かります。
