我们如何才能实现最快的 Bignum 平方？

快速 bignum 平方计算

问题：
给定两个表示为无符号 DWORD 动态数组的 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中文网其他相关文章！