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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Признание и обвинение: почему общество не верит рассказам женщин о пережитом насилии Признание и обвинение: почему общество не верит рассказам женщин о пережитом насилии

Как общество относится к рассказам женщин о травматичном опыте?

Forbes
Весь мир — театр: Библионочь — 2019 в Ленинке Весь мир — театр: Библионочь — 2019 в Ленинке

Гости «Библионочи в Ленинке»

Cosmopolitan
Австралийцы отыскали новую популяцию вымирающих беличьих кускусов Австралийцы отыскали новую популяцию вымирающих беличьих кускусов

Экологи обнаружили в Косцюшко новую популяцию беличьих кускусов

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

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

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

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

Cosmopolitan
Почему шутки, рассказанные мужчинами, кажутся нам более смешными Почему шутки, рассказанные мужчинами, кажутся нам более смешными

Мужчины-шутники поднимают свой статус в коллективе, а женщины только вредят себе

Psychologies
Эволюция капитализма Эволюция капитализма

Могут ли появиться новые миллиардеры в России

Forbes
По вертикали: 8 головокружительных лифтов По вертикали: 8 головокружительных лифтов

Внешний лифт — это не только транспортное средство

Вокруг света
Какие вложения в науку могут повлиять на экономический рост Какие вложения в науку могут повлиять на экономический рост

Volkswagen тратит на НИОКР сумму, сопоставимую с финансированием всей науки

Forbes
Диета против ПМС Диета против ПМС

Как быть, если ПМС мешает работе и отравляет личную жизнь

Лиза
Райские кущи Райские кущи

Сорок лет назад Юбер де Живанши и Филипп Вене купили поместье Дю‑Жонше

AD
Как выбрать микроволновку и на что обратить внимание при покупке Как выбрать микроволновку и на что обратить внимание при покупке

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

CHIP
Суд в США приговорил Марию Бутину к 18 месяцам тюрьмы Суд в США приговорил Марию Бутину к 18 месяцам тюрьмы

Американский суд вынес приговор россиянке Марии Бутиной

Forbes
Приходит с возрастом Приходит с возрастом

Своими мыслями с Grazia делится Яна Кушнер

Grazia
Тритон из Тайского залива Тритон из Тайского залива

Пикап Mitsubishi Triton давно и хорошо известен у нас под названием L200

4x4 Club
Паутина для клиента. Как российские банки превращаются в технологические компании Паутина для клиента. Как российские банки превращаются в технологические компании

Банки строят финансовые экосистемы, которые позволяют монетизировать big data

Forbes
«Нам не нужны роботы»: миллиардер Вадим Мошкович рассказал, для кого он открыл школу «Летово» «Нам не нужны роботы»: миллиардер Вадим Мошкович рассказал, для кого он открыл школу «Летово»

Интервью с миллиардером Вадимом Мошковичем в открытой им школе «Летово»

Forbes
Сардиния. Инструкция по применению Сардиния. Инструкция по применению

Я еду на запад, потому что на востоке уже везде был

4x4 Club
Состояние Билла Гейтса превысило $100 млрд Состояние Билла Гейтса превысило $100 млрд

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

Forbes
«Я очень сильно боялся летать» «Я очень сильно боялся летать»

Интервью с известным тревел-блогером Сергеем Долей

OK!
Почему важно воспитывать в детях скромность Почему важно воспитывать в детях скромность

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

Psychologies
Женщина, которая поет Женщина, которая поет

15 апреля у Аллы Пугачевой юбилей – 70 лет

Лиза
Расколотый мир: как я живу с рассеянным склерозом Расколотый мир: как я живу с рассеянным склерозом

История 29-летней Анастасии, болеющей рассеянным склерозом

Cosmopolitan
Внимание на старт Внимание на старт

Самые впечатляющие модели автомобилей класса люкс

Robb Report
Майкл Джей Фокс: «Я договорился с болезнью» Майкл Джей Фокс: «Я договорился с болезнью»

Майкл Фокс об отношениях с болезнью Паркинсона, ошибках и вере в лучшее

Psychologies
«Я отказалась от карьеры в пользу жизни» «Я отказалась от карьеры в пользу жизни»

Карьерному продвижению Эми Робертс предпочла жизнь менее стабильную и свободную

Psychologies
Слушайте меня! Искусство ведения диалога Слушайте меня! Искусство ведения диалога

Как научиться говорить так, чтобы к твоим словам прислушивались

Лиза
Искусство с видом на Кремль: как ГУМ стал арт-дилером Искусство с видом на Кремль: как ГУМ стал арт-дилером

Интервью с руководителем проекта ГУМ-Red-Line 2019 Игорем Казаковым

Forbes
В отеле «Балчуг Кемпински Москва» состоится шестая благотворительная барахолка В отеле «Балчуг Кемпински Москва» состоится шестая благотворительная барахолка

14 апреля благотворительная распродажа пройдет в отеле «Балчуг Кемпински Москва»

Cosmopolitan
Сила мысли Сила мысли

Как можно работать с мыслями — и почему стоит это делать

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