用Strassen算法乘n位2位数的算法

Question

设计和分析了一种算法，使A和B相乘，每个n位长，但将它们分割成3个大小相等的块，并使用Strassen算法。你能得到的最佳跑步时间是多少？

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

我看过视频，也读过讲座，但仍然不知道该怎么做。任何帮助都将不胜感激，谢谢！

Answer 1

既然这是家庭作业，我一开始只给你一个提示：

将两个n位数字分成三个块意味着将它们表示为X = x_0 + x_1 b + x_2 b^2和Y = y_0 + y_1 b + y_2 b^2，其中b是基，例如b = 2^(n/3)。计算它们的乘积XY。它是基b中的一个四次多项式.

这个多项式的系数可以从以下六个乘积中加减计算：

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)方法更快。