Кто может объяснить алгоритм Умножение Карацубы?
На пальцах. Предположим что у нас есть два целых числа размерностью 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: исправил опечатки.
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
Итого получили классическое умножение столбиком, только в стоичной системе счисления.
Только в классическом умножении у нас четыре умножения, а в предложенном алгоритме всего три.