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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Ловушки для трендов: как вовремя услышать сигналы рынка Ловушки для трендов: как вовремя услышать сигналы рынка

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

Forbes
Все, что ты должна знать о татуаже бровей и даже больше Все, что ты должна знать о татуаже бровей и даже больше

Toп-мастер сети студий LION TATTOO Марина Чернецова делится лайфхаками.

Cosmopolitan
Почему Марс красный? Ученые связали это с наличием воды в прошлом планеты! Почему Марс красный? Ученые связали это с наличием воды в прошлом планеты!

Почему знаменитая Красная планета именно такая? Ученые, похоже, нашли объяснение

ТехИнсайдер
Обзор накопителя SSD Western Digital Black SN750 NVMe: создан для геймеров Обзор накопителя SSD Western Digital Black SN750 NVMe: создан для геймеров

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

CHIP
Сколько лет на самом деле было героям всем известных книг Сколько лет на самом деле было героям всем известных книг

В каком возрасте герои ощутили на себе все трудности жизни

Maxim
12 футболистов, игравших под странными номерами 12 футболистов, игравших под странными номерами

После прочтения этой статьи ты сможешь осадить любого футбольного эрудита

Maxim
Новая «голубая фишка»: стоит ли покупать акции «Сибура» в случае IPO Новая «голубая фишка»: стоит ли покупать акции «Сибура» в случае IPO

В случае проведения IPO акции «Сибура» наверняка станут новой «голубой фишкой»

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

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

CHIP
Экологические зоны. Как это работает в Европе? Экологические зоны. Как это работает в Европе?

К чему стоит готовиться российским автомобилистам

АвтоМир
Хрустящая тема Хрустящая тема

Ароматные свежие огурчики – непременный компонент летних салатов

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

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

CHIP
Какие вложения в науку могут повлиять на экономический рост Какие вложения в науку могут повлиять на экономический рост

Volkswagen тратит на НИОКР сумму, сопоставимую с финансированием всей науки

Forbes
Что мы увидели в фильме «Пираньи Неаполя» про итальянских АУЕшников Что мы увидели в фильме «Пираньи Неаполя» про итальянских АУЕшников

В Российский прокат выходит криминальная драма про малолеток

Maxim
За одни и те же деньги За одни и те же деньги

Jeep Wrangler и УАЗ «Хантер» в дуэльных заездах

4x4 Club
Что будет, если съесть 3 ложки соли? Только правда и ничего кроме правды Что будет, если съесть 3 ложки соли? Только правда и ничего кроме правды

Не делайте этого!

Playboy
Поединок Пса и Бриенны, смерть Оберина Мартелла и повзрослевшие Старки: полный гид по четвертому сезону Поединок Пса и Бриенны, смерть Оберина Мартелла и повзрослевшие Старки: полный гид по четвертому сезону

Вспоминаем все, что произошло в четвертом сезоне "Игры престолов"

Esquire
Елизавета Баварская Елизавета Баварская

О местах силы, супермоделях, итальянской кухне и любимых модных тенденциях

Vogue
Почему не стоит выбирать телевизор прямо в магазине? Почему не стоит выбирать телевизор прямо в магазине?

Принесли из магазина домой, подключили, а телевизор плохо показывает?

CHIP
Николай Немоляев: Николай Немоляев:

Интервью с Николаем Немоляевым

Караван историй
Почему любая диета — это клетка Почему любая диета — это клетка

Почему многие диеты заканчиваются срывами, а сброшенные килограммы возвращаются?

Psychologies
Единый договор об использовании Интернета: письмо создателя Всемирной паутины Единый договор об использовании Интернета: письмо создателя Всемирной паутины

В марте исполнилось 30 лет с момента создания Всемирной паутины

Популярная механика
Демография без географии. Почему пустеют регионы России Демография без географии. Почему пустеют регионы России

Для успешного развития экономики в России пригодны всего 5-7 регионов

Forbes
Вторник 14 мая Вторник 14 мая

Хроника одного дня, который мог бы стать самым обычным, если бы не трагедия

Esquire
Может ли повербанк испортить смартфон? Может ли повербанк испортить смартфон?

Что будет, если внутрь смартфона сразу установить повербанк огромной емкости?

CHIP
Как провести выходные и не жалеть о потраченном времени: 12 лучших идей Как провести выходные и не жалеть о потраченном времени: 12 лучших идей

Пора начинать отдыхать с умом

Playboy
История семьи Саклер, которая подсадила Америку на «легальный наркотик» История семьи Саклер, которая подсадила Америку на «легальный наркотик»

Многие в США становятся наркоманами, принимая рецептурные обезболивающие

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

Разбираем самые распространенные финансовые ошибки вместе с экспертом

Cosmopolitan
Хронология успеха Роузи Хантингтон-Уайтли Хронология успеха Роузи Хантингтон-Уайтли

Британская модель Роузи Хантингтон-Уайтли добилась всего, чего только можно

GQ
Анфиса Черных: «Если у парня нет чувства юмора - это «до свидания». Анфиса Черных: «Если у парня нет чувства юмора - это «до свидания».

Анфиса Черных - о жизни на острове и кино

Cosmopolitan
Надежда Ангарская «Делаю вид, что я на правильном питании» Надежда Ангарская «Делаю вид, что я на правильном питании»

Участница шоу Comedy Woman ответила на несерьезные вопросы «СтарХита»

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