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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Женщины для женщин: как Наталья Водянова и Серена Уильямс инвестируют в фемтех Женщины для женщин: как Наталья Водянова и Серена Уильямс инвестируют в фемтех

Стартапы в области женского здоровья, в которые инвестируют знаменитые женщины

Forbes
Правильные пищевые привычки с детства: что важно знать? Правильные пищевые привычки с детства: что важно знать?

Одна из главных задач – научить подрастающего малыша правильно питаться

9 месяцев
Молекулы, необходимые для жизни, найдены в образцах астероида Бенну Молекулы, необходимые для жизни, найдены в образцах астероида Бенну

В породе, доставленной с астероида Бенну, обнаружены 14 из 20 аминокислот

ТехИнсайдер
Метеозависимость Метеозависимость

Метеозависимость существует, и причины ее довольно разнообразны

Maxim
Соскочить с крючка вины: как распознать манипуляцию с первой секунды Соскочить с крючка вины: как распознать манипуляцию с первой секунды

Что такое навязанная вина и как она связана с манипуляцией?

VOICE
Спец расскажет… Что такое VoLTE и почему это круто? Спец расскажет… Что такое VoLTE и почему это круто?

Что такое VoLTE, какие преимущества дает, и как включить VoLTE на смартфоне?

CHIP
Когда закончится нефть Когда закончится нефть

Медленное угасание отрасли, служащей хребтом российской экономики, неизбежно

Forbes
Кети Топурия: Не умею ждать, терпеть и молчать Кети Топурия: Не умею ждать, терпеть и молчать

Интервью с солисткой A’Studio о том, как выжить в российском шоу-бизнесе

Cosmopolitan
Человек любопытный. Почему умение учиться — главный навык будущего Человек любопытный. Почему умение учиться — главный навык будущего

Университеты должны учить тому, что будет востребовано через несколько лет

Forbes
Минюст против Спилберга: Сможет ли Netflix бороться за «Оскар» Минюст против Спилберга: Сможет ли Netflix бороться за «Оскар»

Нельзя просто ограничить Netflix возможность выдвигать фильмы на «Оскар»

Forbes
Место лечит Место лечит

Заниматься здоровьем гораздо приятнее с видом на окружающие красоты

Robb Report
Айзек Хэмпстед-Райт: Айзек Хэмпстед-Райт:

Айзек Хэмпстед-Райт о том, каково это — взрослеть на съемочной площадке

Esquire
Как платить телефоном вместо карты? Как платить телефоном вместо карты?

Рассказываем, как превратить свой телефон в электронный кошелек для оплаты

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

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

АвтоМир
Обзор недорогого стедикама для смартфонов Hohem iSteady Mobile Обзор недорогого стедикама для смартфонов Hohem iSteady Mobile

Если вы хотите снимать крутые видео на смартфон, вам не обойтись без стедикама

CHIP
Самые странные вещи, конфискованные у путешественников в США (фотоподборка) Самые странные вещи, конфискованные у путешественников в США (фотоподборка)

Странные вещи, которые люди пытались незаметно провести с собой

Maxim
«Музыка — это мой дар и мое наказание» «Музыка — это мой дар и мое наказание»

Timbaland: где он пропадал несколько лет и как преодолел творческий кризис

OK!
Над пропастью поржи Над пропастью поржи

Ходят слухи, что российский юмор снова на взлете

Esquire
8 ошибок в дачной электрике, которые лучше не совершать 8 ошибок в дачной электрике, которые лучше не совершать

С электрикой шутки плохи - тем более в деревянном доме

CHIP
Ариана Гранде получила на сцене удар лимоном в грудь от поклонников Бейонсе Ариана Гранде получила на сцене удар лимоном в грудь от поклонников Бейонсе

В 25-летнюю певицу бросили цитрус во время ее концерта на фестивале Coachella

Cosmopolitan
Звезды, которые не худеют к лету Звезды, которые не худеют к лету

Эти звезды ни капли не переживают по поводу цифр на весах

Лиза
10 крутых файтингов для ПК, консолей и смартфонов: пока ждем Mortal Kombat 11 10 крутых файтингов для ПК, консолей и смартфонов: пока ждем Mortal Kombat 11

Самые интересные игры жанра файтинг за последние несколько лет

CHIP
10 киногероинь с идеальным весенне-летним гардеробом 10 киногероинь с идеальным весенне-летним гардеробом

Образы Одри Хепберн, Джейн Биркин, Лив Тайлер и других вдохновляют на покупки

Vogue
Как носить олимпийки этой весной Как носить олимпийки этой весной

Они давно перестали быть атрибутом дачников и гопников

GQ
Превратите хлам в энергию Превратите хлам в энергию

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

4x4 Club
Cannes 2019: куда движется главный кинофестиваль мира Cannes 2019: куда движется главный кинофестиваль мира

Сохранят ли Канны за собой звание кинофестиваля № 1 или сдадут позиции?

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

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

Grazia
Паутина для клиента. Как российские банки превращаются в технологические компании Паутина для клиента. Как российские банки превращаются в технологические компании

Банки строят финансовые экосистемы, которые позволяют монетизировать big data

Forbes
Американская мечта Американская мечта

Меган Маркл нужно вспомнить судьбу другой разведенной американки с амбициями

Tatler
В США опубликован доклад Мюллера о российском вмешательстве в выборы В США опубликован доклад Мюллера о российском вмешательстве в выборы

Документ включает итоги двухлетнего расследования о вмешательстве России

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