3. Alle geraden Fibonacci Zahlen summieren

Alle geraden Fibonacci Zahlen summieren

  • V

    nachtfeuer schrieb:

    In Assembler brauchst du bloß drei Register und die Ausgaberoutine.
    Angenommen AX=1 und BX=1 (alias Aerni und Bert)
    dann geht es weiter mit

    add eax,ebx
    add ebx,eax ;lustiges Fibonacci-PingPong

    add edi,gerade Zahl
    Genaugenommen ein Superlernbeispiel, etwas Asm-Code in sein C-Programm einzubauen.

    Das ist nicht so einfach. Die Schleife müßte zum Beispiel zwei Ausgänge haben. 😮
    Ein super Lernbeispiel, wie man sich verschätzen kann.

    nachtfeuer schrieb:

    das ist ja zum Totlachen hier, wann schreitet endlich mal ein Moderator ein?

    Ok, hiermit schreite ich ein.

    nachtfeuer schrieb:

    Ja muß ich denn erst Drogen nehmen, um hier Antworten zu posten? 😃
    *rotfl*rotfl*

    Das hast Du offensichtlich gemacht. Willkommen im Klub.

    0
  • ?

    Mich würde mal interessieren, was du von meiner Lösung hältst, Volkard.

    #include <iostream>
int main(){std::size_t _e0,_$,_o_,_0xFF=_e0=_$=1e3/1e2/1e1;for(_0xFF=_o_=(--_e0);(_o_=(0e0-1)*(-_0xFF-_$))<-1+4e6+((_e0+=_o_%2?0x0&0xFF:_o_)/1);_0xFF=_$,_$=_o_);std::cout<<_e0;}
    0

  • Bin zwar nicht Volkard, aber dein Code ist nicht standardkonform wegen der führenden Unterstriche. Vielleicht ist Volkard anderer Meinung, vielleicht auch nicht.

    0
  • Mod

    Da ist noch viel Obfukationspotential, dass nicht genutzt wurde:
    -Keine Trigraph-Sequenzen
    -for-Schleife anstatt Rekursion. Rekursion ist viel schwerer lesbar.
    -Die Literale könnte man sogar noch mehr obfuskieren (mir gefällt die jetzige Mischung aus Hex und Exponentialschreibweise 👍 ), indem man sie durch sinnlose Variable ersetzt, beispielsweise kann man eine 1 bekommen, indem man den ersten Parameter der main-Funktion benutzt (und hofft, dass niemand Argumente an das Programm übergibt).
    -Man kann ausnutzen, dass Funktionen implizit int zurückgeben, wenn man nichts angibt. Dies macht Konstrukte wie main() möglich. Das ist zwar nicht ISO-konform, aber praktisch jeder Compiler kann das aus Kompatibilitätsgründen
    -Falls Funktionen mit Parametern benutzt werden (z.B. main), dann natürlich mit der alten C Syntax für Parameter. Ist der Parameter ein int, dann ist er das natürlich nur implizit.

    0
  • V

    ssdfsdf schrieb:

    Mich würde mal interessieren, was du von meiner Lösung hältst, Volkard.

    #include <iostream>
int main(){std::size_t _e0,_$,_o_,_0xFF=_e0=_$=1e3/1e2/1e1;for(_0xFF=_o_=(--_e0);(_o_=(0e0-1)*(-_0xFF-_$))<-1+4e6+((_e0+=_o_%2?0x0&0xFF:_o_)/1);_0xFF=_$,_$=_o_);std::cout<<_e0;}

    Ich finde sie, obwohl technisch fein aufgeführt, nicht so hübsch. Die Obfuskation hat die ganze Sache sehr lang gemacht, zum Beispiel 1e3/1e2/1e1 oder (0e0-1) oder 0x0&0xFF oder das /1. Mit genug Längermachen kann das jeder.
    _$ ist eine GCC-Erweiterung, gell? Die 4e6 ist so verborgen, daß jeder denkt, es würde prinzipiell nur eine Zahl berechnen können, was zu Fellhuhns Lösung führt.

    0
  • N

    volkard schrieb:

    ssdfsdf schrieb:

    Mich würde mal interessieren, was du von meiner Lösung hältst, Volkard.

    #include <iostream>
int main(){std::size_t _e0,_$,_o_,_0xFF=_e0=_$=1e3/1e2/1e1;

for(_0xFF=_o_=(--_e0);(_o_=(0e0-1)*(-_0xFF-_$))<-1+4e6+((_e0+=_o_%2?0x0&0xFF:_o_)/1);_0xFF=_$,_$=_o_);std::cout<<_e0;}

    Ich finde sie, obwohl technisch fein aufgeführt, nicht so hübsch. Die Obfuskation hat die ganze Sache sehr lang gemacht, ...

    So lang, dass das Codefenster wieder mal aus dem normalen Tabellenrahmen herausragt...;)
    (IE und Opera)
    ...leider nirgendwo OpenMP Beispiel 😞

    0
  • V

    nachtfeuer schrieb:

    ...leider nirgendwo OpenMP Beispiel 😞

    Ähm, das wäre nutzlos. Kannst ja nicht einfach parallelisieren. Wie weit ist die asm-Lösung mit dem Ping-Pong-Trick?

    0
  • Mod

    volkard schrieb:

    nachtfeuer schrieb:

    ...leider nirgendwo OpenMP Beispiel 😞

    Ähm, das wäre nutzlos. Kannst ja nicht einfach parallelisieren. Wie weit ist die asm-Lösung mit dem Ping-Pong-Trick?

    Hmm, man könnte einen Thread die Fibonacci-Zahlen ausrechnen lassen und dem anderen die schwere, rechenintensive Aufgabe anvertrauen, auf gerade/ungerade zu prüfen und die Summe zu berechnen. Morgen kann ich eine MPI Version damit machen, wenn das jemand sehen will. Mal gucken wir langsam das Programm durch so viel Overhead wird.

    0
  • V

    SeppJ schrieb:

    volkard schrieb:

    nachtfeuer schrieb:

    ...leider nirgendwo OpenMP Beispiel 😞

    Ähm, das wäre nutzlos. Kannst ja nicht einfach parallelisieren. Wie weit ist die asm-Lösung mit dem Ping-Pong-Trick?

    Hmm, man könnte einen Thread die Fibonacci-Zahlen ausrechnen lassen und dem anderen die schwere, rechenintensive Aufgabe anvertrauen, auf gerade/ungerade zu prüfen und die Summe zu berechnen. Morgen kann ich eine MPI Version damit machen, wenn das jemand sehen will. Mal gucken wir langsam das Programm durch so viel Overhead wird.

    👍
    Oder in der rekursiven Variante für jeden Aufruf von f einen Thread starten.
    Wegen return f(n-2)+f(n-1) bietet es sich ja geradezu an, f(n-2) und f(n-1) parallel berechnen zu lassen.

    0
  • N

    SeppJ schrieb:

    Hmm, man könnte einen Thread die Fibonacci-Zahlen ausrechnen lassen und dem anderen die schwere, rechenintensive Aufgabe anvertrauen, auf gerade/ungerade zu prüfen und die Summe zu berechnen. Morgen kann ich eine MPI Version damit machen, wenn das jemand sehen will. Mal gucken wir langsam das Programm durch so viel Overhead wird.

    :):):):):):):):) ...man könnte statt 4 Mio 2^4000000-1 rechnen oder so...die
    Idee mit MPI finde ich stark 👍

    volkard schrieb:

    Ähm, das wäre nutzlos. Kannst ja nicht einfach parallelisieren. Wie weit ist die asm-Lösung mit dem Ping-Pong-Trick?

    Der Ping-Pong-Trick ist recht ausgereift und hat, wenn man die Registerinhalte on the fly testet - oder auch nur irgendwo in den Speicher schreibt - tatsächlich zwei "Ausgänge" (und Rückfluglandepunkte) - und so eine kleine Parallelisieroptimiergrundlage.;)

    0
  • Mod

    Hier eine MPI-parallelisierte Version. Sie läuft bei mir geschätzte 0.5 Sekunden. Man lasse sich dies eine Lehre sein, dass Amdahls Gesetz kein akademisches Theoretikergeschwätz ist.

    #include <iostream>
#include <mpi.h>

using
  std::cout;
using
  std::endl;

const unsigned int
  max = 4e6;

const int
  work_tag = 1;
const int
  exit_tag = 2;

inline unsigned int
next_fibonacci ()
{
  static unsigned int
    prelast = 1;
  static unsigned int
    last = 1;
  unsigned int
    current = prelast + last;
  prelast = last;
  last = current;
  return current;
}

int
main (int argc, char *argv[])
{

  MPI_Init (&argc, &argv);

  int
    rank_size;
  MPI_Comm_size (MPI_COMM_WORLD, &rank_size);
  if (rank_size < 2)
    {
      cout << "Dieses Programm benoetigt mindestens 2 MPI Prozesse!" << endl;
    }
  else
    {
      // Alles passt, normaler Programmablauf kann starten
      int
        rank;
      MPI_Comm_rank (MPI_COMM_WORLD, &rank);

      if (rank == 0)
        {
          // Summiert gerade Fibonacci-Zahlen
          unsigned int
            sum = 0;
          unsigned int
            fibonacci = 0;
          MPI_Status
            status;
          do
            {
              if (fibonacci % 2 == 0)
                sum += fibonacci;
              MPI_Recv (&fibonacci, 1, MPI_INT, 1, MPI_ANY_TAG,
                        MPI_COMM_WORLD, &status);
            }
          while (status.MPI_TAG == work_tag);
          cout << "Summe aller geraden Fibonacci Zahlen kleiner als " << max
            << " ist " << sum << "." << endl;
        }

      else if (rank == 1)
        {
          // Generiert Fibonacci Zahlen und verschickt diese
          unsigned int
            fibonacci;
          while ((fibonacci = next_fibonacci ()) < max)
            {
              MPI_Send (&fibonacci, 1, MPI_INT, 0, work_tag, MPI_COMM_WORLD);
            }
          // Sende exit_tag, um die anderen Prozesse zu beenden
          MPI_Send (0, 0, MPI_INT, 0, exit_tag, MPI_COMM_WORLD);
        }
    }

  MPI_Finalize ();
}

    Die von volkard vorgeschlagene Version mit der Threadexplosion muss aber jemand anderes programmieren.

    0
  • V

    Ich dachte, ich sei hart im Nehmen. Aber so eine blöde Formatierung wie bei Dir habe ich ja noch nie gesehen. Du reißt dauernd dicht zusamnmengehörende Sachen wie Typ und Variable auseinander. Das macht das Lesen viel spannender. Aber den Effekt kannst Du noch besser auskosten, wenn da ein wenig mehr Abstand ist. Ich mach's Dir mal vor.
    Außerdem muß man Funktionsname und Parameterliste optisch trennen. Auch sind die geschweiften Klammern manchmal senkrecht unter dem Blockeröffner und manchmal schräg drunter. Das kann man verbessern, indem sie auch manchmal dahinter sind. An den vielen else ändere ich mal nichts, das kann man nicht überbieten.

    #include <iostream>
#include <mpi.h>

using

std::cout;
	using

std::endl;
	const unsigned int

max = 4e6;
	const int

work_tag = 1;
	const int

exit_tag = 2;
	inline unsigned int

next_fibonacci () {
	static unsigned int

	prelast = 1;
		static unsigned int

	last = 1;
		unsigned int

	current = prelast + last;
		prelast = last;

	last = current;
		return current;
}
	int

main

(int argc, char *argv[]) 
		{
	MPI_Init (&argc, &argv);
		int

	rank_size;

	MPI_Comm_size (MPI_COMM_WORLD, &rank_size);
		if

	(rank_size < 2) {
		cout << "Dieses Programm benoetigt mindestens 2 MPI Prozesse!" << endl;
}
		else {

	// Alles passt, normaler Programmablauf kann starten
		int

		rank;
			MPI_Comm_rank

		(MPI_COMM_WORLD, &rank);
			if (rank == 0) {

			// Summiert gerade Fibonacci-Zahlen
				unsigned int

			sum = 0;
				unsigned int

			fibonacci = 0;
				MPI_Status

			status;
				do {
		if

	(fibonacci % 2 == 0)
		sum += fibonacci;
			MPI_Recv

				(&fibonacci, 1, MPI_INT, 1, MPI_ANY_TAG,

					MPI_COMM_WORLD, &status);
			}while

			(status.MPI_TAG 
		== work_tag);

			cout << "Summe aller geraden Fibonacci Zahlen kleiner als " << max
					 << " ist " << sum << "." << endl;
		}

		else if

		(rank == 1) 
	{
			// Generiert Fibonacci Zahlen und verschickt diese
				unsigned int

			fibonacci;
				while

			((fibonacci = next_fibonacci ()) < max) {
				MPI_Send

			(&fibonacci, 1, MPI_INT, 0, work_tag, MPI_COMM_WORLD);
				}

			// Sende exit_tag, um die anderen Prozesse zu beenden
				MPI_Send

			(0, 0, MPI_INT, 0, exit_tag, MPI_COMM_WORLD);
		}
	}

	MPI_Finalize ();
}
    0
  • Mod

    Das ist nicht wirklich mein Stil, ich habe den Quelltext vorher bloß durch GNU-indent gejagt. Das schreckliche was du hier siehst ist der indent Standardstil.
    Der Grund, warum ich das gemacht habe ist, dass mein Editor die (automatische) Einrückung mittels einer Mischung aus Tabs und Leerzeichen macht und wenn ich das hier im Forum poste, sieht mein schön eingerückter Text hinterher noch schrecklicher aus als das was indent verbrochen hat.

    0
  • Mod

    Ahh, ich habe rausgefunden wie man emacs beibringt, immer nur Leerzeichen zu verwenden. Jetzt kann ich endlich direkt aus dem Editor hier ins Forum kopieren. So sieht mein normaler Stil aus:

    #include <iostream>
#include <mpi.h>

using std::cout;
using std::endl;

const unsigned int max=4e6;

const int work_tag=1;
const int exit_tag=2;

inline unsigned int next_fibonacci()
{
  static unsigned int prelast=1;
  static unsigned int last=1;
  unsigned int current=prelast+last;
  prelast=last;
  last=current;
  return current;
}

int main(int argc, char *argv[])
{

  MPI_Init(&argc, &argv);

  int rank_size;
  MPI_Comm_size(MPI_COMM_WORLD, &rank_size);
  if (rank_size<2) 
    {
      cout<<"Dieses Programm benoetigt mindestens 2 MPI Prozesse!"<<endl;
    }
  else
    {
      // Alles passt, normaler Programmablauf kann starten
      int rank;
      MPI_Comm_rank(MPI_COMM_WORLD, &rank);

      if (rank == 0) {
        // Summiert gerade Fibonacci-Zahlen
        unsigned int sum=0;
        unsigned int fibonacci=0;
        MPI_Status status;
        do
          {
            if (fibonacci%2==0) sum+=fibonacci;
            MPI_Recv(&fibonacci, 1, MPI_INT, 1, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
          } while (status.MPI_TAG==work_tag);  
        cout<<"Summe aller geraden Fibonacci Zahlen kleiner als "<<max<<" ist "<<sum<<"."<<endl;	
      } 

      else if (rank==1)
        {
          // Generiert Fibonacci Zahlen und verschickt diese
          unsigned int fibonacci;
          while ((fibonacci=next_fibonacci())<max)
            {
              MPI_Send(&fibonacci, 1, MPI_INT, 0, work_tag, MPI_COMM_WORLD);
            }
          // Sende exit_tag, um die anderen Prozesse zu beenden
          MPI_Send(0, 0, MPI_INT, 0, exit_tag, MPI_COMM_WORLD);
        }
    }

  MPI_Finalize();
}
    0
  • K

    Du setzt die geschweiften Klammern trotzdem komisch.

    0
  • 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
Anmelden zum Antworten