對錶示為 DWORD 數組的大整數進行平方的最快演算法是什麼？

快速 bignum 平方計算

本文旨在確定計算表示為無符號 DWORD 動態數組的 bigint 的 y = x^2 的最快方法。

問題陳述

將bigint x 表示為陣列DWORD：

DWORD x[n+1] = { LSW, ......, MSW };

其中：

• n 1 是使用的DWORD 數量
• x = x[0] x[1]

在不損失精確度的情況下盡快找到 y = x^2 的值。

假設：

• 使用C 和32 位元整數算術計算

樸素方法（O(n^2) 乘法）

樸素法涉及將x 乘以自身，這需要O(n^2) 時間。這可以表示為：

y = x * x
y = (x0 + x1 + x2 + ...xn)*(x0 + x1 + x2 + ...xn)

將乘積展開，我們得到：

y0     = x0*x0
y1     = x1*x0 + x0*x1
y2     = x2*x0 + x1*x1 + x0*x2
y3     = x3*x0 + x2*x1 + x1*x2
...
y(2n-3) = xn(n-2)*x(n  ) + x(n-1)*x(n-1) + x(n  )*x(n-2)
y(2n-2) = xn(n-1)*x(n  ) + x(n  )*x(n-1)
y(2n-1) = xn(n  )*x(n  )

Karatsuba 乘法

Karatsuba 演算法可以用來加速乘法O(n^log2 (3))。雖然看起來很有希望，但該演算法的遞歸性質可能會為大數帶來顯著的效能開銷。

最佳化的Schönhage-Strassen 乘法

Schönhage-Strassen 演算法在O( 下提供更快的乘法nlog(n)(log(log(n)) )) 使用分治法方法。然而，由於溢出問題以及需要對無符號整數進行模運算，該演算法具有實際限制。

結論

對於較小的數字，簡單的 O(n^2) 乘法方法是最有效率。對於較大的數字，建議使用 Karatsuba 乘法演算法。可以探索進一步的最佳化來提高性能，例如使用 FFT（快速傅立葉變換）或 NTT（數論變換）。

以上是對錶示為 DWORD 數組的大整數進行平方的最快演算法是什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！