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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Как брат с сестрой создали в Томске бизнес с незрячими массажистами Как брат с сестрой создали в Томске бизнес с незрячими массажистами

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

Forbes
Почему нужно смотреть новый фильм Франсуа Озона Почему нужно смотреть новый фильм Франсуа Озона

Почему эта картина заслуживает вашего внимания и почему ее нужно поддержать

Esquire
Неандертальцы наследили на португальских пляжах Неандертальцы наследили на португальских пляжах

Археологи обнаружили на португальском побережье отпечатки ног неандертальцев

N+1
Viva la diva! Viva la diva!

Моника Беллуччи откладывает переезд в Португалию из-за молодого кавалера

StarHit
«Эффект кислого винограда»: как неудачи и страх провала мешают нам исполнять мечты «Эффект кислого винограда»: как неудачи и страх провала мешают нам исполнять мечты

Почему мы бессознательно обесцениваем то, что раньше вдохновляло?

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

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

OK!
Эд Стоппард: «Одна из главных причин смотреть «Падение ордена» — моя солидная борода!» Эд Стоппард: «Одна из главных причин смотреть «Падение ордена» — моя солидная борода!»

Во всю мощь разворачивается второй сезон «Падения ордена»

Maxim
Тайные миллиардеры: 9 человек, о чьем богатстве мы узнали из уголовных дел Тайные миллиардеры: 9 человек, о чьем богатстве мы узнали из уголовных дел

Слуги народа, у которых следователи обнаружили суммы более 1 млрд рублей

Forbes
Что будет, если отказаться от сладкого на 3 месяца (если ты на это способен, конечно) Что будет, если отказаться от сладкого на 3 месяца (если ты на это способен, конечно)

Сахар — это «фу», и мы все это знаем

Playboy
Лучшие шутки про первую фотографию черной дыры Лучшие шутки про первую фотографию черной дыры

Ученым наконец удалось запечатлеть горизонт событий, и это вызвало взрыв юмора

Maxim
От Питера до Москвы на электротяге: невероятно быстро и очень медленно От Питера до Москвы на электротяге: невероятно быстро и очень медленно

Jaguar I-Pace: быстрый, красивый, дерзкий и полностью электрический

Популярная механика
Техника на грани фантастики: «Сухой» КР-860 Техника на грани фантастики: «Сухой» КР-860

В конце 1990-х годов в России мог появиться самый большой пассажирский самолет

Популярная механика
Журнал Минобороны рассказал о том, что российские военные владеют боевой парапсихологией Журнал Минобороны рассказал о том, что российские военные владеют боевой парапсихологией

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

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

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

Tatler
Иллюзия правды: как нам навязывают убеждения Иллюзия правды: как нам навязывают убеждения

Мы часто не замечаем, как чужое мнение становится нашим

Psychologies
От фотохостинга к авиации: как сооснователь Pinterest развивает сервис воздушного такси От фотохостинга к авиации: как сооснователь Pinterest развивает сервис воздушного такси

Все мысли Пола Шарры заняты созданием воздушного электротакси

Forbes
Неверность партнера: какие могут быть причины? Неверность партнера: какие могут быть причины?

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

Psychologies
За семью печатями За семью печатями

«СтарХит» узнал детали закрытой вечеринки в честь юбилея Аллы Пугачевой

StarHit
«Грустно видеть, как горит часть нас». Что известно о пожаре в Соборе Парижской Богоматери «Грустно видеть, как горит часть нас». Что известно о пожаре в Соборе Парижской Богоматери

Власти Франции пока не делают однозначных выводов о причинах пожара в Нотр-Даме

Forbes
Новое открытие: 20 минут на природе почти избавляют нас от стресса. Почему и как? Новое открытие: 20 минут на природе почти избавляют нас от стресса. Почему и как?

А ты давно был на природе? Спойлер: парк тоже считается

Playboy
Дом, который построил Джон Дом, который построил Джон

Английское поместье Хэтфилд-хаус пользуется славой у кинематографистов

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

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

Forbes
Мы что-то упускаем Мы что-то упускаем

Что такое «синдром упущенной выгоды»

Добрые советы
Что будет, если бросить заниматься спортом? 5 изменений в организме (и когда их ждать) Что будет, если бросить заниматься спортом? 5 изменений в организме (и когда их ждать)

Что будет, если ты прекратишь тренироваться

Playboy
Обуть готов! Обуть готов!

Подростковый бизнес: редкие сникеры как символ социального статуса

Robb Report
Тревел-версия Тревел-версия

Блогеры из разных стран рассказали о бьюти-привычках их соотечественниц

Cosmopolitan
Елена Шлёнкина: «В России есть спрос на дизайн» Елена Шлёнкина: «В России есть спрос на дизайн»

Елена Шлёнкина — об истории интерьерной отрасли и о своём жизненном пути

SALON-Interior
Ценность впечатлений Ценность впечатлений

Импрессионисты и модернисты как самый стабильный сектор арт-рынка

Robb Report
Вне игры Вне игры

Тата Карапетян, героиня самого громкого светского расставания сезона

Tatler
Кремль, Путину. Экс-владельца «Югры» арестовали после письма Набиуллиной президенту Кремль, Путину. Экс-владельца «Югры» арестовали после письма Набиуллиной президенту

Эльвира Набиуллина писала о ситуации с банком «Югра» Владимиру Путину

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