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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Поп-стоицизм: как античная философская школа стала модной в современном мире Поп-стоицизм: как античная философская школа стала модной в современном мире

Как учение стоиков стало трендом и причем тут КПТ?

Forbes
Электрика вызывали? Электрика вызывали?

Мотоциклетные марки сдаются на милость электромобильности одна быстрее другой

Robb Report
Известный по единственному крылу вид козодоев оказался гибридом Известный по единственному крылу вид козодоев оказался гибридом

Как ученые раскрыли одну из главных орнитологических загадок спустя 35 лет

N+1
Смена курса. Какой разворот в экономике произошел после майского указа Путина Смена курса. Какой разворот в экономике произошел после майского указа Путина

В 2018 году обозначился поворот в направлении экономики предложения

Forbes
11 способов становиться немного умнее каждый день 11 способов становиться немного умнее каждый день

Интеллект, как и тело, требует правильного питания и регулярных тренировок

Psychologies
Что скрывал король гламура Что скрывал король гламура

Сергей Зверев пришел на «Прямой эфир» без привычной блестящей короны

StarHit
Мама, я хочу в Доминикану! Мама, я хочу в Доминикану!

Доминикана: страна, где орхидея – сорняк, а девушка – произведение искусства

Cosmopolitan
Кому добавки? Кому добавки?

Нуж­ны ли нам пи­ще­вые до­бав­ки для кра­со­ты ко­жи и во­лос?

Glamour
Гитлер и Сталин как полководцы Гитлер и Сталин как полководцы

Расследование военного историка Алексея Исаева

Популярная механика
Отцовский капитал. Сколько многодетных родителей в списке Forbes Отцовский капитал. Сколько многодетных родителей в списке Forbes

Кто из рейтинга 200 богатейших бизнесменов России обзавелся большой семьей?

Forbes
Черные дыры в кино, которые оказались ближе всего к правде Черные дыры в кино, которые оказались ближе всего к правде

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

Playboy
Трёхминутные медитации Трёхминутные медитации

Простые техники, чтобы улучшить настроение и снять стресс

Yoga Journal
Белошвейка, которая называла королеву сестрой Белошвейка, которая называла королеву сестрой

Герцогиня де Шеврёз — виртуозная политическая интриганка эпохи двух кардиналов

Дилетант
Время поколений действия. Как решить проблему финансирования венчурных проектов Время поколений действия. Как решить проблему финансирования венчурных проектов

В России на наших глазах происходит смена поколений предпринимателей

СНОБ
Поклонник красоты и простоты Поклонник красоты и простоты

Яну Хайцеэру есть что рассказать. Ведь он стоял у истоков внедорожного движения

4x4 Club
Обуть готов! Обуть готов!

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

Robb Report
Моя улица Моя улица

Вместо галерей у этих художников — городские стены

Собака.ru
Допинг для марафонца. Как зять Сергея Лаврова строит фармхолдинг на партнерстве с государством и связях Допинг для марафонца. Как зять Сергея Лаврова строит фармхолдинг на партнерстве с государством и связях

Как Александр Винокуров стал заметным игроком на российском фармрынке

Forbes
Финтех от физтеха Финтех от физтеха

Николай Сторонский построил компанию-единорог и попал в список Forbes

Forbes
Гаджеты – это новая форма близости Гаджеты – это новая форма близости

Гаджеты не могут быть причиной конфликтов в семье

Psychologies
Plastic positive — новый тренд: звезды, защищающие «улучшайзинг» Plastic positive — новый тренд: звезды, защищающие «улучшайзинг»

Сторонники plastic positive призывают не стесняться пластических операций

Cosmopolitan
Красочная война: спортивный пейнтбол Красочная война: спортивный пейнтбол

Спортивный пейнтбол — полноценная спортивная дисциплина с четким регламентом

Популярная механика
«Сейчас испытываем нехватку то одного, то другого миллиарда»: Алексей Мордашов о богатстве, работе по 12 часов, ошибках и диете «Сейчас испытываем нехватку то одного, то другого миллиарда»: Алексей Мордашов о богатстве, работе по 12 часов, ошибках и диете

Отрывок беседы с миллиардером Алексеем Мордашовым

Forbes
«Русские не уловили сигнал». Сторонник Трампа призвал ввести новые санкции против России «Русские не уловили сигнал». Сторонник Трампа призвал ввести новые санкции против России

Сенатор Линдси Грэм заявил, что США должны ввести новые санкции против России

Forbes
6 неожиданных вещей, потрогав которые, нужно срочно мыть руки 6 неожиданных вещей, потрогав которые, нужно срочно мыть руки

На этих предметах бактерий больше, чем под бочком унитаза

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

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

Playboy
Цифровой обольститель. Легко ли найти любовь с помощью новых технологий Цифровой обольститель. Легко ли найти любовь с помощью новых технологий

Российский рынок дейтинга оценивается примерно в $66 млн, а мировой — в $5 млрд

Forbes
Фотопроект в честь Всемирного дня информирования об аутизме Фотопроект в честь Всемирного дня информирования об аутизме

В мире проживают около 24,8 млн людей с аутизмом

Cosmopolitan
Уютное местечко Уютное местечко

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

Лиза
Все будет хорошо Все будет хорошо

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

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