Алгоритм умножения 2 чисел на n бит с использованием алгоритма Штрассена

Question

Разработайте и проанализируйте алгоритм для умножения 2 чисел A и B, каждый длиной n бит, но разбиение их на 3 части одинакового размера и использование алгоритма Штрассена. Какое лучшее время вы можете получить?

У меня есть два числа, которые имеют длину n и разделены на три равные части. Например, 123 делится на 1, 2 и 3. Насколько я понимаю, я должен использовать матрицы. Однако алгоритм Штрассена не имеет для меня никакого смысла.

Я смотрел видео и читал лекции, но до сих пор не знаю, что делать дальше. Любая помощь будет оценена, спасибо!

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, Это будет 4-х степенной полином в базе b,

Коэффициенты этого многочлена могут быть вычислены с добавлением и вычитанием из этих 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 была уменьшена с вычисления 9 произведений n/3-битных чисел до всего 6, что делает его быстрее, чем метод O(n^2), которому обучают в школе.