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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Как фотограф Рино Бариллари снимал Одри Хепберн, принцессу Диану и 12 раз ломал ребра Как фотограф Рино Бариллари снимал Одри Хепберн, принцессу Диану и 12 раз ломал ребра

О том, почему профессия папарацци все еще жива и востребована

Forbes
Саймон Мерреллс: «Марк Хэмилл невероятно классный парень!» Саймон Мерреллс: «Марк Хэмилл невероятно классный парень!»

MAXIM продолжает общаться с героями второго сезона «Падения Ордена»

Maxim
Исследование выявило белок, замедляющий старение с помощью регуляции РНК Исследование выявило белок, замедляющий старение с помощью регуляции РНК

Белок PELOTA играет центральную роль в замедлении старения и продлении жизни

ТехИнсайдер
Внимание на старт Внимание на старт

Самые впечатляющие модели автомобилей класса люкс

Robb Report
«Дикое» государство: 7 фактов о жизни на Аляске «Дикое» государство: 7 фактов о жизни на Аляске

Вечная мерзлота, действующие вулканы, множество диких животных — все это Аляска

ТехИнсайдер
Стражи Галактики Стражи Галактики

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

Tatler
Упущенный триллион: удастся ли России вернуть капиталы из офшоров Упущенный триллион: удастся ли России вернуть капиталы из офшоров

По оценкам западных экономистов, россияне хранят в офшорах порядка $1 трлн

Forbes
Как говорить с подростком о контрацепции Как говорить с подростком о контрацепции

Как говорить с ребенком о его личной контрацепции, не вмешиваясь в личную жизнь

Домашний Очаг
«Бизнес-план семейной жизни провалился, и я этому рад» «Бизнес-план семейной жизни провалился, и я этому рад»

Успешные бизнесмены работают и в офисе, и дома, и в отпуске

Psychologies
Легенды Британии Легенды Британии

Автомобили Land Rover Discovery обросли огромным количеством мифов и слухов

4x4 Club
Правильное начало дня поможет избежать стресса Правильное начало дня поможет избежать стресса

Утром тело сильнее реагирует на стресс, чем вечером

Psychologies
MIT прекращает работать с китайскими Huawei и ZTE из-за подозрений в кибершпионаже MIT прекращает работать с китайскими Huawei и ZTE из-за подозрений в кибершпионаже

Один из главных университетов США прекращает все связи с Huawei и ZTE

Forbes
Расколотый мир: как я живу с рассеянным склерозом Расколотый мир: как я живу с рассеянным склерозом

История 29-летней Анастасии, болеющей рассеянным склерозом

Cosmopolitan
Один в поле воин: 3 российских дизайнера, которые борются со спортшиком Один в поле воин: 3 российских дизайнера, которые борются со спортшиком

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

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

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

Maxim
Рай, но есть нюансы Рай, но есть нюансы

Стоит ли ехать в Венесуэлу?

4x4 Club
Секс-драйв: усатое удовольствие от мини-вибратора Volita Секс-драйв: усатое удовольствие от мини-вибратора Volita

Знакомимся с мощным секс-девайсом от Fun Factory

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

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

Forbes
15 мыслей Александра Роднянского 15 мыслей Александра Роднянского

Александр Роднянский рассказал GQ о новой репутации фестиваля «Кинотавр»

GQ
Украинская дуэль: сможет ли Порошенко переиграть Зеленского Украинская дуэль: сможет ли Порошенко переиграть Зеленского

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

Forbes
В режиме экономии В режиме экономии

Как объяснить ребенку, что придется отказаться от каких-то своих «хотелок»

Лиза
Мания величия Мания величия

Почему нужно было ждать целых 13 лет, чтобы сделать большой внедорожник

4x4 Club
Британец потратил большую часть жизни на коллекционирование банок и получил титул самого скучного человека в стране Британец потратил большую часть жизни на коллекционирование банок и получил титул самого скучного человека в стране

О самом скучном человеке Британии

Maxim
10 лучших розыгрышей XX века 10 лучших розыгрышей XX века

Если привычные каждодневные шуточки уже приелись, вдохновитесь этой статьей

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

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

Forbes
Вернуть былой блеск. Пять причин, почему инвесторам пора вкладываться в золото Вернуть былой блеск. Пять причин, почему инвесторам пора вкладываться в золото

Время замедления и страхов — лучшее время для золота

Forbes
Герой нашего времени. Кто и зачем становится розничным инвестором в России Герой нашего времени. Кто и зачем становится розничным инвестором в России

Лишь 2 млн россиян инвестируют на фондовом рынке

Forbes
10 несказочных историй про чудеса 10 несказочных историй про чудеса

Как подвиги сочетаются с парадоксами русской жизни

Русский репортер
Кумир скромных миллионеров Кумир скромных миллионеров

Полноразмерный кроссовер Audi Q7 комфортен, технологичен и капризен

4x4 Club
Боевые шагоходы: со страниц фантастики в реальность Боевые шагоходы: со страниц фантастики в реальность

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

Популярная механика
Открыть в приложении