Как 23-летний студент опроверг давнюю гипотезу об одной из простейших математических операций
Ученики начальной школы могут заучивать таблицу умножения однозначных чисел, но простого запоминания будет недостаточно, когда учитель задаст задачу на умножение трёхзначных чисел. Здесь требуется алгоритм: учеников учат выстраивать числа друг над другом и умножать каждую цифру нижнего числа на каждую цифру верхнего. На протяжении тысячелетий математики считали это самым быстрым способом умножения, пока в 1960 году 23-летний молодой человек не сделал шокирующее открытие, которое привело к загадке, остающейся неразгаданной до сих пор.
Эта загадка имеет решающее значение для всех, кто имеет отношение к цифровому миру, поскольку умножение является основополагающей операцией для компьютеров. Шифрование, робототехника, искусственный интеллект, обработка звука и практически всё остальное, чем мы заставляем заниматься кремниевые чипы, связано с умножением, причём иногда огромных чисел, умножаемых многократно. В таких масштабах даже простая операция становится «узким местом», и любое дополнительное повышение эффективности имеет глобальные экономические последствия.
Чтобы понять суть этого «узкого места», обратите внимание на то, как «школьный» алгоритм справляется с увеличением размера чисел. При умножении двух двузначных чисел выполняется четыре однозначных умножения. Если перейти к паре трёхзначных чисел, то потребуется девять однозначных умножений. Нагрузка растёт пропорционально квадрату количества разрядов (n², где n — количество разрядов в умножаемых числах). При анализе подобного алгоритма компьютерные учёные не измеряют скорость в секундах, поскольку она зависит от аппаратного обеспечения. Вместо этого они подсчитывают количество вычислительных шагов. Они также игнорируют второстепенные детали, такие как время, необходимое для переноса единицы при умножении. Когда числа становятся достаточно большими, эти низкоуровневые операции перестают иметь значение, поскольку их полностью затмевают более ресурсоёмкие операции. Информатики обозначают количество шагов с помощью так называемой нотации «большого O»: например, алгоритм, который учат в начальной школе, требует O(n²) шагов, что читается как «порядка n в квадрате». В общих чертах, если числа в два раза длиннее, для выполнения алгоритма требуется в четыре раза больше вычислительной работы. Если числа в тысячу раз длиннее, требуется в миллион (1 000 в квадрате) раз больше работы.
Ещё с древних времён математики подозревали, что O(n²) является неотъемлемым пределом скорости умножения. Известный советский профессор математики Андрей Колмогоров сформулировал предел скорости O(n²) в виде формальной гипотезы и упомянул о ней во время семинара в Московском государственном университете в 1960 году. Когда математики выдвигают гипотезу, они бросают другим вызов и ждут, пока другие либо докажут, либо опровергнут её. Потребовалась всего неделя, чтобы Анатолий Карацуба, тогда 23-летний студент из аудитории, вернулся и доказал, что Колмогоров ошибался. Колмогоров был ошеломлён. Результат был опубликован в престижном журнале «Труды Академии наук СССР», но, что забавно, Карацуба не писал статью. Колмогоров сам написал формальное доказательство и представил его к публикации, указав Карацубу в качестве ведущего автора. Карацуба узнал о статье только тогда, когда получил репринты по почте.
Гениальность Карацубы заключалась в том, что он понял: дорогостоящие и трудоёмкие умножения можно заменить на простые и быстрые сложения. Сложение двух n‑значных чисел занимает всего O(n) времени, поскольку требует лишь одного прохода по цифрам, а не полного прохода по верхнему числу для каждой цифры нижнего числа, как при умножении. Чтобы понять, как Карацуба заменил умножение сложением, рассмотрим небольшой пример. Для такой простой задачи этот метод будет чрезмерно сложным, но он позволяет сэкономить значительное время, когда числа становятся больше.
В этом простом примере давайте вычислим чему равно 12 × 34.
Сначала разделим оба числа на десятки и единицы. Присвоим a = 1 и b = 2 (для 12), а также c = 3 и d = 4 (для 34). В алгебраическом виде 12 × 34 можно переписать как (10a + b) × (10c + d).
Раскроем скобки: 100(ac) + 10(ad + bc) + (bd).
Чтобы решить уравнение традиционным способом, необходимо выполнить четыре отдельных умножения: ac = 3, ad = 4, bc = 6 и bd = 8, что в точности соответствует методу умножения столбиком, используемому в начальной школе. (Обратите внимание, что мы не учитываем умножения на 100 или на 10, поскольку они сводятся лишь к добавлению нулей в конце чисел). Карацуба придумал гениальный алгебраический трюк. Как только вы вычислите первый и последний члены, ac и bd, вы сможете определить этот надоедливый средний член (ad + bc) с помощью всего одного дополнительного умножения вместо двух. Вам не нужно вычислять ad и bc по отдельности:
(ad + bc) = ((a + b) × (c + d)) — ac — bd,
Или, если использовать наши конкретные числа:
((1 × 4) + (2 × 3)) = ((1 + 2) × (3 + 4)) — 3 — 8 = 10.
Остановимся на мгновение, чтобы обратить внимание на странность в приведённом выше уравнении. Получается, что для быстрого умножения 12 × 34 нужно сложить 1 и 2 в числе 12, а также 3 и 4 в числе 34. Это вряд ли можно назвать очевидным. Неудивительно, что потребовалось столько времени, чтобы кто‑то до этого додумался. Однако в итоге это снижает нагрузку: поскольку мы уже вычислили ac и bd, в правой части остается только одно умножение, плюс несколько сложений и вычитаний.
Вернувшись к выражению 100(ac) + 10(ad + bc) + (bd), мы видим, что нам потребуется всего три умножения вместо четырёх. Мы вычисляем ac и bd обычным способом, а затем используем приём Карацубы, чтобы вычислить (ad + bc) с помощью одного умножения. Подставляя ac = 3, bd = 8 и (ad + bc) = 10, получаем ответ 408.
Мы сократили процедуру на одно умножение. Если это кажется незначительным, у Карацубы есть ещё одна идея. Допустим, мы умножаем более крупные числа: 1234 × 5678. Мы разбиваем их пополам, как и раньше: a = 12, b = 34, c = 56 и d = 78, и записываем задачу в виде (100a + b) × (100c + d) = 10 000(ac) + 100(ad + bc) + (bd).
Мы можем решить эту задачу с помощью трёх умножений. Однако в этих умножениях теперь участвуют двузначные числа. К счастью, мы знаем способ умножения двузначных чисел, при котором для каждого из них требуется всего по три однозначных умножений! В итоге задача, для решения которой традиционным способом потребовалось бы 16 однозначных умножений, теперь требует всего девяти. Благодаря рекурсивному применению приёма Карацубы к большим числам экономия растёт. Он делит входные числа пополам, затем делит эти половины пополам и так далее, применяя этот обмен «четыре на три» на всех уровнях. Время выполнения алгоритма составляет примерно O(
), что значительно быстрее, чем O(n²). Для сравнения: умножение пары тысячных чисел требует миллиона однозначных умножений при использовании школьного метода, но менее 57 000 — при использовании алгоритма Карацубы.
Эффективность этого алгоритма от 23-летнего математика заложена в повседневно используемое программное обеспечение. Из‑за дополнительных накладных расходов (сложение, управление повторяющимся разделением и объединением чисел и так далее) его преимущества по сравнению с алгоритмом начальной школы проявляются только тогда, когда числа становятся относительно большими. Например, Python — популярный язык программирования, который, как известно, хорошо обрабатывает целые числа любого размера. Если заглянуть в исходный код Python (поищите тут «Karatsuba»), то можно увидеть, что он основан на гибридном подходе. Для входных данных небольшого размера он использует школьную математику, но как только числа достигают примерно 630 десятичных разрядов, он переключается и применяет алгоритм Карацубы. Такое количество разрядов может показаться гигантским по меркам обывателя, но компьютеры работают с гораздо большими числами. (Техническое примечание: на большинстве современных машин Python хранит большие числа в системе счисления с основанием 
, поэтому указанный порог Карацубы в 70 цифр в системе счисления с основанием соответствует примерно 630 десятичным цифрам).
Алгоритм Карацубы дал старт продолжавшейся несколько десятилетий гонке за установлением предельной скорости умножения. Эта гонка завершилась в 2019 году, когда математики Дэвид Харви и Йорис ван дер Ховен описали чрезвычайно сложный алгоритм, превзошедший алгоритм Карацубы в разы больше, чем любой из предыдущих прорывов. Новый алгоритм работает за время O(n × log n). Здесь log обозначает логарифм n — функцию, которая растёт очень медленно. Это ошеломляющий результат. Функция n × log n лишь ненамного превышает само число n. Это означает, что вычисление произведения двух огромных чисел требует лишь немного больше времени, чем их сложение или даже простое считывание из памяти (для считывания всех n цифр числа требуется n вычислительных шагов).
Однако этот триумф сопровождается важной оговоркой. Точно так же, как алгоритм Карацубы превосходит школьный подход только при достаточно больших числах, алгоритм Харви‑ван дер Ховена не показывает преимущества, пока числа не становятся поистине «галактическими». В информатике «галактический алгоритм» — это формальный термин, обозначающий метод, который впечатляюще эффективен при работе с достаточно большими числами, но никогда не будет полезен на практике из‑за огромных размеров этих чисел.
Но даже с такой оговоркой это было переломным достижением. Оно закрепило за собой рекорд самого быстрого из известных методов умножения в теоретическом плане и могло бы открыть путь к алгоритмам, работающим за O(n × log n) шагов — не только в теории, но и на практике. Сегодня теоретики информатики полагают, что O(n × log n) — это максимально возможная скорость умножения, и формальное доказательство этого стало «святым Граалем» для этой узкой области математики. Но, как напоминает нам история, широкий консенсус — это не математическое доказательство. Гипотезы о пределе скорости умножения уже опровергались ранее.
Комментарии (40)
MaximArbuzov
19.08.2026 13:07Новый алгоритм работает за время O(n × log n).
Был же уже алгоритм FFT с таким же временем работы и похожий на него NTT.
Как будто в статье не хватает каких-то деталей.
malkovsky
19.08.2026 13:07У них битовая сложность не n log n. Если вы хотите применять классический nlogn FFT Кули-Тьюки для умножения чисел (вычислили на комплексных корнях -> перемножили -> проинтерполировали), то вместе с n будет расти и точность, требуемая от этих преобразований, уже n log n не получается.
Если на основе NTT, то есть видимо Shonhage-Strassen, та же проблема: для числа длины n нужно поле хотя бы из n элементов, мультипликативная группа, при вычислении на которой из цифр длины О(1) получаются уже значения длины О(log n)
MaximArbuzov
19.08.2026 13:07Спасибо. Мне кажется, что такого объяснения и не хватает для полноты статьи.
wataru
19.08.2026 13:07Там фактически O(n log n log log n). Ибо при сильно больших n числа не помещаются в машинное слово и там уже длинная арифметика внутри длинной арифметики вылезает.
CitizenOfDreams
19.08.2026 13:07А где и для чего практически используются числа с сотнями десятичных знаков?
petsernik
19.08.2026 13:07Не удивлюсь, если в шифровании, раньше вот два больших простых числа перемножали, попробовать по произведению угадать каких именно — сложная задача.
malkovsky
19.08.2026 13:07Да, криптография -- основной пользователь арифметики с большими числами, а это https, сертификаты, подписи и прочая аутентификация, криптовалюта, ...
vanxant
19.08.2026 13:07... поэтому на практике ассиметричное шифрование используется для получения одноразового сеансового ключа, а дальше фигачится какой-нибудь AES или Кузнечник (блочные симметричные шифры на базе перемешивания бит и подстановки байтов по таблице, без всяких там хитрых умножениев)
dronperminov
19.08.2026 13:07В то же время математики не знают, можно ли некоммутативно перемножить две матрицы 3х3 быстрее, чем за 23 произведения (алгоритм с 23 произведениями известен ещё с 1976). Казалось бы, всего-то 27 значений, не сотни, не тысячи, но ответа нет...
si_12345
19.08.2026 13:07Вспомогательные произведения
В алгоритме с 23 умножениями сначала вычисляются 23 вспомогательных произведения (обозначим их (P_1, \dots, P_{23})). Для примера вот первые два:
А также несколько вспомогательных произведений, участвующих в вычислении (c_{11}):
Вычисление результата
Результирующий элемент (c_{11}) (верхний левый угол матрицы (C = A \cdot B)) выражается через найденные произведения следующим образом:
Аналогично вычисляются и остальные 8 элементов матрицы.
dronperminov
19.08.2026 13:07Всё так, различных (неэквивалентных) некоммутативных алгоритмов с 23 умножениями огромное множество (как минимум более 70 тысяч). А вот возможен ли хотя бы один некоммутативный алгоритм с 22 умножениями пока никто не знает. При этом для случае 2x2 с 7 умножениями (алгоритм Штрассена) абсолютно все алгоритмы эквивалентны друг другу, то есть он такой один уникальный.
В коммутативном случае (когда в линейных комбинациях произведений участвуют элементы матриц A и B) известен алгоритм с 21 произведением, но такие алгоритмы нельзя использовать для рекурсивного блочного умножения, а потому исследователей интересуют именно некоммутативные алгоритмы.
Dr_Faksov
19.08.2026 13:07А я, на всякий случай, напомню, что курс школьной математики для разных континентов разный. Включая таки мелочи как раскрытие скобок, операции с дробями и решение систем линейных уравнений. Математика многогранна. И умножать можно вообще не зная таблицы умножения. Чисто на сложении.
piuzziconezz
19.08.2026 13:07Есть книга "Пробуждающаяся наука". Там описана эволюция математики от шумеров, древних египтян и далее. В том числе подробно как они выполняли арифметические действия. Тогда же еще не пришли к полностью позиционной системе счисления и вообще основание было не десятичное.
SensDj
19.08.2026 13:07процессор же просто сдвигает все биты первого числа несколько раз и складывает получающиеся числа если во втором числе включен нужный бит. Сплошные сдвиги и сложения, никаких умножений, причём сдвиги на 32 и на 64 позиции процессор делает одновременно (параллельно) на аппаратном уровне, и затем сложение тоже делает частично параллельно на аппаратном уровне, человек так на листочке не умеет,
при этом Дипсик настаивает что алгоритм Карацубы таки выгоден для больших чисел: "Оптимальный диапазон для Карацубы обычно лежит в области от 1000 до 10000 бит"
Fedorkov
19.08.2026 13:07причём сдвиги на 32 и на 64 позиции процессор делает одновременно (параллельно) на аппаратном уровне
Надо пояснить, что тут речь не о параллелизме в привычном программисту смысле. Речь об электрической цепи с большим ветвлением и с маленькой длиной - для того, чтобы напряжение быстрее распространялось по ней, и чтобы она могла работать на бóльших частотах.
tea_cher
19.08.2026 13:07Вот-вот, тоже сразу подумал, что умножение в двоичной арифметике - не то же самое, что и в десятичной.
Или вот в логарифмическом представлении вообще умножение чисел сводится к сложению их логарифмов:
32 × 64 = ?
log2 (32×64) = log2 (32) + log2 (64) = 5 + 6 = 11 = log2 (2^11) = log2 (2048)
32×64 = 2048
mayorovp
19.08.2026 13:07Параллельно складывать 64 числа не так просто как кажется, даже на аппаратном уровне. Первые процессоры совершенно точно умножали итеративно.
Насколько я знаю, первой оптимизацией аппаратного умножения стал перевод одного из множителей в систему счисления по основанию 4 с базой {-1, 0, 1, 2}. Для умножения в этой системе счисления достаточно только сдвигов и смены знака, но это несколько отличается от вашего описания.
Второй оптимизацией стало использование таблицы квадратов. И она работает настолько хорошо, что складывать кучу разрядов параллельно становится просто глупо. Только вот для 64х разрядов таблицу квадратов не составить, так что там совершенно точно используется комбинация разных методов.
Akon32
19.08.2026 13:07процессор же просто сдвигает все биты первого числа несколько раз и складывает получающиеся числа если во втором числе включен нужный бит. Сплошные сдвиги и сложения, никаких умножений
Это да, и как раз потому, что в одном умножении много сложений, операция умножения медленнее/сложнее для реализации, чем операция сложения. Но можно упростить описанным методом. Хотя, конечно, это больше имеет смысл для целых произвольной точности, либо когда числа не влезают в регистры.
chebo
19.08.2026 13:07А я вот слышал про китайский метод умножения
Китайский (или графический) метод умножения — это визуальный способ перемножения чисел с помощью линий. Он позволяет находить результат без использования классической таблицы умножения, заменяя её подсчетом точек пересечения
У него О(от чего?) получается?
ksbes
19.08.2026 13:07Там эн-квадрат получается. По построению - квадратная сетка же!. Просто сами операции проще - подсчёт вместо сложения и умножения (ну если не брать перенос десятков). Но само количество инкриментов -растёт квадратично.
wataru
19.08.2026 13:07Есть относительно простой и быстрый алгоритм за O(n log n log log n) (но это не точно). И работает он быстрее карацубы даже на совсем небольших числах. Так что это не галактический алгоритм.
Работает это через быстрое преобразование Фурье. Есть варианты и на целочисленном аналоге. Пребразуйте каждое число по отдельности, перемножте значения покомпонентно, преобразуйте назад, сделайте переносы.
И идея простая: представим каждое число в виде полинома - цифры будут коэффициентами.
Вот было у нас
, заменим 10 на x, получим 
Потом можно перемножить 2 полинома и подставить x=10. Подстановка очень проста - просто берем коэффициенты и записываем их в виде цифр. Только некоторые могут быть больше 10, и надо сделать переносы с меньших разрядов.
А произведение полиномов это известная задача, решающаяся FFT. Потому что прямое преобразование - это вычисление значений полинома в точках-корнях-из-единицы. Обратное преобразование по значениям в точках восстанавливает полином. Так что произведение полиномов просто делается в пространстве спектра - ведь значения в точках тупо перемножаются покомпонентно.
На практике, пока количество цифр поменьше чем 2^64/81 можно игнорировать log log n в оценке сложности, потому что числа в вычислениях помещаются в процессорное слово.
LaRN
19.08.2026 13:07А почему сложность не 9*n умножений + n сложений? Ведь уникальных цифр 9, дальше только сдвиг на разряд и слодение. Можно закешировать все 9 вариантов и подставлять когда нужно.
wataru
19.08.2026 13:07n сложений и дают этот самый медленный O(n^2). Ведь для сложения чисел из n цифр надо O(n) операций. Ваши кеширования особо не помогают в этом наивном умножении столбиком.
LaRN
19.08.2026 13:07А разве n^2 это не от того, что каждый из n разрядов числа A умножается на каждый из n разрядов числа B? И сложения промежуточных результатов тут как будто вообще не учитываются, а если их учитывать, то было бы n^2 + n и n исключается из оценки, тк он имеет не самую максимальную степень.
ksbes
19.08.2026 13:07Сложность всех сложений тоже N^2. Т.е. в умножении столбиков два эн-квадрата: от перемножения и от последующего (поразрядного) сложения. Убрав первое вы оставляете второе. Да будет быстрее - но рост по прежнему квадратичный.
ksbes
Ну вообще-то есть алгоритм О(1). Правда его бычно для малых чисел используют, но в теории ничто не мешает его использовать и для любого конечного числа чисел. Таблица умножения.
Тут явно не мешает уточнение формулировок. Всё же речь идёт о манипуляциях с цифрами в позиционных системах исчислений.
Для сравнения - умножению и делению чисел записанных римскими цифрами раньше в университетах именитые учёные (буквально - я не помню, вроде Фибоначи тот же) учились в течении лет. А в логарифмическом масштабе (оно же - экпоненциальная или “научная” нотация) умножение и деление - это одно действие сложения.
Так что чётче надо задачу формулировать!
OlegMax
Научная нотация - это совсем другое
Так любую NP-полную задачу можно свести к O(1). Достаточно простого советского справочника с ответами
ksbes
Ну не совсем-совсем. Потому и в кавычках. Намёк на float - в котором всё и считают. Во многом потому что перемножение флоатов быстрее целых (aka с фиксированной точкой).
Дело не в этом. А в том, что просто “задача перемножения чисел” в математике вообще как таковая не не то что не решается, а не ставится. Просто за ненадобностью (результат просто есть по определению операции - фактически та же таблица). Ставится задача поиска, например, десятичной записи произведения, зная десятичную запись множителей. Но это - значительно более узкая задача.
OlegMax
Откуда вы это взяли?
leshabirukov
Полагаю, логика @ksbes в том, что для перемножения fp32 по сравнению с int32 вам надо перемножать лишь мантиссы (со знаком), а экспоненты надо лишь сложить, что и даёт экономию, ведь сложение алгоритмически проще.
Fedorkov
Перемножение реализуется аппаратно, то есть это всё одна инструкция (в современных процессорах - от 0.5 до 3 тактов).
IgorPie
удачи вам с денормализованными числами
mivlad
Числа мельче PHP_FLOAT_MIN ненужны!
mayorovp
А они что, перемножаются каким-то особенным образом?
piuzziconezz
"перемножение флоатов быстрее целых"
Но это не точно
ImagineTables
Сдаётся мне, если число растёт, а разрядность (размер машинного слова) — нет (это очень реалистичное допущение), lookup перестаёт быть
O(1)(индекс надо делить), а с ним и алгоритм.bt2901
Забавно, что вы называете здесь именно Фибоначчи: именно Леонардо Пизанский (его настоящее имя) привёз в Италию арабские цифры вместо римских. Написал об этом несколько книг-учебников, которые знакомили простых торговцев с арифметикой в десятичной системе счисления.
Леонардо был в своём проекте настолько успешен, что сейчас про эту его деятельность никто и не помнит и не знает :)