4. Primzahlenberechnung

Primzahlenberechnung

  • ?

    Hallo,

    volkard schrieb:

    afair heißt der befehl in assembler fsqrt [...]

    OK, ich habe etwas mit Google gefunden, allerdings verstehe ich als absoluter Anfänger nicht, wie ich das einsetzen muss, da ich bisher nur mit Ganzzahlwerten und -registern gearbeitet habe.

    Für meine Primzahlenberechnung ist ja letztlich die Wurzel nur interessant, weil ich durch jede Zahl bis zu der Wurzel teilen muss und auf einen Rest prüfen muss - ist der Rest gleich 0, ist es keine Primzahl.

    Es wäre sehr nett, wenn mir jemand erklären könnte, was an meinem Programm falsch ist - wenn jemand fsqrt passend einbauen kann, ist das sicherlich nett, weil der Befehl sicherlich wesentlich perfomanter ist als meine langatmige Schleife.

    Ich bedanke mich schon jetzt bei jedem, der sich damit Mühe gibt ...

    Mfg
    Claus von der Burchard

    0
  • V

    ich kann dir nicht mit assembler helfen. aber mit primzahl-dingen.

    fsqrt willste ja haben für sowas wie
    while(teiler<=sqrt(zahl))
    kannst das umgehen mit
    while(teiler*teiler<=zahl)

    0
  • C

    ... manchmal kommt man halt nicht auf die einfachsten Ideen. Ich werde das morgen mal umsetzen und hoffe, dass es dann geht.

    Was mir auch noch aufgefallen ist, dass ich das ganze nochmal so umbauen sollte, dass nur jede zweite Zahl geprüft wird. Wenn x nicht durch zwei teilbar ist, ist x auch nicht durch 4 teilbar. Damit sollte ich einen Geschwindigkeitsvorteil erhalten ...

    Gleichzeitig kann ich natürlich auch alle geraden Zahlen außer 2 von der Betrachtung ausschließen.

    Ich werde mich morgen noch mal melden, ob ich vorangekommen bin,
    bis dahin vielen Dank für die Hilfe,

    Schönen Gruß,
    Claus von der Burchard

    0
  • L

    Junge,
    warum machst du das nicht mit vb? Mit ASM bist du nur ein ganz kleines bisschen schneller.... oder machst du das, um asm zu lernen?

    0
  • V

    Lutz schrieb:

    Junge,
    warum machst du das nicht mit vb? Mit ASM bist du nur ein ganz kleines bisschen schneller.... oder machst du das, um asm zu lernen?

    am schluß manchmal sogar langsamer, weil man irgendwann sich nicht mehr traut, neue tricks einzubasteln.

    0
  • C

    Lutz schrieb:

    Junge,
    warum machst du das nicht mit vb? Mit ASM bist du nur ein ganz kleines bisschen schneller.... oder machst du das, um asm zu lernen?

    Hallo Lutz,

    erstens mache ich das, um Assembler zu lernen, außerdem habe ich ein Programm, wo ich eine sechsstellige Zahl habe und die nächste Primzahl brauche. Und ich denke schon, dass ich wesentlich schneller sein werde. Man bedenke, dass VB bei weitem nicht so schnell ist wie C++ - das ewige Manko.

    Ich werde mich jetzt um die Umsetzung kümmern ... mir ist übrigens noch aufgefallen, dass ich auf jeden Fall von unten zählen sollte, weil es wahrscheinlicher ist, dass eine Zahl durch 5 teilbar ist als durch 6743 - und so dürften im Schnitt Nicht-Primzahlen schneller erkannt werden ...

    Schönen Gruß,
    Claus von der Burchard

    0
  • C

    Hallo,

    ich habe meinen Code umgeändert - aber ich bekomme immer noch einen Überlauffehler, der mir immer noch nicht nachvollziehbar ist.

    Was ich mir vorstellen könnte, ist, dass das div falsch ist, weil ich damit auch bei einem separaten Aufruf Probleme hatte. Die Frage: Wenn ich durch ebx teile, müsste doch eax geteilt werden, wo auch das Ergebnis hinkommt, und der Rest müsste in edx, oder?

    So mein jetziger Code:

    .386
.MODEL FLAT

.CODE
_run:

init:           mov     ecx,[esp+4]             ;ecx = start value
                xor     ebx,ebx                 ;ebx = 0

search:         inc     ebx
                mov     eax,ecx
                div     ebx
                cmp     edx,0
                je      get_next

                mov     eax,ebx
                mul     ebx
                cmp     eax,ecx
                jng     search

gotprim:
                mov     eax,ecx
                ret     16

get_next:       inc     ecx    
                xor     ebx,ebx
                jmp     search

END _run

    Vielleicht kann mir ja jemand weiterhelfen ...

    Schönen Gruß,
    Claus von der Burchard

    0
  • M

    EDIT: sorry, ich hab diesen beitrag zeitgleich mit deinem getippt und deinen neuen code somit noch nicht gesehen.

    volkard schrieb:

    fsqrt willste ja haben für sowas wie
    while(teiler<=sqrt(zahl))
    kannst das umgehen mit
    while(teiler*teiler<=zahl)

    naja, keine schlechte idee um das problem zu umgehen, aber ich würde dennoch FSQRT vorziehen. wenn ich das richtig verstanden habe, dann müsste man für jede zahl, die auf prim untersucht werden soll, einmal die wurzel ziehen. bei der obigen idee müsste man bei jedem schleifendurchlauf multiplizieren, was sicherlich länger dauert. hier mal ein beispiel für FSQRT:

    fild dword ptr [variable]
fsqrt
fistp dword ptr [variable]

    das war jetzt TASM syntax, sollte aber auch so mit masm gehen.
    dann noch zu deinem code:

    dec     ebx

                cmp     ebx,0
                jne     found

    das CMP ist hier überflüssig. DEC setzt auch das zeroflag.

    found:          mov     eax,ecx
                div     ebx
                cmp     edx,0

    ich glaube du vergisst hier das EDX register. DIV mit 32-bit operand teilt EDX:EAX durch den entsprechenden operanden. also am besten vor dem teilen ein XOR EDX,EDX oder ein CDQ (wenn du sicher bist, dass das höchste bit von EAX=0 ist) ausführen.

    ach ja, wenn du FSQRT benutzen solltest, würde ich vorher testen ob der übergebene wert auch positiv ist. eine lokale variable wäre auch nicht verkehrt, da man nicht direkt die register benutzen kann. also ein kleiner stack frame á la:

    push ebp
mov ebp,esp
sub esp,4    ; 4 bytes für lokale variablen
...
...
mov esp,ebp
pop ebp
ret 4

    oh, wieso benutzt du eigentlich RET 16? ich dachte deine funktion hätte nur einen parameter.

    0
  • C

    malfunction schrieb:

    hier mal ein beispiel für FSQRT:

    fild dword ptr [variable]
fsqrt
fistp dword ptr [variable]

    das war jetzt TASM syntax, sollte aber auch so mit masm gehen.

    OK, aber wie würde ich das jetzt einbauen? Also, zum Beispiel mit cmp ... ich habe das noch nicht ganz überblickt ...

    malfunction schrieb:

    das CMP ist hier überflüssig. DEC setzt auch das zeroflag.

    OK, ist jetzt eh anders

    malfunction schrieb:

    found:          mov     eax,ecx
                div     ebx
                cmp     edx,0

    ich glaube du vergisst hier das EDX register. DIV mit 32-bit operand teilt EDX:EAX durch den entsprechenden operanden. also am besten vor dem teilen ein XOR EDX,EDX oder ein CDQ (wenn du sicher bist, dass das höchste bit von EAX=0 ist) ausführen.

    Ah, jetzt verstehe ich das. Siehe mein ganz neuer Code unten ...

    malfunction schrieb:

    oh, wieso benutzt du eigentlich RET 16? ich dachte deine funktion hätte nur einen parameter.

    Oh, da muss ich nochmal hinterfragen. Ich habe diese Art, das ganze per CallWindowProc auch nur von einem Turtorial ...

    Zu meinem neuen Code:
    Immerhin ruft er ihn auf. Nur hängt er jetzt in einer Endlosschleife *hm* 😞 . Vielleicht finde ich das jetzt selber, trotzdem nehme ich Hinweise natürlich gerne an.

    .386
.MODEL FLAT

.CODE
_run:

init:           mov     ecx,[esp+4]             ;ecx = start value
                xor     ebx,ebx                 ;ebx = 0

search:         inc     ebx
                mov     eax,ecx
                xor     edx,edx
                div     ebx
                cmp     edx,0
                je      get_next

                mov     eax,ebx
                mul     ebx
                cmp     eax,ecx
                jng     search

gotprim:
                mov     eax,ecx
                ret     16

get_next:       inc     ecx    
                xor     ebx,ebx
                jmp     search

END _run

    Schönen Gruß,
    Claus von der Burchard

    0
  • M

    ändere mal am besten XOR EBX, EBX in MOV EBX, 2 um. du scheinst hier immer durch 1 zu teilen, was natürlich ohne rest geht. danach inkrementierst du deine "start value" und setzt den zähler (EBX) wieder auf 0. dadurch teilst du beim nächsten durchlauf wieder durch 1. usw usw.

    oh, noch ne kleine frage am rande: soll die rückgabe die nächste primzahl sein die größer als oder größer/gleich dem parameter ist?

    0
  • C

    Natürlich, das ist es. Allerdings bin ich nicht ganz einverstanden:
    Es muss mov ebx,1 sein. Schließlich wird ebx ganz am Anfang inkremiert und ist somit bei 2.

    Die Funktion soll, so wie sie es tut, die nächste Primzahl finden, die größer oder gleich wie die Ausgangszahl ist. Das ganze kann man ganz einfach umändern, indem man am Anfang ein inc ecx setzt (OK, das wirst Du wahrscheinlich wissen 😉 ).

    Der Vollständigkeit halber die (hoffentlich) Final-Version:

    .386
.MODEL FLAT

.CODE
_run:

init:           mov     ecx,[esp+4]             ;ecx = start value
                mov     ebx,1                   ;ebx = 1

search:         inc     ebx
                mov     eax,ecx
                xor     edx,edx
                div     ebx
                cmp     edx,0
                je      get_next

                mov     eax,ebx
                mul     ebx
                cmp     eax,ecx
                jng     search

gotprim:
                mov     eax,ecx
                ret     16

get_next:       inc     ecx    
                mov     ebx,1
                jmp     search

END _run

    Aufruf in VB:

    Private Declare Function ASM_cdLong _
    Lib "user32" Alias "CallWindowProcA" _
   (ByRef asm As Long, _
    ByVal PA1 As Long, _
    ByVal PA2 As Long, _
    ByVal PA3 As Long, _
    ByVal PA4 As Long) As Long

    '...
    Static asm(10) As Long    ' C:\masm32\bin\prim.exe 06.04.2004 15:03:01 (GMT)

    If asm(0) = 0 Then
        asm(0) = &H4244C8B:   asm(1) = &H1BB:       asm(2) = &HC18B4300
        asm(3) = &HF3F7D233:  asm(4) = &H7400FA83:  asm(5) = &HF7C38B0D
        asm(6) = &H7EC13BE3:  asm(7) = &HC2C18BEC:  asm(8) = &HBB410010
        asm(9) = &H1:         asm(10) = &HDFEB&
    End If

    MsgBox ASM_cdLong(asm(0), 5, 0, 0, 0)

    So, jetzt teste ich gleich noch die Geschwindigkeit.

    Mfg
    Claus von der Burchard

    0
  • C

    Hallo,

    ASM ist wie erwartet schneller - allerdings nicht so sehr, wie ich gedacht hätte:

    ASM Time: 0,058107943886723 Sek
VB  Time: 0,174044466545329 Sek

    Allerdings verbraucht CallWindowProc auch ein wenig Zeit 😉 ...

    Ich danke allen, die mir geholfen haben auf dem langen Weg der Problemlösung ...

    Schönen Gruß,
    Claus von der Burchard

    0
  • R

    benche mal meinen versuch auf deinem system:

    __forceinline int IsPrimeasm(int num)
{
	__asm
	{
		mov Ecx,num
		mov Ebx,1
		mov edi,0
m1:
		add Ebx,2
		xor Edx,Edx
		mov Eax,Ecx
		div Ebx
		cmp edx,0
		jz m2
		cmp Ebx,Eax
		jb m1
		mov edi,1
m2:
		mov num,edi
	}
	return num;
}

    hatte ich mal in nem vc++ source, daher mußt du es ein bissl umschreiben, war damals ziemlich fix wenn ich mich recht entsinne.

    rapso->greets();

    0
Anmelden zum Antworten