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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

«Если какие сложности, основной груз на мне»: как женщины воспитывают приемных детей «Если какие сложности, основной груз на мне»: как женщины воспитывают приемных детей

Forbes Woman исследовал гендерные аспекты приемного родительства

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

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

CHIP
Физики объяснили радиальные полосы вокруг посадочных модулей на Луне Физики объяснили радиальные полосы вокруг посадочных модулей на Луне

Почему узоры от спускаемых На Луну космических аппаратов практически идентичны?

N+1
Изобретения под запретом: как режим санкций ведет к дефициту технологий Изобретения под запретом: как режим санкций ведет к дефициту технологий

Санкции против России отразились и на сфере патентных отношений

Forbes
Страдания от избытка красоты: что такое синдром Стендаля Страдания от избытка красоты: что такое синдром Стендаля

Что такое синдром Стендаля и в чем он выражается

ТехИнсайдер
Выброси из головы! Выброси из головы!

Головную боль хотя бы раз в жизни испытывали 98% людей

Лиза
По прозвищу «Тихий» По прозвищу «Тихий»

Nissan Qashqai — модель, которая сформировала нынешнюю автомобильную моду

4x4 Club
Как заработать миллионы на открытом коде: от Red Hat до Nginx Как заработать миллионы на открытом коде: от Red Hat до Nginx

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

Forbes
Стражи Галактики Стражи Галактики

Александр Фридман дал Tatler Teen свое первое в жизни интервью

Tatler
Хватит это терпеть Хватит это терпеть

ПМС, ток­си­коз, лю­бовь к тор­там и про­чие при­чу­ды — не по­вод для иро­нии

Glamour
Почему все в криптомире говорят о DeFi Почему все в криптомире говорят о DeFi

Как децентрализация в финансах может сделать банковскую систему открытой

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

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

Maxim
К кому на Каму К кому на Каму

Хореограф Алексей Мирошниченко превращает Пермь в новую Мекку для балетоманов

Vogue
«Наша любовь устала»: Алентова призналась, почему они с Меньшовым жили врозь «Наша любовь устала»: Алентова призналась, почему они с Меньшовым жили врозь

77-летняя актриса откровенно рассказала о самом личном

Cosmopolitan
9 советов, как себя вести, когда твоя девушка приболела (ты справишься!) 9 советов, как себя вести, когда твоя девушка приболела (ты справишься!)

Как вести себя, если твоя девушка «расклеилась»

Playboy
В одном флаконе В одном флаконе

Как красиво обустроить совмещенный санузел

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

Подробный разбор второго сезона «Игры престолов»

Esquire
Дьявол в деталях Дьявол в деталях

Оскар Потоков о смысле бизнеса, любви к семье и страсти к автомобилям

Robb Report
Замужем в Италии Замужем в Италии

Мы попросили пять женщин, вышедших замуж за итальянцев, рассказать свою историю

Домашний Очаг
Без тормозов: самые яркие новинки Нью-Йоркского автосалона — 2019 Без тормозов: самые яркие новинки Нью-Йоркского автосалона — 2019

Новинки от Bugatti, Porsche, Lincoln, Fiat

Forbes
Как стать президентом: 10 лайфхаков Владимира Зеленского Как стать президентом: 10 лайфхаков Владимира Зеленского

Как пройти путь от комика до президента страны

Forbes

Мультсериал «Любовь,смерть и роботы» — с сексом, котиками и расчлененкой

Esquire
Железный человек Железный человек

У ангела Victoria’s Secret Марты Хант есть внутренний стержень

Tatler
Гонка длиною в 6 лет: что стоит за слиянием сетей «Красное & Белое», «Бристоль» и «Дикси» Гонка длиною в 6 лет: что стоит за слиянием сетей «Красное & Белое», «Бристоль» и «Дикси»

История одной из самых загадочных сделок в российском ретейле

Forbes
Вместе весело Вместе весело

За каждым талантливым сатириком и комендантом стоит женщина с чувством юмора

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

Как произвести впечатление на девушку?

Playboy
«Я целый год не покупала одежду. Как это меня изменило?» «Я целый год не покупала одежду. Как это меня изменило?»

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

Psychologies
Игры кончились Игры кончились

Кит Харингтон рассказал GQ, за что ненавидит сериал, сделавший его знаменитым

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

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

Cosmopolitan
Как научить девочек выживать в сексистском мире Как научить девочек выживать в сексистском мире

Советы, которые помогут воспитать сильных и уверенных в себе женщин

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