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

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
Обзор Asus VivoBook E203MA-FD825TS: легкий ноутбук для работы Обзор Asus VivoBook E203MA-FD825TS: легкий ноутбук для работы

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

CHIP
Терапия CRISPR/Cas помогла снизить «плохой» холестерин при семейной гиперхолестеринемии Терапия CRISPR/Cas помогла снизить «плохой» холестерин при семейной гиперхолестеринемии

Как помогла терапия CRISPR/Cas при семейной гиперхолестеринемии

N+1
Мой ласковый и нежный Мой ласковый и нежный

Другого Карла Лагерфельда — милого друга — вспоминает Сати Спивакова

Tatler
Как кофеин влияет на мозг и тело: неожиданные факты Как кофеин влияет на мозг и тело: неожиданные факты

Исследования выявили ряд интересных фактов, связанных с кофеином

Psychologies
Карнивор-диета: основные принципы одной из самых необычных диет современности Карнивор-диета: основные принципы одной из самых необычных диет современности

Когда мясо у тебя на первое и на десерт

Playboy
Как стать куклой: юные знаменитости, которые помолодели из-за операций Как стать куклой: юные знаменитости, которые помолодели из-за операций

Ради карьеры селебрити готовы делать инъекции и пластику в совсем юном возрасте

Cosmopolitan
Россия вмешивалась в американские выборы, но сговора с Трампом не было: что мы узнали из доклада Мюллера Россия вмешивалась в американские выборы, но сговора с Трампом не было: что мы узнали из доклада Мюллера

Главные выводы из доклада Мюллера

Esquire
У него есть всё У него есть всё

Посмотрим, соответствует ли флагманский внедорожник марки заявлению маркетологов

4x4 Club
Бабушка vs система Бабушка vs система

Как тверская пенсионерка меняет страну с помощью одиночных пикетов

Русский репортер
Борьба с мигрантами: как Россия строит свою «мексиканскую стену» Борьба с мигрантами: как Россия строит свою «мексиканскую стену»

Глава Якутии предложил ограничить сферы, в которых смогут работать мигранты

Forbes
Главное – этикетка. Что на самом деле знают о вине винные критики Главное – этикетка. Что на самом деле знают о вине винные критики

Винные дегустаторы — это уникумы или талантливые фокусники

Forbes
«Пусть лучше буду битый, нежели мятый внутри» «Пусть лучше буду битый, нежели мятый внутри»

Интервью с актером Александром Горбатовым

OK!
Что лучше всего спрашивать у девушки на первом свидании? Памятка из 9 вопросов Что лучше всего спрашивать у девушки на первом свидании? Памятка из 9 вопросов

Если будете придерживаться этой инструкции на свидании, все будет как по маслу

Playboy
Виктор Черномырдин: моё кредо — разговаривать Виктор Черномырдин: моё кредо — разговаривать

Виталий Черномырдин вспоминает о своём выдающемся отце

Дилетант
Что посмотреть в пятницу вечером: лучшие фильмы за всю историю Что посмотреть в пятницу вечером: лучшие фильмы за всю историю

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

Популярная механика
Состояние Билла Гейтса превысило $100 млрд Состояние Билла Гейтса превысило $100 млрд

Состояние миллиардера Билла Гейтса на днях превысило отметку $100 млрд

Forbes
Две свадьбы, одни похороны: полный гид по третьему сезону Две свадьбы, одни похороны: полный гид по третьему сезону

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

Esquire
12 пар брюк, которые вы будете носить в этом сезоне 12 пар брюк, которые вы будете носить в этом сезоне

Какие брюки совершенно точно могут заменить джинсы в любом casual образе

GQ
Майкл Джей Фокс: «Я договорился с болезнью» Майкл Джей Фокс: «Я договорился с болезнью»

Майкл Фокс об отношениях с болезнью Паркинсона, ошибках и вере в лучшее

Psychologies
Отто фон Бисмарк — железный канцлер с человеческим лицом Отто фон Бисмарк — железный канцлер с человеческим лицом

1 апреля исполняется 204 года со дня рождения Отто фон Бисмарка

Maxim
Почему отменили повторный приезд Тони Роббинса в Россию Почему отменили повторный приезд Тони Роббинса в Россию

Школа бизнеса «Синергия» решила отменить приезд Тони Роббинса в нашу страну

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

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

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

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

Forbes
Sabi Miss: «Он хотел превратить меня в куклу!» Sabi Miss: «Он хотел превратить меня в куклу!»

Первое интервью певицы Sabi Miss после разрыва с продюсером

Cosmopolitan
«Синонимы» Надава Лапида – последний шанс увидеть целый Нотр-Дам «Синонимы» Надава Лапида – последний шанс увидеть целый Нотр-Дам

Еще один триумфатор Берлинского кинофестиваля добрался до России

GQ
Как успешные люди проводят выходные, чтобы всю неделю быть на подъеме Как успешные люди проводят выходные, чтобы всю неделю быть на подъеме

Пролежать у телевизора или компьютера весь день — это не лучший вариант

Playboy
€12 500 за задержание. Что значит решение ЕСПЧ по акции «Он вам не Димон» €12 500 за задержание. Что значит решение ЕСПЧ по акции «Он вам не Димон»

ЕСПЧ присудил компенсацию задержанной на акции «Он вам не Димон»

Forbes
Последний сезон «Игры престолов»: интервью с лордом Варисом и Мелисандрой Последний сезон «Игры престолов»: интервью с лордом Варисом и Мелисандрой

Все обсуждают «Игру престолов», главную премьеру весны (а то и года)

Esquire
Klim Eastwood: «Я хочу оставаться загадкой, как круги на полях» Klim Eastwood: «Я хочу оставаться загадкой, как круги на полях»

Первый виртуальный рэпер рассказал, как пришел в рэп

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