Problem bei der Anwendung von des div Operators (Assembler)

[anku]

Hi,

ich versuche gerade mir (Inline) Assembler bei zu bringen und hab nun ein Problem bei der Verwendung des 'div' Operators. Mein kleines Programm soll einfach testen ob eine Zahl Prim ist oder nicht.
Am besten erstmal ein bissel Source. Ich hab ihn soweit ich es selbst verstehe Kommentiert

Delphi-Quellcode:

procedure Test4Prim( Value: Integer);
var Primat: Integer;
begin
        asm

                mov eax, Value          // Value => eax
                mov ecx, 2              // Teiler => ecx
                mov edx, 1              // edx initielisieren, damit edx <> 0
        @Loop:
                cmp eax, ecx            // Teiler und Zahl vergleichen

                je @Prim                // if eax = ecx then Prim

                push eax                // eax Sichern

                div ecx                 // eax durch ecx teilen (??)  hier bricht er ab..

                inc ecx                 // Inc( Teiler bzw ecx, 1)

                cmp edx, 0
                pop eax                 // eax wiederherstellen, da durch Division überschrieben

                jnz @Loop               // if RestDerDivision (edx) <> 0 then goto Loop ( ZeroFlag nicht gesetzt)
                jz @NotPrim             // if RestDerDivision (edx) = 0 then goto NotPrim ( es ist keine Primzahl)

        @Prim:
                mov Primat, 1           // Primat auf 1 setzen, wird für die Ausgabe abgefragt
                jmp @Exit               // gehe sofort nach Exit

        @NotPrim:
                mov Primat, 0           // Primat auf 0 setzen, wird für die Ausgabe benötigt
        @Exit:
                nop                     // Tu garnix IMHO die beste Anweisung, sollte es auch im Berufsleben geben :)

        end;
        if Primat = 1 then Writeln('Das war eine Primzahl')
        else Writeln('Das war keine Primzahl');
end;

an der Stelle
div ecx // eax durch ecx teilen (??) bricht das Programm einfach ab.. der Debuger meldet nix..

Kann mir jemand sagen was ich anders machen muss? Kann man womöglich nicht durch das ECX Register teilen?
Vielen Dank schonmal für eure Hilfe

MfG
anku

[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;

[anku]

Wow, vielen dank für die ausführliche Antwort!

Meine Variante geht ist sogar noch ineffektiver, da ich nicht bei der Wurzel halt mache, sondern noch munter weiter dividiere (für mehr reicht mein ASM skill noch nicht..)
Mir gehts im Moment auch noch nicht um die Effiziens sonder einfach darum irgendwas mit Assembler zu schreiben. Die Sache mit dem Primsieb ist natürlich auch interessant, nur möchte ich dass dann selber schreiben. In Delphi bzw OP hatte ich mir schonmal eins programmiert. An dein Assembler Sieb kommt es aber bestimmt nicht ran, wenngleich ich es so gut es ging 'optimiert' habe (gerade zahlen werden ausgelassen, ein bit entspricht einer Zahl..).

So ich werd dann gleich mal weiter mit den Mnemnonics quälen

MfG

Edit:

So, ich hab jetzt das EDX Register auf 0 gesetzt und nun funktioniert die Division! Ich hätte eigentlich gedacht, dass er den Inhalt des Registers überschreibt, egal welcher Inhalt drin ist.. Na gut, aber das war ja auch mein erster ASM Versuch