- 28,291
- 46
- 8 Ноя 2022
Колмогоров считал этот предел незыблемым. Студент разрушил его меньше чем за неделю.
<div class="articl-text-cover" style="position:relative;width:100%;max-width:800px;margin-left:auto;margin-right:auto;aspect-ratio:1200/676;margin-bottom:2rem;overflow:hidden">
Умножение кажется одной из самых простых математических операций, пока числа помещаются в школьную тетрадь. Для двузначных и трёхзначных примеров достаточно привычного алгоритма в столбик. Но когда компьютеру приходится перемножать числа длиной в тысячи, миллионы или миллиарды цифр, каждая лишняя операция превращается в серьёзную нагрузку. От скорости подобных вычислений зависят шифрование , обработка звука, робототехника, искусственный интеллект и многие другие задачи. При этом математики до сих пор не доказали, какой алгоритм умножения нельзя превзойти в принципе.
Школьный способ устроен просто. Каждую цифру одного числа нужно по очереди умножить на каждую цифру другого, а затем сложить промежуточные результаты. Для двух двузначных чисел потребуется четыре однозначных умножения, для трёхзначных — уже девять. Если длина каждого множителя равна n цифрам, число основных операций растёт примерно как n².
Компьютерные специалисты сравнивают алгоритмы не по времени в секундах, поскольку результат зависит от процессора, памяти и других особенностей оборудования. Вместо этого считают, как увеличивается объём работы при росте входных данных. Для описания используют нотацию O-большое. Школьный алгоритм имеет сложность O(n²). Если числа удлинить вдвое, вычислений потребуется примерно в четыре раза больше. При увеличении длины в тысячу раз нагрузка вырастет примерно в миллион раз.
На протяжении столетий подобный рост считался неизбежным. В 1960 году советский математик Андрей Колмогоров сформулировал предположение, что умножить большие числа быстрее O(n²) невозможно. Гипотезу он озвучил на семинаре в Московском государственном университете.
Опровергнуть её удалось всего через неделю. 23-летний студент Анатолий Карацуба нашёл способ сократить число умножений, заменив часть из них гораздо более дешёвыми сложениями и вычитаниями. Колмогоров сам оформил доказательство и отправил работу в «Доклады Академии наук СССР», указав Карацубу первым автором. Молодой математик узнал о публикации, когда получил по почте оттиски статьи.
Суть открытия лучше всего видна на небольшом примере. Пусть нужно вычислить 12 × 34. Число 12 можно записать как 10a + b, где a = 1, b = 2. Аналогично 34 превращается в 10c + d, где c = 3, d = 4.
После раскрытия скобок получается выражение:
100ac + 10(ad + bc) + bd.
Обычный способ требует отдельно вычислить четыре произведения: ac, ad, bc и bd. В данном случае получатся 3, 4, 6 и 8. Карацуба заметил, что среднюю часть ad + bc необязательно считать двумя отдельными умножениями.
Её можно получить по формуле:
ad + bc = (a + b)(c + d) − ac − bd.
Для чисел 12 и 34 сначала складывают цифры внутри каждого множителя: 1 + 2 = 3 и 3 + 4 = 7. Затем перемножают результаты и вычитают уже известные значения ac и bd:
3 × 7 − 3 − 8 = 10.
Вместо четырёх умножений остаются три: ac, bd и (a + b)(c + d). Дополнительные сложения и вычитания обходятся дешевле, особенно при работе с очень длинными числами. После подстановки получается 300 + 100 + 8 = 408.
Для двузначного примера выигрыш кажется небольшим, однако метод допускает многократное повторение. При умножении 1234 на 5678 оба числа делят пополам: a = 12, b = 34, c = 56, d = 78. Выражение принимает вид:
10 000ac + 100(ad + bc) + bd.
На верхнем уровне снова нужны только три умножения вместо четырёх. Каждое из них связано уже с двузначными числами, но к ним можно применить тот же приём. В итоге школьный алгоритм потребовал бы 16 однозначных умножений, а схема Карацубы обходится девятью.
Для очень больших чисел разбиение продолжают рекурсивно. Сначала исходные множители делят пополам, затем каждую половину снова разделяют, пока задача не сводится к простым операциям с короткими фрагментами. На каждом уровне четыре умножения заменяются тремя. Общая сложность снижается примерно до O(n^1,585).
Разница быстро растёт вместе с длиной входных данных. Перемножение двух тысячезначных чисел школьным методом требует около миллиона однозначных умножений. Алгоритму Карацубы нужно менее 57 тысяч. Экономия превышает порядок, хотя итоговая схема добавляет расходы на разбиение чисел, промежуточные суммы и последующую сборку результата.
Поэтому современные программы обычно сочетают несколько способов. Для коротких чисел проще применять обычное умножение, поскольку служебные операции внутри более сложного алгоритма съедают весь выигрыш. После определённого порога программа переключается на метод Карацубы.
Подобную гибридную схему использует Python. Язык программирования умеет работать с целыми числами практически неограниченной длины. Для сравнительно небольших значений интерпретатор применяет школьный алгоритм, а примерно после 630 десятичных цифр переходит к алгоритму Карацубы. Внутри Python большие числа хранятся не в привычной десятичной системе, а блоками по 30 двоичных разрядов, поэтому внутренний порог в 70 таких блоков примерно соответствует 630 цифрам в десятичной записи.
Открытие Карацубы запустило многолетнюю гонку за более быстрым умножением. Математики последовательно снижали число необходимых операций, разрабатывая всё более сложные методы. Наиболее заметный результат появился в 2019 году, когда Дэвид Харви и Йорис ван дер Хувен описали алгоритм со сложностью O(n log n).
Логарифм растёт очень медленно, поэтому n log n лишь немного больше самого n. Для сравнения, чтобы просто прочитать число длиной n цифр, компьютеру уже требуется порядка n шагов. Следовательно, алгоритм Харви и ван дер Хувена приближает умножение двух огромных чисел к теоретическому минимуму: операция занимает лишь немного больше времени, чем чтение множителей или их сложение.
Практическая польза пока ограничена. Новый способ начинает выигрывать только на числах невероятной длины, которые почти не встречаются в реальных вычислениях. В информатике подобные методы называют галактическими алгоритмами. Название применяют к схемам с превосходной асимптотикой, но настолько высоким порогом эффективности, что обычные компьютеры практически никогда до него не добираются.
Несмотря на это ограничение, работа 2019 года установила новый теоретический рекорд. Она показала, что умножение можно выполнять за O(n log n) шагов, по крайней мере для достаточно больших чисел. Теперь многие специалисты считают именно такую скорость предельной.
Доказательства пока нет. Математики не установили нижнюю границу , которая запрещала бы существование ещё более быстрого метода. История уже показывала, насколько опасно принимать общепринятое мнение за окончательный ответ. В 1960 году предел O(n²) казался настолько естественным, что его готовились доказывать, однако студент разрушил гипотезу за несколько дней.
Сегодня главный вопрос звучит иначе: действительно ли O(n log n) описывает минимально возможную сложность умножения, или где-то скрывается ещё один неожиданный приём. Пока математики умеют перемножать огромные числа почти так же быстро, как читать их, но всё ещё не знают, можно ли сделать следующий шаг.
<div class="articl-text-cover" style="position:relative;width:100%;max-width:800px;margin-left:auto;margin-right:auto;aspect-ratio:1200/676;margin-bottom:2rem;overflow:hidden">
Умножение кажется одной из самых простых математических операций, пока числа помещаются в школьную тетрадь. Для двузначных и трёхзначных примеров достаточно привычного алгоритма в столбик. Но когда компьютеру приходится перемножать числа длиной в тысячи, миллионы или миллиарды цифр, каждая лишняя операция превращается в серьёзную нагрузку. От скорости подобных вычислений зависят шифрование , обработка звука, робототехника, искусственный интеллект и многие другие задачи. При этом математики до сих пор не доказали, какой алгоритм умножения нельзя превзойти в принципе.
Школьный способ устроен просто. Каждую цифру одного числа нужно по очереди умножить на каждую цифру другого, а затем сложить промежуточные результаты. Для двух двузначных чисел потребуется четыре однозначных умножения, для трёхзначных — уже девять. Если длина каждого множителя равна n цифрам, число основных операций растёт примерно как n².
Компьютерные специалисты сравнивают алгоритмы не по времени в секундах, поскольку результат зависит от процессора, памяти и других особенностей оборудования. Вместо этого считают, как увеличивается объём работы при росте входных данных. Для описания используют нотацию O-большое. Школьный алгоритм имеет сложность O(n²). Если числа удлинить вдвое, вычислений потребуется примерно в четыре раза больше. При увеличении длины в тысячу раз нагрузка вырастет примерно в миллион раз.
На протяжении столетий подобный рост считался неизбежным. В 1960 году советский математик Андрей Колмогоров сформулировал предположение, что умножить большие числа быстрее O(n²) невозможно. Гипотезу он озвучил на семинаре в Московском государственном университете.
Опровергнуть её удалось всего через неделю. 23-летний студент Анатолий Карацуба нашёл способ сократить число умножений, заменив часть из них гораздо более дешёвыми сложениями и вычитаниями. Колмогоров сам оформил доказательство и отправил работу в «Доклады Академии наук СССР», указав Карацубу первым автором. Молодой математик узнал о публикации, когда получил по почте оттиски статьи.
Суть открытия лучше всего видна на небольшом примере. Пусть нужно вычислить 12 × 34. Число 12 можно записать как 10a + b, где a = 1, b = 2. Аналогично 34 превращается в 10c + d, где c = 3, d = 4.
После раскрытия скобок получается выражение:
100ac + 10(ad + bc) + bd.
Обычный способ требует отдельно вычислить четыре произведения: ac, ad, bc и bd. В данном случае получатся 3, 4, 6 и 8. Карацуба заметил, что среднюю часть ad + bc необязательно считать двумя отдельными умножениями.
Её можно получить по формуле:
ad + bc = (a + b)(c + d) − ac − bd.
Для чисел 12 и 34 сначала складывают цифры внутри каждого множителя: 1 + 2 = 3 и 3 + 4 = 7. Затем перемножают результаты и вычитают уже известные значения ac и bd:
3 × 7 − 3 − 8 = 10.
Вместо четырёх умножений остаются три: ac, bd и (a + b)(c + d). Дополнительные сложения и вычитания обходятся дешевле, особенно при работе с очень длинными числами. После подстановки получается 300 + 100 + 8 = 408.
Для двузначного примера выигрыш кажется небольшим, однако метод допускает многократное повторение. При умножении 1234 на 5678 оба числа делят пополам: a = 12, b = 34, c = 56, d = 78. Выражение принимает вид:
10 000ac + 100(ad + bc) + bd.
На верхнем уровне снова нужны только три умножения вместо четырёх. Каждое из них связано уже с двузначными числами, но к ним можно применить тот же приём. В итоге школьный алгоритм потребовал бы 16 однозначных умножений, а схема Карацубы обходится девятью.
Для очень больших чисел разбиение продолжают рекурсивно. Сначала исходные множители делят пополам, затем каждую половину снова разделяют, пока задача не сводится к простым операциям с короткими фрагментами. На каждом уровне четыре умножения заменяются тремя. Общая сложность снижается примерно до O(n^1,585).
Разница быстро растёт вместе с длиной входных данных. Перемножение двух тысячезначных чисел школьным методом требует около миллиона однозначных умножений. Алгоритму Карацубы нужно менее 57 тысяч. Экономия превышает порядок, хотя итоговая схема добавляет расходы на разбиение чисел, промежуточные суммы и последующую сборку результата.
Поэтому современные программы обычно сочетают несколько способов. Для коротких чисел проще применять обычное умножение, поскольку служебные операции внутри более сложного алгоритма съедают весь выигрыш. После определённого порога программа переключается на метод Карацубы.
Подобную гибридную схему использует Python. Язык программирования умеет работать с целыми числами практически неограниченной длины. Для сравнительно небольших значений интерпретатор применяет школьный алгоритм, а примерно после 630 десятичных цифр переходит к алгоритму Карацубы. Внутри Python большие числа хранятся не в привычной десятичной системе, а блоками по 30 двоичных разрядов, поэтому внутренний порог в 70 таких блоков примерно соответствует 630 цифрам в десятичной записи.
Открытие Карацубы запустило многолетнюю гонку за более быстрым умножением. Математики последовательно снижали число необходимых операций, разрабатывая всё более сложные методы. Наиболее заметный результат появился в 2019 году, когда Дэвид Харви и Йорис ван дер Хувен описали алгоритм со сложностью O(n log n).
Логарифм растёт очень медленно, поэтому n log n лишь немного больше самого n. Для сравнения, чтобы просто прочитать число длиной n цифр, компьютеру уже требуется порядка n шагов. Следовательно, алгоритм Харви и ван дер Хувена приближает умножение двух огромных чисел к теоретическому минимуму: операция занимает лишь немного больше времени, чем чтение множителей или их сложение.
Практическая польза пока ограничена. Новый способ начинает выигрывать только на числах невероятной длины, которые почти не встречаются в реальных вычислениях. В информатике подобные методы называют галактическими алгоритмами. Название применяют к схемам с превосходной асимптотикой, но настолько высоким порогом эффективности, что обычные компьютеры практически никогда до него не добираются.
Несмотря на это ограничение, работа 2019 года установила новый теоретический рекорд. Она показала, что умножение можно выполнять за O(n log n) шагов, по крайней мере для достаточно больших чисел. Теперь многие специалисты считают именно такую скорость предельной.
Доказательства пока нет. Математики не установили нижнюю границу , которая запрещала бы существование ещё более быстрого метода. История уже показывала, насколько опасно принимать общепринятое мнение за окончательный ответ. В 1960 году предел O(n²) казался настолько естественным, что его готовились доказывать, однако студент разрушил гипотезу за несколько дней.
Сегодня главный вопрос звучит иначе: действительно ли O(n log n) описывает минимально возможную сложность умножения, или где-то скрывается ещё один неожиданный приём. Пока математики умеют перемножать огромные числа почти так же быстро, как читать их, но всё ещё не знают, можно ли сделать следующий шаг.
- Источник новости
- www.securitylab.ru
