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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Сети финансовой поддержки: как люди выручают друг друга в условиях кризиса Сети финансовой поддержки: как люди выручают друг друга в условиях кризиса

Как работает неформальная экономика во времена нестабильности

Forbes
«Игры разумов»: страсти вокруг словаря «Игры разумов»: страсти вокруг словаря

Когда вы последний раз пользовались бумажным словарем

Psychologies
В Испании нашли древнейшее на Пиренейском полуострове изделие из зуба бегемота В Испании нашли древнейшее на Пиренейском полуострове изделие из зуба бегемота

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

N+1
Очень при­ят­но, Джордж Очень при­ят­но, Джордж

Пят­на­дцать ми­нут в ком­па­нии Джор­джа Клу­ни — и все, вы обез­ору­же­ны

Glamour
Используй ложку и телефон: 20 способов доставить себе удовольствие Используй ложку и телефон: 20 способов доставить себе удовольствие

Двадцать разных способов мастурбации на любой вкус и цвет

Cosmopolitan
Смогут ли российские сенаторы вылечить бизнес? Смогут ли российские сенаторы вылечить бизнес?

В Совете Федерации зародилась идея создать Центр санации бизнеса (ЦСБ)

Forbes
Никаких «Фокусов» Никаких «Фокусов»

Ford уходит из РФ со всей легковой линейкой. Чем это чревато для автовладельцев?

АвтоМир
Стражи Галактики Стражи Галактики

Александр Фридман дал Tatler Teen свое первое в жизни интервью

Tatler
«Москвич-2140». Машина времени «Москвич-2140». Машина времени

Каково в Москве ездить на советском олдтаймере

АвтоМир
Все, что нам известно о фильме «Бонд 25» Все, что нам известно о фильме «Бонд 25»

Юбилейная картина начинает складываться по мере поступления новых деталей

GQ
Эволюция капитализма Эволюция капитализма

Могут ли появиться новые миллиардеры в России

Forbes
Обида и гнев на мать: стоит ли ей о них говорить? Обида и гнев на мать: стоит ли ей о них говорить?

Станет ли нам легче, если мы расскажем матери о своих чувствах

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

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

Forbes
Коньяк по праздникам. Что происходит с мировым потреблением дорогого алкоголя Коньяк по праздникам. Что происходит с мировым потреблением дорогого алкоголя

Более 80% женщин и 66% мужчин в России употребляют алкоголь из-за традиции

Forbes
Катя возвращается — и ее спасли вы! Катя возвращается — и ее спасли вы!

Такие пациенты, как Катя Фролова, встречаются хорошо если раз в несколько лет

Cosmopolitan
7 признаков, что вы не готовы дружить с бывшим 7 признаков, что вы не готовы дружить с бывшим

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

Psychologies
Электрика вызывали? Электрика вызывали?

Мотоциклетные марки сдаются на милость электромобильности одна быстрее другой

Robb Report
Медитация — секретное оружие против мигрени Медитация — секретное оружие против мигрени

Головная боль может быть разных типов, и самый загадочный из них — мигрень

Psychologies
В чем поехать за город на выходные В чем поехать за город на выходные

Оказывается, спортивный костюм – не единственный вариант для поездки на природу

GQ
Из девочки в мальчика и другие бьюти-эксперименты звездных детей Из девочки в мальчика и другие бьюти-эксперименты звездных детей

Дети знаменитостей также меняют цвет волос, делают стрижки и даже красятся

Cosmopolitan

Мультсериал «Любовь,смерть и роботы» — с сексом, котиками и расчлененкой

Esquire
«Сейчас я счастлива!» «Сейчас я счастлива!»

Телеведущая и просто красивая женщина Арина Шарапова

OK!
Госбанкам могут запретить покупать частных конкурентов. Что это значит? Госбанкам могут запретить покупать частных конкурентов. Что это значит?

Госбанкам могут запретить скупать своих частных конкурентов

Forbes
Рейтинг индукционных варочных панелей 2019: как выбрать лучшую модель Рейтинг индукционных варочных панелей 2019: как выбрать лучшую модель

Как подобрать подходящий вариант варочной панели для своей кухни

CHIP
Цукерберг и другие: самые влиятельные бизнесмены мира по версии Time Цукерберг и другие: самые влиятельные бизнесмены мира по версии Time

Американский журнал Time попытался ответить на вопрос «Кто пишет историю?»

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

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

Forbes
Что нам мешает проявлять себя? Что нам мешает проявлять себя?

Как распрощаться с ограничивающими установками?

Psychologies
Porsche Cayenne Coupe Porsche Cayenne Coupe

Дебют кроссовера с покатой крышей как будто напрашивался с самого начала

Quattroruote
Домашний дефибриллятор и другие действительно полезные гаджеты для здоровья Домашний дефибриллятор и другие действительно полезные гаджеты для здоровья

Подборка полезных медицинских приборов, которые спасают жизни

Популярная механика
6 неожиданных вещей, потрогав которые, нужно срочно мыть руки 6 неожиданных вещей, потрогав которые, нужно срочно мыть руки

На этих предметах бактерий больше, чем под бочком унитаза

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