Optimierte Division mit zweierpotenzen

[Franky]

Hi Leute, hier mal ein kleines Beispiel, wie man die Division mit festen zweierpotenzen doppelt so schnell bewerkstelligt:

Code: Alles auswählen

#Compare=0

Global a,b,c.l,*adr1.long,*adr2.long,adr1.l,adr2.l
adr1=AllocateMemory(80000)
adr2=AllocateMemory(80000)

;Rechnung: c=a/8

Zeit=GetTickCount_()
   For b=1 To 99999
    CompilerIf #compare
     *adr1=adr1
    CompilerEndIf
     For a=-9999 To 9999
 !        MOV    eax,dword [v_a]
; !        MOV    ebx,dword [v_a]
 ;!        MOV    eax,ebx
 !        MOV    ebx,8
 !        CDQ
 !        IDIV   ebx
 ;!        MOV    ebx, eax
 ;!        MOV    dword [v_c],ebx
 !        MOV    dword [v_c],eax
     CompilerIf #Compare
       *adr1\l=c
       *adr1+4
     CompilerEndIf
   Next
 Next
zeit2=GetTickCount_()
   For b=1 To 99999
     CompilerIf #compare
      *adr2=adr2
     CompilerEndIf
;    CallDebugger
    For a=-9999 To 9999
!        MOV    ebx,dword [v_a]
!         SAR    ebx,3
!        MOV    dword [v_c],ebx
!         CMP    ebx,0
!         JNL l___div_end
!            SAL ebx,3
!           CMP dword[v_a],ebx
!            JE l___div_end
!               INC dword[v_c]
         __div_end:
     CompilerIf #compare
         *adr2\l=c
         *adr2+4
     CompilerEndIf
  Next
 Next
zeit3=GetTickCount_()
 
CompilerIf #compare
*adr1=adr1
*adr2=adr2
dif=0
For a=0 To 19998
     If *adr1\l<>*adr2\l
            INC dif
           Debug Str(a-9999)+"/8="+Str(*adr1\l)+"   SAR a,3="+Str(*adr2\l)+"  %8="+Str(a%8)
     EndIf 
     *adr1+4
     *adr2+4
Next 
CompilerEndIf 
MessageRequester("Ergebnis:","Freds Method: "+Str(zeit2-zeit)+"ms"+Chr(13)+"My Method: "+Str(zeit3-zeit2)+"ms"+Chr(13)+"Menge der Unterschiede: "+Str(dif))

Das erste stellt Freds Code Dar (aus dem ASM-Output kopiert). Das da drunter ist meins.

[NicTheQuick]

Bei mir siehts so aus:

Freds Method: 88867ms
My Method: 15212ms
Menge der Unterschiede: 0 (auch mit #compare = 1)

Also 5,84 mal so schnell.

[RSBasic]

Freds Method: 158219ms
My Method: 121562ms
Menge der Unterschiede: 0

[NicTheQuick]

@RSBasic:

Das wundert mich ein bisschen. Hattest du auch den Debugger aus? Dein
Prozessor ist nämlich sicherlich schneller als mein 1200-er.

[milan1612]

Freds Method: 43875ms
My Method: 7735ms
Menge der Unterschiede: 0

Ist also signifikant schneller

[RSBasic]

@RSBasic:

Das wundert mich ein bisschen. Hattest du auch den Debugger aus? Dein
Prozessor ist nämlich sicherlich schneller als mein 1200-er.

Nein, der war an.

Hab jetzt den Debugger ausgeschaltet:

Freds Method: 45891ms
My Method: 8625ms
Menge der Unterschiede: 0

[Kaeru Gaman]

> Das erste stellt Freds Code Dar (aus dem ASM-Output kopiert).

da stellt sich mir die frage, von welchem PB-code eigentlich?

ich persönlich würde z.b. eine zweierpotenz-teilung grundsätzlich so schreiben:

Code: Alles auswählen

Var >> 3

anstatt so

Code: Alles auswählen

Var / 8

ich bin jetzt zu faul, durch dein komisches gepointere durchzusteigen...

mich würde mal interessieren
a) wie soll ich deinen code einsetzen, wenn ich ne stinknormale variable teilen will
b) wie sieht deine demo aus, ergänzt um einen direkten vergleich mit Var >> 3

letzteres wollte ich eigentlich mal grad hinschreiben,
aber deine komischen adr-pointer sind mir jetzt zu aufwendig,
um da schnell nen vergleich hinschreiben zu können.

[PMTheQuick]

---------------------------
Ergebnis:
---------------------------
Freds Method: 30015ms
My Method: 8250ms
Menge der Unterschiede: 0
---------------------------
OK
---------------------------


Ziemlicher Unterschied

Gruss
PMTheQuick

[PMV]

> Das erste stellt Freds Code Dar (aus dem ASM-Output kopiert).

da stellt sich mir die frage, von welchem PB-code eigentlich?

ich persönlich würde z.b. eine zweierpotenz-teilung grundsätzlich so schreiben:

Code: Alles auswählen

Var >> 3

anstatt so

Code: Alles auswählen

Var / 8

ich bin jetzt zu faul, durch dein komisches gepointere durchzusteigen...

mich würde mal interessieren
a) wie soll ich deinen code einsetzen, wenn ich ne stinknormale variable teilen will
b) wie sieht deine demo aus, ergänzt um einen direkten vergleich mit Var >> 3

Richtig vermutet, wie schon als Kommentar angegeben verwendet Franky
den ASM-Output von

Code: Alles auswählen

;Rechnung: c=a/8

... wenn ich anstelle des ASM folgendes einsetzte

Code: Alles auswählen

c = a >> 3

ist Freds Optimierung besser ...
Fred: ~5500
Franky: ~7000
Das Problem hierbei ... Bitshift funktioniert natürlich nur bei Zahlen >= 0


Fals also mit negativen Zahlen zu rechnen ist, ist Frankys viel besser.

MFG PMV

[Kaeru Gaman]

Hi Leute, hier mal ein kleines Beispiel, wie man die Division mit festen zweierpotenzen doppelt so schnell bewerkstelligt:

...so und nun nenn mir mal den exponenten, den ich ner 2 geben muss, um ne negative zahl rauszubekommen....