Alle geraden Fibonacci Zahlen summieren

Man sieht das du die Aufgabenstellung nur halb gelesen hast. Versuch es noch ein Mal.

Doug_HH

Omega_ schrieb:

Man sieht das du die Aufgabenstellung nur halb gelesen hast. Versuch es noch ein Mal.

Ja stimmt, hast recht

Doug_HH

Aber jetzt...

Das war Step by Step

int f1 = 0, f2 = 1, f3 = 0, summe = 0;

for( int x = 0; f3 <= 4000000; x++) 
{ 
	if(!(f3 % 2))
	{
		summe += f3;
	}

	f1 = f2; 

	f2 = f3; 

	f3 = f2 + f1; 
}

cout << summe << endl;

Sieht nicht verkehrt aus, obwohl ich f3 % 2 == 0 bevorzugen würde.
Jetzt kannst du dein Ergebnis mit der auf Seite 3 genannten Lösung vergleichen und siehst, ob du richtig liegst.
Oder Schritt für Schritt nachrechnen.

volkard

Geschlossene Formel gefunden und Schleife und Rekursion weggemacht.

#include <cmath>
#include <iostream>
using namespace std;
#define I pow(5,l
#define l .5)

int main(){
double max=4000000;; //<-- Hier Obergrenze verstellen!
cout<<int(int(pow((
(I*l+l,3*floor(log(
max*I+l/3/log((I*l+
l)+1/l/I-l*l<<'\n';
}

nachtfeuer

das ist ja zum Totlachen hier, wann schreitet endlich mal ein Moderator ein?
Ja muß ich denn erst Drogen nehmen, um hier Antworten zu posten?
*rotfl*rotfl*

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.

Fellhuhn

#include <iostream> 
int main(){ std::cout << 4613732 << std::endl; }

Fertig.

volkard

Fellhuhn schrieb:

#include <iostream> 
int main(){ std::cout << 4613732 << std::endl; }

Fertig.

Dagegen habe ich die Obergrenze verstellbar gelassen.

volkard

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.

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;}

DocShoe

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

SeppJ

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.

volkard

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.

nachtfeuer

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

volkard

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?

SeppJ

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.

volkard

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.

nachtfeuer

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.;)

SeppJ

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.

volkard

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 ();
}