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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Опасная иллюзия: почему не стоит путать искусственный интеллект с чат-ботами Опасная иллюзия: почему не стоит путать искусственный интеллект с чат-ботами

ИИ — спаситель человечества или его зловещий повелитель?

Forbes
Комнатные облака Бернднаута Смилде Комнатные облака Бернднаута Смилде

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

Популярная механика
Не только человеческий рефлекс: все ли животные зевают? Не только человеческий рефлекс: все ли животные зевают?

Все ли живые организмы имеют рефлекс зевоты?

ТехИнсайдер
Народный автомобиль СССР: проект, убитый войной Народный автомобиль СССР: проект, убитый войной

КИМ-10 — автомобиль, который так и не стал народным

Популярная механика
Как повысить самооценку и обрести уверенность? 11 советов психолога Как повысить самооценку и обрести уверенность? 11 советов психолога

Заниженная самооценка мешает нам строить здоровые отношения и карьеру

Psychologies
Спец расскажет… Что такое VoLTE и почему это круто? Спец расскажет… Что такое VoLTE и почему это круто?

Что такое VoLTE, какие преимущества дает, и как включить VoLTE на смартфоне?

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

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

Esquire
Как распознать токсичного начальника и что делать дальше Как распознать токсичного начальника и что делать дальше

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

Psychologies
Поздно их воспитывать! Поздно их воспитывать!

Звездный статус от ссор с родителями не спасает

Лиза
Незримый мост: как пересечь Мессинский пролив Незримый мост: как пересечь Мессинский пролив

Со времён Гомера морской путь с Апеннинского полуострова на Сицилию не изменился

4x4 Club
Как забыть девушку, от которой ты без ума: 12 самых верных способов Как забыть девушку, от которой ты без ума: 12 самых верных способов

Страдать будешь в другой раз

Playboy
Киборги среди нас: для чего биохакеры вживляют микросхемы под кожу Киборги среди нас: для чего биохакеры вживляют микросхемы под кожу

Британский биохакер хочет подарить человечеству новое чувство

Популярная механика
Единорог-беспилотник: как ученый из Китая отправил на американские дороги грузовики без водителей Единорог-беспилотник: как ученый из Китая отправил на американские дороги грузовики без водителей

Стартап TuSimple — сильный участник рынка беспилотных грузоперевозок

Forbes
«Она построила лучший авиационный бизнес в стране»: жизнь и принципы Наталии Филевой «Она построила лучший авиационный бизнес в стране»: жизнь и принципы Наталии Филевой

Как соосновательница S7 создала самую эффективную в своей отрасли компанию

Forbes
Батерс: «В рэпе всё в отталкивается от звука, а он значительно прокачался» Батерс: «В рэпе всё в отталкивается от звука, а он значительно прокачался»

Музыкант, смешивающий стоунер-рок и рэп

Esquire
Детский мир Детский мир

Декоратор Мия Карлова воссоздала в загородном доме атмосферу детства на даче

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

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

CHIP
Звезда сериала «Кадетство» и вдова Евгения Евстигнеева внезапно умерла в 55 лет Звезда сериала «Кадетство» и вдова Евгения Евстигнеева внезапно умерла в 55 лет

Звездные подруги говорят, что актриса страдала от затяжной депрессии

Cosmopolitan
Из девочки в мальчика и другие бьюти-эксперименты звездных детей Из девочки в мальчика и другие бьюти-эксперименты звездных детей

Дети знаменитостей также меняют цвет волос, делают стрижки и даже красятся

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

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

Forbes
Медитация — секретное оружие против мигрени Медитация — секретное оружие против мигрени

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

Psychologies
Два светила — это сила Два светила — это сила

Изучаем законы взаимовыгодного брака

Tatler
«Полгода — у меня, полгода — у него»: как Петр Авен и Вячеслав Кантор делят одну картину на двоих «Полгода — у меня, полгода — у него»: как Петр Авен и Вячеслав Кантор делят одну картину на двоих

Петр Авен рассказал, во сколько он оценивает свою коллекцию русского искусства

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

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

Forbes
Когда не надо начинать свое дело: 10 аргументов в пользу работы «на дядю» Когда не надо начинать свое дело: 10 аргументов в пользу работы «на дядю»

Работа в офисе — вовсе не антитренд

Psychologies
Цифровой обольститель. Легко ли найти любовь с помощью новых технологий Цифровой обольститель. Легко ли найти любовь с помощью новых технологий

Российский рынок дейтинга оценивается примерно в $66 млн, а мировой — в $5 млрд

Forbes
Звездные мамочки рассказали о трудностях материнства Звездные мамочки рассказали о трудностях материнства

6 апреля телеканал «Супер» запускает реалити «#Яжемать»

Cosmopolitan
Верный ход Верный ход

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

StarHit
Спец расскажет… Как выигрывать технику в интернете Спец расскажет… Как выигрывать технику в интернете

Как выиграть смартфон в конкурсе в интернете?

CHIP
Красочная война: спортивный пейнтбол Красочная война: спортивный пейнтбол

Спортивный пейнтбол — полноценная спортивная дисциплина с четким регламентом

Популярная механика
Открыть в приложении