Reviews / articles about OS/2 |
Operating systems: ArcaOS, eComStation, IBM OS/2 Warp |
|
|
|
|
DATE: 2003-01-13 09:55:31 AUTHOR: Max Alekseyev
В последнее время появилось много проектов распределённых вычислений (см. обзоры здесь, тут или там), зазывающих всех желающих занять время простоя компьютера полезными и не очень вычислениями. Наиболее известным подобным проектом является взлом RC5, проводимый distributed.net, который в то же время относится к наиболее бессмысленным. Общая схема участия в том или ином проекте выглядит так: вы скачиваете клиента под свою платформу/операционную систему, настраиваете и запускаете его в фоне. Клиент периодически общается с сервером - запрашивает у него данные на обработку и отсылает результаты. При этом клиент выполняется в idle приоритете и не мешает основной работе. Таким образом, компьютер работает как и прежде, но уже никогда не простаивает. Если вы хотите принять участие в одном из проектов, немедленно
возникает вопрос какой из них предпочесть. Кажется разумным сравнивать
проекты распределённых вычислений по следующим критериям:
Я не ставлю перед собой цель дать исчерпывающую сравнительную характеристику различных проектов, а всего лишь хочу представить своего фаворита - проект GIMPS, в котором принимаю участие уже несколько лет. Ниже идёт подробное описание проекта по указанным критериям. Желающие смогут легко сравнить его с другими проектами. Итак, знакомьтесь: Great Internet Mersenne Prime Search (GIMPS) - широкомасштабный интернет-проект по поиску простых чисел Мерсенна. 1. Цели и методы проектаВ школе нас учат, что все натуральные числа большие единицы
разделяются на простые и составные. По определению число
называется простым, если оно имеет ровно два натуральных делителя:
единицу и само себя. Последовательность простых чисел начинается так: Определение того, является ли данное число простым или составным, в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, предложенный (и строго обоснованный теоретически) детерминированный алгоритм практически непригоден, в виду его большой (хотя и полиномиальной) сложности. Поэтому в криптографии с открытым ключом, где используются простые числа порядка 10300, простоту по-прежнему определяют с помощью эффективного вероятностного алгоритма Милера-Рабина. Важно отметить, что если практика довольствуется числами, являющимися простыми с вероятностью близкой к 1, то теория такие числа не приемлет: если про число утверждается, что оно простое, это должно быть строго доказано. Эта разница подчёркивается в разделение алгоритмов на вероятностные и детерминированные. Если мы зададимся вопросом, какое же наибольшее простое число известно человечеству - то ответом будет какое-то простое число Мерсенна. Простые числа Мерсенна имеют вид Mp = 2p-1. Заметим, что простота числа 2p-1 влечёт простоту p; в противном случае p=xy для x,y>1 и число 2p-1 = 2xy-1 не будет простым в виду делимости на 2x-1. Как следует из названия, целью проекта GIMPS является поиск новых простых чисел Мерсенна. Самое большое известное на данный момент простое число M13466917 = 213466917-1 было найдено в рамках проекта GIMPS в конце 2001 года. Более того, четыре (!) предыдущих рекорда также были получены участниками GIMPS. Числа Мерсенна выгодно отличаются от остальных простых чисел
наличием эффективного (детерминированного!) критерия их простоты,
носящего имя Люка-Лемера: Lk+1 = Lk2 - 2. Для поиска простых чисел Мерсенна сервер GIMPS раздаёт клиентам простые "экспоненты" p для проверки числа Mp на простоту. Клиент вычисляет последовательность чисел L1, L2, ..., Lp-1 по модулю числа Mp (т.е. вычисляются не сами числа Lk, длина которых растёт экспоненциально; а остатки от деления Lk на Mp, длина которых ограничена p битами). Если последнее число в этой последовательности получается нулевым, то по критерию Люка-Лемера число Mp является простым. На сегодняшний день достоверно известны только первые 38 чисел Мерсенна. Также найдено большое число Мерсенна, порядковый номер которого пока не установлен. 2. Практическая значимостьПростые числа Мерсенна интересны уже тем, что они стабильно удерживают рекорд как самые большие известные простые числа, что уже обсуждалось выше. Кроме того, простые числа Мерсенна играют важную роль в некоторых проблемах теории чисел. Например, тот же Евклид обнаружил, что если число Mp = 2p-1 простое, то число Mp(Mp+1)/2 = 2p-1(2p-1) будет совершенным, т.е. равно сумме своих собственных делителей (примеры таких чисел: 6=1+2+3, 28=1+2+4+7+14, 496=1+2+4+6+16+31+62+124+248), а Эйлер в последствии доказал, что все чётные совершенные числа имеют указанный вид (вопрос о существовании нечётного совершенного числа открыт до сих пор). Простые числа Мерсенна также применяются для построения генераторов псевдо-случайных чисел с большими периодами. Примером является Mersenne Twister. 3. Личная выгода от участияПлох тот солдат, который не мечтает стать генералом. Есть, конечно, альтруисты, которым интересен счёт ради счёта. Но многие люди питают надежду на успех и денежное вознаграждение. И не зря. Многие проекты распределённых вычислений так или иначе финансируются. И участник, нашедший на своём компьютере заветное значение/объект поиска, как правило, награждается кругленькой суммой. В этом смысле, такие проекты можно рассматривать как лотерею, в которой вы платите за участие своим компьютерным временем, считаете что-то полезное (или бесполезное), и имеете шанс выиграть приз. Причём, шанс на успех прямо пропорционален вложенным мощностям - как и в лотерее: чем больше билетов вы покупаете, тем больше вероятность выигрыша. GIMPS планирует выиграть награду в $100000, обещанную Electronic Frontier Foundation за нахождение простого числа из более чем 107 десятичных цифр. Из суммы этого приза планируется сделать выплаты всем "открывателям" простых чисел Мерсенна (до $5000 на каждое), авторам программного обеспечения, и авторам новых эффективных алгоритмов поиска (если таковые будут найдены). Заметим, что текущий рекордсмен M13466917 содержит чуть более 4000000 десятичных цифр. Таким образом, для достижения планки в 107 цифр, GIMPS надо увеличить "экспоненту" (и соответственно длину числа) в 2.5 раза. Кроме денежного вознаграждения, имя открывателя навсегда будет записано в анналы математики. 4. Вероятность успехаЭвристические оценки показывают, что в интервале для p от 5255000 до 79300000 ждут своего открытия ещё 4 неизвестных простых числа Мерсенна. Подробную информацию о их возможном распределении, а также об ожидаемых трудозатратах на их нахождение, можно узнать на странице статистики проекта. 5. Наличие клиента под OS/2До недавнего времени участникам проекта, использующим OS/2, приходилось довольствоваться клиентом древней версии 18.1 датируемой 1999 годом, в то время как версии под другие OS ушли далеко вперёд. Меня это не устраивало. Поэтому, как только появилось достаточно свободного времени, я взялся за портирование последней версии клиента под OS/2. Теперь клиент версии 22.12 под OS/2 доступен для скачивания с официального сайта наряду с клиентами под другие OS. Как maintainer последних версий SysBar/2 хочу сказать о планах на будущее: планируется добавить к клиенту GIMPS возможность вывода текущего состояния в pipe для удобного отображения в PipeMonitor.
Дополнительная информация:
Комментарии:
|
|
|||||||||||||||||||||||||||||||||||||||
(C) OS2.GURU 2001-2021
