Mail.ruПочтаМой МирОдноклассникиИгрыЗнакомстваНовостиПоискСмотриComboВсе проекты
, Источник: Forbes

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

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

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

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

Фото: Depositphotos

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

Десять лет спустя проблемой занялись два немецких математика, которые предложили еще более экономичный алгоритм — с числом шагов не больше чем N * logN * log (logN). Алгоритм Шёнхаге-Штрассена, однако, тоже не оптимален: эти же математики предположили, что возможно перемножать большие числа так, чтобы число шагов не росло быстрее чем N * logN. Однако ни предложить конкретный способ, ни даже доказать его возможность не удавалось вплоть до настоящего времени.

Именно эту задачу и решили Харви и Ван дер Хэвен. Они предложили способ построить именно такой алгоритм.

Насколько подобные математические приемы способны ускорить реальные вычисления? По словам Харви, чтобы перемножить два числа с миллиардом десятичных знаков, современному компьютеру понадобится около месяца. Применение алгоритма Шёнхаге-Штрассена позволит уложиться в 30 секунд. Алгоритм, способ построения которого предлагает сам Харви, справится с задачей еще быстрее. Более того, математики предполагают, что это, вероятно, и есть теоретически возможный предел скорости умножения, хотя строго доказать эту гипотезу им пока не удалось. Однако если это так, данную математическую задачу можно считать окончательно решенной.

Фото: Natalie Choi / UNSW
Перемножить два числа с миллиардом десятичных знаков, современному компьютеру понадобится около месяца. Применение алгоритма Шёнхаге-Штрассена позволит уложиться в 30 секунд.

Насколько большим должно быть число, чтобы алгоритм Харви-Ван-дер-Хэвена дал преимущество в скорости вычисления? «Понятия не имею», — честно отвечает Харви, однако в своей статье он приводит в качестве примера умножение, дающее результат 10214857091104455251940635045059417341952. Это действительно очень большое число: во всей видимой Вселенной, к примеру, содержится всего порядка 1080 элементарных частиц.

Однако тот факт, что столь большие числа не соответствуют количеству чего бы то ни было в реальном мире, вовсе не значит, что открытие математиков бесполезно. Умножение — неотъемлемая часть других вычислительных процедур, таких как деление или извлечение корней. Данный результат окажется полезным и тем, кто намерен вычислить много-премного знаков числа «пи» или, к примеру, расширить список известных человечеству простых чисел.

У этой работы есть еще одно интересное следствие. При обосновании преимуществ квантового компьютера нередко приводят в качестве примера алгоритмы шифрования. Эти алгоритмы часто построены на разложении очень больших чисел на множители. Квантовый «алгоритм Шора» справляется с этой задачей довольно легко, тогда как для классического алгоритма разложение достаточно большого числа потребует времени, сравнимого с возрастом Вселенной. Однако в этих примерах всегда неявно подразумевается, что эффективность классического алгоритма — величина, определенная раз и навсегда. Работа австралийского и французского математиков показывают, что это далеко не так. А вдруг математики будущего предложат настолько изящный классический способ разложения числа на множители, что существующие шифры легко можно будет взломать не только на квантовом, но и на классическом компьютере? Сравнение квантовых и классических алгоритмов некорректно, пока не показано, что и тот и другой действительно являются лучшими из теоретически возможных.

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

Это тоже интересно:

Поделись полезной статьей с друзьями — нажми одну из кнопок ниже!
Хиты продаж и новинки
Самые лучшие цены на смартфоны
Комментарии
32
ДОЛЬЧЕВИТА
математика - это песня! и, кстати, самый лучший способ лечения и профилактики слабоумия всякого: и старческого и юного - решение задач ))) гораздо эффективнее разгадывания ребусов и изучения иностранных языков!
СсылкаПожаловаться
dres sev
как можно писать о квантовом компьютере, если квантового компьютера не существует?
СсылкаПожаловаться
as.
В ответ на комментарий от Lexx История переписки7
Lexx
Если ты такой "от бога" диванный аналитик, безошибочно определяющий мировоззрение человека по двум сообщениям в интернетах, может ответишь? В каком состоянии находится мировоззрение у людей, которые под подобными статьями пишут про власть и депутатов?
СсылкаПожаловаться
Полностью читать то, что тебе пишут не судьба? ))
СсылкаПожаловаться
Lexx
В ответ на комментарий от as. История переписки6
as.
Перельман доказал, что односвязное многообразие ровно одно. Исходной идеей доказательства является использование так называемого «потока Риччи»: мы берем односвязное компактное 3-многообразие, наделяем его произвольной геометрией (т. е. вводим некоторую метрику с расстояниями и углами), а затем рассматриваем его эволюцию вдоль потока Риччи. ... Перельману путем преодоления неимоверных технических трудностей, с использованием тяжелого аппарата уравнений с частными производными, удалось внести поправки в поток Риччи вблизи особых точек таким образом, что при эволюции топология многообразия не меняется, особых точек не возникает, а в конце концов, оно превращается в круглую сферу. Звучит как записки шизофреника. По факту так и есть. Данная статья из этого же разряда. Ты сказал, что это наука. Я подозреваю, что-то не то с твоим мировоззрением как минимум. Безоглядно верить всяким небылицам, разве это признак умного человека?
СсылкаПожаловаться
Если ты такой "от бога" диванный аналитик, безошибочно определяющий мировоззрение человека по двум сообщениям в интернетах, может ответишь? В каком состоянии находится мировоззрение у людей, которые под подобными статьями пишут про власть и депутатов?
СсылкаПожаловаться
as.
По твоем словам, я однозначно понял, что: статья претендует на научность, но глупые люди не обсуждают эту статью в научном стиле. Моя точка зрения такова - статья, полная чушь. А чушь нельзя обсуждать серьезно. В одном согласен с тобой. Девяносто процентов комментаторов мэйл ру, имеют образование ниже уровня городской канализации.
СсылкаПожаловаться
Lexx
В ответ на комментарий от as. История переписки6
as.
Перельман доказал, что односвязное многообразие ровно одно. Исходной идеей доказательства является использование так называемого «потока Риччи»: мы берем односвязное компактное 3-многообразие, наделяем его произвольной геометрией (т. е. вводим некоторую метрику с расстояниями и углами), а затем рассматриваем его эволюцию вдоль потока Риччи. ... Перельману путем преодоления неимоверных технических трудностей, с использованием тяжелого аппарата уравнений с частными производными, удалось внести поправки в поток Риччи вблизи особых точек таким образом, что при эволюции топология многообразия не меняется, особых точек не возникает, а в конце концов, оно превращается в круглую сферу. Звучит как записки шизофреника. По факту так и есть. Данная статья из этого же разряда. Ты сказал, что это наука. Я подозреваю, что-то не то с твоим мировоззрением как минимум. Безоглядно верить всяким небылицам, разве это признак умного человека?
СсылкаПожаловаться
не путай, я сказал "статья, претендующая на научность". потому что за исключением пары человек статьи на этом ресурсе публикуют бездари. научными статьи тут быть не могут априори, не тот сайт и не та публика.
СсылкаПожаловаться
as.
В ответ на комментарий от Lexx История переписки5
Lexx
да, точно. кто-то "в школе так умножал", кто-то про повседневную жизнь россиян тут вещает, кто-то про власть, кто-то про жадных депутатов. под статьёй, претендующей на научность. хочешь сказать, они не тупые?
СсылкаПожаловаться
Перельман доказал, что односвязное многообразие ровно одно. Исходной идеей доказательства является использование так называемого «потока Риччи»: мы берем односвязное компактное 3-многообразие, наделяем его произвольной геометрией (т. е. вводим некоторую метрику с расстояниями и углами), а затем рассматриваем его эволюцию вдоль потока Риччи. ... Перельману путем преодоления неимоверных технических трудностей, с использованием тяжелого аппарата уравнений с частными производными, удалось внести поправки в поток Риччи вблизи особых точек таким образом, что при эволюции топология многообразия не меняется, особых точек не возникает, а в конце концов, оно превращается в круглую сферу. Звучит как записки шизофреника. По факту так и есть. Данная статья из этого же разряда. Ты сказал, что это наука. Я подозреваю, что-то не то с твоим мировоззрением как минимум. Безоглядно верить всяким небылицам, разве это признак умного человека?
СсылкаПожаловаться
Lexx
В ответ на комментарий от as. История переписки4
as.
По факту, ты оскорбил присутствующих тут людей, абсолютно не аргументируя свое поведение. Кроме слов про науку и тупых комментаторов, я лично не услышал ничего. Обьяснять словами - ты ничего не понимаешь в науке, удел демагога. Такому можно лишь "подзатыльником" ответить. Так что если что имеешь сказать, не балаболь, а аргументируй. Хотя я понял, что у тебя одна извилина и та, от шапки. Еще, предложение надо начинать с большой буквы. Вас, "псевдо-умных", любителей бросаться словами, даже этому не научили.
СсылкаПожаловаться
да, точно. кто-то "в школе так умножал", кто-то про повседневную жизнь россиян тут вещает, кто-то про власть, кто-то про жадных депутатов. под статьёй, претендующей на научность. хочешь сказать, они не тупые?
СсылкаПожаловаться
as.
В ответ на комментарий от Lexx История переписки3
Lexx
я не считаю себя самым умным. но то, как пишутся здесь "статьи" и как их комментируют, вызывает уныние. идиократия всё ближе.
СсылкаПожаловаться
По факту, ты оскорбил присутствующих тут людей, абсолютно не аргументируя свое поведение. Кроме слов про науку и тупых комментаторов, я лично не услышал ничего. Обьяснять словами - ты ничего не понимаешь в науке, удел демагога. Такому можно лишь "подзатыльником" ответить. Так что если что имеешь сказать, не балаболь, а аргументируй. Хотя я понял, что у тебя одна извилина и та, от шапки. Еще, предложение надо начинать с большой буквы. Вас, "псевдо-умных", любителей бросаться словами, даже этому не научили.
СсылкаПожаловаться
Lexx
В ответ на комментарий от as. История переписки2
as.
Алло, " не тупой"! Тут пишут такую хрень, что плакать хочется! Если бы математика была бы точной наукой, ракеты, доставляющие грузы на орбиту, были бы без рулевых двигателей. Так как использование точных наук предполагает расчет всех факторов, влияющих на полет!А доказывать людям что во вселенной - не более определенного количества частиц - это как раз для такого " не тупого" как ты. Видимо Энштейн для тебя - светило мировой науки? ( как пример).
СсылкаПожаловаться
я не считаю себя самым умным. но то, как пишутся здесь "статьи" и как их комментируют, вызывает уныние. идиократия всё ближе.
СсылкаПожаловаться
Петр Голубев
В ответ на комментарий от Lexx
Lexx
Ало, люди! Тут пишут про новое открытие в математике, возможно это приведёт к прорыву в сложных математических и научных вычислениях. Неужели стаду кроме как поср@ть в комментах ничего не интересно?
СсылкаПожаловаться
Вы правы. (
СсылкаПожаловаться
as.
В ответ на комментарий от Lexx
Lexx
Ало, люди! Тут пишут про новое открытие в математике, возможно это приведёт к прорыву в сложных математических и научных вычислениях. Неужели стаду кроме как поср@ть в комментах ничего не интересно?
СсылкаПожаловаться
Алло, " не тупой"! Тут пишут такую хрень, что плакать хочется! Если бы математика была бы точной наукой, ракеты, доставляющие грузы на орбиту, были бы без рулевых двигателей. Так как использование точных наук предполагает расчет всех факторов, влияющих на полет!А доказывать людям что во вселенной - не более определенного количества частиц - это как раз для такого " не тупого" как ты. Видимо Энштейн для тебя - светило мировой науки? ( как пример).
СсылкаПожаловаться
Сергей
на главной Мейла статья названа "новый трюк поразил интернет". Я так и не понял - суть трюка не описана, потом - это не трюк а просто более удобный способ. И ни слова о том, как интернет на это среагировал. Где "поразил"-то? Журналисты мейла только и умеют, что писать чушь, а когда им (даже вежливо) делаешь замечания - они тебя просто банят.
СсылкаПожаловаться
Lexx
Ало, люди! Тут пишут про новое открытие в математике, возможно это приведёт к прорыву в сложных математических и научных вычислениях. Неужели стаду кроме как поср@ть в комментах ничего не интересно?
СсылкаПожаловаться
Lexx
В ответ на комментарий от Арсен Османов
Арсен Османов
Да здравствует полная деградация.
СсылкаПожаловаться
читаешь комментарии и понимаешь. действительно деградация. что все эти люди несут? почему они такие тупые?
СсылкаПожаловаться
иван петров
"Новостя" однако... очень поможет в повседневной жизни россиян!!!
СсылкаПожаловаться
Арсен Османов
Да здравствует полная деградация.
СсылкаПожаловаться
Андрей
Чушь какая-то, всегда так умножаю....
СсылкаПожаловаться
Бойко Борис
тоже мне открытие еще в школе так умножал
СсылкаПожаловаться
W T
В ответ на комментарий от Василий Алибабаевич
Василий Алибабаевич
А в чем суть способа? Ну покажите хотя бы на примере трехзначных чисел!
СсылкаПожаловаться
"Согласно оценкам, его преимущество проявляется начиная с чисел, имеющих не менее 10 000 десятичных разрядов." - Так что "столбиком" будет проще.
СсылкаПожаловаться
Чтобы оставить комментарий, вам нужно авторизоваться.
Вы не ввели текст комментария
Вы не ввели текст комментария
Обнаружили ошибку? Выделите ее и нажмите Ctrl+Enter.
Подпишитесь на нас