# Gerade Terme der Fibonacci-Folge aufsummieren



## ac (3. Sep 2013)

hey, 

wie in der Überschrift angegeben, wollte ich die Fibonacci-Folge (n = 4 Millionen) berechnen und von den Termen nur die geraden Terme aufsummieren.
Dazu der folgende Code :


```
public class Problem2 {

	static int sum = 0;
	static int cur = 0;


	//Methode zur Berechnung der Fibonacci-Folge
	public int fib(int n){
		
			if(n == 0){
				return 0 ;
			}
		
		else if(n == 1){
				return 1;
			}
		
		else{
				return fib(n-1) + fib(n-2); 
			}
		
		
	}
	
	
	//Methode, die tatsächliche Summe bildet
	//Grenze = 4 Millionen wird als Parameter übergeben
	public int berechnung(int grenze){
		
		//Schleifenkopf mit oberer Grenze und Zählvariable
		for(int i= 1; i < grenze; i++){			
			
			//für jeden Wert i wird die obige fib-Methode aufgerufender 
			//in der fib-Methode berechnete Wert wird in cur geschrieben
			cur = fib(i);
			
                       //Prüfe, ob der in cur gespeicherte Wert gerade ist
                           if(cur % 2 == 0){					
				 sum += cur;                  //Falls gerade, so speichere in sum
		
			}
		}
		
		return sum;				           //gebe am Ende das Ergebnis aus
	
	}
	
	
	
	public static void main(String[] args){
		
		Problem2 pr2 = new Problem2();
		
		System.out.println("Die Summe der geraden Terme unter 4 Mil. : "  + pr2.berechnung(4000000));
		
		
		}
		
			
		
	

}
```


nun, zu meinem Problem: das Programm kompiliert zwar, aber wenn ich es ausführe passiert rein gar nichts. Kann mir jmd. vtl. sagen woran das liegen kann?
Hab im Internet vorhin gelesen, dass die rekursive fib()-Methode, die die Fibonacci-Folge berechnen soll, für große n sehr ineffiezient sein soll...stimmt das? falls ja, so würde das erklären, warum das so lange dauert....falls nicht, dann muss ich irgendwo einen Fehler gemacht haben....


----------



## bequiet (4. Sep 2013)

Naja fang halt mal kleiner an, lass den Test mal mit 10 laufen, dann mit 100.. dann siehst du schon direkt das die Ausfühung so lange dauert.

Die Laufzeit von Fibonacci ist exponentiell.

Sofern ich mich recht erinnere, soll die Rekursive Methode gegenüber der Iterativen eine deutlich bessere Laufzeit haben, aber ist lang her.


----------



## ac (4. Sep 2013)

ok. danke für die Antwort...Habs jetzt für 10 getestet, da kam auch schon direkt ein Ergebnis raus. Für 100 dauert die berechnung schon extrem lang...jetzt wird mir klar, warum der bei 4 mille so lange gebraucht hat und trotzdem kein ergebnis ausgespuckt hat....da scheint, die fib() Methode echt ineffizient zu sein...


----------



## pinkysbrain (4. Sep 2013)

Du möchtest ja x Werte im Intervall von 1...x berechnen.
Zur Zeit machst du für jeden Wert die ganze Rekursion.
Allerdings lässt sich das deutlich einfacher über eine Iteration machen.


```
public static long fib(int max) {
    	int n0 = 0;
    	int n1 = 1;
    	long summe = 0;
    	// Der erste Wert der hinzuaddiert wird ist fib(2) = 1
    	for (int i=0;i<max;i++) {
    	    int n2 = n0+n1;
    	    n0 = n1;
    	    n1 = n2;
    	    if (n2%2 == 0)
    	       summe+=n2;
    	}
    	return summe;
    }
```

Die Methode berechnet dir die Summe bis zum Maximum (bei max = 10 die summe aller Funktionswerte bis fib(9)).
Das Programm terminiert für max = 4000000 in unter 1s.


----------



## DrZoidberg (4. Sep 2013)

Wenn du für die Summe ein long verwendest, kommst du aber maximal bis n = 93. Für n = 4.000.000 müsstest du BigInteger nehmen.


----------



## pinkysbrain (4. Sep 2013)

Ah ok habe den Überlauf nicht beachtet (habe vergessen abzuschätzen in welchem Bereich man sich bewegt), es ging mir auch eher um den Weg als um die korrekten Rückgabeparameter.


----------



## ac (4. Sep 2013)

hallo,

vielen Dank für die hilfreichen Beiträge. Die Hilfe, die man hier bekommt, ist enorm. 
da ich noch nie mit BigInteger gearbeitet habe, muss ich mir ma jetzt anschauen, wie man damit umgeht.
Ansonsten ist alles ok...



gruß,
ac


----------



## bequiet (5. Sep 2013)

Ist eig. das gleiche wie int.. nur eben ein größerer Wertebereich.


----------



## stg (5. Sep 2013)

Die kannst deine Summe übrigens auch explizit, also sogar in konstanter Laufzeit, berechnen. (Herleitung über die Formel von Moivre-Binet und geometrische Summen.)


----------



## ac (24. Sep 2013)

hallo,

sry, dass ich so spät antworte  Aber musste aus diversen Gründen diese Aufgabe beiseite legen. Nun hab ich es wieder aufgegriffen, und versucht, die obigen ratschläge in die Tat umsetzen. Bei BigInteger hatte ich probleme die vordefinierten methoden zu verstehen. Das Programm funktioniert nicht so ganz...ich vermute mal dass es an der Bedingung der for-schleife liegt, dass mit dem compareTo bereitet mir sorgen....also hier das Programm in BigInteger-Version:


```
import java.math.BigInteger;


public class Problem2 {

	 BigInteger sum = BigInteger.valueOf(0);
	 BigInteger cur = BigInteger.valueOf(0);
	
	


	//Methode zur Berechnung der Fibonacci-Folge
	public BigInteger fib(BigInteger n){
		
		BigInteger n0 = BigInteger.valueOf(0);
		BigInteger n1 = BigInteger.valueOf(1);
		BigInteger summe = BigInteger.valueOf(0);
		
		for(BigInteger i = BigInteger.valueOf(0); i.compareTo(n) ; i = i.add(BigInteger.ONE)){
		
			BigInteger n2 = n0.add(n1);
			n0 = n1;
			n1 = n2;
			
			if(n2.mod(2) == 0){
				summe += n2;
			}
		
		}
		
		return summe;
	}
	
	
	//Methode, die tatsächliche Summe bildet
	//Grenze = 4 Millionen wird als Parameter übergeben
	public BigInteger berechnung(BigInteger grenze){
		
		
		for(BigInteger i= BigInteger.valueOf(0); 
				i.compareTo(grenze); i = i.add(BigInteger.ONE) ){			//Schleifenkopf mit oberer Grenze und Zählvariable
			
			//für jeden Wert i wird die obige fib-Methode aufgerufender 
			//in der fib-Methode berechnete Wert wird in cur geschrieben
			cur = fib(i);
			
			if(cur.mod(2) == 0){					//Prüfe, ob der in cur gespeicherte Wert gerade ist
				sum += cur;						//Falls gerade, so speichere in sum
		
			}
		}
		
		return sum;								//gebe am Ende das Ergebnis aus
	
	}
	
	
	
	public static void main(String[] args){
		
		Problem2 pr2 = new Problem2();
		
		BigInteger max = new BigInteger("4000000");
		
		
		System.out.println("Die Summe der geraden Terme unter 4 Mil. : "  + pr2.berechnung(big));
		
		
		}
		
			
		
	

}
```


----------



## stg (24. Sep 2013)

Verständnisfragen sind das eine, aber der von dir gepostete Code dürfte ja nicht einmal kompilieren, so voller Fehler ist er. Bring das doch erst mal in Ordnung, vielleicht erübrigt sich dein Problem dann ja schon von alleine?


----------



## ac (25. Sep 2013)

nun ich habe das Programm weiterhin ein bisschen modifiziert, nun sieht es so aus:


```
import java.math.BigInteger;


public class Problem2 {

	 BigInteger sum = BigInteger.valueOf(0);
	 BigInteger cur = BigInteger.valueOf(0);
	
	


	//Methode zur Berechnung der Fibonacci-Folge
	public BigInteger fib(BigInteger n){
		
		BigInteger n0 = BigInteger.valueOf(0);
		BigInteger n1 = BigInteger.valueOf(1);
		BigInteger summe = BigInteger.valueOf(0);
		
		for(BigInteger i = BigInteger.valueOf(0); i.compareTo(n) > 0 ; i = i.add(BigInteger.ONE)){
		
			BigInteger n2 = n0.add(n1);
			BigInteger even = BigInteger.valueOf(2);
			BigInteger test = BigInteger.valueOf(0);
			n0 = n1;
			n1 = n2;
			
			if(n2.mod(even) == test){
				summe = summe.add(n2);
			}
		
		}
		
		return summe;
	}
	
	
	//Methode, die tatsächliche Summe bildet
	//Grenze = 4 Millionen wird als Parameter übergeben
	public BigInteger berechnung(BigInteger grenze){
		
		 
		
		for(BigInteger i= BigInteger.valueOf(0); 
				i.compareTo(grenze) > 0; i = i.add(BigInteger.ONE) ){			//Schleifenkopf mit oberer Grenze und Zählvariable
			
			//für jeden Wert i wird die obige fib-Methode aufgerufender 
			//in der fib-Methode berechnete Wert wird in cur geschrieben
			cur = fib(i);
			BigInteger even = BigInteger.valueOf(2);
			BigInteger test = BigInteger.valueOf(0);
			if(cur.mod(even) == test){					//Prüfe, ob der in cur gespeicherte Wert gerade ist
				sum = sum.add(cur);						//Falls gerade, so speichere in sum
		
			}
		}
		
		return sum;								//gebe am Ende das Ergebnis aus
	
	}
	
	
	
	public static void main(String[] args){
		
		Problem2 pr2 = new Problem2();
		
		BigInteger max = BigInteger.valueOf(4000000);
		
		
		System.out.println("Die Summe der geraden Terme unter 4 Mil. : "  + pr2.berechnung(max));
		
		
		}
		
			
		
	

}
```


aber das Programm terminiert zwar, aber da kommt als Ergebnis immer 0 raus. Ich such den Fehler, kann ihn allerdings nicht finden


----------



## stg (25. Sep 2013)

Du vergleichst BigInteger-Objekte (!) mit 
	
	
	
	





```
==
```
. Du willst aber nicht prüfen, ob die Objekte identisch sind, sondern nur, ob sie den gleichen Wert haben. Solche Vergleiche machst du über die 
	
	
	
	





```
equals
```
-Methode.

Schau dir mal an, was die 
	
	
	
	





```
compareTo
```
-Methode zurückgibt. So wie du es jetzt dort stehen hast, springt dein Programm niemals in die for-Schleifen.

Die Methode 
	
	
	
	





```
berechnung
```
 kannst du dir komplett sparen. Du berechnest doch (so, wie es sein soll, da du sonst eine katastrophale Laufzeit hättest) innerhalb der Methode 
	
	
	
	





```
fib
```
 schon das, was du tatsächlich berechnen willst. Beachte bei der Ausgabe allerdings noch, dass die Fibonacci Zahl f_n natürlich die (n+1)te Zahl der Fibanacci-Folge ist. Wenn du also unter den ersten 4.000.000 Fibonacci-Zahlen aufsummieren willst, dann musst du deine Methode mit dem Wert 3.999.999 aufrufen.

Je nachdem, wie gut du in Mathe bist, kansnt du ja auch noch meinen Hinweis von der letzten Seite beachten, und versuchen eine explizite Formel für den von dir gewünschten Wert zu bestimmen. Somit erreichst du sogar konstante Laufzeit. Wenn es dir aber nur um die Programmierübung geht, dann vergiss die Anmerkung einfach.


----------

