Der Algo. basierst auf einem SPP = Strong Pseudo Prime Test zu festen Basen. Auf
http://primes.utm.edu/prove/prove2_3.html kannst du das nachlesen.
Zitat:
If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
If n < 4,759,123,141 is a 2, 7 and 61-SPRP, then n is prime.
besonders diese Passage ist interessant da sie bei meinem Algorithmus angewendet wird.
Zusätzlich wird aber ein schnellerer Test vorgschaltet der den Kandidaten zu den ersten 32 Primzahlen bis 137 testet. Es ist also eine einfache Trial Division falls der Kandidat < 137 * 137 ist.
Bei beiden Tests werden extensiv modulare Divisionen benötigt. Die CPU Laufzeit der Divisionen ist aber wesentlich schlechter als die der Multiplikation. Ergo: wird der erste schnelle Test nicht per Divisionen durchgeführt sondern per Multiplikationen, man "dividiert modular" indem man mit dem modualeren Inversen der kleinen Primzahlen zu 2^32 den Kandidaten testet.
Eine ähnliche "Ersetzung" der langsammen Divisonen habe ich auch im nachfolgendem SPP Test angewendet. Statt aber mit dem modularem Inversen zu arbeitet arbeitet der SPP Test, bzw. genauergesagt dessen modulare Exponentation in der sogenannten Montgomery Domain. Montgomery war ein Mathematiker der verschiede Tricks entdeckt hat, ua. eben auch seinen am meist bekannten "Montgomer Trick". Mit diesem ist es möglich eben eine modulare Exponentation so umzubauen das statt der vielen modularen Divisionen nur Multiplikationen benötigt werden.
Die obige
Unit ist dabei eine Weiterentwicklung meines ursprünglichen Sources, in einem Contest im FastCode Projekt. Mein ursprünglicher Source nutzte zb. eben nicht die Trialdivision zu den ersten 32 Primzahlen. Allereine schon dieser Test eliminiert eine sehr große Anzahl von zusammengesetzten Zahlen.
Bei beiden Tests lässt sich nun Assembler leider nicht vermeiden. D.h. eine reine PASCAL Imlpementation wäre eventuell zwar möglich würde aber einen enormen und unnötigen Overhead im erzeugten Compilat bedingen. Das ich also Assembler gewählt habe liegt im Grunde nur daran das nur damit bestimmte Operationen möglich waren. Zb. wird ein Überlauf bei mathem. Operationen durch die Auswertung der Prozessorflags als notwendiges Feature des Algorithmus durchgeführt. In reinem PASCAL hat man aber diese Möglichkeit nicht. Das der Code in Assembler ist liegt also nicht daran das er primär auf Performance entwicklet wurde, sondern nur daran das so die Möglichkeiten der CPU ausgenutzt werden konnten.
Zitat:
Du meinst bestimmt 'Big
Oh'
Ja, eben die Komplexität des Verfahrens die als Big O angegeben wird.
Hagen schrieb:
Zitat:
Der von euch verwendetet Algorithmus ist in seiner Komplexität viel zu schlecht.
Gruß Hagen