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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Как Мэй Хабиб заработала $285 млн на ИИ-агентах, способных заменить 90% работников Как Мэй Хабиб заработала $285 млн на ИИ-агентах, способных заменить 90% работников

Как Мэй Хабиб создает ПО на базе ИИ, которое берет на себя рутинные задачи

Forbes
Война пяти королей: полный гид по второму сезону Война пяти королей: полный гид по второму сезону

Подробный разбор второго сезона «Игры престолов»

Esquire
Ученые обнаружили, что на самом деле сделало Марс красным Ученые обнаружили, что на самом деле сделало Марс красным

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

Inc.
Эльбрус. Охота за видами Эльбрус. Охота за видами

Впервые на вершинах Эльбруса человек оказался около 200 лет назад

4x4 Club
«Мамонты следующие»: Colossal Biosciences вернула к жизни вымерших 10 тысяч лет назад лютоволков «Мамонты следующие»: Colossal Biosciences вернула к жизни вымерших 10 тысяч лет назад лютоволков

Как ученым Colossal Biosciences удалось произвести на свет щенков лютоволка

VC.RU
Hyundai I30 N. Один такой Hyundai I30 N. Один такой

Hyundai I30 N выходит на наш рынок в середине весны

АвтоМир
Сценарии будущего, которые мы выбираем Сценарии будущего, которые мы выбираем

Может, пора отказаться от жизненного плана, сформированного еще в раннем детстве

Psychologies
Как выбрать миксер для дома: правила профи Как выбрать миксер для дома: правила профи

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

CHIP
Не только Азия Не только Азия

Мотор-шоу в Шанхае и выставка в Нью-Йорке в этом году идут одновременно

АвтоМир
Самые богатые владельцы спортивных команд 2019. Рейтинг Forbes Самые богатые владельцы спортивных команд 2019. Рейтинг Forbes

Топ-10 богатейших владельцев спортивных команд

Forbes
Рэпер, равнявшийся на Маска: как Нипси Хассл изменил музыкальный бизнес Рэпер, равнявшийся на Маска: как Нипси Хассл изменил музыкальный бизнес

В чем заключается наследие убитого рэпера Нипси Хассла?

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

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

Psychologies
Приспособленец Приспособленец

QX50 — гремучая смесь: новая платформа, уникальный мото, электроруль и вариатор

АвтоМир
Психология симулянтов: что заставляет людей притворяться тяжелобольными? Психология симулянтов: что заставляет людей притворяться тяжелобольными?

Почему некоторые люди готовы притворяться, будто тяжело больны

Psychologies
Колготки в сеточку и мини на грани разумного: эволюция стиля Ирины Салтыковой Колготки в сеточку и мини на грани разумного: эволюция стиля Ирины Салтыковой

Как наша Дейнерис из 90-х перевернула представление о сексуальности

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

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

Forbes
Экспансия на север: как Индия завоевывает Россию Экспансия на север: как Индия завоевывает Россию

Индийские инвестиции в российскую экономику составляют более $8 млрд

Forbes
Какие психические заболевания есть у персонажей «Игры престолов»? Какие психические заболевания есть у персонажей «Игры престолов»?

Кажется, что в Вестеросе никому не помешает хороший рехаб

GQ
Финальный сезон «Игры престолов», серия 2: закрытие гештальтов и подготовка к битве за Винтерфелл Финальный сезон «Игры престолов», серия 2: закрытие гештальтов и подготовка к битве за Винтерфелл

Осторожно: в тексте очень много спойлеров

Esquire
Как тренируется и питается Василий Ломаченко? Как тренируется и питается Василий Ломаченко?

Боксер придерживается дисциплины не только в спортивном зале, но и на кухне

GQ
Плавали, знаем Плавали, знаем

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

Лиза
Самые необычные роботы, похожие на животных Самые необычные роботы, похожие на животных

Роботы, на создание которых инженеров вдохновили животные

Популярная механика
Как миллениалы разрушают индустрию личных финансов Как миллениалы разрушают индустрию личных финансов

На Западе миллениалы уже вовсю диктуют рынку личных финансов свои условия

Forbes
Тест Audio-Technica QuietPoint 40BT: автономные так себе шумодавы Тест Audio-Technica QuietPoint 40BT: автономные так себе шумодавы

Легкие In-Ear-наушники с приемлемой системой активного шумоподавления

CHIP
Как смертельный яд помогает лечить болезни: российская разработка Как смертельный яд помогает лечить болезни: российская разработка

Ученые находят новые применения ядам в медицине

Популярная механика
Ключи к силе и легкости Ключи к силе и легкости

Практика йоги критического выравнивания для избавления от последствий стресса

Yoga Journal
Спец расскажет… GearBest или AliExpress: в чем разница и что лучше? Спец расскажет… GearBest или AliExpress: в чем разница и что лучше?

В каком из китайских интернет-магазинов выгоднее и дешевле заказывать товары

CHIP
Болезни, которые мешают нам похудеть Болезни, которые мешают нам похудеть

Ты стараешься следить за питанием, но лишний вес никак не уходит

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

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

OK!
«Сейчас испытываем нехватку то одного, то другого миллиарда»: Алексей Мордашов о богатстве, работе по 12 часов, ошибках и диете «Сейчас испытываем нехватку то одного, то другого миллиарда»: Алексей Мордашов о богатстве, работе по 12 часов, ошибках и диете

Отрывок беседы с миллиардером Алексеем Мордашовым

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