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

ForbesНаука

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

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

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

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

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

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

Natalie Choi / UNSW

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

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

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

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

Как фотограф Рино Бариллари снимал Одри Хепберн, принцессу Диану и 12 раз ломал ребра Как фотограф Рино Бариллари снимал Одри Хепберн, принцессу Диану и 12 раз ломал ребра

О том, почему профессия папарацци все еще жива и востребована

Forbes
Петр Кулешов: «Пить не перестал, но делаю это реже» Петр Кулешов: «Пить не перестал, но делаю это реже»

Ведущий о том, как борется со страшной болезнью и мошенниками

StarHit
Объект, обнаруженный на краю Солнечной системы, бросает тень на существование Девятой планеты Объект, обнаруженный на краю Солнечной системы, бросает тень на существование Девятой планеты

Чем уникален седноид на краю Солнечной системы, получивший прозвище «Аммонит»

Inc.
Что может разрушить даже самый счастливый брак? 3 строгих заповеди Что может разрушить даже самый счастливый брак? 3 строгих заповеди

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

Playboy
«Рапунцель» и «Румпельштильцхен»: как сказочницы сочиняли совсем не детские истории «Рапунцель» и «Румпельштильцхен»: как сказочницы сочиняли совсем не детские истории

О шести сказочницах, которые говорили о женской судьбе

Forbes
10 масок, которые мы носим 10 масок, которые мы носим

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

Psychologies
Смешные деньги Смешные деньги

Как устроена империя Александра Маслякова

GQ
Муж на час Муж на час

Николас Кейдж второй месяц добивается аннулирования четырехдневного брака

StarHit
Первая леди Украины: что мы знаем о Елене Зеленской Первая леди Украины: что мы знаем о Елене Зеленской

Будет ли Елена Зеленская принимать активное участие в политической карьере мужа

Forbes
Ясно, солнечно, позитивно Ясно, солнечно, позитивно

Яркий, полный жизни интерьер в Санкт–Петербурге — вызов дождливой погоде

SALON-Interior
Как платить телефоном вместо карты? Как платить телефоном вместо карты?

Рассказываем, как превратить свой телефон в электронный кошелек для оплаты

CHIP

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

Esquire
Бренд «Обама»: почему (и как) Мишель и Барак Обама стали только популярнее, уйдя из Белого дома Бренд «Обама»: почему (и как) Мишель и Барак Обама стали только популярнее, уйдя из Белого дома

Среди американцев Барак и Мишель Обама — самая популярная пара. Как так вышло?

Esquire
Последний сезон «Игры престолов»: интервью с лордом Варисом и Мелисандрой Последний сезон «Игры престолов»: интервью с лордом Варисом и Мелисандрой

Все обсуждают «Игру престолов», главную премьеру весны (а то и года)

Esquire
Добро пожаловать в «Твин Пикс» Добро пожаловать в «Твин Пикс»

Путешествие по местам съемок «Твин Пикс»

4x4 Club
Минюст против Спилберга: Сможет ли Netflix бороться за «Оскар» Минюст против Спилберга: Сможет ли Netflix бороться за «Оскар»

Нельзя просто ограничить Netflix возможность выдвигать фильмы на «Оскар»

Forbes
В США подросток заявил, что он — пропавший без вести Тимоти Питцен. Мальчика не могли найти восемь лет В США подросток заявил, что он — пропавший без вести Тимоти Питцен. Мальчика не могли найти восемь лет

Подросток сообщил полицейским, что он Тимоти Питцен, исчезнувший в 2011 году

Esquire
Финал близко: где смотреть «Игру престолов» 8 сезон онлайн? Финал близко: где смотреть «Игру престолов» 8 сезон онлайн?

Фанаты легендарного сериала ликуют: стартовал восьмой сезон «Игры престолов»!

CHIP
Высокое напряжение Высокое напряжение

Jaguar I-Pace, который даже в России уже научился ездить из Петербурга в Москву

Quattroruote
Смертельное ожирение: истории людей, сбросивших сотни килограммов Смертельное ожирение: истории людей, сбросивших сотни килограммов

Рассказываем, как разные люди с экстремальным весом ведут борьбу за жизнь

Cosmopolitan
Выбить глаз Лондону… Выбить глаз Лондону…

При первом знакомстве с Jaguar E-PACE возникают крайне реакционные мысли

4x4 Club
Студенты МГУ выиграли самый престижный в мире турнир по программированию Студенты МГУ выиграли самый престижный в мире турнир по программированию

Команда из МГУ победила на международной олимпиаде по программированию ICPC

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

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

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

ЦБ отмечает рост спекулятивных валютных операций

Forbes
Человек-амфибия: 9 мифов о Жак-Иве Кусто Человек-амфибия: 9 мифов о Жак-Иве Кусто

Исследователю, показавшему миру подводную жизнь, было чем удивить аудиторию

Вокруг света
«Теперь каждую таблеточку проверяю»: как Анастасия Нифонтова стала первой женщиной, покорившей «Дакар» «Теперь каждую таблеточку проверяю»: как Анастасия Нифонтова стала первой женщиной, покорившей «Дакар»

Что помогло мотогонщице Анастасии Нифонтовой проехать «Дакар» в зачете Original

Forbes
Очень при­ят­но, Джордж Очень при­ят­но, Джордж

Пят­на­дцать ми­нут в ком­па­нии Джор­джа Клу­ни — и все, вы обез­ору­же­ны

Glamour
Интернет возмущён сложностью игры Sekiro: Shadows Die Twice Интернет возмущён сложностью игры Sekiro: Shadows Die Twice

FromSoftware, как обычно, выпустили самую сложную игру сезона

Maxim
ЦБ решил не менять ключевую ставку. Как это скажется на валюте, фондовом рынке и кредитах? ЦБ решил не менять ключевую ставку. Как это скажется на валюте, фондовом рынке и кредитах?

ЦБ сохранил ставку на уровне 7,75%, однако допустил ее снижение во 2-3 кварталах

Forbes
Посмертная выставка коллекции Георгия Генса открылась в Малаге Посмертная выставка коллекции Георгия Генса открылась в Малаге

Собрание Георгия Генса впервые выставлено заграницей в новом формате

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