Ts11

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

На пальцах. Предположим что у нас есть два целых числа размерностью 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: исправил опечатки.