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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Совы не то, чем кажутся: почему современное кино нельзя представить без Дэвида Линча Совы не то, чем кажутся: почему современное кино нельзя представить без Дэвида Линча

Как Линч стал одним из величайших режиссеров XX и XXI века

Forbes
Кто заплатит Флойду Мейвезеру $500 млн за возвращение в бокс? Кто заплатит Флойду Мейвезеру $500 млн за возвращение в бокс?

Стриминговая платформа DAZN Леонарда Блаватника тратит огромные деньги на спорт

Forbes
Гремучие змеи попили воды с тел сородичей Гремучие змеи попили воды с тел сородичей

Герпетологи изучили, как зеленые гремучники собирают дождевую воду

N+1
Диалог с молчанием Диалог с молчанием

«Проклятые» вопросы о внеземных цивилизациях и их поиске

Огонёк
Исследование выявило один фактор, по которому можно понять, что вы находитесь в здоровых отношениях Исследование выявило один фактор, по которому можно понять, что вы находитесь в здоровых отношениях

Как узнать, что ваши отношения здоровые? Поможет поступок, выявленный учеными

ТехИнсайдер
Как стать хорошим начальником: советы от успешных боссов из фильмов Как стать хорошим начальником: советы от успешных боссов из фильмов

В числе коучей мистер Бернс из «Симпсонов» и даже доктор Перри Кокс из «Клиники»

Playboy
044 Rose: «Украинское отличие — в том, что мы из ничего делаем все» 044 Rose: «Украинское отличие — в том, что мы из ничего делаем все»

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

Esquire
Город Город

Более века Лазурный Берег неразрывно связан с понятием «дольче вита»

Esquire
Как найти сломанную ДНК Как найти сломанную ДНК

Ученые установили, как фермент репарации NEIL-1 определяет участки ДНК человека

Популярная механика
Быстрее, выше, сильнее! Быстрее, выше, сильнее!

Все словно помешались на собственной эффективности

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

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

Playboy
Экономика Железного трона: «Игра престолов» как бизнес-империя Экономика Железного трона: «Игра престолов» как бизнес-империя

Во сколько оценивается бренд «Игры престолов» и сколько шоу приносит HBO

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

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

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

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

Maxim
Елена Шлёнкина: «В России есть спрос на дизайн» Елена Шлёнкина: «В России есть спрос на дизайн»

Елена Шлёнкина — об истории интерьерной отрасли и о своём жизненном пути

SALON-Interior
Торжество разума. Как застройщиков заставляют воспринимать жителей всерьез Торжество разума. Как застройщиков заставляют воспринимать жителей всерьез

За рубежом набирают силу «соглашения об общественной пользе»

Forbes
Костюм Адама: звезды, которые не стесняются демонстрировать мужское достоинство Костюм Адама: звезды, которые не стесняются демонстрировать мужское достоинство

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

Cosmopolitan
Вне игры Вне игры

Тата Карапетян, героиня самого громкого светского расставания сезона

Tatler
Что делать, если ваш мужчина — геймер Что делать, если ваш мужчина — геймер

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

Psychologies
Максим Ползиков: Смешать, но не взбалтывать: как устроена внутренняя кухня ресторанного бизнеса Максим Ползиков: Смешать, но не взбалтывать: как устроена внутренняя кухня ресторанного бизнеса

Как Ginza умудряется сохранять уровень сервиса при таком размере компании

СНОБ
Вклад каждого. На чем зарабатывает финансовый супермаркет «Банки.ру» Вклад каждого. На чем зарабатывает финансовый супермаркет «Банки.ру»

Выручка компании «Банки.ру» превысила 1 млрд рублей

Forbes
25 все еще (почему-то) крутых вещей 25 все еще (почему-то) крутых вещей

В этом переменчивом мире есть вещи и люди, которые забыли выйти из моды

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

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

Glamour
Финансовый грабеж. Экономист Мовчан о том, почему в России невозможно соблюдать законы Финансовый грабеж. Экономист Мовчан о том, почему в России невозможно соблюдать законы

Почему в России невозможно соблюдать законы

Forbes
4 главных страха, которые мешают вам жить на максимуме 4 главных страха, которые мешают вам жить на максимуме

В чем причина нашей пассивности?

Psychologies
Куда уходит детство Куда уходит детство

В 7-м классе Алла Пугачева напророчила себе славу

StarHit
Превратите хлам в энергию Превратите хлам в энергию

Мне казалось, расходы на топливо ничтожны по сравнению с тратами на автомобиль

4x4 Club
А он нам нужен? А он нам нужен?

Мы поездили на компактном кроссовере, чтобы понять, зачем он нам

АвтоМир
Почему люди носят сандалии именно с носками? Всему виной Древняя Греция и СССР Почему люди носят сандалии именно с носками? Всему виной Древняя Греция и СССР

Вы тоже порабощены советской культурой и боитесь показывать ноги!

Playboy
5 лучших брендов в России 5 лучших брендов в России

Впервые для России составлен список лучших торговых марок

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