Fibonacci Folge

[deadc0de]

Guten Tag,
hier ein kleines Programm ind Java zur berechnung der Fibonacci-Folge.

import java.math.BigInteger;

public class fibFolge{
	public static void main(String[] args) {
		final long fibFolgeAus = 100000;
		System.out.println(berechneFib(BigInteger.valueOf(1), BigInteger.valueOf(1), fibFolgeAus));
	}
	
	private static BigInteger berechneFib(BigInteger alterWert, BigInteger neuerWert, long folge){
		for(long i = 0; i < folge - 2; i++){
			neuerWert = neuerWert.add(alterWert);
			alterWert = neuerWert.subtract(alterWert);
		}

		return neuerWert;
	}
}

Kritik ist erwünscht.

Grüße deadc0de

[SeppJ]

Du berechnest den nächsten Wert aus dem Vorherigen, dann berechnest du rückwärts den vorherigen Wert aus dem gerade berechneten nächsten Wert. Kommt dir das nicht ein bisschen umständlich vor?

[deadc0de]

@SeppJ ja, das war mir klar, deshalb habe ich es korrigiert. Danke.

import java.math.BigInteger;

public class fibpipip {
	public static void main(String[] args) {
		final long fibFolgeAus = 100000;
		System.out.println(berechneFib(BigInteger.valueOf(1), BigInteger.valueOf(1), fibFolgeAus));
	}
	
	private static BigInteger berechneFib(BigInteger alterWert, BigInteger neuerWert, long folge){		
		for(long i = 3; i < folge; i++){
			if(i % 2 == 0){
				neuerWert = neuerWert.add(alterWert);
			}
			else{
				alterWert = alterWert.add(neuerWert);
			}
		}
		
		return neuerWert.add(alterWert);
	}
}

Gruß

deadc0de

[SeppJ]

Kommt dir das nicht noch umständlicher vor?

Etwas anders gefragt: Du sollst den Wert von zwei Variablen vertauschen. Du darfst keine imports benutzen. Wie würdest du das machen?

[wob]

Ganz allgemein: Sean Parents Public Service Announcement: How to write Fibonacci

[TGGC]

@deadc0de sagte in Fibonacci Folge:

final long fibFolgeAus = 100000

Wenn du die Zahl mit einem kleine Programm ausrechnen kannst, sag Bescheid.

[wob]

@TGGC sagte in Fibonacci Folge:

Wenn du die Zahl mit einem kleine Programm ausrechnen kannst, sag Bescheid.

Wo ist das Problem?

[deadc0de]

@TGGC ich verstehe das Problem nicht...

[TGGC]

Das Problem ist quadratischer Aufwand, da bei einem naiven Algorithmus der Speicher für das Zwischenergebnis schnell anwächst.

[wob]

@deadc0de sagte in Fibonacci Folge:

@TGGC ich verstehe das Problem nicht...

Das könnte etwas länger dauern, wenn man nicht klug berechnet. Berechne es folgendermaßen:

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}$

und schau, was oben links rauskommt...

Ob der Aufwand wirklich quadratisch ist? Also die Potenz ist logarithmischer Aufwand (die Zahlen werden aber immer größer, mit denen man rechnet). Ich bezweifle mal, dass es gesamt quadratisch ist.

[SeppJ]

@wob sagte in Fibonacci Folge:

Ob der Aufwand wirklich quadratisch ist? Also die Potenz ist logarithmischer Aufwand (die Zahlen werden aber immer größer, mit denen man rechnet). Ich bezweifle mal, dass es gesamt quadratisch ist.

Die Addition wird linear teurer mit der Länge der beteiligten Zahlen. Da wir O(N) Additionen machen, deren Länge auch mit O(N) skaliert, kommt insgesamt O(N²) heraus.

[deadc0de]

@SeppJ das stimmt, allerdings ist das bei der Fibonacci Folge kaum zu vermeiden. Mit diesem Algorithmus braucht man etwa 10 Sekunden für die 1.000.000te Folge und das ist schon ziemlich gut denke ich, weil das Ergebnis auf die Ziffer genau ist.

[wob]

@SeppJ sagte in Fibonacci Folge:

Da wir O(N) Additionen machen

Sind das nicht eher O(log n)?

[SeppJ]

@wob sagte in Fibonacci Folge:

@SeppJ sagte in Fibonacci Folge:

Da wir O(N) Additionen machen

Sind das nicht eher O(log n)?

Wie? Die Schleife geht von 0 bis N-2. Eine besseres Beispiel für O(N) gibt es wohl kaum.

Es ginge natürlich prinzipiell insgesamt in O(log(N)), aber das soll der Threadersteller mal schön selber rausfinden, wie.

[hustbaer]

@SeppJ meinst du die "closed form"? Weil wenn nicht... dann steig ich grad aus

[SeppJ]

@hustbaer sagte in Fibonacci Folge:

@SeppJ meinst du die "closed form"? Weil wenn nicht... dann steig ich grad aus

Ja. Ich gehe davon aus, dass wollen auch TGGC und wob sehen.

[wob]

@SeppJ sagte in Fibonacci Folge:

Wie? Die Schleife geht von 0 bis N-2. Eine besseres Beispiel für O(N) gibt es wohl kaum.

Wozu habe ich ein Video verlinkt und die Formel daraus nochmal aufgeschrieben? Bestimmt nicht, um eine schlechtere Variante zu diskutieren.

Man kann auch fib(n) berechnen mit Hilfe von $\sqrt 5$. https://en.wikipedia.org/wiki/Square_root_of_5#Relation_to_the_golden_ratio_and_Fibonacci_numbers

Aber auch da müsste man mal schauen, wie die Komplexität so aussieht, weil man ja eine gewisse Anzahl von Nachkommastellen braucht...

[Swordfish]

@wob Gibts da neben Binet's Formel nicht noch eine andere Möglichkeit?

[SeppJ]

@wob sagte in Fibonacci Folge:

@SeppJ sagte in Fibonacci Folge:

Wie? Die Schleife geht von 0 bis N-2. Eine besseres Beispiel für O(N) gibt es wohl kaum.

Wozu habe ich ein Video verlinkt und die Formel daraus nochmal aufgeschrieben?

??? TGGC und ich haben dem Threadersteller erklärt, warum seine jetzige Variante nicht so gut ist. Eben weil sie O(N²) ist.

@Swordfish sagte in Fibonacci Folge:

@wob Gibts da neben Binet's Formel nicht noch eine andere Möglichkeit?

Siehe wobs Beitrag mit der Matrix.

[Swordfish]

@SeppJ Sobald ich Nerven für den Inder hab' mach' ich das.

[deadc0de]

@Swordfish ist auf jeden Fall ein relativ spannendes Projekt. Ich sitze da auch schon seit Tagen dran das ganze zu optimieren.