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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

На это грантов не дают: как именитый хирург спасает финскую усадьбу под Выборгом На это грантов не дают: как именитый хирург спасает финскую усадьбу под Выборгом

Илья Слепцов восстанавливает на территории Киискиля исторические постройки

Forbes
Редактируем фото профессионально: 3 хороших бесплатных программы Редактируем фото профессионально: 3 хороших бесплатных программы

Три хороших и бесплатных программы для качественной обработки изображений

CHIP
3D-печатные пещеристые тела восстановили эрекцию у свиней 3D-печатные пещеристые тела восстановили эрекцию у свиней

Ученые создали биомиметические модели полового члена свиньи с помощью 3D-печати

N+1
Полный тюнинг Полный тюнинг

Как Дана Борисова стала нимфоманкой и почему поругалась с родной сестрой

StarHit
Как научиться довольствоваться тем, что есть, и перестать сравнивать свою жизнь с чужими Как научиться довольствоваться тем, что есть, и перестать сравнивать свою жизнь с чужими

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

ТехИнсайдер
Иракское досье и «карманный Путин». О чем мир узнал благодаря WikiLeaks Джулиана Ассанжа Иракское досье и «карманный Путин». О чем мир узнал благодаря WikiLeaks Джулиана Ассанжа

Что стало явным благодаря WikiLeaks Джулиана Ассанжа?

Forbes
«Мстители: Финал»: сказка о непотерянном времени «Мстители: Финал»: сказка о непотерянном времени

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

GQ
«Символы же не горят? Они же навсегда?» «Символы же не горят? Они же навсегда?»

Почему нам так больно при виде горящего Собора Парижской Богоматери?

Psychologies
«Седых волос у него прибавилось». Борис Титов навестил Майкла Калви в СИЗО «Седых волос у него прибавилось». Борис Титов навестил Майкла Калви в СИЗО

Калви провел в СИЗО уже почти два месяца

Forbes
Чайный пакетик за $14000 и туалетная бумага за $376900: удивительно бестолковые дорогие вещи Чайный пакетик за $14000 и туалетная бумага за $376900: удивительно бестолковые дорогие вещи

Когда у тебя есть все нужное, а деньги жгут карман

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

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

CHIP
В начале была музыка В начале была музыка

Как Полу Маккартни удалось записать лучший альбом года

The Rake
Все будет хорошо Все будет хорошо

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

StarHit
Валерия: «Иногда плачу в три ручья Валерия: «Иногда плачу в три ручья

Певица Валерия о секрете молодости, обожании мужа и проблемах

StarHit
Об этом не расскажут в «Прямом эфире» Об этом не расскажут в «Прямом эфире»

Андрей Малахов коллекционирует современное петербургское искусство

Собака.ru
8 причин, почему каждый мужик должен делать маникюр и педикюр (внезапно) 8 причин, почему каждый мужик должен делать маникюр и педикюр (внезапно)

Почему мужчинам необходимо делать маникюр и педикюр в салоне

Playboy
Создана новая онлайн-платформа для освоения навыков кибербезопасности Создана новая онлайн-платформа для освоения навыков кибербезопасности

«Лаборатория Касперского» представила в Москве новую платформу

CHIP
7 странных вещей, которые отправляли в космос — от пиццы до светового меча 7 странных вещей, которые отправляли в космос — от пиццы до светового меча

Самые необычные вещи, которые когда-либо отправляли в космос

Playboy
Успеть к восходу Успеть к восходу

Гонка Rally Nippon — одно из самых ярких мероприятий, посвящённых автомобилям

Robb Report
Не опять, а Сноу Не опять, а Сноу

Звезда «Игры престолов» Кит Харингтон и его «Дольче»

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

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

Forbes
Как предприниматель из России помогает печатать на 3D-принтерах детали для Boeing, SpaceX и BMW Как предприниматель из России помогает печатать на 3D-принтерах детали для Boeing, SpaceX и BMW

Бизнес Константина Иванова вырос из московского стартапа в глобальную компанию

Forbes
Как наладить лактацию? Как наладить лактацию?

Недостаток и избыток молока у кормящей мамы

9 месяцев
В горах мое сердце В горах мое сердце

На чем держится райская красота в горах

Вокруг света
Титан, тишина и саморазрушение: на что способны современные шины Титан, тишина и саморазрушение: на что способны современные шины

Современные шины – не просто резиновая смесь на колесных дисках

Популярная механика
Женщина, которая поет Женщина, которая поет

15 апреля у Аллы Пугачевой юбилей – 70 лет

Лиза
Какое из своих «Я» мы показываем другим? Какое из своих «Я» мы показываем другим?

Можно ли расшифровать бессознательные особенности человека

Psychologies
Сардиния. Инструкция по применению Сардиния. Инструкция по применению

Я еду на запад, потому что на востоке уже везде был

4x4 Club
Орбитальные ломы Орбитальные ломы

Сверхтяжелые ракеты SpaceX могут стать носителем первого легального оружия

Популярная механика
Как бывшая компания Дерипаски борется за центр Петербурга Как бывшая компания Дерипаски борется за центр Петербурга

«Главстрой» не оставляет попыток заполучить лакомый кусок в центре Петербурга

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