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

Question

Design and analyze an algorithm to multiply 2 numbers A and B, each n bits longs, but partitioning them into 3 equal sized pieces each and using the Strassen's algorithm. What is the best running time you can get?

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

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

Answer 1

由于这是作业，所以我首先给出一个提示:

将两个 n 位数字分成三个 block 意味着将它们表示为 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 的 4 次多项式。

这个多项式的系数可以通过这 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) 方法更快。