О приближающих глобальное потепление негодяях

Всем привет, с вами снова фанатичный апологет огромных чисел и странных разделов математики. Когда-то давно я уже писал про бесконечный и медитативный процесс поиска красивых ракушек и камешков среди морского песка и гальки, приводил параллели с (не такой уж, как выяснилось) огромной процедурно-генерированной Вселенной No Man`s Sky, реальной Вселенной, ну и всякое такое.

Сегодня я продолжу брести по пляжу, всё дальше и дальше удаляясь от основательно обжитых регионов с шезлонгами, прибрежными кафешками, и всё ближе — к диким местам, куда, кажется, ещё не ступала нога человека и где лишь крики чаек и прочих бакланов дополняют шум прибоя.

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

Чтобы не повторяться, начну на том месте, где остановился в прошлый раз. Итак, есть ряд кажущихся некоторым странными людей, которые в виде хобби занимаются поиском простых чисел Мерсенна (далее ПЧМ). Делают они это уже примерно четверть века, аж с 1996 года. За столь долгий период, как вы понимаете, уже успело родиться и вырасти до сознательного возраста целое поколение, а какой прогресс произошёл в вычислительной технике — и вовсе говорить излишне. Тактовая частота процессоров тогда исчислялась десятками мегагерц, сравните с теми «монстрами», которые сейчас проживают в каждом чехле мобильного телефона, не говоря уж и десктопах и серверах.

Тем не менее, даже на таких, казалось бы, микроскопических мощностях, люди умудрялись находить ПЧМ.

Объёмы вычислений, конечно же, были куда ниже, чем в данный момент — по той простой причине, что и экспоненты двойки были меньше. Кстати говоря, объёмы работ в GIMPS`е (Great Internet Mersenne Prime Search) исторически исчисляются в гигагерцо-днях, каждый из которых представляет собой примерную производительность 1GHz Pentium 4 в течение суток.

И вот, если сравнить первое найденное GIMPS`ом ПЧМ, проверка которого на простоту занимает 0.05 ГГц*дней, с последним, найденным на данный момент, с его 257 «гигагерцами», то получается, что сложность вычислений за эти 25 лет выросла где-то в пять тысяч раз. Закон Мура нервно курит в сторонке.

Но хочу заметить, что и те 257 гигагерце-дней, которые я привёл в качестве примера — уже история. Просто потому, что у последнего найденного ПЧМ степень двойки составляет 82,5 миллиона, а за прошедшие с того момента два года фронт работ проекта добрался до 100 миллионов, где проверка на простоту стоит уже 380 гигагерце-дней.

Собственно говоря, именно к этой «круглой дате» я и приурочил написание заметки.

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


Однако, существует ряд вполне стройных с математической точки зрения размышлений, указывающих на то, что мы либо (не дай бог) пропустили какое-то число, ошибившись в расчётах, либо — имеем дело с аномалией распределения, существенно отличающейся от предыдущего набора данных. Говоря простым языком — «уже давно пора бы».


Возвращаясь от частного к общему, хочу поведать, каким же образом GIMPS справляется со столь стремительно возрастающей сложностью вычислений. Строго говоря — не только справляется, но и набирает скорость!

Происходит это благодаря совокупности причин, главная из которых — тот самый закон Мура, стабильно поставляющий нам всё более производительные устройства, а также — всё более дешёвые способы получить вычислительную мощность. Например — облака вроде Гугла, Амазона, в которых можно арендовать практически неограниченную компьютерную мощь. Вторая причина связана с первой — и представляет собой всё более широкое использование графических процессоров, работа с которыми имеет ряд нюансов, но в целом — GPU, в том числе специализированные, которыми можно попользоваться в тех же облаках, гораздо производительнее обычных процессоров на ряде операций, например — поиске делителей.

Помимо роста «вширь», существуют и причины ускорения, представляющие собой оптимизацию алгоритмов и использующего эти алгоритмы ПО. Да что там — в сообществе GIMPS уже неоднократно были открыты (именно открыты — в виде оригинальных научных исследований) новые математические феномены, пригодные для поиска ПЧМ. Адаптируются и интегрируются, разумеется, и внешние работы. Из последних успехов можно назвать реализацию взамен теста Люка-Лемера вероятностного алгоритма Миллера-Рабина с проверкой ошибок методом Роберта Гербикса, практически исключающую возможность неверного результата, а также использование VDF, "Verifiable Delay Function", благодаря которой стало возможным отказаться от проверочных тестов — при повсеместном использовании это нововведение, фактически, удвоит производительность проекта.

Но не алгоритмами едиными. Самое важное, как и в любой коллективной деятельности — это люди. Те самые, которые приближают глобальное потепление, сутками напролёт гоняя многочисленные компьютеры и серверы. Учёные, в том числе всемирно-известные математики, блестящие программисты, выжимающие всю мощь из видеокарт, и обычные, незаметные, но важные винтики проекта — энтузиасты, мало-помалу, экспонента за экспонентой, грызущие этот бесконечный кусок гранита. Правда, энтузиаст энтузиасту рознь — недавно, например, число гимпсовцев пополнил замечательный человек, миллиардер, филантроп… нет, не Тони Старк, но где-то рядом — Бен Дело, выделивший кусочек своих миллиардов на аренду десятка-другого серверных стоек и стремительно вырвавшийся в лидеры по выполняемой работе (ваш покорный слуга, кстати, занимает там лишь скромное 25-ое место):


Зачем все мы этим занимаемся? Универсального ответа нет. В прошлой заметке я уже описывал свои соображения — относительно того, что вижу некую красоту в столь огромных и в то же время простых числах (ну и про мерянье с инопланетянами, конечно). У других могут быть совершенно отличающиеся мотивы.

Так или иначе — до ста миллионов в экспоненте или после, рано или поздно, но очередное простое число Мерсенна мы непременно отыщем, торжественно вам обещаю. И, конечно же, приглашаю присоединиться к нашей вакханалии, благо — это совсем не сложно. Будем греть атмосферу вместе.