Кто может объяснить алгоритм Умножение Карацубы?

Question

[Isaac Clark]

Здравствуйте, подскажите пожалуйста.
Разбираю алгоритм умножения Карацубы и столкнулся с проблемой, что не могу понять как работает правильно step5.
То есть, мы взяли step1 и добавили к нему четыре нуля, почему?
Потому что в step2 у нас четыре цифры?
Почему в step4 мы добавили два нуля?
Пожалуйста, объясните "на пальцах", как правильно работать с этой формулой и как правильно получить step5, а точнее, как и откуда берутся эти нули.
Спасибо за помощь и ваше время.

Answer 1

[Sumor]

ab × cd
По формуле получаем:

(a × c) × 1000   +   b × d   +   ( (a + b) × (c + d) - a × c - b × d ) × 100 =
= 1000 × a × c + b × d  + ( a × c + a × d + b × c + b × d - a × c - b × d ) × 100 =
= 1000 × a × c + b × d  + ( a × d + b × c )  × 100 =
= 1000 × a × c + 100 × a × d + 100 × b × c + b × d

Итого получили классическое умножение столбиком, только в стоичной системе счисления.
Только в классическом умножении у нас четыре умножения, а в предложенном алгоритме всего три.

Comments

[Isaac Clark]

а откуда берутся цифры 1000 и 100, объясните пожалуйста?

[Sumor]

Цифры 1000 и 100 из первой строчки ниоткуда не берутся. Они часть "рецепта" по быстрому умножению чисел.
Показанный вывод доказывает, что предложенный алгоритм соответствует каноническому умножению в столбик.
Цифры 1000 и 100 из последней строчке соответствуют умножению в столбик:
·········ab
·········cd
---------
·······b×d= b×d
·····a×d··= 100×a×d
·····b×c··= 100×b×c
··a×c···· = 1000×a×c
--------
1000 × a × c + 100 × a × d + 100 × b × c + b × d
Так как мы оперируем двузначными числами, то у нас не по одному нолику прибавляется, а по два на каждый разряд.

[Mrrl]

Sumor: Так может быть, там не 1000, а 10000?

[Sumor]

Да точно! Везде вместо 1000 читать 10000.

Answer 2

[Сергей Протько]

На пальцах. Предположим что у нас есть два целых числа размерностью n. Тогда

X = 10^(n/2) * a + b;
Y = 10^(n/2) * c + d;

Перемножим:
X * Y = (10^(n/2) * a + b) * (10^n/2 * c + d)

Или если упростить

X * Y = 10^n * ac + 10^(n/2) * (ad + bc) + dc;
Или если добавить переменных:

s1 = ac; // step 1
s2 = bd; // step 2
s3 = ad + bc; //step 3
X * Y = 10^n * s1 + 10^(n/2) * s3 + s2;

По сути пятый стэп - это как раз таки вот эта формула.

Вся соль в том, что когда мы вычисляем s1 или s2 или s3 мы опять имеем дело с умножением и можем применить этот же алгоритм, рекурсивненько уменьшая размерность операндов, за счет чего понижается количество необходимых операций.

@updated: исправил опечатки.

Comments

[Isaac Clark]

что такое ^n ?

[Сергей Протько]

Dark_Knight: "в степени n". В примере приведенном вами n = 4.

Answer 3

[Антон Меньшов]

В дополнение к вышестоящим объяснениям добавлю: мне сначала было легче разобраться с быстрым умножением матриц (умножение Штрассена, https://ru.wikipedia.org/wiki/Алгоритм_Штрассена). Это один из самых наглядных (в математическом смысле) быстрых алгоритмов типа "разделяй и властвуй". Для меня проще думать в терминах матриц, нежели составных частей чисел.