|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
|
#1
|
|||
|
|||
Тест проверки простоты чисел Мерсенна
Уважаемые коллеги!
Предлагаю исходный текст рабочей программы (встраиваемой процедуры Дельфи) на Ассемблере, реализующей алгоритм теста Люка-Лемера для определения простоты произвольных чисел Мерсенна. Напомню суть теста: число Мерсенна 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 - разр. процессоров). Но не имею самого железа, а также ассемблер для него. Извиняюсь за скудное комментирование в исходнике. p.s. Пробовал вариант программы на чистом ассемблере. К удивлению работает на 20% медленнее, чем ассемблер в Дельфи. |