3. Alle geraden Fibonacci Zahlen summieren

Alle geraden Fibonacci Zahlen summieren

  • B

    Das ist GNU-Style, beim Emacs cc-mode ist das der Default.

    0
  • N

    Danke SeppJ - nur so kriegen wir die Hardware aus den Strümpfen 😉

    Zum Asm Teil: es macht zwar viel mehr Spaß, sich den Algorithmus selber auszutüfteln, aber sei's drum:
    Wer sich nicht so mit Asm auskennt: bitte nicht abschrecken lassen. Der Witz dieses Programms ist nur der Ping-Pong-Algorithmus und die
    Prüfung des letzten Bits in einem Register.

    (compiliert mit FASMW)
    (editiert mit Notepad++)
    (debugger:debug,debugx,dosbox,braindebug)

    org 100h

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

Nochmal:					;Man könnte Prüfen und Summieren auch auslagern, aber wir machen gleich alles in
	cmp eax,250000h 		;einem Rutsch, 250000h = 4000000d
	ja Abschluss			
	cmp ebx,250000h
	ja Abschluss			;Wenn alles aufsummiert ist, geht es zur Endabrechnung
	add eax,ebx				;jetzt gehts los: Zahl alt plus Zahl neu
	bt eax,0				;Ist das erste Bit in EAX(ganz rechts) an Stelle Nr."0" eine 1?
	jnc Aufsummiereinganga	;nein, wir müssen die Zahl zur Gesamtsumme hinzuzählen

Re1:
	add ebx,eax				;der zweite Teil dieser ping-pong-fibonacci algo-funktion
	bt ebx,0				             
	jnc Aufsummiereingangb 
	jmp Nochmal				;der Hauptalgorithmus ist hier fertig, es kann von vorn losgehen

Aufsummiereinganga:
	add edi,eax				;edi dient als Aufsummierstelle
	call Ausgabe			;Vista startete das ComProgramm u.a. mit dem Wert FFFF in Edi, siehe oben                     
	jmp Re1 				;unsere Rückfahrkarte zur nächsten Etappe im Programm
Aufsummiereingangb:
	add edi,ebx
	call Ausgabe
	jmp Nochmal
;-------------------------------hier unten ist nur standardmäßiger Include-Header-kram----------------------;
;-----------------------------------------------------------------------------------------------------------;
Abschluss:
mov eax,0
mov ecx,0
mov edx,0
mov ebx,0
mov esi,0
mov edi,0
int 20h

Ausgabe:
	push eax				;Vorbereitungen, Register sichern und Konvertierwerte laden
	push ecx
	push edx
	push esi
	mov esi,10				;XYZhex durch 10 teilen, um auf Dezimalwerte zu kommen
	mov eax,edi				;AX wird mit der Summe der Hauptrechnung geladen
	mov ecx,0				;unser Zählregister muß auf Null stehen

Konvertierloop:
	mov edx,0				;wichtige(!) Initialisierung für die fehlerfreie Restdivision
	div esi 				;Das Ax-Register ist hier selbstverständlich und darum nicht genannt
	push dx 				;Rest der Division auf zur Stapelwarteschlange, hinten anstellen                                 
	inc cx					;Stapeleinträge merken für die Printschleife
	or  eax,eax				;ist eax=0?
	jnz Konvertierloop		;nein, play again

Printloop:
	mov eax,00000200h		;Ah=2,d.h. ein einzelnes Zeichen (Byte), ASCII-Code in DL, ausgeben
	pop dx					;Sex mit dx...                                  
	add dx,30h				;mögliche Ergebnis-Werte: 31,32,33,34,35,36,37,38,39
	int 21h
	loop Printloop			;der Befehl loop liest die Anzahl der Wiederholungen aus dem CX Register
	mov dl,0ah				;es folgt hier noch ein klassischer Zeilenumbruch
	int 21h
	mov dl,0dh
	int 21h

	pop esi
	pop edx
	pop ecx
	pop eax
	ret

    Der Hexcode für dieses Com-Programms (nenne mich .com) sieht so aus:
    (wirkt aber sehr aufgeblasen mit vielen Nullen, wegen der 32-Bit Register (mov eax,1=
    66B801000000))

    G:\debug fibo.com

-d 100 1b7
193C:0100  66 B8 01 00 00 00 66 BB-01 00 00 00 66 BF 00 00   f.....f.....f...
193C:0110  00 00 66 3D 00 00 25 00-77 2F 66 81 FB 00 00 25   ..f=..%.w/f....%
193C:0120  00 77 26 66 01 D8 66 0F-BA E0 00 73 0C 66 01 C3   .w&f..f....s.f..
193C:0130  66 0F BA E3 00 73 0A EB-D9 66 01 C7 E8 30 00 EB   f....s...f...0..
193C:0140  EC 66 01 DF E8 28 00 EB-C9 66 B8 00 00 00 00 66   .f...(...f.....f
193C:0150  B9 00 00 00 00 66 BA 00-00 00 00 66 BB 00 00 00   .....f.....f....
193C:0160  00 66 BE 00 00 00 00 66-BF 00 00 00 00 CD 20 66   .f.....f...... f
193C:0170  50 66 51 66 52 66 56 66-BE 0A 00 00 00 66 89 F8   PfQfRfVf.....f..
193C:0180  66 B9 00 00 00 00 66 BA-00 00 00 00 66 F7 F6 52   f.....f.....f..R
193C:0190  41 66 09 C0 75 F0 66 B8-00 02 00 00 5A 83 C2 30   Af..u.f.....Z..0
193C:01A0  CD 21 E2 F2 B2 0A CD 21-B2 0D CD 21 66 5E 66 5A   .!.....!...!f^fZ
193C:01B0  66 59 66 58 C3 00 00 00                           fYfX....
    0
  • 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