我們如何實現最快的 Bignum 平方？

快速bignum 平方計算

問題：
給定兩個表示為無WORD 動態符號組的bigint，在沒有精度的情況下盡可能快地計算y = x^2

上下文：
問題出現在加速 bignum 除法的背景下，其中平方運算至關重要。

問題：
如何以最有效的方式計算y = x^2

答案：
初始方法：
初始方法使用乘法y = xx，透過減少來避免多次乘法NN 次乘法到(N 1)*(N/2)

Karatsuba 乘法：
Karatsuba乘法演算法用於進一步最佳化乘法運算。它使用分而治之的方法，透過將大數分解為較小的方塊來加速乘法。

效能測量：
測試表明，最佳化後的 Karatsuba 乘法優於初始 O( N^2) 較大數字（約 32*98）的乘法演算法位元）。

用於 SQR 實現的改進的 Schönhage-Strassen 乘法：
改進的 Schönhage-Strassen 乘法，稱為 FFT（快速傅立葉變換），用於加速 SQR 運算。然而，由於精度損失，它被認為無法使用。

NTT最佳化：
NTT（數論轉換）用於最佳化乘法和SQR運算。它比 FFT 更快，但需要模運算，並且受到數字大小的限制。

目前狀態：
目前實作使用最佳化的 Karatsuba 演算法進行 SQR 運算，當數字大小超過一定閾值，並且針對較小數字採用初始快速 SQR 方法。

傑出問題：
作者承認可能有一個更簡單或更有效的解決方案被忽略了。繼續尋找更好的演算法。

以上是我們如何實現最快的 Bignum 平方？的詳細內容。更多資訊請關注PHP中文網其他相關文章！