3. Alle geraden Fibonacci Zahlen summieren

Alle geraden Fibonacci Zahlen summieren

  • 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