Problem bei der Anwendung von des div Operators (Assembler)

[negaH]

Doch man kann durch ECX und jedes andere Register dividieren. Aber bei einer 32Bit Division dividiert man tatsächlicher weise EDX:EAX also einen 64Bit Wert. Somit sollte EDX mit 0 initialisiert werden vor JEDER Division von EAX. Denn nach der Division enthält EAX die Teiler und EDX den Rest.

Also

EDX:EAX div ECX = EAX und
EDX:EAX mod ECX = EDX

Somit wird bei einer Divsion gleichzeitig Dividend und der modulare Rest berechnet.

Nun zu deinem Primzahl Problem. Du testest eine Zahl per Division durch alle kleineren Zahlen bis zur Wurzel der getesteten Zahl. Dieses Verfahren ist das asymptotisch ineffizenteste Verfahren. Einen Schritt besser kommst du wenn du nur durch alle Primzahlen kleiner der Wurzel testest. Du benötigst alle 6542 Primzahlen bis 2^16 um damit Zahlen bis 2^32 zu testen. Noch besser ist bei Zahlen bis 2^32 einen strengen Pseudo Primzahltest zu den Bases 2,7,61 durchzuführen. Eine gute Impelementation schafft es eine beliebige 32 Bit Zahl so in ca. 1200 Taktzyklen zu testen.

Die dahinterliegende Begründung findest du hier http://primes.utm.edu/glossary/page.php?sort=StrongPRP

Will man allerdings alle kleinen Primzahlen succesive berechnen so gibt es Primzahlsiebe die natrülich viel effizienter sind. Für alle Primzahlen bis 2^32 = 203.280.221 Stück würde ich dann ein 8/30 Comb Sieb benutzen. Eine Implementierung von mir berechnet alle diese Primzahlen innerhalb von 13 Sekunden.

Gruß Hagen

Delphi-Quellcode:

function IsPrime(N: Cardinal): Boolean; register;
// test if N is prime, do some small Strong Pseudo Prime test in certain bounds
// not PIC safe !!
// very fast, about 1200 clockcycles
// copyright by Hagen Reddmann, don't remove this line
asm
       TEST  EAX,1            // Odd(N) ??
       JNZ   @@1
       CMP   EAX,2            // N == 2 ??
       SETE  AL
       RET
@@1:   CMP   EAX,73           // N  < 73 ??
       JB    @@C
       JE    @@E              // N == 73 ??
       PUSH  ESI
       PUSH  EDI
       PUSH  EBX
       PUSH  EBP
       PUSH  EAX              // save N as Param for @@5
       LEA   EBP,[EAX - 1]    // M == N -1, Exponent
       MOV   ECX,32           // calc remaining Bits of M and shift M'
       MOV   ESI,EBP
@@2:   DEC   ECX
       ADD   ESI,ESI
       JNC   @@2
       PUSH  ECX              // save Bits as Param for @@5
       PUSH  ESI              // save M' as Param for @@5
       CMP   EAX,08A8D7Fh     // N >= 9080191 ??
       JAE   @@3
// now if (N < 9080191) and SPP(31, N) and SPP(73, N) then N is prime
       MOV   EAX,31
       CALL  @@5              // 31^((N-1)(2^s)) mod N
       JC    @@4
       MOV   EAX,73           // 73^((N-1)(2^s)) mod N
       PUSH  OFFSET @@4
       JMP   @@5
// now if (N < 4759123141) and SPP(2, N) and SPP(7, N) and SPP(61, N) then N is prime
@@3:   MOV   EAX,2
       CALL  @@5
       JC    @@4
       MOV   EAX,7
       CALL  @@5
       JC    @@4
       MOV   EAX,61
       CALL  @@5
@@4:   SETNC AL
       ADD   ESP,4 * 3
       POP   EBP
       POP   EBX
       POP   EDI
       POP   ESI
       RET
// do a Strong Pseudo Prime Test
@@5:   MOV   EBX,[ESP + 12]   // N on stack
       MOV   ECX,[ESP +  8]   // remaining Bits
       MOV   ESI,[ESP +  4]   // M'
       MOV   EDI,EAX          // T = b, temp. Base
@@6:   DEC   ECX
       MUL   EAX
       DIV   EBX
       MOV   EAX,EDX
       ADD   ESI,ESI
       JNC   @@7
       MUL   EDI
       DIV   EBX
       AND   ESI,ESI
       MOV   EAX,EDX
@@7:   JNZ   @@6
       CMP   EAX,1            // b^((N -1)(2^s)) mod N ==  1 mod N ??
       JE    @@A
@@8:   CMP   EAX,EBP          // b^((N -1)(2^s)) mod N == -1 mod N ?? , EBP = N -1
       JE    @@A
       DEC   ECX              // second part to 2^s
       JNG   @@9
       MUL   EAX
       DIV   EBX
       CMP   EDX,1
       MOV   EAX,EDX
       JNE   @@8
@@9:   STC
@@A:   RET
@@B:   DB    3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
@@C:   MOV   EDX,OFFSET @@B
       MOV   ECX,18
@@D:   CMP   AL,[EDX + ECX]
       JE    @@E
       DEC   ECX
       JNL   @@D
@@E:   SETE  AL
end;