Умножение ниже n log n: улучшение, которое не видно на ноутбуке

Какой вопрос решают

Сколько элементарных битовых шагов нужно, чтобы точно перемножить два n-битовых числа? Важно учитывать не только арифметику, но и перемещение данных по лентам вычислительной машины.

Что заявляет рукопись

Заявлен единый детерминированный алгоритм точного умножения со сложностью O(n·(lg n)^(1−κ)), где κ=2⁻¹⁸², на фиксированной многоленточной машине Тьюринга.

Почему выбрано: Позволяет показать ценность теоретического изменения класса роста без обещаний практического ускорения.

До и после

Harvey и van der Hoeven опубликовали O(n log n) в Annals of Mathematics в 2021 году, также в многоленточной битовой модели. Новый заявленный вклад — уменьшение степени логарифма. Независимая прежняя работа не подтверждает новое уменьшение.

Внешние первичные источники: Harvey, van der Hoeven — Integer multiplication in time O(n log n).

Точное утверждение и условия

109-01, теорема 1, PDF с. 3: фиксированное конечное число одномерных лент и конечный алфавит; обычное двоичное представление, точный результат с дополнением до 2n бит; худшее время O(n(lg n)^(1−2⁻¹⁸²)). Это не модель вещественной арифметики с бесплатной перестановкой памяти.

Источник: указанные теоремы в локальных PDF ниже. Формулировка пересказана, но ключевые кванторы, модель и оговорки сохранены.

Три уровня объяснения

Следующие аналогии и объяснения — наша интерпретация, не дополнительные теоремы.

НеспециалистуДаже крошечное положительное уменьшение показателя когда-нибудь выигрывает у прежней функции роста. Но слово «когда-нибудь» может означать размеры, не имеющие физического смысла.

РазработчикуУскорить FFT-арифметику недостаточно, если перестановки массивов всё ещё стоят n log n в принятой модели. Надо ускорять и вычисления, и движение данных.

Подготовленному читателюВведение сочетает гауссово ресэмплирование, пакетные линейные преобразования, обмен адресованными блоками и экономию ранга в синтетических слоях бабочек. Контроль точности должен позволить окончательное округление и перенос разрядов без ошибки.

Загрузка локального эксперимента…

Архитектура доказательства

Пересказ вводного обзора, а не построчная проверка доказательства.

Свести точное умножение к семейству преобразований с управляемой фиксированной точностью.

Согласовать экономию в линейных сетях и движении блоков на фиксированном числе лент.

Закрыть рекуррентную оценку и восстановить точное целое произведение. Константа κ фиксируется очень консервативно.

Что известно о проверке

Для группы 109 scope note не найден. Соседние формализации матричного умножения или других алгоритмов не переносят проверку на эту теорему.

Отдельного scope note для этой семьи в переданном контексте нет.

Главные риски аудита. Равномерность единой машины, стоимость адресации и движения, точность промежуточных преобразований. Нужна независимая проверка всей цепочки, а не только арифметической экономии.

Наличие PDF, извлечение текста, успешный маленький эксперимент и внешний результат-предшественник — разные виды свидетельств. Ни один из них здесь не отмечен как независимое подтверждение всей новой теоремы.

Практика: наш вывод, не обещание автора

Немедленная замена GMP или другой библиотеки не обоснована. Возможный исследовательский интерес — отдельные леммы о перемещении данных и линейных сетях, если удастся извлечь практически значимые варианты.

Ограничения переноса

Если отбросить неизвестные константы и порог, относительный множитель выигрыша равен (log₂n)^κ. При n=2⁶⁴ бит его отклонение от 1 порядка 10⁻⁵⁴. Это вычисление формы оценки, не прогноз времени и не бенчмарк.

Исходники и реальный охват чтения

Номера страниц относятся к физическим страницам PDF, начиная с 1. Ссылки на GitHub не закреплены на текущем commit; воспроизводимый источник — локальный путь и SHA-256.

109-01 · Integer multiplication below n log n

Реальный охват: Просмотрены PDF с. 1–4: Модель, теорема и архитектура; 73-страничное доказательство не прочитано полностью. Полный объём PDF: 73 с.

PDF (в комплекте)Онлайн-версия (может обновиться)

math_sources/math_research_07_of_08/preprints/Integer-multiplication-below-n-log-n-September-23-2026/paper.pdfSHA-256: 834f644c3ce67932b9f7357d3615fb8fea4a7ff198d90e4f6883a15ba9df7129

Каталог: context/CONTENTS.md, строка 2702. Путь и хеш относятся к загруженной версии.

Семейство в CONTENTS.md, строка 2695. Структурированные заметки · Журнал внешней сверки.