Почему одно умножение меняет порядок роста

Коротко

В формуле T(n) = a·T(n/b) + f(n) число подзадач a стоит в ПОКАЗАТЕЛЕ: ответ - n^(log_b a). Поэтому экономия одного умножения из четырёх меняет не константу, а порядок: log₂ 4 = 2 превращается в log₂ 3 = 1.585. Тот же приём продолжается: Тоом-Кук режет числа на три части и обходится пятью умножениями вместо девяти - n^(log₃ 5) = n^1.465. Предел этой лестницы - быстрое преобразование Фурье с n·log n, и ему посвящена отдельная глава. Общее правило: чтобы ускорить алгоритм деления, надо уменьшать ЧИСЛО ПОДЗАДАЧ, а не цену склейки.

Если ты понимаешь, почему a стоит в показателе, знаешь идею Тоом-Кука и видишь границу этой лестницы, листай до «Теперь сам».

Как думаешь, что выгоднее ускорить

Есть алгоритм с рекуррентностью T(n) = 4·T(n/2) + n, то есть Θ(n²). Тебе предлагают два улучшения на выбор. Первое: ускорить объединение в десять раз - было n, стало n/10. Второе: избавиться от одной подзадачи - было четыре, стало три.

Первое звучит внушительнее: десять раз! Второе - всего на четверть меньше работы за уровень. А на деле первое не меняет ничего (Θ(n²) как было), а второе превращает квадрат в n^1.585, то есть на тысяче элементов даёт выигрыш в семнадцать раз, а на миллионе - в триста.

На что это похоже

Проценты по вкладу. Разница между вкладом под 4% и под 3% на одном году - копейки. Но это СТАВКА, она работает на каждом шаге, и через тридцать лет разрыв становится кратным. Число подзадач a - такая же ставка: оно применяется на каждом уровне рекурсии, а уровней log n.

Механизм: где стоит a и где стоит f(n)

T(n) = a·T(n/b) + f(n)

число подзадач a  →  в ПОКАЗАТЕЛЕ:  n^(log_b a)
цена склейки f(n) →  слагаемым, и решает только в режиме «корень тяжелее»

УМНОЖЕНИЕ ЧИСЕЛ: лестница по числу частей

столбик                 n²                  каждая цифра с каждой
разрез пополам, наивно  4·T(n/2)  → n²      ничего не выиграли
Карацуба                3·T(n/2)  → n^1.585 = n^(log₂ 3)
Тоом-Кук (три части)    5·T(n/3)  → n^1.465 = n^(log₃ 5)
Тоом-Кук (четыре части) 7·T(n/4)  → n^1.404 = n^(log₄ 7)
...
предел лестницы         БПФ       → n·log n

Идея Тоом-Кука та же, что у Карацубы, только вместо «числа» берётся МНОГОЧЛЕН: разрезав число на k частей, мы получаем многочлен степени k−1, произведение двух таких - многочлен степени 2k−2, а он однозначно восстанавливается по 2k−1 значениям. Значит достаточно 2k−1 умножений в точках вместо k² умножений частей.

k = 2 (Карацуба):   2·2 − 1 = 3 умножения  вместо 4
k = 3 (Тоом-3):     2·3 − 1 = 5 умножений  вместо 9
k = 4:              2·4 − 1 = 7 умножений  вместо 16

Правило

Число подзадач a стоит в показателе n^(log_b a), поэтому убрать одну подзадачу - значит изменить ПОРЯДОК роста, а ускорить объединение - только константу (если режим не «корень тяжелее»). Отсюда лестница алгоритмов умножения: разрезав числа на k частей, произведение можно получить за 2k−1 умножений вместо k², потому что произведение многочленов степени k−1 восстанавливается по 2k−1 значениям. Карацуба - это k = 2 (три вместо четырёх), Тоом-Кук - k = 3 (пять вместо девяти) и дальше. Чем больше k, тем лучше показатель и тем больше накладных сложений: в библиотеках стоят все эти алгоритмы сразу, каждый на своём диапазоне размеров.

Разбор: как одна подзадача меняет число на конце

Посчитаем, во сколько раз отличаются алгоритмы на числах из n = 2^20 цифр (около миллиона).

алгоритм            показатель        операций примерно      отношение к n²
столбик             2.000             1.1 · 10¹²             1
Карацуба            1.585             3.5 · 10⁹              ≈ 315
Тоом-3              1.465             6.6 · 10⁸              ≈ 1 660
БПФ                 нет (n·log n)     2.1 · 10⁷              ≈ 52 000

У БПФ в столбце «показатель» стоит прочерк не случайно: показателя степени у него нет вовсе. n·log n растёт быстрее любой линейной функции и медленнее любой n^(1+ε), поэтому в лестницу показателей эта строка не помещается - она её обрывает.

Нецелые показатели в таблице считаются так: n^1.585 при n = 2²⁰ - это 2^(20·1.585) = 2^31.7, а 2^31.7 ≈ 3.5·10⁹. Так же получены и остальные строки.

Обрати внимание на шаг между строками. От столбика к Карацубе - экономия одной подзадачи из четырёх, и выигрыш в триста с лишним раз. От Карацубы к Тоом-3 - ещё четыре подзадачи из девяти, и выигрыш всего впятеро. Лестница даёт всё меньше с каждой ступенькой, а накладные расходы растут: у Тоом-3 требуется интерполяция с делениями на маленькие константы, и порог его включения в библиотеках - тысячи цифр.

Вот почему реальные реализации длинной арифметики выглядят как лестница с порогами: до сотни слов - столбик, до нескольких тысяч - Карацуба, дальше Тоом-Кук, а на очень больших - умножение через преобразование Фурье. Каждый следующий алгоритм лучше асимптотически и хуже по константе.

Разбор: Тоом-3 на числах, за пять умножений вместо девяти

Карацубу мы считали руками, а Тоом-Кук до сих пор был только словами. Посчитаем и его - 123456 · 654321, основание B = 100, по три части в каждом числе.

Фокус в том, что число - это многочлен в точке B. Пишем оба числа многочленами:

123456 = 12·B² + 34·B + 56      →   P(t) = 12t² + 34t + 56
654321 = 65·B² + 43·B + 21      →   Q(t) = 65t² + 43t + 21

У произведения R = P·Q степень 4, то есть ПЯТЬ коэффициентов - значит хватит пяти значений. Берём точки 0, 1, −1, 2 и «бесконечность» (там значение - это произведение старших коэффициентов):

точка   P      Q      R = P·Q
  0     56     21      1176        ← 56·21
  1    102    129     13158        ← 102·129
 −1     34     43      1462        ← 34·43
  2    172    367     63124        ← 172·367
  ∞     12     65       780        ← 12·65

ПЯТЬ умножений - вместо девяти у наивного «каждая часть с каждой»

Теперь интерполяция: по пяти значениям находим пять коэффициентов R. Это линейная система, и для фиксированных точек её решение выписывается раз и навсегда формулами со сложениями и делениями на маленькие константы (2, 3, 6) - именно их и считают «накладными расходами» Тоом-Кука. Здесь ответ такой:

R(t) = 780t⁴ + 2726t³ + 5354t² + 3122t + 1176

проверка: R(1)  = 780 + 2726 + 5354 + 3122 + 1176 = 13158   ✓
          R(−1) = 780 − 2726 + 5354 − 3122 + 1176 = 1462     ✓
          R(2)  = 12480 + 21808 + 21416 + 6244 + 1176 = 63124 ✓

Остаётся подставить t = B = 100 и разнести переносы:

R(100) = 780·10⁸ + 2726·10⁶ + 5354·10⁴ + 3122·10² + 1176
       = 78 000 000 000 + 2 726 000 000 + 53 540 000 + 312 200 + 1 176
       = 80 779 853 376

проверка: 123456 · 654321 = 80 779 853 376   ✓

Вот и весь Тоом-Кук: девять произведений частей заменились пятью, а разница ушла в сложения и деления на константы. Карацуба - это ровно тот же приём при k = 2: три точки, три умножения.

Разбор: почему больше частей - не всегда лучше

Казалось бы, если k = 3 лучше k = 2, надо брать k побольше. Посмотрим на показатель как функцию от k:

показатель = log_k (2k − 1)

k = 2:  log₂ 3   = 1.585
k = 3:  log₃ 5   = 1.465
k = 4:  log₄ 7   = 1.404
k = 8:  log₈ 15  = 1.302
k = 32: log₃₂ 63 = 1.195

Показатель действительно падает - но медленно, и к единице подходит только в пределе. А цена растёт быстро: при k частях надо вычислить значения в 2k−1 точках и потом ИНТЕРПОЛИРОВАТЬ обратно, а это O(k²) сложений и делений на каждом уровне рекурсии, причём с делениями на растущие константы, что на целых числах требует аккуратности.

Отсюда и итог: увеличивать k до бесконечности бессмысленно. Правильный следующий шаг - не «ещё больше частей», а другой способ считать значения и интерполировать: если брать точки не произвольные, а КОРНИ ИЗ ЕДИНИЦЫ, то и вычисление значений, и обратный переход делаются за n·log n. Это и есть быстрое преобразование Фурье - последняя глава раздела.

Что ломается без этого

Первое: оптимизировать объединение там, где решают подзадачи: ускорение f(n) в десять раз не изменит Θ(n²), если режим «листья тяжелее». Второе: считать, что Тоом-Кук - это «Карацуба, только лучше», и ставить его на коротких числах: интерполяция съест весь выигрыш. Третье: забывать, что все эти алгоритмы требуют ПОРОГОВ, и без них работают медленнее школьного столбика. Четвёртое: думать, что показатель можно довести до 1 увеличением k: log_k(2k−1) стремится к 1 только в пределе, а накладные расходы растут как k². Пятое: переносить рассуждение на задачи, где подзадачи не независимы: вся лестница держится на том, что произведения частей можно считать отдельно.

Зачем это в работе

Практическая польза - в умении читать чужие библиотеки. Открыв исходники GMP или больших целых Python, увидишь ровно эту лестницу: mul_basecase, mul_karatsuba, mul_toom22, mul_toom33, mul_fft с порогами, подобранными замером на конкретной архитектуре. Знание, что там происходит, экономит часы при отладке производительности криптографического кода. Общий же принцип применим далеко за пределами умножения: если у тебя рекурсивная схема и она медленная, первым делом посмотри на ЧИСЛО ПОДЗАДАЧ, а не на цену склейки. Именно так были ускорены умножение матриц (Штрассен), преобразование Фурье и некоторые задачи геометрии.

Теперь сам

Придумали алгоритм, который режет числа на 5 частей и обходится 9 умножениями вместо 25. Какой у него показатель и лучше ли он Тоом-3?

Ответ. Рекуррентность: T(n) = 9·T(n/5) + n. Показатель - log₅ 9.

log₅ 9 = ln 9 / ln 5 = 2.197 / 1.609 = 1.365

Сравниваем с Тоом-3 (log₃ 5 = 1.465): новый алгоритм лучше по порядку роста.

Но проверим, укладывается ли он в общую формулу. По теории для k частей достаточно 2k − 1 умножений, здесь k = 5, то есть 2·5 − 1 = 9 - ровно столько и заявлено. Значит это не «новый алгоритм», а очередная ступенька Тоом-Кука, Тоом-5, и её показатель log₅ 9 = 1.365 честно стоит между log₄ 7 = 1.404 и log₈ 15 = 1.302.

Практический вывод тот же, что в разборе: показатель лучше, а интерполяция по девяти точкам дороже, чем по пяти, поэтому порог включения выше. Если бы кто-то заявил 8 умножений на 5 частей, стоило бы насторожиться: 2k − 1 - это не «сколько удалось», а доказанная НИЖНЯЯ оценка для схем такого вида (результат Винограда: произведение двух многочленов с k коэффициентами меньше чем за 2k − 1 умножений не получить). Заявка на восемь была бы поводом искать ошибку, а не радоваться.

Главное

Число подзадач a стоит в показателе n^(log_b a), поэтому одна убранная подзадача меняет ПОРЯДОК роста, а ускорение склейки - только константу. Разрезав числа на k частей, произведение получают за 2k − 1 умножений вместо k²: произведение многочленов степени k−1 однозначно восстанавливается по 2k−1 значениям. Отсюда лестница: Карацуба (k=2, показатель 1.585), Тоом-3 (k=3, 1.465), Тоом-4 (1.404) и так далее; показатель log_k(2k−1) падает медленно, а цена интерполяции растёт как k², поэтому в библиотеках стоят все алгоритмы сразу, каждый на своём диапазоне с подобранным порогом. Предел лестницы достигается не увеличением k, а сменой точек: корни из единицы дают n·log n - это быстрое преобразование Фурье.