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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

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

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

Forbes
С чего начинался Рунет: герои и проекты, создавшие интернет в России С чего начинался Рунет: герои и проекты, создавшие интернет в России

Фигуры и проекты, определившие развитие Рунета

Forbes
Астрономы отыскали экстремально яркие события разрыва звезд сверхмассивными черными дырами Астрономы отыскали экстремально яркие события разрыва звезд сверхмассивными черными дырами

Астрономы описали класс рекордно ярких транзиентов

N+1
Илон Маск из Китая. Кто изобретает заново люксовые электрокары Karma Илон Маск из Китая. Кто изобретает заново люксовые электрокары Karma

Производитель электрокаров Karma существует чуть больше 10 лет

Forbes
Ежи от болезней и средневековый фастфуд: странные пищевые привычки времен Средневековья Ежи от болезней и средневековый фастфуд: странные пищевые привычки времен Средневековья

Страдающие ежи и Средневековье: что ели люди в эпоху рыцарей?

ТехИнсайдер
Рождение ультрагиганта. Что означает сделка между Chevron и Anadarko Рождение ультрагиганта. Что означает сделка между Chevron и Anadarko

Chevron может стать публичной нефтяной компанией номер два в мире

Forbes
10 киногероинь с идеальным весенне-летним гардеробом 10 киногероинь с идеальным весенне-летним гардеробом

Образы Одри Хепберн, Джейн Биркин, Лив Тайлер и других вдохновляют на покупки

Vogue
Правда ли, что смузи вредно для зубов — мнение стоматолога Правда ли, что смузи вредно для зубов — мнение стоматолога

Разбираем на ингредиенты самый модный напиток современности

Maxim
Богатейшие жены в Кремле, Госдуме и Совете Федерации Богатейшие жены в Кремле, Госдуме и Совете Федерации

Кто из жен слуг народа в прошлом году заработал миллиард рублей?

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

Три главные заповеди повседневных кроссовок

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

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

Esquire
Агенты под прикрытием Агенты под прикрытием

Основательницы проекта FoodyFit, о «полезных» продуктах, которые делают нас хуже

Grazia
Неон-киллер Неон-киллер

Евгения Крегжде поразила нас в самое сердце

Maxim
Alphabet — неожиданный бенефициар IPO Uber. Его доля может стоить $5 млрд Alphabet — неожиданный бенефициар IPO Uber. Его доля может стоить $5 млрд

Готовясь к IPO, Uber связывает с материнской компанией Google массу рисков

Forbes
Мой ласковый и нежный Мой ласковый и нежный

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

Tatler
Говорящие с деревьями Говорящие с деревьями

Природа особенно хороша тогда, когда мы познаем ее на чувственном уровне

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

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

Maxim
В первом чтении В первом чтении

Тина Канделаки написала книгу о том, что она делает с лицом

Tatler
Богатый внутренний мир Богатый внутренний мир

Интерьер 50-метровой Aurora от дизайнера Ахилла Сальвани

Robb Report
5 признаков, что тебе пора с ней окончательно расстаться (беги, глупец, все потеряно) 5 признаков, что тебе пора с ней окончательно расстаться (беги, глупец, все потеряно)

Важно понимать, что иногда отношения должны просто закончиться

Playboy
Финальный сезон «Игры престолов», серия 2: закрытие гештальтов и подготовка к битве за Винтерфелл Финальный сезон «Игры престолов», серия 2: закрытие гештальтов и подготовка к битве за Винтерфелл

Осторожно: в тексте очень много спойлеров

Esquire
Интервью: Николай Костер-Вальдау и Джером Флинн о финале «Игры престолов» Интервью: Николай Костер-Вальдау и Джером Флинн о финале «Игры престолов»

Интервью с Николаем Костером-Вальдау и Джеромом Флинном

Cosmopolitan
5 причин, почему встречаться с женщиной постарше – твой лучший выбор 5 причин, почему встречаться с женщиной постарше – твой лучший выбор

Нужно прекратить стесняться того, что вы встречаетесь с женщиной старше вас

Playboy
Профессиональный шутник: кто пишет сценарии для ситкомов в России Профессиональный шутник: кто пишет сценарии для ситкомов в России

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

Esquire
От Питера до Москвы на электротяге: невероятно быстро и очень медленно От Питера до Москвы на электротяге: невероятно быстро и очень медленно

Jaguar I-Pace: быстрый, красивый, дерзкий и полностью электрический

Популярная механика
Диеты без психотерапии бесполезны. И вот почему Диеты без психотерапии бесполезны. И вот почему

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

Psychologies
540 последних амурских тигров: как их спасти 540 последних амурских тигров: как их спасти

За последние 100 лет в мире стало на 96% меньше тигров

Популярная механика
Валютные спекулянты проявили рекордный за год интерес к российским активам Валютные спекулянты проявили рекордный за год интерес к российским активам

ЦБ отмечает рост спекулятивных валютных операций

Forbes
Ведают, что творят Ведают, что творят

Homo Faber — выставка, которая возвращает веру в будущее

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

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

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