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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Долгая зима: как за пять лет изменились венчурные инвестиции в женские стартапы Долгая зима: как за пять лет изменились венчурные инвестиции в женские стартапы

Почему в России уменьшается объем финансирования проектов предпринимательниц

Forbes
Неожиданный поворот: 10 фактов из истории моды, которые тебя удивят Неожиданный поворот: 10 фактов из истории моды, которые тебя удивят

Арина Яганова перечисляет самые невообразимые факты из истории моды

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

Источником базальтов, добытых станцией «Чанъэ-6», была мантия из слоев Луны

N+1
«Смерть ребенка: горе может разрушить, а может помочь обрести смысл жизни» «Смерть ребенка: горе может разрушить, а может помочь обрести смысл жизни»

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

Psychologies
Ошибка выжившего: как Москва искажает представление о счастье и бесконечно производит зависть Ошибка выжившего: как Москва искажает представление о счастье и бесконечно производит зависть

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

Правила жизни
Москва 1930-х годов — в воспоминаниях итальянского писателя Курцио Малапарте: фрагмент романа Москва 1930-х годов — в воспоминаниях итальянского писателя Курцио Малапарте: фрагмент романа

Отрывок из романа "Бал в Кремле" Курцио Малапарте

Esquire
Мания величия Мания величия

Почему нужно было ждать целых 13 лет, чтобы сделать большой внедорожник

4x4 Club
Почему люди носят сандалии именно с носками? Всему виной Древняя Греция и СССР Почему люди носят сандалии именно с носками? Всему виной Древняя Греция и СССР

Вы тоже порабощены советской культурой и боитесь показывать ноги!

Playboy
Фальшивки XXI века: чем опасны нелицензионные картриджи для принтеров Фальшивки XXI века: чем опасны нелицензионные картриджи для принтеров

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

Популярная механика
Лев Лещенко: «Могу сам и обои поклеить» Лев Лещенко: «Могу сам и обои поклеить»

Певец Лев Лещенко раскрыл тайну, почему ни разу не изменил за 50 лет

StarHit
Бронебойный бесшумный “Удав Бронебойный бесшумный “Удав

Бронебойный бесшумный “Удав" замена ПМ?

Популярная механика
Сага о викингах: как Тор Хаген сделал миллиардное состояние на «круизах для думающих людей» Сага о викингах: как Тор Хаген сделал миллиардное состояние на «круизах для думающих людей»

Норвежец Тор Хаген организует океанские круизы не так, как это делают другие

Forbes
Под конвоем заботы. Как женщины отстаивают свое право на труд Под конвоем заботы. Как женщины отстаивают свое право на труд

Можно ли бороться с законами, запрещающими профессии для женщин

Forbes
6 распространенных заблуждений о тревоге 6 распространенных заблуждений о тревоге

Чрезмерное беспокойство ухудшает качество жизни

Psychologies
Все на выход Все на выход

Юлия Янина о том, как одевать звезд на «Оскара» и в Канны и как наряжаться самой

Vogue
Как российский конкурент IBM и Oracle завоевывает клиентов по всему миру Как российский конкурент IBM и Oracle завоевывает клиентов по всему миру

За что стартап Филиппа Денисова так ценят инвесторы и клиенты

Forbes
От рэпа до ножа — один баттл! От рэпа до ножа — один баттл!

Специальная правительственная комиссия по урегулированию хип-хоп-деятельности

Maxim
Опять завел свою пластинку… Опять завел свою пластинку…

С занудой жить нелегко

Лиза
Железный человек Железный человек

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

Tatler
ВТБ помог миллиардеру Гордееву рассчитаться с «ФК Открытие» ВТБ помог миллиардеру Гордееву рассчитаться с «ФК Открытие»

ВТБ рефинансировал кредиты структур Сергея Гордеева на 40 млрд рублей

Forbes
Рублевка на Лазурном берегу: виллы и поместья российских миллиардеров во Франции Рублевка на Лазурном берегу: виллы и поместья российских миллиардеров во Франции

У участников российского списка Forbes много недвижимости во Франции

Forbes
Президент «Русэнергосбыта» Михаил Андронов: Потребители энергии смогут зарабатывать на электросетях Президент «Русэнергосбыта» Михаил Андронов: Потребители энергии смогут зарабатывать на электросетях

Будут ли солнечные батареи и ветряные электростанции популярны в России

СНОБ
11 невероятных женщин с аутизмом и их истории, меняющие мир 11 невероятных женщин с аутизмом и их истории, меняющие мир

Удивительные и талантливые женщины с аутизмом

Playboy
Плавали, знаем Плавали, знаем

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

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

Хакатоны могут стать эффективным HR-инструментом

Forbes
Почему жертвы жестокого обращения часто не могут бросить своих мучителей? Почему жертвы жестокого обращения часто не могут бросить своих мучителей?

Что заставляет жертву вязнуть в мучительных отношениях?

Psychologies
Усинский тракт Усинский тракт

Дорожная часть обычно остаётся за кадром, но так бывает не всегда…

4x4 Club
«Я изменила, но наш брак распался задолго до этого» «Я изменила, но наш брак распался задолго до этого»

Измена — лишь свидетельство того, что все уже разрушено

Psychologies
3 крупнейших скандала, связанных с несоблюдением кибергигиены 3 крупнейших скандала, связанных с несоблюдением кибергигиены

Интересные скандалы, связанных с нарушением правил пользования Интернетом

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

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

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