Программа тестирования произвольных чисел Мерсенна (2^p-1) метода Люка-Лемера

[Виктор Смирнов]

Я разработал на delphi программу тестирования простоты произвольных чисел Мерсенна (2^p-1) с использованием метода Люка-лемера. Числа представлены в виде массивов 32-х разрядных элементов типа cardinal, основные процедуры реализованы на ассемблере, реализация в windows xp. Не могу найти аналоги для оценки быстроты программы. Мой интерес
был в том,чтобы научиться работать со сверхбольшими числами (в частности возводить в квадрат или делить по модулю 2^p-1). К примеру число 2^216091-1 состоит из 6753-х 32-х разрядных элементов.
Временные характеристики для степеней p(CPU 2,6 Ггерц, ОЗУ 1 Гбайт):
1. 2^2-1 <1 сек
2. 2^3-1 <1 сек
3. 2^5-1 <1 сек
4. 2^7-1 <1 сек
5. 2^13-1 <1 сек
6. 2^17-1 <1 сек
7. 2^19-1 <1 сек
8. 2^31-1 <1 сек
9. 2^61-1 <1 сек
10. 2^89-1 <1 сек
11. 2^107-1 <1 сек
12. 2^127-1 <1 сек
13. 2^521-1 <1 сек
14. 2^607-1 <1 сек
15. 2^1279-1 <1 сек
16. 2^2203-1 <1 сек
17. 2^2281-1 <1 сек
18. 2^3217-1 <1 сек
19. 2^4253-1 <1 сек
20. 2^4423-1 <1 сек
21. 2^9689-1 5 сек
22. 2^9941-1 5 сек
23. 2^11213-1 8 сек
24. 2^19937-1 46 сек
25. 2^21701-1 59 сек
26. 2^23209-1 1 мин 12 сек
27. 2^44497-1 8 мин 28 сек
28. 2^86243-1 1 час 1 мин 6 сек
29. 2^110503-1 2 час 8 мин 51 сек
30. 2^132049-1 3 час 32 мин 26 сек
31. 2^216091-1 15 час 58 мин 0 сек

[Виктор Смирнов]

Выставляю рабочую версию программы тестирования
чисел Мерсенна (для желающих проверить на своем ПК).
Чтобы не считать сутками, p (в этом варианте программы)
ограничено значением 132049, хотя проверялись начальные
вычеты для p=43112609 (по предварительным прикидкам
полный просчет для 46-го числа на моем ПК около 15000 лет).
Программа имеет 3 режима задания p:
- выбор из списка (простых чисел) пользователем вручную одного числа ;
- выбор из списка программой автоматически подряд диапазона чисел
с сохранением результата тестирования;
- ввод пользователем вручную прозвольного числа.
Флаг "Контрольная точка" служит при тестировании чисел
(p>132049) с сохранением в контрольной точке промежуточных вычетов
(сверхбольших чисел) в файле на диске с возможностью
возбновления тестирования данного числа с этой точки.
О себе. Я в прошлом системный программист на мейнфремах,
рабочий язык Ассемблер. Delphi использовал достаточно примивно
для интерфейса и сервиса, рабочие процедуры на ассемблере
с учетом специфики команд Intel для 32-х разрядных регистров
целочисленной арифметики. Жду ваших данных по прогонам на ваших ПК.
Программа с файлом простых чисел во вложении svv7744510.rar

[Виктор Смирнов]

По результатам прогона формируются краткие отчеты

[Виктор Смирнов]

Уважаемые коллеги!
Мною разработана программа на Ассемблере в Дельфи проверки делимости первых 105 000 000 чисел Мерсенна вида 2^p-1, где p - простое (Prime) ,
на простые делители d в интервале d= 2^1 ... 2^32-1. При этом делитель соответствует условию d=2*p*r+1, где r=1,2,3,...
Опытным путем было установлено, что отсутствуют делители для r=2*k , где k==1,3,5,7,...
На настоящий момент времени протестироано первые 4 000 000 чисел Мерсенна, из них делимых - 780435.
Скорость проверки - 50 000 чисел за 75 минут, Файл inform с результатами тестирования может быть выслан по e_Mail.
n-порядковый номер числа, p- степень, d- наименьший делитель числа.
Для примера начало файла inform
n p d
5. 11 23
9. 23 47
10. 29 233
12. 37 223
13. 41 13367
14. 43 431
15. 47 2351
16. 53 6361
17. 59 179951
19. 67 193707721
20. 71 228479
21. 73 439
22. 79 2687
23. 83 167
25. 97 11447
27. 103 2550183799
29. 109 745988807
30. 113 3391
32. 131 263
36. 151 18121
37. 157 852133201
38. 163 150287
39. 167 2349023
40. 173 730753
41. 179 359
42. 181 43441
43. 191 383
44. 193 13821503
45. 197 7487
47. 211 15193
48. 223 18287
50. 229 1504073


ВИКТОР СМИРНОВ, ТВЕРЬ

[Виктор Смирнов]

Уважаемые коллеги!
Предлагаю исходный текст рабочей программы (встраиваемой процедуры Дельфи) на Ассемблере,
реализующей алгоритм теста Люка-Лемера для определения простоты произвольных чисел Мерсенна.
Напомню суть теста: число Мерсенна M=2^p-1, где р-простое, будет простым, если построив последовательность
вычетов Vn (n=1...p-1) следущего вида: V1=4; Vn = (Vn-1*Vn-1 mod 2^p-1) -2 (n=2...p-1) получим Vp-1=0.
Для p<32 данный алгоритм реализуется тривиально, для p>32 есть определенные трудности.
В моей программе числа представлены в виде массивов 32-х разрядных элементов типа cardinal.
В приложении представлен текст рабочей версии функции test_lucas_lemer, результат работы которой булевское
значение. True - тестируемое число простое, false - составное. Маскимальное значение степени p (в программе
sp) определяется размерами массивов V (вычет) и W (квадрат вычета). Размер массива n расчитывается по
формуле n=p/32+1. Следующий этап написания более производительного варианта программы - программа
для многопроцессорной модели для паралльного вычисления разрядов массива W (в т.ч. для 64 - разр. процессоров).
Но не имею самого железа, а также ассемблер для него. Что мы хуже GIMS?
Извиняюсь за скудное комментирование в исходнике.
p.s. Пробовал вариант программы на чистом ассемблере. К удивлению работает на 20% медленнее, чем ассемблер в Дельфи.

[Demon_12]

Сообщение от Виктор Смирнов

Чтобы не считать сутками, p (в этом варианте программы)
ограничено значением 132049, хотя проверялись начальные
вычеты для p=43112609 (по предварительным прикидкам
полный просчет для 46-го числа на моем ПК около 15000 лет).

Все дело в умножении (возведении в квадрат, в данном случае). Классическое умножение растет пропорционально квадрату размера множителей. Если реализовать умножение при помощи Быстрого Преобразования Фурье, то там рост будет иметь линейную зависимость.
В моей реализации на Delphi, Фурье начинает обгон при размере в 512-1024 32битных слов, а при размере массива 1048576 двойных слов классика выполняется 18514 с (5 ч 8 м 34с), БФП 23,77 с!!! (P4 E5300 при загрузке 1 ядра) Как вам разница? Так что для 46-го понадобится пару месяцев.

[Виктор Смирнов]

Сообщение от Demon_12

В моей реализации на Delphi, Фурье начинает обгон при размере в 512-1024 32битных слов, а при размере массива 1048576 двойных слов классика выполняется 18514 с (5 ч 8 м 34с), БФП 23,77 с!!! (P4 E5300 при загрузке 1 ядра) Как вам разница? Так что для 46-го понадобится пару месяцев.

Уважаемый коллега. Вы могли бы поделиться исходным текстом вашей программы на Delphi? Заранее признателен Виктор Смирнов

[Rasheet]

>На настоящий момент времени протестироано первые 4 000 000 чисел >Мерсенна, из них делимых - 780435.
>Скорость проверки - 50 000 чисел за 75 минут, Файл inform с >результатами тестирования может быть выслан по e_Mail.
>n-порядковый номер числа, p- степень, d- наименьший делитель числа.
>Для примера начало файла inform

. . . .
>20. 71 228479
>21. 73 439
>22. 79 2687
>23. 83 167
>25. 97 11447

- А где делитель на №26 не простое число 101?

>27. 103 2550183799
>29. 109 745988807
>30. 113 3391
>32. 131 263
. . . .
>ВИКТОР СМИРНОВ, ТВЕРЬ[/QUOTE]

- А где делители на №№33-35 не простые числа Мерсенна
137, 139, 149?... Также нет делителей на другие непростые числа...

. . .
>Скорость проверки - 50 000 чисел за 75 минут, Файл inform
. . .

....)))) Хотя я понимаю, что инф. указанна не верно, например, чтобы найти делитель только лишь для №26 числа М101 для этой "быстрой 32 разрядной" ассемблерной программы может потребоваться всего то ничего 2-3 года. А на самом деле это всеголишь первое такое (немножко сложное) не простое число. А таких чисел (не простых чуть ли не каждое ~5....). Просто их делитель большеват.. А сколько времени может уйти например на поиск делителя числа М137, 139, 149 - у каждого такого числа время (на подсчеты) увеличивается в разы по мере размера числа Мерсенна...

Почему, бы, не попробовать оптимизировать (ускорить) погу вычисления с помощью новых технологий таких как использование параллельных регистров MMX, SSE? Кстати, можно использовать технологии CUDA.. Хотя все это уже используется и считается... - В интернете такие страсти по этому поводу описывают... (Используют большие ЭВМ)...

Рашит.

[Виктор Смирнов]

Уважаемый коллега! В программе проверяется делимость на числа d в интервале d= 2^1,...,2^32-1 (т.е. размер делителя не более одного 32 разр. слова). Цель программы - первичный отсев составных чисел Мерсеенна, а это примерно 20%.

[Виктор Смирнов]

Уважаемые коллеги!
На просьбу дать исходный текст теста Люка-Лемера, привязанный к Делфи,
я сформировал проект с простейшим варантом программы без всякого сервиса (в частности,
убрал работу с базой данных простых чисел, отсутствует возможность прерывания
вычислений и формирования файла "контрольной точки", и другое).
Исходные данные задаются в тексте программы.
Это - порядковый номер тестируемого числа Мерсенна (nPrime),
согласно нумерации их в базе простых чисел, и значение степени (sp).
Я меня база данных на 105 млн. первых простых чисел.
Эта программа может быть использована в учебных целях.
Виктор Смирнов.