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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Психологический портрет: что такое синдром незавершенных дел и синдром Феникса Психологический портрет: что такое синдром незавершенных дел и синдром Феникса

Психология: что лежит в основе синдромов Феникса и незавершенных дел?

Forbes
Обзор Asus VivoBook E203MA-FD825TS: легкий ноутбук для работы Обзор Asus VivoBook E203MA-FD825TS: легкий ноутбук для работы

Тестируем компактный и недорогой ноутбук от Asus

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

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

N+1
«Душа компании и мама для всех». Каким человеком была Наталья Филева «Душа компании и мама для всех». Каким человеком была Наталья Филева

Как Наталья Филева боролась за интересы частного бизнеса

Forbes
Тест-полоска: как Минздрав помогает регионам лечить пациентов с диабетом Тест-полоска: как Минздрав помогает регионам лечить пациентов с диабетом

Как реализуется федеральная программа «Борьба с сахарным диабетом»

Forbes
Совсем другое дело Совсем другое дело

Что сейчас происходит в жизни Анджелины Джоли

Grazia
Как российский конкурент IBM и Oracle завоевывает клиентов по всему миру Как российский конкурент IBM и Oracle завоевывает клиентов по всему миру

За что стартап Филиппа Денисова так ценят инвесторы и клиенты

Forbes
Какие компании выживут в этом столетии Какие компании выживут в этом столетии

Отрывок из книги «Впереди перемен» Джона Коттера

Forbes
Все будет хорошо Все будет хорошо

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

StarHit
Алла навсегда Алла навсегда

О своих встречах с Аллой Борисовной Пугачевой рассказывает главный редактор ОК!

OK!
«Открылось окно возможностей»: экономисты о победе Зеленского «Открылось окно возможностей»: экономисты о победе Зеленского

Что победа Владимира Зеленского означает для экономики и газовых споров

Forbes
Почему все в криптомире говорят о DeFi Почему все в криптомире говорят о DeFi

Как децентрализация в финансах может сделать банковскую систему открытой

Forbes
Иллюзия правды: как нам навязывают убеждения Иллюзия правды: как нам навязывают убеждения

Мы часто не замечаем, как чужое мнение становится нашим

Psychologies
Нежелезный Феликс Нежелезный Феликс

Каким был организатор убийства Григория Распутина

Дилетант
Совместными усилиями Совместными усилиями

Все са­мые но­вые тех­но­ло­гии — на служ­бе у ва­ше­го те­ла и ва­шей кра­со­ты

Glamour
9 признаков того, что ты ей не абсолютно не интересен (извини, это правда конец) 9 признаков того, что ты ей не абсолютно не интересен (извини, это правда конец)

Это просто нужно признать, быстрее пережить трагедию и быстрее переключиться

Playboy
Почему Хит Леджер сыграл Джокера лучше всех Почему Хит Леджер сыграл Джокера лучше всех

И почему всех Джокеров сравнивают именно с ним

GQ
Артист балета Игорь Цвирко: «Мне нужен хаос, нужно куда-то бежать, торопиться» Артист балета Игорь Цвирко: «Мне нужен хаос, нужно куда-то бежать, торопиться»

Цвирко примерил коллекцию Henderson

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

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

Psychologies
Белошвейка, которая называла королеву сестрой Белошвейка, которая называла королеву сестрой

Герцогиня де Шеврёз — виртуозная политическая интриганка эпохи двух кардиналов

Дилетант
История с бородой История с бородой

В нашей рубрике «Люди» Сергей Чумин

4x4 Club
Пьерпаоло Пиччоли о новых талантах в столице Катара и моде «без фигни» Пьерпаоло Пиччоли о новых талантах в столице Катара и моде «без фигни»

Член жюри конкурса Fashion Trust Arabia и креативный директор Valentino

Vogue
Чертова дюжина: 12 океанских монстров Чертова дюжина: 12 океанских монстров

Жизнь на глубине тяжела и неказиста

Вокруг света
Сила вредных привычек Сила вредных привычек

Как табачные короли Игорь Кесаев и Сергей Кациев стали алкогольными магнатами

Forbes
Гонка на опережение. Как не сойти с ума на работе Гонка на опережение. Как не сойти с ума на работе

Человеческая жизнь больше, чем круглосуточная работа на износ без выходных

Forbes

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

Cosmopolitan
Гордость и предубеждение Гордость и предубеждение

Дженнифер Лопес не хочет верить, что жених начал изменять ей еще до свадьбы

StarHit
Разведка США поддержала стартап, который предсказывает кибератаки Разведка США поддержала стартап, который предсказывает кибератаки

Об инструменте Omnisense, предсказывающим кибератаки

Forbes
Весь мир - это я: новый проект дизайнера Яны Недзвецкой Весь мир - это я: новый проект дизайнера Яны Недзвецкой

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

Cosmopolitan
Веское слово Джексона Веское слово Джексона

Разменяв восьмой десяток, Джексон не собирается останавливаться на достигнутом

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