Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Power-Funktion verschnellern?


ScorpionKing - Sa 09.04.05 08:10
Titel: Power-Funktion verschnellern?
Hi Leute,
ich brauche eine schnellere Funktion, die Power ersetzt. Also kennt jemand von euch einen Weg die Potenzierung ohne Power und natürlich schneller durchzuführen??

MfG, ScorpionKing!


Moderiert von user profile iconmatze: Topic aus Off Topic verschoben am Sa 09.04.2005 um 10:36


Phobeus - Sa 09.04.05 09:35
SHL? Wobei ich mir fast sicher bin, dass Power darauf zurpckgreift.


tommie-lie - Sa 09.04.05 10:02
user profile iconPhobeus hat folgendes geschrieben:
SHL? Wobei ich mir fast sicher bin, dass Power darauf zurpckgreift.
Power selbst nicht, höchstens der Compiler bei der Optimierung, aber selbst da wäre ich mich nicht sehr sicher...

Du könntest mal in den Fließkommabefehlssätzen (FPU, SSE, SSE2, 3DNow! und wie sie nicht alle heißen) nach einem Befehl suchen, der die Potenz ausrechnet. Ich habe eben beim Überfliegen der Standard-FPU-Befehle nichts gefunden, aber vielleicht findest du ja was.


retnyg - Sa 09.04.05 11:09
guck dir mal den code von delphifans typarser an. dadrin ist ne assembler power funktion, wenn ich mich richtig erinnere.


ScorpionKing - Sa 09.04.05 12:19
ja, okay, werde ich machen! danke!


Spaceguide - So 10.04.05 18:32
Wenn du immer zur gleichen Basis die Potenz berechnest, kannst du ja mal mit ln() und exp() herumspielen und das ln()-Ergebnis zwischenspeichern.


BenBE - So 10.04.05 20:19
Zum Wurzeln ziehen nutz ich diesen Source:


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
 
    PUSH    EAX
    FILD    DWORD PTR [ESP]

    FLDLN2
    FLD     TBYTE PTR [A]               // Load the input number
    FYL2X                               // Get the log out of it
    FDIVRP                              // Divide the log by N to get the N-th root's log
    FLDL2E                              // Calc e^(ln(N-th root)) --> N-th root
    FMULP   ST(1), ST(0)
    FLD     ST(0)
    FRNDINT
    FSUB    ST(1), ST(0)
    FXCH    ST(1)
    F2XM1
    FLD1
    FADDP
    FSCALE
    FSTP    ST(1)

    POP     EAX


Wenn Du das FDIVRP in Zeile 7 durch FMULP ersetzt, kannst Du damit Potenzieren. Davor gingen aber glaube für's reine Potenzieren noch einige Zeilen wegzulassen. Der kann aber speziell am Anfang noch etwas optimiert werden.


.Chef - Mo 11.04.05 12:49
Wenn ich jetzt noch wüsste, wo meine Assemblerversion von Power rumliegt ... :gruebel:

Edit: Gefunden! Und sogar kommentiert ...

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
 
function xfPower(a,b : Extended) : Extended;
asm
  ffree st(0)
  ffree st(1)
  fld   b          //b laden
  fld   a          //a laden
  fyl2x            //b*ln(a)
  fst   st(1)      //in st(1) kopieren
  frndint          //runden
  fsub  st(1),st   //Vorkommaanteil auf 0 setzen
  fld1             //1 laden
  fscale           //temp:="2 hoch Integer-Anteil"
  fld   st(2)      //Nachkommaanteil laden
  f2xm1            //"2 hoch Nachkommaanteil -1"
  fld1             //1 laden
  faddp st(1),st   //+1
  fmulp st(1),st   //*temp
end;


BenBE - Mo 11.04.05 13:00
BAsierend auf meinem Src aus dem vorigen Src, müsste das etwa so hier funktionieren:


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
 
Function ASMPower(A, B:Extended): Extended;
asm
    FLD     TBYTE PTR [B]
    FLDLN2
    FLD     TBYTE PTR [A]               // Load the input number
    FYL2X                               // Get the log out of it
    FMULP                               // Multiply the log by N to get the N-th powers's log
    FLDL2E                              // Calc e^(ln(a)*B) --> A^^B
    FMULP   ST(1), ST(0)
    FLD     ST(0)
    FRNDINT
    FSUB    ST(1), ST(0)
    FXCH    ST(1)
    F2XM1
    FLD1
    FADDP
    FSCALE
    FSTP    ST(1)
end;


Weiß aber jetzt grad nicht, in wie weit, ab dem FLDL2E noch was optimiert werden kann.


.Chef - Mo 11.04.05 13:04
Ach ja, sooo viel schneller als das normale Power ist meine Funktion nicht. Braucht etwa reichlich die Hälfte der Zeit ...


BenBE - Mo 11.04.05 13:17
Ab Zeile 8 entspricht meine Funktion dem normalen Power, was auch von Delphi genutzt wird. Ginge das noch optimaler?

@Chef: Wie sieht denn deine aus?


.Chef - Mo 11.04.05 13:21
user profile iconBenBE hat folgendes geschrieben:
@Chef: Wie sieht denn deine aus?
Siehe oben, habs reineditiert.


Sprint - Mo 11.04.05 13:26
http://dennishomepage.gugs-cats.dk/PowerChallenge.htm


BenBE - Mo 11.04.05 19:47
@Chef: Wozu die beiden FFREE-Zeilen am Anfang? Können die nicht weg?
Wenn die nur zum Freigeben von zwei Registern sind, dann werden sie nicht benötigt, da Delphi selber für einen leeren FPU-Stack sorgt (bei eigenen Routinen) und jegliche anderen Routinen ihre Daten auch wieder abräumen.


delfiphan - Mo 11.04.05 19:53
Übrigens: Meine Funktion ist mehr oder weniger nur eine geinlinte Version von Power :D


.Chef - Mo 11.04.05 20:12
@Ben: Keine Ahnung, was Delphi macht. Ich bin schließlich "Vintage"-Asm-Programmierer ...


delfiphan - Mo 11.04.05 20:15
@ScorpionKing: Ist deine Basis/Exponent ganzzahlig? Benützst du eine vorgegebene Basis (z.B. e)?
Übrigens: Für x^2 solltest du stets sqr(x) benützen und nicht Power(x,2) und auch nicht x*x.
Für ein ganz allgemeines "Hoch" wirst du wohl nichts finden, was viel schneller ist als Power.


BenBE - Mo 11.04.05 20:29
Naja, für y=x^2 kann man in ASM folgendes nehmen:


Delphi-Quelltext 
1:
2:
3:
4:
5:
 
Function Sqr(var X: Extended): Extended;
asm
    FLD     TBYTE PTR [X]
    FMUL    ST(0), ST(0)
end;


Für x^(2^n) braucht man einfach nur Zeile 4 wiederholen.


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
 
Function Power2N(var X: Extended; N: DWORD): Extended;
asm
    FLD     TBYTE PTR [X]
    MOV     ECX, N
    INC     ECX
    JMP     @@Start
@@Loop:
    FMUL    ST(0), ST(0)
@@Start:
    DEC     ECX
    JNS     @@Loop:
end;


//Edit: Source gefixt.


ScorpionKing - Di 12.04.05 14:13
danke! ihr habt mir schon sehr gut geholfen!


ScorpionKing - Mi 13.04.05 13:21
und gibt es dazu auch ein tutorial? (also zur berechnung mit assembler, wie oben in den power-funktionen verwendet?)


BenBE - Mi 13.04.05 22:47
Siehe Tut&Bücher-Sektion. Dort müsste ein Link zu Assembler aus der GE-Packt-Reihe stehen ... Ansonsten einfach dich mal umgucken: Zu ASM gibt's genug Quellen im Netz ...


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!