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