Как следует из описания метода Карацюбы, вместо четырех умножений потребуется три. Например, если нужно перемножить число из 4-х блоков, не принципиально в какой разрядности, на число из 3-х блоков, то на аппаратном уровне потребуется 12 команд mul при умножении столбиком, соответственно по Карацюбе — только 9. Я тут посчитал, по моему методу тоже потребуется 9 умножений, но это реально заумь.

Смотри, квадрат x отличается от квадрата соседнего числа x + 1 на 2x + 1, это школьники знают. Мы, в отличие от школьников, понимаем, что основание квадрата изменяется при добавлении 1 в 0-й бит. И можем построить формулу при инкрементировании любого бита:

2^(i + 1) * x + 2^(2i), где i — индекс инкрементируемого разряда. Подставь вместо i нолик, получишь "школьную" формулу.

А теперь представим, что добавляем не по одному биту, а целым блоком по смещению i (по границе блока) — как изменится формула? А вот так:

2^(i + 1) * x * y + 2^(2i) * y^2, где y — целый блок битов.

Известно, что любое произведение нечетных чисел можно представить в виде разницы квадратов (метод факторизации Ферма). У нас как бы обратная задача, нам не разложить число надо, а получить. Короче, вычисляем не произведение, а разность квадратов. У меня получается столько же умножений, сколько у Карацюбы. Есть один минус, по крайней мере для тебя: формула расчитана на двоичный формат, а ты, помнится, пилишь десятичный.

P.S. Прикинул еще раз — можно исхмтриться, и в исходном примере обойтись не 9, а 7 умножениями. Семью, Марти! Пошли на Абеля, а? На подсанкционного...


P.P.S. И все же 9... Квадрат у игрека забыл подставить... отбой с Абелем.