-
SSA
（一種高效的二進制乘法算法）
鎖定
SSA代表Schönhage–Strassen algorithm，是一種非常高效的二進制大數乘法算法。一般用於將數萬至數萬億位二進制數相乘，是許多高精度計算算法的底層核心。
SSA由 Arnold Schönhage 與 Volker Strassen 在1971年開發，通過在整數模環中迭代使用快速數論變換，可以在 O(n logn loglogn) 的時間複雜度內將兩個 n bit 的二進制大數相乘。
- 外文名
- Schönhage–Strassen algorithm
我們首先考慮如何計算兩個大數 a 與 b 的積對
的模，其中 a 與 b 都是小於
的正數。
首先將 N 分解為 K 與 M 的積，其中 K 是2的冪次。
這樣，a與b就能寫成K位的
進制的數，除了最高的一位因為 a 與 b 可以等於
而可以等於
，其它的位都將小於
。計算a與b的積模
，即是計算兩個長度為K的數列的負循環卷積。
為了讓負循環卷積可以正確完成，需要選取一個數字n，在模
的環中計算卷積。這就需要卷積後的各位結果均在一個長度在
的區間內，這樣我們計算結果模
的值就夠了。
一般來説，選取
即可。
注意到
，所以2是一個2n次原根。如果n是K的倍數，那麼
將是2的冪，
。這樣，傅里葉變換可以只通過加減法和移位運算完成。
對a與b進行傅里葉變換後，需要將它們變換後的係數逐點相乘。這個乘法是模
的，可以遞歸地使用如上算法。直到n過小時，可以直接計算係數的積並對
取模。
然後，對結果進行逆變換，去除權重即得最終結果。
若想得到兩個大數 a 與 b 的完整積，只需要在第一步將N取得足夠大，使積一定小於
即可。
- 參考資料
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：4次歷史版本
- 最近更新： w_ou