Rekursionseinstieg: Fakultät - Logikproblem!?

Danke - würde ich gerne mal mit testen aber ich nutze minGW als Compiler und der nutzt GAS statt NASM.
Brauche daher den Inline-Code in AT&T-Syntax statt Intel.

Habe bisher das als Umbau gemacht:

unsigned int fiboAsm(int n)
{
         __asm__ (
                "movl $n, %ecx \n\t"
                "movl $1,%eax \n\t"
                "movl $1,%ebx \n\t"


                "cmpl $2,%ecx \n\t"
                "jbe endek2 \n\t"
                "subl $2,%ecx \n\t"
"start: \n\t"
                "addl %ebx,%eax \n\t"
                "movl %eax,%edx \n\t"
                "subl %ebx,%edx \n\t"


                "loop start2 \n\t"
                "jmp ende \n\t"
"start2: \n\t"
                "addl %edx,%eax \n\t"
                "movl %eax,%ebx \n\t"
                "subl %edx,%ebx \n\t"
                "loop start \n\t"
                "jmp ende \n\t"
"endek2: \n\t"
                "movl %ecx,%eax \n\t"
"ende: \n\t"
        );
}

Allerdings gibt der Compiler mir folgende Fehlermeldung:

Zitat

[Linker error] undefined reference to `n'

Da ich sonst nichts mit Assembler zu tun habe weiß ich auch nicht wie ich die C-Variable n korrekt in den Inline-Assembler-Code integriere.

Jepp so geht es tatsächlich - Dankeschön.
Hier nun der Gesamtvergleich in C++:

#include <vector>
#include <windows.h>
#include <limits.h>


using namespace std;


unsigned long long fiboRek1(unsigned n){
         if (n<=1) return n;
         return fiboRek1(n-1) + fiboRek1(n-2);
}


unsigned long long fiboIt(unsigned n){
         std::vector<unsigned long long> v;
         v.push_back(0);
         v.push_back(1);
         for (long int i=2; i<=n; i++)
             v.push_back(v[i-1]+v[i-2]);  
         return v[n];
}


unsigned long long fiboRek2(unsigned long long);
unsigned long long fiboRek2(unsigned long long, unsigned long long, unsigned long long);


unsigned int fiboAsm(int n)
{
         __asm__ (
                "movl %0, %%ecx \n\t"
                "movl $1,%%eax \n\t"
                "movl $1,%%ebx \n\t"


                "cmpl $2,%%ecx \n\t"
                "jbe endek2 \n\t"
                "subl $2,%%ecx \n\t"
"start: \n\t"
                "addl %%ebx,%%eax \n\t"
                "movl %%eax,%%edx \n\t"
                "subl %%ebx,%%edx \n\t"


                "loop start2 \n\t"
                "jmp ende \n\t"
"start2: \n\t"
                "addl %%edx,%%eax \n\t"
                "movl %%eax,%%ebx \n\t"
                "subl %%edx,%%ebx \n\t"
                "loop start \n\t"
                "jmp ende \n\t"
"endek2: \n\t"
                "movl %%ecx,%%eax \n\t"
"ende: \n\t"
               : : "a" (n)
        );
}




int main(){
    unsigned i, x, n ;
    unsigned long long fibo;
    double T=10000;

    LARGE_INTEGER lStart, lEnd, lFreq;


    QueryPerformanceFrequency(&lFreq);

    printf("\nGr\x94\xE1tes maximal anzeigbares Ergebnis: %21llu\n\n", ULLONG_MAX); 
    printf ("Bis zu welcher Fibonacci-Zahl soll gerechnet werden?: ");
    scanf ("%d",&n);


    FILE * outfile = fopen( "FiboOut.txt", "w" );    
    fprintf(outfile, "    x              Fib(x)-Rek1    t-Rek1 [ms]            Fib(x)-Rek2  t-Rek2 [ms]              Fib(x)-It   t-It [ms]              Fib(x)-Asm  t-Asm [ms]");

    for(i=0; i<=n;i++){
             fprintf(outfile, "\n");
             fprintf(outfile, "%5d || ", i);
             QueryPerformanceCounter(&lStart);
             fprintf(outfile, "%21llu | ", fiboRek1(i));
             QueryPerformanceCounter(&lEnd);
             fprintf(outfile, "%10d || ", ((lEnd.QuadPart - lStart.QuadPart) * 1000) / lFreq.QuadPart);


             QueryPerformanceCounter(&lStart);
             for( x=0; x<=T; x++)
                  fibo =  fiboRek2(i);
             fprintf(outfile, "%21llu | ", fibo);
             QueryPerformanceCounter(&lEnd);
             fprintf(outfile, "%8.5f || ", (((lEnd.QuadPart - lStart.QuadPart) * 1000) / lFreq.QuadPart)/T);

             QueryPerformanceCounter(&lStart);
             for( x=0; x<=T; x++)
                  fibo =  fiboIt(i);
             fprintf(outfile, "%21llu | ", fibo);
             QueryPerformanceCounter(&lEnd);
             fprintf(outfile, "%8.5f || ", (((lEnd.QuadPart - lStart.QuadPart) * 1000) / lFreq.QuadPart)/T);

             QueryPerformanceCounter(&lStart);
             for( x=0; x<=T; x++)
                  fibo =  fiboAsm(i);
             fprintf(outfile, "%21llu | ", fibo);
             QueryPerformanceCounter(&lEnd);
             fprintf(outfile, "%8.5f || ", (((lEnd.QuadPart - lStart.QuadPart) * 1000) / lFreq.QuadPart)/T);
             }
   return 0;
}            


unsigned long long fiboRek2(unsigned long long n){
         if (n < 2) return n;
         return fiboRek2(1, 1, n);    
}


unsigned long long fiboRek2(unsigned long long a, unsigned long long b, unsigned long long n){
         if (n < 3) return b;
         return fiboRek2(b,  a + b, n - 1);    
}

Um dennoch genauer als eine Millisekunde zu kommen hab ich mich erstmal etwas anders beholfen bis jemand eine bessere Möglichkeit findet.
Laut den jetzigen Ergebnissen ist die Inline-Assembler-Variante klar die schnellste Methode gefolgt von der 2. Rekursionsmethode und dann der iterativen.
Bleibt dennoch das Problem mit der Bereichsüberschreitung ab Fib(47).

Hab das zum Testen auch mal bereits kompiliert in den Anhang ... ja "gehangen".

Edit: So hab jetzt die Methoden konsequent auf unsigned long long umgestellt um den Wertebereich so weit wie möglich zu vergrößern.
Außer natürlich bei der Assembler-Methode - die bleibt auf unsigned int (Will mir nicht vorstellen was man da für Kopfstände machen muss um unsigned long long hinzubekommen... )
Heißt bis auf die Assemblermethode kann man mit den anderen bis auf Fib(96) rechnen - dann ist Schluss.
Will man mehr muss man ganz andere, eigene und vor allem langsamere Variablentypen bemühen. (Ähnlich wie bei der bigint.au3)

Hi zusammen,
da es ja auch zwei Möglichkeiten gibt, Assembler direkt in AutoIt einzubinden, war ich mal so frei und habe die freundlicherweise schon von RAPTOR-ONE im Assemblercode vorgestellte Fibonaccifunktion "AutoItkompatibel" gemacht.

Die erste Variante benötigt keinerlei Includes, im Prinzip wird der Bytecode in den Speicher geschrieben und per Funktion dort aufgerufen. Man könnte das Script noch etwas "tunen", aber ich habe es der Übersichtlichkeit wegen so gemacht....
Die Zeiten sind kein Witz, ich vermute, daß die AutoIt-Timer einfach an die Grenzen kommen. Die Berechnung der Zahl (egal welche^^) erfolgt auf meinem Rechner in ca. zwei hundertstel Millisekunden
Da ist vom speed her nicht mehr viel zu verbessern denke ich

Für die 2. Variante benötigt man die Asm.AU3 autoit.de/wcf/attachment/7479/
Allerdings ist jetzt auch der Code wesentlich lesbarer. Da bei jedem Aufruf der Funktion der komplette Assembler gestartet werden muss, ist diese Variante nur sinnvoll, wenn es nicht auf die letzte hunderttausenstel Sekunde ankommt...
Ich habe die Mnemonics in Bytecode übersetzt, jetzt sieht man auch, woher der beim Beispiel 1 kommt^^

Andy:

das hatte ich auch gestern Abend noch probiert, aber ich weiß nicht, wie ich den Code sauber umwandeln kann.

Hier mein Versuch:

#include <ASM.au3>

; Initial an asm object
Global $Asm = AsmInit()
$n = 30
AsmReset($Asm) ;Zeilennummer Kommentar
AsmAdd($Asm, " mov ecx, " & $n ) ;0E
AsmAdd($Asm, " mov eax, 1" ) ;13
AsmAdd($Asm, " mov ebx, 1" ) ;19
AsmAdd($Asm, " cmp ecx, 2" ) ;1E
AsmAdd($Asm, " jbe $+19" ) ;21 jbe @endek2
AsmAdd($Asm, " sub ecx, 2" ) ;23
AsmAdd($Asm, "start: ")
AsmAdd($Asm, " add eax, ebx" ) ;26 fn2(ax) = fn1(ax) + fn(bx)
AsmAdd($Asm, " mov edx, eax" ) ;28 fn2(cx) = fn2(ax)
AsmAdd($Asm, " sub edx, ebx" ) ;2A fn1(dx) = fn2(dx) - fn(bx)
AsmAdd($Asm, " loop $+4" ) ;2C loop @start2
AsmAdd($Asm, " jmp $+E" ) ;2E jmp @ende"
AsmAdd($Asm, "start2: ")
AsmAdd($Asm, " add eax, edx" ) ;30 fn2(ax) = fn1(ax) + fn(dx)
AsmAdd($Asm, " mov ebx, eax" ) ;32 fn2(bx) = fn2(ax)
AsmAdd($Asm, " sub ebx, edx" ) ;34 fn1(bx) = fn2(bx) - fn(dx)
AsmAdd($Asm, " loop @start" ) ;36 loop @start
AsmAdd($Asm, " jmp $+4" ) ;38 jmp @ende"
AsmAdd($Asm, "endek2: ")
AsmAdd($Asm, " mov eax, ecx" ) ;3A
AsmAdd($Asm, "ende: ")
AsmAdd($Asm, " ret ") ;3C

ConsoleWrite(String(AsmGetBinary($Asm)) & @CRLF)

$Ret = MemoryFuncCall("int", AsmGetPtr($Asm))

MsgBox(0, "Demo 0: Fibonacci via Inline ASM", "Fibonacci (" & $n & ") = " & $Ret[0])

; Release the asm object
AsmExit($Asm)
Exit

Ich hatte trancexx gefragt, aber sie konnte / wollte mir nicht helfen!

Kannst du mir den Weg erklären, wie du das gemacht hast?

Danke,
UEZ

... ohne Worte...

... eigentlich wollte ich ja nur anmerken das der Unterschied nicht der Rekursion geschuldet ist sondern der Berechnung....
.... aber das jetzt sowas hier dabei enstanden ist.... ne....

Jungs ich hab ne Menge hierbei gelernt - Danke an ALLE!

Hi UEZ,

ähnlich war mein Versuch anfangs auch, allerdings bekam ich permanent Fehlermeldungen. Also habe ich den Binärstring in eine Datei geschrieben und diese mit dem Debugger IDA eingelesen. So fand ich heraus, daß der "AutoIt-Assembler" keine Vorwärts-Sprünge beim LOOP-Befehl auflösen kann!
Das heisst,

AsmAdd($Asm, " loop $+4" ) ;2C loop @start2
AsmAdd($Asm, " jmp $+E" ) ;2E jmp @ende"
AsmAdd($Asm, "start2: ")

funktioniert nicht!

Also habe ich die Zeilen mit

AsmAdd($Asm, "dec ecx"); ;ecx = ecx -1
AsmAdd($Asm, "jecxz $+F"); ;Jump to target , if ECX is Zero

angepasst, und nu gehts^^

Am meisten hat mich fasziniert, Programme direkt aus dem Speicher auszuführen. Man spart also den (im Vergleich zur Laufzeit der Funktion) extrem langsamen DLL-Aufruf. Ich habe leider von C nicht sonderlich viel Ahnung, vielleicht gäbe es eine Möglichkeit, "kompilierten" C-code direkt in den Speicher einzupflanzen (wie in meinem 1. Assemblerbeispiel). Dann bräuchte man die Umwege über den Assembler auch nicht mehr zu machen....

Ich benutze HIEW um die Hex Codes in die Datei und W32Dasm um den ASM Code angezeigt zu bekommen!

Ich habe auch das Bespiel von RAPTOR-ONE versucht in ASM zu bekommen, aber irgendwie will es nicht so richtig! Deins geht ja wunderbar.

Ich würde gerne wissen, woran das liegt.

Ich habe dein Beispiel mit der Demo3 (mein Versuch) erweitert:

Hier der Disassembler Code:

:00000000 55                  push ebp
:00000001 8BEC                mov ebp, esp
:00000003 8B8D08000000        mov ecx, dword ptr [ebp+00000008]
:00000009 C7C001000000        mov eax, 00000001
:0000000F C7C301000000        mov ebx, 00000001
:00000015 81F902000000        cmp ecx, 00000002
:0000001B 761C                jbe 00000039
:0000001D 81E902000000        sub ecx, 00000002
:00000023 03C3                add eax, ebx
:00000025 8BD0                mov edx, eax
:00000027 2BD3                sub edx, ebx
:00000029 67E202              loop 0000002E
:0000002C EB0D                jmp 0000003B
:0000002E 03C2                add eax, edx
:00000030 8BD8                mov ebx, eax
:00000032 2BDA                sub ebx, edx
:00000034 67E2EC              loop 00000023
:00000037 EB02                jmp 0000003B
:00000039 8BC1                mov eax, ecx
:0000003B 5D                  pop ebp
:0000003C C3                  ret

Weiß du, warum meins nicht funktioniert?

Danke,
UEZ

ja, wie schon geschrieben, der " AUTOIT-Assembler" bekommt es nicht auf die Reihe, einen LOOP mit "nach vorne" gerichteter Adresse auszuführen (bei deinem Autoit-Assembler Zeile 17) . D.h. dort ist irgendetwas im Code suboptimal/buggy. Also muß man sich behelfen und "zu Fuß" den Loop emulieren, also ecx decrementieren, auf Zeroflag testen und abhängig davon jumpen.
Was allerdings ohne weiteres funktionieren sollte, ist per irgendeinem Assembler den BYTECODE zu generieren und diesen dann auszuführen. Die Übergabeparameter müssen dann natürlich im bytecode per Hex(Binary($parameter)) ersetzt werden!

Zitat

einmal x86 und einmal x64

genau so siehts aus^^.
Da der Code auch bei "größeren" Projekten sehr kompakt wird, könnte man beide Funktionen abhängig vom BS implementieren, falls es wirklich mal auf Geschwindigkeit ankommen sollte.

Als Beispiel mal den CRC32-Checksum in Assembler:
Ich habe die Bytecodes wieder angefügt

/EDIT/ Dateigrößen von 22MB werden in 13 Millisekunden abgefertigt....

Zitat

Dann kann man gleich 2 Versionen erstellen, einmal x86 und einmal x64. Damit läuft es dann auch im 64bit-modus von AutoIt

Dazu habe ich noch eine Frage. Gesetzt den Fall, es wird mit AutoIt32 ein Script gebastelt, welches (Im eingefügten Bytecode) 64-Bit Befehle verarbeitet. Werden die dann auf einer 64-Bit-Maschine mit 32-Bit BS auch ausgeführt, oder führt das zu einer Schutzverletzung? Eigentlich sollte das BS davon ja überhaupt nichts mitbekommen, oder werden 64-Bitbefehle erkannt und nicht zugelassen?

Ich erwähnte oben, daß der Autoit-Code im Zusammenspiel mit dem Bytecode noch zu "tunen" sei...

$tCodeBuffer = DllStructCreate("byte[512]") ;Speicher für den assemblercode belegen
DllStructSetData($tCodeBuffer, 1, "0x558BECC7C100000000C7C001000000C7C30100000081F902000000761A81E90200000003C38BD02BD349E30D03C28BD82BDA67E2EEEB028BC15DC3") ;das ist der bytecode
$substruct = DllStructCreate("byte[4]", DllStructGetPtr($tCodeBuffer) + 5) ;position der Variablen im bytecode

For $i = 1 To 46 ;die Fibonaccizahlen von 1-46
DllStructSetData($substruct, 1, $i) ; Inhalt der Variablen an die Position im Bytecode setzen
$a = DllCall("user32.dll", "int", "CallWindowProcW", "ptr", DllStructGetPtr($tCodeBuffer), "int", 0, "int", 0, "int", 0, "int", 0);bytecode aufrufen, rückgabe in a[0]
ConsoleWrite("Die " & $i & ". Fibonaccizahl lautet " & $a[0] & " Berechnungszeit: " & $x & " ms" & @CRLF)
Next

Auf diese Art und Weise lassen sich nicht nur Variablen, sondern auch Pointer auf API-Funktionen übergeben. Da diese schon im Speicher stehen, entfällt das komplette (mit relativ viel Overhead verbundene) Procedere des DLL-Calls. Funktionsparameter in der richtigen Reihenfolge auf den Stack pushen, Funktionspointer in eax, Call eax, fertig....ggf werde ich dafür auch mal ein Beispiel machen. Gerade für sehr viele Funktionsaufrufe wird sich das lohnen, der Overhead fällt ja komplett weg!