3. Alle geraden Fibonacci Zahlen summieren

Alle geraden Fibonacci Zahlen summieren

  • V

    Wenn ich richtig sehe, geht das nicht mit anderen Obergrenzen, oder?
    Weil die beiden Tests auf 4000000 beide am Anfang der Schleife stehen.
    Einer müßte am Anfang stehen und einer nachg Re1.

    0
  • N

    volkard schrieb:

    Wenn ich richtig sehe, geht das nicht mit anderen Obergrenzen, oder?
    Weil die beiden Tests auf 4000000 beide am Anfang der Schleife stehen.
    Einer müßte am Anfang stehen und einer nachg Re1.

    Naja, das Programm müsste genaugenommen nach jeder (PingPong)Addition den Registerinhalt auf Wertüberschreitung überprüfen
    und dann das Programm beenden. Ja, es gibt hier noch einiges an Optimierungsbedarf, für alle die Lust haben...,herzlich eingeladen 😉 🙂

    Und und wenn wir das hinter uns haben, und auch die tolle MPI-Variante von SeppJ
    einstudiert und durchgekaut haben, dann können wir uns auch an eine Cuda und OpenCl Möglichkeit heranwagen...;)

    0
  • V

    Naja, auf Überläufe überprüft hat noch keine der Implementierungen.

    Irgendwie hätte ich an sowas gedacht. Völlig ungetestet, ich habe seit Jahren keinen assembler mehr benutzt, nur mal die Idee hingeschrieben, statt ping-pong nur ping-swap.

    mov eax,1                    ;Ausgangsbedingungen, Aerni=1
mov ebx,1                    ;und Bert = 1
mov edi,0                    ;Initialisierung des Edi=Summe-Registers 

Nochmal:                     ; do{
    bt ebx,1                 ;   if(!(b&1))
    jne skipSum              ;   //Fortsetzung
    add edi,ebx              ;      s+=b;
skipSum:                     ;
    add eax,ebx              ;   a+=b;
    xchg eax,ebx             ;   swap(a,b);
    cmp ebx,250000h          ; }while(b<=4000000);
    jle Nochmal              ; //Fortsetzung
fertig:
   call Ausgabe              ; cout<<s;
    0
  • N

    Hey, die Kommentierung ist super.
    den Befehl bt und seine Wirkung kann man schnell mit dem Debug-Clone von
    Paul Vojta überprüfen (http://math.berkeley.edu/~vojta/)(unten auf der Seite ist der debug-link) (debug kann dat nich)
    Der Algorithmus erinnert ein wenig an das Euklidbeispiel von der MASM-Seite
    (http://msdn.microsoft.com/de-de/library/td2x50t8(v=VS.80).aspx)
    und ist ziemlich SevenofNine-like 😉👍

    0
  • V

    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;
    0
  • N

    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   ................
    0
  • 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...

    0
  • C
    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
    0
  • V

    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.

    0
  • V

    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.

    0
  • S

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

    0
  • C
    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.

    0
  • P

    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=5n−∑i=0n−1f3i+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)(−1n−i)\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))−(52i−1+2(2i−1))=∑i=0k(4⋅52i−1+2)=20∑i=0k25i−1+k(k−1)\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)

    =20∑i=0k−125i+500+k(k−1)= 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+2⋅0)=∑i=0k(4⋅52i+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

    =4∑i=0k25i+k(k−1)−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

    0
  • V

    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

    0
  • V

    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

    0
  • V

    pumuckl schrieb:

    =4∑i=0k25i+k(k−1)−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...

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

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

    0
  • P

    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=5n−∑i=0n−1f3i+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 😞

    0
Anmelden zum Antworten