对表示为 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中文网其他相关文章！