Welcome to eComStation.RU site!

Select your language: Russian English Deutch Spanish Italian Portuguese Czech Polish French

Frequently asked questions and answers:

eComStation.RU

ru · en · de · es · it · pt · cz · pl · fr
eComStation - это совершенно другая операционная система для PC (IBM OS/2 Warp)
Программы, новости, статьи, поддержка пользователей, оборудование, вопросы и ответы.
 
      Что такое OS/2?НовостиУстановкаОбновлениеПрименениеБудущееСообществоКупить    
(Карта сайта)

 
 
Списки протестированного OS/2 оборудования
Как получить драйверы OS/2 бесплатно

 
Обновление

 
Программы

 
(Санкт-Петербург)

 
Преимущества (1)

 
Разработчику (1)

 
(Пайпы программ)

 
Компании: (1)

 
История (1):

 
(Бонусы)

 
Советы:

 
(Барьеры и решения)

 
Технологии: (1)

 
(Применение в науке, лаборатории, ..)

 

 
Готовые решения:

 
Новая eComStation:

 
Будущее: (1)

 
(Ссылки на другие сайты)

 
(Картинка дня)

 
Артефакты OS/2

 
Гаджеты

 

Распределённые вычисления и проект GIMPS


TITLE: Распределённые вычисления и проект GIMPS

DATE: 2003-01-13 09:55:31

AUTHOR: Max Alekseyev

В последнее время появилось много проектов распределённых вычислений (см. обзоры здесь, тут или там), зазывающих всех желающих занять время простоя компьютера полезными и не очень вычислениями. Наиболее известным подобным проектом является взлом RC5, проводимый distributed.net, который в то же время относится к наиболее бессмысленным.

Общая схема участия в том или ином проекте выглядит так: вы скачиваете клиента под свою платформу/операционную систему, настраиваете и запускаете его в фоне. Клиент периодически общается с сервером - запрашивает у него данные на обработку и отсылает результаты. При этом клиент выполняется в idle приоритете и не мешает основной работе. Таким образом, компьютер работает как и прежде, но уже никогда не простаивает.

Если вы хотите принять участие в одном из проектов, немедленно возникает вопрос какой из них предпочесть. Кажется разумным сравнивать проекты распределённых вычислений по следующим критериям:

  1. Цели и методы проекта
  2. Практическая значимость
  3. Личная выгода от участия
  4. Вероятность успеха
  5. Наличие клиента под используемую OS (в нашем случае OS/2)

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

Итак, знакомьтесь: Great Internet Mersenne Prime Search (GIMPS) - широкомасштабный интернет-проект по поиску простых чисел Мерсенна.

1. Цели и методы проекта

В школе нас учат, что все натуральные числа большие единицы разделяются на простые и составные. По определению число называется простым, если оно имеет ровно два натуральных делителя: единицу и само себя. Последовательность простых чисел начинается так:
2,3,5,7,11,13,17,19,23,29,31,...
Ещё Евклид доказал, что простых чисел бесконечно много.

Определение того, является ли данное число простым или составным, в общем случае не такая уж тривиальная задача. Только в 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.

Числа Мерсенна выгодно отличаются от остальных простых чисел наличием эффективного (детерминированного!) критерия их простоты, носящего имя Люка-Лемера:
Число Mp является простым тогда и только тогда, когда оно делит число Lp-1, где числа Lk определяются рекуррентным соотношением:

L1 = 4,
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.


Буду рад любым пожеланиям/багрепортам, касаемым OS/2 версии клиента GIMPS,
Max Alekseyev


Дополнительная информация:

  • Дата публикации статьи: 2003-01-13 09:55:31 -- Max Alekseyev
  • Материал этой статьи распространяется на условиях лицензии GFDL

 

Попробуй программу:

Lucide - просмотр документов PDF/DjVu в eComStation.

Комментарии:

Vladimir Solovyov
2003-01-14 10:37:09

Забавно

Max
2003-01-14 21:22:09

Кстати, вот она же:

[url]

Gennady Kudryashoff
2003-01-17 16:36:28

Лучше бы спортировали Globus Toolkit под OS/2. ;-)

[url]

Ваpеный
2003-01-18 20:11:18

Полезная штука. Я думаю надо договоpиться с коpпоpацией Сеpенити Системс и встpоить GIMPS/2 клиент в eCS. Пpичем, чтобы он pаботал всегда и пpинудительно, а то вдpуг еще найдутся в миpе идиоты (!) котоpые не захотят искать такие полезные для науки данные.

Еще pаз, спасибо автоpу поpта.

шагал
2003-01-18 20:15:04

нихpена ничего не понял! зачем все это?

Max
2003-01-19 00:26:50

"Зачем все это? Лучше бы водки выпили..."

(c) из писем Белинского Гоголю

Max
2003-02-06 03:42:11

Новость от проекта GIMPS: завершена двойная проверка чисел меньших M(6972593), чем с большой долей вероятности доказано, что это число является 38-м простым числом Мерсенна.

Оригинал тут: [url]'>[e-mail]

Соответственно, просьба заменить в статье про GIMPS фразу

"На сегодняшний день достоверно известны только первые 37 чисел Мерсенна. Также найдены два больших числа Мерсенна, порядковые номера которых пока не установлены."

на фразу

"На сегодняшний день достоверно известны только первые 38 чисел Мерсенна. Также найдено большое число Мерсенна, порядковый номер которого пока не установлен."

Max
2003-02-15 12:30:59

Завтра-послезавтра выйдет версия клиента 22.13:

New features in Version 22.13 of primeos2

-----------------------------------------

+ High Resolution Timer support

+ Smart detection of running "another copy"

- 32-bit TCP/IP stack dependancy removed

bax
2003-02-17 09:17:40

А можно ли сделать такую же фичу, как в RC5-клиенте: отслеживать наличие ppp-соединения? А то ручками посылать результаты ломает как-то.

Max
2003-02-18 05:05:50

bax: вообще-то эта фича там есть - она просто ломиться в инет через определенные промежутки времени, пока не поймает момент наличия соединения. Посмотри внимательно настройки по primeos2 -m

Max
2003-05-28 22:40:32

Версия 23.4: [url]

Max
2006-03-21 23:57:48

Версия 24.14: [url]

Sendy
2006-04-06 16:07:23

Я тоже похожим занимаюсь, но больше привлекает физические и медицинские проекты. подробшей можно посмотреть на [url]

Alex_soldier
2016-06-14 04:34:02

Прошло 13,5 лет, и вот какие результаты появились в проекте GIMPS: В интервале для p от 5255000 до 79300000 оказалось не 4, а целых 10 простых чисел! Причем проверены еще не все претенденты! Номера счастливчиков: 40: 2^20,996,011 -1 41: 2^24,036,583 -1 42: 2^25,964,951 -1 43: 2^30,402,457 -1 44: 2^32,582,657 -1 45: 2^37,156,667 -1 46: 2^42,643,801 -1 47: 2^43,112,609 -1 48: 2^57,885,161 -1 49: 2^74,207,281 -1 Вероятно, проект не развивался бы так динамично, если бы не соперничество команд за места в рейтингах. Всего в проекте более 900 команд, борющихся за позиции в результирующих таблицах. Желающих поучаствовать приглашаю присоединиться к команде GIMPS.Russia - [url]

Прокомментируйте эту статью (напоминаем, автор работал над текстом несколько недель, уважайте мнение других).


Ваше имя:

Ваш E-Mail:

CODE:
......

  

Ваш комментарий:


Если в компьютере eComStation что-то не работает (USB глючит / сеть медленно / только 1 процессор / программы часто падают) - это не повод удалять ОС. Надо ее настроить. Вопросы и ответы eCSFAQ

Статьи

Операционная система
Программное обеспечение
Оборудование
Для разработчика
Разное
Колонка редактора


Готовая eComStation на SSD диске

 





Последний активный опрос: Какая высота барьера RPM?

IBM OS/2 Warp

 
Обучение новичков

Списки протестированного OS/2 оборудования

 
Статьи


   
  Почему eComStation?
Возможности
Особенности
Применение
Ролики и скриншоты
   eComStation для
для бизнесменов
для студентов и инженеров
для продавцов компьютеров
сообщество пользователей
   Разработчик
Распространить программу
Описание API, библиотеки
Начать новый проект
Конкурсы
   Программы
Он-лайн каталог
Выбрать через eCo Market
   Служба поддержки
Отправить вопрос
Купить eComStation
Вопросы и ответы
Обучение новичков
 
 
© 2001 - 2014 eCo Software, All rights reserved
eComStation is a registered trademark of Serenity Systems International
OS/2 Warp is a registered trademark of IBM Corporation
 

 

 
Картинка дня: