Математик нашел максимально эффективный алгоритм перемножения больших чисел

ForbesНаука

Лучше, чем в столбик: новый способ перемножать большие числа

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

Алексей Алексенко

gettyimages-1050544130.png__1555075270__54248.png
Фото Getty Images

Дэвид Харви, сотрудник университета Нового Южного Уэлльса в Сиднее, и его французский коллега Йорис Ван дер Хэвен, решили задачу, поставленную математиками еще полвека назад. Речь идет о доказательстве гипотезы Шёнхаге-Штрассена. Согласно этой гипотезе, возможен такой алгоритм перемножения целых N-значных чисел, что число шагов алгоритма с возрастанием числа не будет увеличиваться быстрее, чем N * logN.

Простейший алгоритм умножения знаком всем с начальной школы: это так называемое «умножение в столбик». Чтобы перемножить два числа, надо по существу умножить каждую цифру первого числа на каждую цифру второго, а потом еще выполнить несколько сложений и расположить результаты в правильном порядке. Ключевой этап — перемножение цифр: если наши числа трехзначные, придется обратиться к таблице умножения 9 раз, а если пятизначные — 25 раз. В общем случае число таких процедур увеличивается пропорционально числу знаков в перемножаемых числах, возведенному в квадрат. И если эти числа достаточно велики, то количество шагов алгоритма становится поистине огромным.

Natalie Choi / UNSW

В 1950-х гг. Советский математик Анатолий Карацуба обнаружил способ уменьшить сложность алгоритма умножения. В его алгоритме число шагов увеличивается не быстрее, чем N1,58 — это существенно меньше, чем N

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Не могу дышать и двигаться: что такое сонный паралич и как от него избавиться Не могу дышать и двигаться: что такое сонный паралич и как от него избавиться

Что на самом деле чувствует человек в состоянии сонного паралича?

Forbes
Китайские соцсети ополчились на Leica из-за новой рекламы Китайские соцсети ополчились на Leica из-за новой рекламы

В Китае сочли видео оскорбительным

Forbes
Тела при нагревании расширяются, но не всегда Тела при нагревании расширяются, но не всегда

Что сдерживает тепловое расширение в уникальном сплаве из четырех элементов

ТехИнсайдер
Теперь без России: какую экономику получит новый президент Украины Теперь без России: какую экономику получит новый президент Украины

В следующий президентский срок Украину будут ожидать серьезные вызовы

Forbes
«Если это не любовь, то что?»: созависимость в отношениях «Если это не любовь, то что?»: созависимость в отношениях

Почему мы выбираем холодных партнеров? Как отличить любовь от созависимости?

Psychologies
Почему шутки, рассказанные мужчинами, кажутся нам более смешными Почему шутки, рассказанные мужчинами, кажутся нам более смешными

Мужчины-шутники поднимают свой статус в коллективе, а женщины только вредят себе

Psychologies
Эд Стоппард: «Одна из главных причин смотреть «Падение ордена» — моя солидная борода!» Эд Стоппард: «Одна из главных причин смотреть «Падение ордена» — моя солидная борода!»

Во всю мощь разворачивается второй сезон «Падения ордена»

Maxim
Почему в XXI веке, когда люди летают в космос, соборы все еще горят (и что ждет Нотр-Дам теперь) Почему в XXI веке, когда люди летают в космос, соборы все еще горят (и что ждет Нотр-Дам теперь)

Почему полеты в космос не помогают человечеству тушить пылающие памятники

Esquire
Стоит ли возвращаться к своей бывшей (если очень хочется) Стоит ли возвращаться к своей бывшей (если очень хочется)

Нормально ли возвращаться к своей бывшей?

Playboy
Кто такой Король Ночи? Почему Джон Сноу ничего не знает? Разговорник для тех, кто никогда в жизни не смотрел Кто такой Король Ночи? Почему Джон Сноу ничего не знает? Разговорник для тех, кто никогда в жизни не смотрел

Разговорник для тех, кто ничего не знает про «Игру престолов»

Esquire
Неожиданный поворот: 10 фактов из истории моды, которые тебя удивят Неожиданный поворот: 10 фактов из истории моды, которые тебя удивят

Арина Яганова перечисляет самые невообразимые факты из истории моды

Cosmopolitan
10 привычек людей, которые все успевают 10 привычек людей, которые все успевают

Суматошный мир заставляет нас постоянно увеличивать скорость

Psychologies
В Центробанке сменился лидер по доходам В Центробанке сменился лидер по доходам

Самый высокий доход среди руководителей ЦБ получил глава департамента

Forbes
«Седых волос у него прибавилось». Борис Титов навестил Майкла Калви в СИЗО «Седых волос у него прибавилось». Борис Титов навестил Майкла Калви в СИЗО

Калви провел в СИЗО уже почти два месяца

Forbes
Изображая голод Изображая голод

Имитаторы эффектов ограничения калорий – что это за вещества

Популярная механика
Дарья Лисиченко: «мне ничего не стоило привить детям привычки правильного питания» Дарья Лисиченко: «мне ничего не стоило привить детям привычки правильного питания»

Чему будут учить на мастер-классах «Нескучный ЗОЖ»

Grazia
Специалист по конфликтам. В Baring Vostok пришел антикризисный менеджер из А1 Специалист по конфликтам. В Baring Vostok пришел антикризисный менеджер из А1

Артем Артюхов из A1 пришел в Baring Vostok, чтобы разрешить конфликт

Forbes
Мунк и творчества Мунк и творчества

Знакомимся с создателем «Крика» – норвежским художником Эдвардом Мунком

Maxim
Все, что нужно узнать об «Игре престолов» прежде, чем выйдут его финальные эпизоды Все, что нужно узнать об «Игре престолов» прежде, чем выйдут его финальные эпизоды

Осторожно: в этой статье спойлеры и куча информации о долгожданном сериале

Maxim
Дьявол в деталях Дьявол в деталях

Оскар Потоков о смысле бизнеса, любви к семье и страсти к автомобилям

Robb Report
Незримый мост: как пересечь Мессинский пролив Незримый мост: как пересечь Мессинский пролив

Со времён Гомера морской путь с Апеннинского полуострова на Сицилию не изменился

4x4 Club
Космический корабль Илона Маска провалил испытания Космический корабль Илона Маска провалил испытания

Запуск астронавтов к МКС на первом частном корабле может быть отложен

Forbes
Миллиардер и революционер: новая жизнь главного инвестора Кремниевой долины Марка Андриссена Миллиардер и революционер: новая жизнь главного инвестора Кремниевой долины Марка Андриссена

Марк Андриссен однажды уже перевернул устои венчурного рынка

Forbes
Солнечный друг Солнечный друг

Насколько важен витамин D для нашего здоровья и красоты

Grazia
Рублевка на Лазурном берегу: виллы и поместья российских миллиардеров во Франции Рублевка на Лазурном берегу: виллы и поместья российских миллиардеров во Франции

У участников российского списка Forbes много недвижимости во Франции

Forbes
Цифровые перебежчики: почему топ-менеджеры крупных финансовых корпораций уходят в криптопроекты Цифровые перебежчики: почему топ-менеджеры крупных финансовых корпораций уходят в криптопроекты

Истории топ-менеджеров, которые решили уйти в рискованный мир биткоина и эфира

Forbes
Первая леди Украины: что мы знаем о Елене Зеленской Первая леди Украины: что мы знаем о Елене Зеленской

Будет ли Елена Зеленская принимать активное участие в политической карьере мужа

Forbes
Блогер в законе. Почему Ким Кардашьян решила стать адвокатом Блогер в законе. Почему Ким Кардашьян решила стать адвокатом

При участии 38-летней звезды Instagram были освобождены двое заключенных из США

Forbes
О театре со вкусом О театре со вкусом

Торжественный обед журнала ОK! с участием номинантов премии «Золотая маска»

OK!
Как цвета влияют на нашу психику Как цвета влияют на нашу психику

Какое влияние цвета оказывают на наше эмоциональное состояние

Vogue
Открыть в приложении