algorithm - 用于将 m 和 n 位整数相乘的 Karatsuba

Question

我试图分析用于将 m 和 n 位整数相乘的 karatsuba 算法。据我了解，将整数分为 m/2 和 n/2 位子问题将是最有效的。问题如下：-

我们可以在这种情况下应用高斯技巧吗？我们是否需要进行一些调整才能应用它。填充较小的整数以匹配大小可能是一个解决方案，但它会影响我的运行时间。
在 karatsuba 算法中，应用高斯技巧，即 (a+b)*(c+d) 需要 T(n/2 +1)，因为子问题的大小可能会增加 1 位数。我可以通过某种方式将子问题的大小严格限制为 n/2。

score 0 · Accepted Answer

实际上，使用 Master 方法的 Karatsuba 算法复杂度是 T(n) = 3 * T(n / 2) + O(n)，

其中 N 是数字长度的最大值。实际上，即使一个子问题的大小比 1 位数大，我们也不在乎。因为它只是一个小常数。

另外，我不确定，你在说什么高斯技巧？通常这是一个技巧，我们将第一个数字拆分为两个部分（a，b），第二个数字拆分为部分（c，d）。

所以 (10 ^ (n / 2) * a + b) * (10 ^ (n / 2) * c + d) = 10^n * a * c + 10 ^ (n / 2) * a * d + 10 ^ (n / 2) * b * c + b * d;

因此，我们需要计算ac、bd和ad + bc = (a + b) * (c + d) - ac - bd。所以我们只需要计算 3 个较小尺寸的产品。而且，是的——我们可以将它应用到 Karatsuba 算法中。

1 回答 1