algorithm - 大数乘法

Question

在分析算法时，我看到我们通常假设乘法采用单条计算机指令。但是当数字的大小(就位数而言)时，这个假设就不合适了。在最基本的乘法形式中，将两个 n 位数相乘通常是 O(n^2)。在这种情况下，计算 x^n.(x 的 n 次方)的复杂性(就位运算而言)可能是多少？

通过解释的方法，复杂度对我来说似乎是 n 的指数(但不确定确切的数字)

Answer 1

计算复杂度x^n当然取决于用于计算幂和乘法的算法。如果您通过平方计算每次求幂的幂，则需要 O(log n) 次乘法。在每一步中，您要么对一个数进行平方，要么将两个数相乘并对两个数中的一个进行平方。

如果x有d(x)数字，x^n有 Θ(n*d(x)) 位数字，在最后一步中，您对大约 n/2*d(x) 的数字进行平方数字(并可能将该数字与较小的数字相乘)，然后通过将重复的平方 x^(2^k) 相乘来完成算法。 , 如果 2^k <= n < 2^(k+1) , 与蓄能器。

让S(m)是平方成本 m -digit 数字(可能与乘以两个任意 M(m) -digit 数字的成本 m 相同，也可能不同)。然后平方需要大约

S(2^(k-1)*d(x)) + S(2^(k-2)*d(x)) + S(2^(k-3)*d(x)) + ...

工作。自 S(m) >= m ，即 S(2^(k-1)*d(x)) 之间和 2*S(2^(k-1)*d(x)) .所以平方的工作由最后一步主导。对于 x^(2^s) 的乘法对于累加器，同样如此，最终的乘法决定了工作。最终的累加器几乎可以和重复的平方一样大，所以总的加注成本x到 n - 重复平方的次方是

Θ(M(2^k*d(x)),

这是Θ(M(n*d(x))) .使用天真的乘法 - M(m) = O(m^2) - 然后你得到的总成本为 O(n^2*d(x)^2) .使用更高级的乘法算法(Karatsuba、Toom-Cook、Schönhage-Strassen 等)，您将获得更低的复杂度，略高于 O(n*d(x)*log (n*d(x)) * log log (n*d(x)))。 .

通过与 x 相乘来迭代计算幂时, 在 n步骤，让M(m,k)表示乘以 m 的成本- 带有 k 的数字-数字。由于其中一个因素始终是 x , 总成本为

M(d(x),d(x)) + M(d(x),2*d(x)) + M(d(x),3*d(x)) + ... + M(d(x),(n-1)*d(x))

与教科书算法同成本M(m,k) = m*k ，总计为 n*(n-1)/2*d(x)^2 ，所以总成本又是Θ(n^2*d(x)^2) .但常数因子大于重复平方取幂。

当您乘以长度相差很大的数字时，就像这里经过几次迭代后发生的那样，据我所知，您不能降低成本 M(m,k)远低于 Θ(m*k) - 如果 m < k , 将数字视为一位数字和 r基数 r*m <= k < (r+1)*m 中的数字 ( b^m) ，如果m，您可以使用更好的算法降低乘以“数字”的成本。足够大，但不能减少 r因素。所以这个算法的复杂度是O(n^2*M(d(x))) , n^2 的因数无法消除。