Алгоритмы Карацубы и Тоом-3 для умножения 3-значных чисел

Question

Мне было интересно об этой проблеме относительно алгоритма Катацубы. При применении Карацуба вы в основном должны сделать 3 умножений за один проход цикла Те (скажем, ab и cd являются 2-значные номера с цифрами соответственно a, b, c and d):

X = bd 
Y = ac 
Z = (a+c)(c+d) 

, а затем мы СУММ искали являются:

bd = X 
ac = Y 
(bc + ad) = Z - X - Y 

Мой вопрос: допустим, у нас есть две 3-значные номера: abc, def. Я узнал, что для этого нам нужно будет всего 5 умножений. Я также нашел этот алгоритм Toom-3, но он использует многочлены, которые я могу, достаточно получить. Может кто-то записать эти умножений и как рассчитать интересные суммы bd + ae, ce+ bf, cd + be + af

Answer 1

Основная идея заключается в следующем: число 237 является многочлен р (х) = 2х + 3x + 7 оценивается в точке х = 10 , Итак, мы можем представить себе каждое целое число, соответствующее полиному, коэффициенты которого являются цифрами числа. Когда мы вычисляем многочлен от x = 10, мы возвращаем наш номер.

Интересно, что для полного задания полинома степени 2 нам нужно его значение только в трех разных точках. Нам нужно 5 значений, чтобы полностью определить многочлен степени 4.

Таким образом, если мы хотим, чтобы умножить два 3 значных числа, мы можем сделать так:

1. Оценка соответствующих полиномов в 5 различных точках.
2. Умножение 5 значений. Теперь мы имеем 5 значений функции многочлена произведения.
3. Нахождение коэффициентов этого многочлена из пяти значений мы вычисленных на шаге 2.

Карацуба умножение работает точно так же, за исключением того, что нам нужно только 3 различных точек. Вместо 10, мы вычисляем многочлен от 0, 1 и «бесконечность», что дает нам b,a+b,a и d,d+c,c, которые умножаются вместе, давая вам X,Z,Y.

Теперь, чтобы написать все это в терминах abc и def. В Wikipedia article, это на самом деле сделано довольно красиво:

1. В разделе оценки, многочлены оцениваются дать, например, c,a+b+c,a-b+c,4a+2b+c,a для первого номера.
2. В продуктах поточечны, соответствующие значения для каждого числа умножается, что дает:

X = cf 
Y = (a+b+c)(d+e+f) 
Z = (a+b-c)(d-e+f) 
U = (4a+2b+c)(4d+2e+f) 
V = ad 

1. В разделе Интерполяции эти значения объединяются, чтобы дать вам цифры в продукте.Это связано с решением системы линейных уравнений 5х5, так что опять-таки это немного сложнее, чем дело Карацубы.