Optimizer

remi_meier · Beitrag von **remi_meier** » 12.06.2005 19:11

Hm... und was heisst das

Naja, wenn ich Zeit find, werd ichs trotzdem mal einbauen..

Helle · Beitrag von **Helle** » 12.06.2005 23:00

Hallo Remi,
auf Wunsch eines einzelnen Herrn

hier eine IDIV-Version (als Test-Prog). Mir gefällt daran der erhöhte Aufwand nicht, aber kannst ja mal testen. Soll nur eine "Machbarkeitsstudie" sein; ein negativer Divisor sollte rel. leicht "nachzurüsten" sein (Absolut-Wert bilden, am Ende nochmal NEG wenn vorher negativ). Auf Registergrössen wurde auch nicht weiter geachtet; ist eben ein Test. Dafür geht der Werte-Bereich von -65335 bis +65335!

Code: Alles auswählen

   divisor.l=0
   shiftwert.b=0
   dividend.l=0
   faktor.l=0 
z.l=0
q.l=0

For dividend= -2000 To 2000
For divisor= 2 To 20

;----- Diese Routine dient zur Ermittlung von Faktor und Shiftwert für einen konstanten Divisor ----
MOV [v_shiftwert],16
MOV EBX,[v_divisor]
 
NOAND:

BSR EAX,EBX
ADD [v_shiftwert],AL
MOV CL,[v_shiftwert]
MOV EAX,1
SHL EAX,CL
MOV ECX,EBX
XOR EDX,EDX 
DIV ECX

PUSHAD
MOV EAX,[v_dividend]
   TEST EAX,80000000h
   JZ l_nominus0 
   NEG EAX
NOMINUS0: 
XOR EDX,EDX
DIV EBX
MOV [v_q],EDX
POPAD

CMP [v_q],0
JE l_plus

SHR EBX,1
CMP EDX,EBX
JB l_noplus
PLUS:
INC EAX
NOPLUS:
MOV [v_faktor],EAX
 
;-------------- Test ------------ 
MOV EAX,[v_dividend]
   TEST EAX,80000000h
   JZ l_nominus 
   NEG EAX
NOMINUS:
IMUL EAX,[v_faktor]
MOV CL,[v_shiftwert]
SHR EAX,CL
   TEST [v_dividend],80000000h
   JZ l_nominus1 
   NEG EAX
NOMINUS1: 
  MOV [v_z],EAX

;---------------- Test "herkömmliche Methode" ------------ 
MOV EAX,[v_dividend]
MOV EBX,[v_divisor]
CDQ
IDIV EBX

   MOV [v_q],EAX
;---------------------------------------------------------


CMP EAX,[v_z]
JE l_noerror

Debug "Error!"
Debug dividend
Debug divisor
Debug z
Debug q
End 

NOERROR:

Debug z
Debug q

Next 
Next 

End

Gruss
Helle

remi_meier · Beitrag von **remi_meier** » 13.06.2005 18:28

Hm.. cool

4x so schnell

Also wenn ich Zeit hab....

Danke auf jeden Fall

Helle · Beitrag von **Helle** » 14.06.2005 14:14

Hallo Remi,
freut mich das die falsche Routine so gut funktioniert

! Als ich gestern mir das Ganze nochmal in Ruhe ansah, dachte ich mich trifft der Schlag! Das war eine Testversion zur Ermittlung des Korrekturfaktors! Bei der Ermittlung der Werte darf natürlich der Dividend nicht auftauchen, der ist ja dort nicht bekannt. Man soll eben auch bei Testentwürfen schon aussagekräftige Variablen-Bezeichner wählen (dividend und nicht d1). Beim hinterher ändern für Weitergaben denkt man nicht weiter mit und schon ist es passiert...
Lange Rede, kurzer Sinn: Anbei die inzwischen für signed überarbeitete RICHTIGE Version (als Test-Version).
Ich kann natürlich sagen, ich wollte euch nur mal testen...

Code: Alles auswählen

;--- "Ersatz" für IDIV mit konstanten positiven Divisor. Für negativen Divisor ist gesonderte Routine angebracht.
;--- Divisor darf keine 2-er Potenz sein! Dafür gibt es Extra-Routinen
;--- Werte-Bereich Dividend von -65335 bis +65335
;--- Werte-Bereich Divisor von +3 bis +65335
   divisor.l = 0
   shiftwert.b = 0
   dividend.l = 0
   faktor.l = 0 
   kwert.l = 0
   multi.l = 0
   divi.l = 0
 
For dividend = -6533 To 6533
For divisor = 3 To 653
;(Werte in o.g. Grenzen willkürlich gewählt)   
;-------------------------------------------------------------------------------------------------------
;Diese Routine dient zur Ermittlung von Faktor, Shiftwert und Korrekturwert für einen konstanten Divisor
;Hier hat natürlich der Dividend nichts zu suchen!
    
           MOV [v_shiftwert],16
           MOV EBX,[v_divisor]

           BSR EAX,EBX
           ;JZ l_error       ;divisor ist Null
           ADD [v_shiftwert],AL
           MOV CL,[v_shiftwert]
           MOV EAX,1
           SHL EAX,CL
           MOV ECX,EBX
           XOR EDX,EDX 
           DIV ECX

           OR EDX,EDX
           ;JZ l_error
           JZ l_pot2        ;divisor ist 2-er Potenz! Normalerweise Sprung zu error, hier wegen Schleife nicht       

           MOV [v_kwert],0
           SHR EBX,1
           CMP EDX,EBX
           JBE l_noplus

           INC EAX
           JMP l_plus
NOPLUS:    MOV [v_kwert],1
PLUS:      MOV [v_faktor],EAX
;-------------------------------------------------------------------------------------------

;-------------- Test mit Multiplikation ------------  
           MOV EAX,[v_dividend]
           TEST EAX,80000000h
           JZ l_nominus 
           SUB EAX,[v_kwert]
           NEG EAX
           JMP l_nominus1 
NOMINUS:   ADD EAX,[v_kwert]
NOMINUS1:  IMUL EAX,[v_faktor]
           MOV CL,[v_shiftwert]
           SHR EAX,CL
           TEST [v_dividend],80000000h
           JZ l_nominus2 
           NEG EAX
NOMINUS2:  MOV [v_multi],EAX

;---------------- Test "herkömmliche Methode" ------------ 
;---- Das Kürzere ist nicht immer das Schnellere!
           MOV EAX,[v_dividend]
           MOV EBX,[v_divisor]
           CDQ
           IDIV EBX
           MOV [v_divi],EAX
;---------------------------------------------------------

           CMP EAX,[v_multi]
           JE l_noerror

Debug "Error!"
Debug dividend
Debug divisor
Debug faktor
Debug kwert
Debug multi
Debug divi
End 

NOERROR:

Debug multi
Debug divi

POT2:

Next divisor 
Next dividend

End

Gruss
Helle

remi_meier · Beitrag von **remi_meier** » 14.06.2005 16:07

LOL, ja, ich habe gestern mit PureFan ein wenig darüber geredet.
Naja, so lange ich es noch nicht eingebaut habe, ärgerts mich nicht

cu
Remi

Übrigens ein kleines Bugfixrelease zum download

Helle · Beitrag von **Helle** » 16.06.2005 12:44

Hier die Version ohne Werte-Einschränkung (aber positiver Divisor):

Code: Alles auswählen

;--- "Ersatz" für IDIV mit konstanten positiven Divisor. Für negativen Divisor ist gesonderte Routine angebracht.
;--- Divisor darf keine 2-er Potenz sein! Dafür gibt es Extra-Routinen
;--- Voller Werte-Bereich (signed long), aber erstmal nur positiver Divisor 
;----------------------------------- Helle, PB3.93, 16.6.2005 --------------------------------------
     
   divisor.l = 123
   shiftwert.b = 0
   dividend.l = 0
   faktor.l = 0 
   kwert.l = 0
   multitime.l = 0
   divitime.l = 0
   multiwert.l = 0
   diviwert.l = 0

;---------------------------------------------------------------------------------------------------
;Diese Routine dient zur Ermittlung von Faktor, Shiftwert und Korrekturwert für einen konstanten positiven Divisor

;----------------------------- Aussieben von Null und 2-er-Potenzen des Divisors -------------------
;---------------- wird benötigt, wenn in einer Testschleife auch der Divisor geändert wird ---------  
           MOV EAX,[v_divisor]
           AND EAX,7fffffffh           ;zur Sicherheit, falls doch negativ  
           MOV CL,31
           XOR DL,DL
WEITER:    SHR EAX,1
           ADC DL,0
           DEC CL
           JNZ l_weiter
           CMP DL,1
           JBE l_error                 ;kein oder nur ein Bit gesetzt (nur ein Bit=2-er-Potenz)  

;----------------------------------------- Eigentliche Routine -------------------------------------      
           MOV EBX,[v_divisor]
           AND EBX,7fffffffh           ;falls negativ, Vorzeichen weg     
           BSR EAX,EBX
           MOV [v_shiftwert],AL   
           MOV CL,[v_shiftwert]
           MOV EDX,1
           SHL EDX,CL
           MOV ECX,EBX
           XOR EAX,EAX 
           DIV ECX

           MOV [v_kwert],0
           SHR EBX,1
           CMP EDX,EBX
           JBE l_noplus

           INC EAX
           JMP l_plus
NOPLUS:    MOV [v_kwert],1
PLUS:      MOV [v_faktor],EAX
           
;-------------------------------------- Test für Division durch 123 --------------------------------
;---------------------------------------- Test mit Multiplikation ----------------------------------
  StartTime = ElapsedMilliseconds() 
 For i = 1 To 10000 
  For dividend = -56789 To 56789
 
           MOV EAX,[v_dividend]
           MOV EDX,85340853h           ;[v_faktor] für Divisor=123
           TEST EAX,80000000h
           JZ l_nominus 
           DEC EAX                     ;weil [v_kwert]=1. Bei Null kann Zeile komplett entfallen
           NEG EAX
           JMP l_nominus1              ;kann bei [v_kwert]=0 auch entfallen!
NOMINUS:   INC EAX                     ;weil [v_kwert]=1. Bei Null kann INC entfallen (nicht die Zeile!)
NOMINUS1:  MUL EDX
           SHR EDX,6                   ;[v_shiftwert] für Divisor=123
           TEST [v_dividend],80000000h
           JZ l_nominus2 
           NEG EDX
NOMINUS2:  MOV [v_multiwert],EDX
   
  Next dividend 
 Next i 
  
  multitime = ElapsedMilliseconds()-StartTime  
 
;---------------------------------------------------------------------------------------------------

;-------------------------------------- Test mit herkömmlicher Division ----------------------------
  StartTime = ElapsedMilliseconds() 
 For i = 1 To 10000 
  For dividend = -56789 To 56789
   
   MOV EAX,[v_dividend]
   
   CDQ 
   IDIV [v_divisor] 

   MOV [v_diviwert],EAX
    
  Next dividend 
 Next i 

  divitime = ElapsedMilliseconds()-StartTime 

;---------------------------------------------------------------------------------------------------
  multit$ = Str(multitime)
  divit$ = Str(divitime)
  multiw$ = Str(multiwert)
  diviw$ = Str(diviwert)

MessageRequester("Vergleichstest","Multiplikationszeit =  "+multit$+Chr(13)+"Divisionszeit         =  "   +divit$+Chr(13)+"Multiplikationsendwert   =  "+multiw$+Chr(13)+"Divisionsendwert           =  "+diviw$)
End 

ERROR:    ;irgendwas
End

Für Geschwindigkeitstest ohne zugeschalteten Debugger starten!

Gruss
Helle

Helle · Beitrag von **Helle** » 17.06.2005 17:32

Damit Remi keine Langeweile hat

: Hier die Version für negativen Divisor, ansonsten alles voller Wertebereich:

Code: Alles auswählen

;--- "Ersatz" für IDIV mit konstanten negativen Divisor. Für positiven Divisor existiert gesonderte Routine.
;--- Divisor darf keine 2-er Potenz sein! Dafür gibt es Extra-Routinen.
;--- Voller Werte-Bereich (signed long). 
;----------------------------------- Helle, PB3.93, 17.6.2005 --------------------------------------
     
   divisor.l = -123
   shiftwert.b = 0
   dividend.l = 0
   faktor.l = 0 
   kwert.l = 0
   multitime.l = 0
   divitime.l = 0
   multiwert.l = 0
   diviwert.l = 0

;---------------------------------------------------------------------------------------------------
;Diese Routine dient zur Ermittlung von Faktor, Shiftwert und Korrekturwert für einen konstanten negativen Divisor

;----------------------------- Aussieben von Null und 2-er-Potenzen des Divisors -------------------
;---------------- wird benötigt, wenn in einer Testschleife auch der Divisor geändert wird ---------  
           MOV EAX,[v_divisor]
           NEG EAX
           MOV CL,31
           XOR DL,DL
WEITER:    SHR EAX,1
           ADC DL,0
           DEC CL
           JNZ l_weiter
           CMP DL,1
           JBE l_error                 ;kein oder nur ein Bit gesetzt (nur ein Bit=2-er-Potenz)  

;----------------------------------------- Eigentliche Routine -------------------------------------      
           MOV EBX,[v_divisor]
           NEG EAX
           BSR EAX,EBX
           MOV [v_shiftwert],AL   
           MOV CL,[v_shiftwert]
           MOV EDX,1
           SHL EDX,CL
           MOV ECX,EBX
           XOR EAX,EAX 
           DIV ECX

           MOV [v_kwert],0
           SHR EBX,1
           CMP EDX,EBX
           JBE l_noplus

           INC EAX
           JMP l_plus
NOPLUS:    MOV [v_kwert],1
PLUS:      MOV [v_faktor],EAX
           
;-------------------------------------- Test für Division durch -123 -------------------------------
;---------------------------------------- Test mit Multiplikation ----------------------------------
  StartTime = ElapsedMilliseconds() 
 For i = 1 To 10000 
  For dividend = -56789 To 56789
 
           MOV EAX,[v_dividend]
           MOV EDX,85340853h           ;[v_faktor] für Divisor=-123
           TEST EAX,80000000h
           JZ l_nominus 
           DEC EAX                     ;weil [v_kwert]=1. Bei Null kann Zeile komplett entfallen
           NEG EAX
           JMP l_nominus1              ;kann bei [v_kwert]=0 auch entfallen!
NOMINUS:   INC EAX                     ;weil [v_kwert]=1. Bei Null kann INC entfallen (nicht die Zeile!)
NOMINUS1:  MUL EDX
           SHR EDX,6                   ;[v_shiftwert] für Divisor=-123
           TEST [v_dividend],80000000h
           JNZ l_nominus2 
           NEG EDX
NOMINUS2:  MOV [v_multiwert],EDX
   
  Next dividend 
 Next i 
  
  multitime = ElapsedMilliseconds()-StartTime  
 
;---------------------------------------------------------------------------------------------------

;-------------------------------------- Test mit herkömmlicher Division ----------------------------
  StartTime = ElapsedMilliseconds() 
 For i = 1 To 10000 
  For dividend = -56789 To 56789
   
   MOV EAX,[v_dividend]
   
   CDQ 
   IDIV [v_divisor] 

   MOV [v_diviwert],EAX
    
  Next dividend 
 Next i 

  divitime = ElapsedMilliseconds()-StartTime 

;---------------------------------------------------------------------------------------------------
  multit$ = Str(multitime)
  divit$ = Str(divitime)
  multiw$ = Str(multiwert)
  diviw$ = Str(diviwert)

MessageRequester("Vergleichstest","Multiplikationszeit =  "+multit$+Chr(13)+"Divisionszeit         =  "   +divit$+Chr(13)+"Multiplikationsendwert   =  "+multiw$+Chr(13)+"Divisionsendwert           =  "+diviw$)
End 

ERROR:    ;irgendwas
End

Gruss
Helle

remi_meier · Beitrag von **remi_meier** » 17.06.2005 18:14

Danke

Theoretisch hätte ich jetzt Zeit (alle Prüfungen sind durch), aber da zeichnet
sich schon wieder Arbeit am Himmel ab: Nächste Woche am Freitag habe
ich einen Programmierwettbewerb, da muss ich noch ein paar Algorithmen
lernen...
Immerhin machts Spass

Helle · Beitrag von **Helle** » 17.06.2005 18:25

Dafür wünsche ich Dir (und ich denke mal nicht nur ich) alles Gute!!!

Gruss
Helle

remi_meier · Beitrag von **remi_meier** » 25.06.2005 13:58

Danke!