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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Из мужского гардероба — в одежду для Барби: как розовый стал женским цветом Из мужского гардероба — в одежду для Барби: как розовый стал женским цветом

Как розовый стал воплощением гендерных стереотипов

Forbes
В России хотят запретить все редкие, крафтовые и коллекционные сорта пива В России хотят запретить все редкие, крафтовые и коллекционные сорта пива

Любые малотиражные или необычные сорта пива могут запретить

Maxim
Самый научный и логичный в мире: 10 фактов о корейском алфавите Самый научный и логичный в мире: 10 фактов о корейском алфавите

Хангыль: самый простой, логичный и необычный алфавит мира

ТехИнсайдер
Джоан Роулинг Джоан Роулинг

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

Дилетант
Используй ложку и телефон: 20 способов доставить себе удовольствие Используй ложку и телефон: 20 способов доставить себе удовольствие

Двадцать разных способов мастурбации на любой вкус и цвет

Cosmopolitan
Несносный босс: как найти к нему подход Несносный босс: как найти к нему подход

Что делать, если источник проблем — ваш босс?

Psychologies
5 типичных ошибок при выборе видеорегистратора: учтите, чтобы не пожалеть 5 типичных ошибок при выборе видеорегистратора: учтите, чтобы не пожалеть

Самые популярные ошибки при выборе видеорегистратора для автомобиля

CHIP
Правильное начало дня поможет избежать стресса Правильное начало дня поможет избежать стресса

Утром тело сильнее реагирует на стресс, чем вечером

Psychologies
Самые необычные роботы, похожие на животных Самые необычные роботы, похожие на животных

Роботы, на создание которых инженеров вдохновили животные

Популярная механика
10 масок, которые мы носим 10 масок, которые мы носим

Какие маски мы носим, чтобы скрыть свое истинное лицо?

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

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

Psychologies
Действительно ли каждый пятый россиянин хочет покинуть страну? Действительно ли каждый пятый россиянин хочет покинуть страну?

Рекордные 20% россиян выразили желание покинуть страну

Forbes
Новое начало Новое начало

Разработка полноценной системы космического туризма

Популярная механика
Газонокосилка или триммер: что лучше? Газонокосилка или триммер: что лучше?

Для чего лучше выбрать газонокосилку, а для чего – триммер

CHIP
Человек любопытный. Почему умение учиться — главный навык будущего Человек любопытный. Почему умение учиться — главный навык будущего

Университеты должны учить тому, что будет востребовано через несколько лет

Forbes
Илон Маск анонсировал создание роботакси Tesla Илон Маск анонсировал создание роботакси Tesla

Tesla собирается выпустить полностью автопилотируемую машину

Forbes
Иная формула Иная формула

Гонки на электрокарах

Популярная механика
Говорящие с деревьями Говорящие с деревьями

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

Psychologies
Дурное послевкусие: как нацпроекты повлияют на экономику России Дурное послевкусие: как нацпроекты повлияют на экономику России

Нацпроекты поддержат экономику, но нужно готовиться и к негативным эффектам

Forbes
33 года со дня смерти “мирного атома”: годовщина аварии на ЧАЭС 33 года со дня смерти “мирного атома”: годовщина аварии на ЧАЭС

Авария на Чернобыльской АЭС стала одной из самых страшных техногенных катастроф

Популярная механика
Секс-драйв: усатое удовольствие от мини-вибратора Volita Секс-драйв: усатое удовольствие от мини-вибратора Volita

Знакомимся с мощным секс-девайсом от Fun Factory

Cosmopolitan
Госбанкам могут запретить покупать частных конкурентов. Что это значит? Госбанкам могут запретить покупать частных конкурентов. Что это значит?

Госбанкам могут запретить скупать своих частных конкурентов

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

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

СНОБ
Как «Кладбище домашних животных», но лучше: 2 альтернативы новому триллеру по Стивену Кингу Как «Кладбище домашних животных», но лучше: 2 альтернативы новому триллеру по Стивену Кингу

Две идеи для тех, кому нужен настоящий Стивен Кинг

Esquire
Этот щенок всегда спит в одной и той же, очень странной позе (нет, он жив) Этот щенок всегда спит в одной и той же, очень странной позе (нет, он жив)

Фотожабы с участием ши-тцу Пэнинин

Playboy
«Принимайте себя утром и вечером, до и после еды» «Принимайте себя утром и вечером, до и после еды»

Как наша героиня от борьбы с собой пришла к принятию и что ей в этом помогло

Psychologies
Российские военные овладели парапсихологией Российские военные овладели парапсихологией

О применении российскими военными методики боевой парапсихологии

Популярная механика
Иду по приборам: первый серийный вертолет Ми-26Т2В Иду по приборам: первый серийный вертолет Ми-26Т2В

Холдинг «Вертолеты России» представил новейший военно-транспортный вертолет

Популярная механика
«Я начал терять скорость». Галицкий впервые рассказал, почему продал «Магнит» «Я начал терять скорость». Галицкий впервые рассказал, почему продал «Магнит»

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

Forbes
Йохан Ингер: «Когда я был мальчиком, очень торопился начать самостоятельную жизнь» Йохан Ингер: «Когда я был мальчиком, очень торопился начать самостоятельную жизнь»

Герой этого номера Grazia – хореограф Йохан Ингер

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