如何實現大數的快速平方計算？

大數的快速平方計算

問題：
給定一個表示為動態數組的bignum無符號DWORD，任務是在不丟失的情況下盡快找到bignum的平方

解：

提供的演算法透過使用分而治之的方法來最佳化乘法來有效計算 bignum 的平方。

最佳化Karatsuba乘法：

調整後與最佳化，對於超過32*98 位元的輸入大小，Karatsuba 乘法比O(N^2) 經典乘法更快。對於較小的數字，快速 sqr 方法仍然更有效。

用於平方實現的修改Schönhage-Strassen 乘法：

FFT 和NTT 變換已被探索用於加速，但它們的準確性損失和實現複雜性使它們不太適合。

NTT最佳化：

NTT 的密集最佳化帶來了效能提升，NTT sqr 閾值設定為31032 位元，NTT mul 設定為139632 位元。

結論：

對於較小的數字，快速 sqr 方法被證明是最快的選擇。在達到閾值之後，Karatsuba 乘法變得更有效率。然而，尋找更有效的唐葉替代品的工作仍在繼續。

以上是如何實現大數的快速平方計算？的詳細內容。更多資訊請關注PHP中文網其他相關文章！