algorithm - 使用 Strassen 算法将 2 个数字与 n 位相乘的算法

Question

设计和分析一种算法，将 2 个数字 A 和 B 相乘，每个 n 位长，但使用 Strassen 算法将它们分成 3 个相等大小的块。您可以获得的最佳运行时间是多少？

我有两个长度为 n 的数字并将它们分成三个相等的部分。例如，123 分为 1、2 和 3。根据我的理解，我必须使用矩阵。但是，Strassen 的算法对我来说没有任何意义。

我看过视频和阅读讲座，但仍然不知道如何进行。任何帮助将不胜感激，谢谢！

Answer 1

由于这是家庭作业，我将首先给出一个提示：

将两个 n 位数字分成三个块意味着将它们表示为基数X = x_0 + x_1 b + x_2 b^2，例如。计算他们的产品。它将是 base 中的 4 次多项式。Y = y_0 + y_1 b + y_2 b^2bb = 2^(n/3)XYb

该多项式的系数可以通过以下 6 个乘积的加减法计算得出：

x_0 y_0
x_1 y_1
x_2 y_2
(x_0 + x_1)(y_0 + y_1)
(x_0 + x_2)(y_0 + y_2)
(x_1 + x_2)(y_1 + y_2)

这样计算 XY 的乘积的工作已经从计算 n/3 位数的 9 个乘积减少到只有 6 个，比学校教授的 O(n^2) 方法更快。