使用 Strassen 算法将 2 个数与 n 位相乘的算法
Algorithm to multiply 2 numbers with n bits using Strassen's algorithm
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 的算法对我来说没有任何意义。
我看过视频和阅读讲座，但仍然不知道如何进行。任何帮助将不胜感激，谢谢！
因为是作业，先提示一下：
将两个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 的 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)方法更快。
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 的算法对我来说没有任何意义。
我看过视频和阅读讲座，但仍然不知道如何进行。任何帮助将不胜感激，谢谢！
因为是作业，先提示一下：
将两个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 的 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)方法更快。