Alle geraden Fibonacci Zahlen summieren



  • Danke.
    Man kann noch den mathematischen Trick einbauen, daß man weiß, daß nur jede dritte Fibonacci-Zahl gerade ist.
    Und da kommt auch Dein Ping-Pong-Trick zum Tragen und harmoniert fein mit dem folgenden Ping-Swap.
    Die Schleife hat wie die vorige auch nur 7 Befehle, aber macht statt einem Fibonacci-Sprung gleich drei auf einmal und hat diesen unangenehmen bedingten Sprung nicht mehr in der Mitte.

    mov eax,1                    ;Ausgangsbedingungen, Aerni=1
    mov ebx,2                    ;und Bert = 2  // erste gerade Fibonaci-Zahl
    mov edi,0                    ;Initialisierung des Edi=Summe-Registers 
    
    Nochmal:                     ; do{
        add edi,ebx              ;   s+=b;  // aufsummieren der geraden zahlen
        add eax,ebx              ;   a+=b;  // ping
        add ebx,eax              ;   b+=a;  // pong
        add eax,ebx              ;   a+=b;  // ping
        xchg eax,ebx             ;   swap(a,b); //swap, damit die neue runde wieder mit ping beginnen darf
        cmp ebx,250000h          ; }while(b<=4000000);
        jle Nochmal              ; //Fortsetzung
    fertig:
       call Ausgabe              ; cout<<s;
    


  • der Thread hier wird immer interressanter...nachdem der arme Threaderöffner gar nicht die Möglichkeit in Betracht gezogen hatte, die Werte einfach per Taschenrechner (oder im Kopf) auszurechnen, in eine Tabelle zu schreiben und einfach auszulesen...

    Sonst:(@volkard) hinter dem label fertig: call Ausgabe - muß noch ein int 20h für das Programmende folgen, sonst landet der Returner im Nichts. Da die Ausgabe hier ja eigentlich nur das Ergebnis herausgeben soll, kann man die Registersicherungen weglassen und den Ret in ein Int 20h verwandeln. Man braucht sie auch nicht mehr callen, sondern nur noch hinter das Schleifenende schreiben:

    org 100h
    
    mov eax,1		     ;Ausgangsbedingungen, Aerni=1 
    mov ebx,2		     ;und Bert = 2  // erste gerade Fibonaci-Zahl 
    mov edi,0		     ;Initialisierung des Edi=Summe-Registers 
    
    Nochmal:		     ; do{ 
        add edi,ebx 	     ;   s+=b;  // aufsummieren der geraden zahlen 
        add eax,ebx 	     ;   a+=b;  // ping 
        add ebx,eax 	     ;   b+=a;  // pong 
        add eax,ebx 	     ;   a+=b;  // ping 
        xchg eax,ebx	     ;   swap(a,b); //swap, damit die neue runde wieder mit ping beginnen darf 
        cmp ebx,3d0900h	     ; }while(b<=4000000); 
        jle Nochmal 	     ; //Fortsetzung 
    
    Ergebnisprinter:		       ; cout<<s;
    	mov esi,10
    	mov eax,edi
    	mov ecx,0
    	mov ebx,0
    
    Konvertierloop:
    	mov edx,0
    	div esi
    	push edx
    	inc ecx
    	or  eax,eax
    	jnz Konvertierloop
    
    Printloop:
    	mov eax,00000200h
    	pop edx
    	add edx,30h
    	int 21h
    	loop Printloop
    Ende:
    int 20h
    

    das Programm ist jetzt sehr klein und sollte scheiße schnell sein - leider bringt diese schöne und genaue Programm auch gleich einen abstrusen Fehler hervor:
    Beim ersten Ausprobieren kam ein falscher Wert heraus, eine Runde zu früh ausgestiegen. Aber wieso?
    Musste mal wieder alles von Hand rechnen, blöde übermüdetheit, blöde komische
    Konverter...250000h !=4000000d !
    Der richtige Hexwert von 4 Mio ist nämlich ist 3d0900..*verkriech* und *schäm*

    naja, und hier wieder die Hexwerte, diesmal viel weniger, echt schön:

    G:\>debug fiboo.com
    -d
    193C:0100  66 B8 01 00 00 00 66 BB-02 00 00 00 66 BF 00 00   f.....f.....f...
    193C:0110  00 00 66 01 DF 66 01 D8-66 01 C3 66 01 D8 66 93   ..f..f..f..f..f.
    193C:0120  66 81 FB 00 09 3D 00 7E-E9 66 BE 0A 00 00 00 66   f....=.~.f.....f
    193C:0130  89 F8 66 B9 00 00 00 00-66 BB 00 00 00 00 66 BA   ..f.....f.....f.
    193C:0140  00 00 00 00 66 F7 F6 66-52 66 41 66 09 C0 75 EE   ....f..fRfAf..u.
    193C:0150  66 B8 00 02 00 00 66 5A-66 83 C2 30 CD 21 E2 F0   f.....fZf..0.!..
    193C:0160  CD 20 00 00 00 00 00 00-00 00 00 00 00 00 00 00   . ..............
    193C:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
    

  • Mod

    Jetzt wäre noch zu klären, ob die handgeschriebenen Assemblerprogramme schneller oder langsamer sind als das was optimierende Compiler aus den C++ Programmen machen...


  • Mod

    mov eax,0                    ;Ausgangsbedingungen, Aerni=0
    mov ebx,2                    ;und Bert = 2  // zweite gerade Fibonaci-Zahl
    mov edi,0                    ;Initialisierung des Edi=Summe-Registers
    
    Nochmal:                     ; do{
        add edi,ebx              ;   s+=b;  // aufsummieren der geraden zahlen
        lea eax,[ebx*4+eax]      ;   a+=4*b;// ping-pong-ping
        xchg eax,ebx             ;   swap(a,b); //swap, damit die neue runde wieder mit ping beginnen darf
        cmp ebx,250000h          ; }while(b<=4000000);
        jle Nochmal              ; //Fortsetzung
    


  • camper schrieb:

    mov eax,0                    ;Ausgangsbedingungen, Aerni=0
    mov ebx,2                    ;und Bert = 2  // zweite gerade Fibonaci-Zahl
    mov edi,0                    ;Initialisierung des Edi=Summe-Registers
    
    Nochmal:                     ; do{
        add edi,ebx              ;   s+=b;  // aufsummieren der geraden zahlen
        lea eax,[ebx*4+eax]      ;   a+=4*b;// ping-pong-ping
        xchg eax,ebx             ;   swap(a,b); //swap, damit die neue runde wieder mit ping beginnen darf
        cmp ebx,250000h          ; }while(b<=4000000);
        jle Nochmal              ; //Fortsetzung
    

    Werners +=4* mit lea. Da war ich auch dran, hab aber keine Doku gefunden, welche Quellregister lea erlaubt. Im Assemblercode sieht man irgendwie besser, was hübsch ist und was nicht. Kein Wunder, daß Knuth sich die Algos gerne in Assembler anschaut.



  • SeppJ schrieb:

    Jetzt wäre noch zu klären, ob die handgeschriebenen Assemblerprogramme schneller oder langsamer sind als das was optimierende Compiler aus den C++ Programmen machen...

    Werners

    int sum = 0;
        for( int prev_even = 0, fibo_even = 2; fibo_even < 4E6; std::swap( prev_even += 4*fibo_even, fibo_even ) )
            sum += fibo_even;
    

    von GCC übersetzt:

    movl	$2, %eax
    	xorl	%ecx, %ecx
    	flds	LC0
    	jmp	L8
    	.p2align 4,,7
    L16:
    	movl	%edx, %eax
    L8:
    	leal	(%ebx,%eax,4), %edx
    	addl	%eax, %ecx
    	movl	%eax, %ebx
    	movl	%edx, 28(%esp)
    	fildl	28(%esp)
    	fxch	%st(1)
    	fucomi	%st(1), %st
    	fstp	%st(1)
    	ja	L16
    

    campers

    int a=0;
    	int b=2;
    	int s=0;
    	do{
    			s+=b;
    			a+=4*b;
    			swap(a,b);
    	}while(b<=4000000);
    

    wird zu

    movl	$2, %eax
    	xorl	%ecx, %ecx
    	jmp	L7
    	.p2align 4,,7
    L10:
    	movl	%edx, %eax
    L7:
    	leal	(%ebx,%eax,4), %edx
    	addl	%eax, %ecx
    	movl	%eax, %ebx
    	cmpl	$4000000, %edx
    	jle	L10
    

    Warum meidet der Compiler xchg? Wenn wie hier zwei Register beteiligt sind, ist es doch schnell und hat kein LOCK eingebaut.

    Werners Code hat so viel f-Zeugs gehabt, weil 4e6 ein double ist. Das war natürlich nur Obfuskationsquatsch und hat in Schnellcode nichts zu suchen. Also statt 4e6 wieder 4000000.

    movl	$2, %eax
    	xorl	%ecx, %ecx
    	jmp	L7
    	.p2align 4,,7
    L13:
    	movl	%edx, %eax
    L7:
    	leal	(%ebx,%eax,4), %edx
    	addl	%eax, %ecx
    	movl	%eax, %ebx
    	cmpl	$3999999, %edx
    	jle	L13
    

    Auch durchaus in Ordnung. Auch ohne xchg.

    Und mein Code

    int main(){
    	int a=1;
    	int b=2;
    	int s=0;
    	do{
    			s+=b;
    			a+=b;
    			b+=a;
    			a+=b;
    			swap(a,b);
    	}while(a<=4000000);
    	cout<<s<<'\n';
    }
    

    wird zu

    movl	$2, %edx
    	movl	$1, %eax
    	.p2align 4,,7
    L6:
    	leal	(%edx,%eax), %ecx
    	addl	%edx, %ebx
    	leal	(%ecx,%edx), %eax
    	cmpl	$4000000, %eax
    	leal	(%eax,%ecx), %edx
    	jle	L6
    

    WAS? Er mag anscheinend lea.



  • Hätte nicht gedacht, dass dieses Thema auf so eine Resonanz stößt.
    😃


  • Mod

    volkard schrieb:

    Warum meidet der Compiler xchg? Wenn wie hier zwei Register beteiligt sind, ist es doch schnell und hat kein LOCK eingebaut.

    Weil es sich nicht mit den anderen Instruktionen paart. Aus diesem Grunde würde ich es im Allgemeinen vermeiden, solche einfachen Vertauschungen kann man ja auch durch simples Aufrollen auflösen.

    int a=0;
        int b=2;
        int s=0;
        do{
                s+=b;
                a+=4*b;
                if(a>4000000)
                    break;
                s+=a;
                b+=4*a;
        }while(b<=4000000);
    

    wobei das in diesem Fall nichts bringen dürfte.



  • Jetzt gehts zwar eher in die mathematische Richtung, aber ich denke mit dem Ansatz von Werner kann man die ganze Aufgabe in ein anderes Gewand bringen:

    f_{3n} = 4f_{3(n-1)} + f_{3(n-2)}, \quad n>1$$ und $$f\_3 = 2, f\_0 = 0

    Gesucht war $$\sum_{i=0}^nf_{3i} = f_{3n} + f_{3(n-1)} + \cdots + f_9 + f_6 + f_3 + f_0$$

    macht also $$\sum_{i=0}^nf_{3i} = (4f_{3(n-1)} + f_{3(n-2)}) + (4f_{3(n-3)} + f_{3(n-3)}) + \cdots + (4f_6 + f_3) + (4f_3 + f_0) + 2 + 0$$

    etwas anders geklammert: $$ = 5\sum_{i=0}^{n-1}f_{3i} - f_{3(n-1)} +2$$

    Das kann man noch ein paarmal (n-1 mal) machen und bekommt dann zusammen:

    i=0nf3i=5ni=0n1f3i+2n\sum_{i=0}^nf_{3i} = 5^n - \sum_{i=0}^{n-1}f_{3i} + 2n

    sieht jetzt nicht so aus als ob man viel gewonnen hätte, aber wenn man das jetzt imer wieder in sich selbst einsetzt, kommt am ende folgendes raus:

    i=0nf3i=i=0n(5i+2i)(1ni)\sum_{i=0}^nf_{3i} = \sum_{i=0}^n (5^i +2i)(-1^{n-i})

    Und weg sind die Fibonaccis 🙂 Wenn man jetzt noch das blöde Alternieren wegbekommen möchte, gilt für grade n (n=2k):

    i=02kf3i=i=0k(52i+2(2i))(52i1+2(2i1))=i=0k(452i1+2)=20i=0k25i1+k(k1)\sum_{i=0}^{2k}f_{3i} = \sum_{i=0}^k (5^{2i} +2(2i)) - (5^{2i-1} +2(2i-1)) = \sum_{i=0}^k (4\cdot5^{2i-1}+2) = 20\sum_{i=0}^{k}25^{i-1} +k(k-1)

    =20i=0k125i+500+k(k1)= 20\sum_{i=0}^{k-1}25^{i} + 500 + k(k-1)

    für ungerade n(n=2k+1):

    i=02k+1f3i=i=0k(52i+1+2(2i+1))(52i+2(2i))(50+20)=i=0k(452i+2)1\sum_{i=0}^{2k+1}f_{3i} = \sum_{i=0}^k (5^{2i+1} +2(2i+1)) - (5^{2i} +2(2i)) - (5^0+2\cdot 0) = \sum_{i=0}^k (4\cdot 5^{2i} + 2) - 1

    =4i=0k25i+k(k1)1= 4\sum_{i=0}^k 25^i +k(k-1) - 1

    die Frage ist jetzt obs für $$\sum_{i=0}^n 25^i$$ ne einfache Formel gibt...

    (und ob ich irgendwo n dicken schnitzer eingebaut hab)

    /edit: Kleiner nachtrag, bei unserem Problem mit 4000000 als größtem fibonacci-Index ist n = 1333333 (ungerade), k = 666666



  • Hihi. Für die Version "13 Apr 2010 21:53" habe ich so angefangen:

    s= f(3) + f(6) + f(9) + ... + f(3n)
    s=f(1)+f(2) + f(4)+f(5) + f(7)+f(8) + f(3n-2)+f(3n-1)
    also
    2s=f(1)+f(2)+f(3)+...+f(3n)
    also
    s=(f(1)+f(2)+f(3)+...+f(3n))/2



  • pumuckl schrieb:

    die Frage ist jetzt obs für $$\sum_{i=0}^n 25^i$$ ne einfache Formel gibt...

    Ja.
    s=25^0 + 25^1 + 25^2 + 25^3 + ... + 25^n
    //beide Seiten mal 25
    25s=25^1 + 25^2 + 25^3 + 25^4 + ... + 25^(n+1)
    //unten minus oben
    24s=25^(n+1)-1
    //beide Seiten durch 24
    s=(25^(n+1)-1)/24



  • pumuckl schrieb:

    =4i=0k25i+k(k1)1= 4\sum_{i=0}^k 25^i +k(k-1) - 1

    die Frage ist jetzt obs für $$\sum_{i=0}^n 25^i$$ ne einfache Formel gibt...

    (und ob ich irgendwo n dicken schnitzer eingebaut hab)

    /edit: Kleiner nachtrag, bei unserem Problem mit 4000000 als größtem fibonacci-Index ist n = 1333333 (ungerade), k = 666666

    Mal einsetzen...

    =4i=066666625i+666666(6666661)1= 4\sum_{i=0}^{666666} 25^i +666666(666666-1) - 1

    Mist, bei 25^666666 hat's nicht mehr gepaßt.



  • pumuckl schrieb:

    etwas anders geklammert: $$ = 5\sum_{i=0}^{n-1}f_{3i} - f_{3(n-1)} +2$$

    Das kann man noch ein paarmal (n-1 mal) machen und bekommt dann zusammen:

    i=0nf3i=5ni=0n1f3i+2n\sum_{i=0}^nf_{3i} = 5^n - \sum_{i=0}^{n-1}f_{3i} + 2n

    Möp, da war der Patzer. Die 5 Multipliziert mit der Summe gibt ne sehr komplizierte Summe wenn man das weiter einsetzen will 😞


Anmelden zum Antworten