Sehr sehr merkwürdige Ereignisse mit Fibonacci Programm

[Guest]

Hallo,
Ich sollte für eine Aufgabe einen nicht rekursiven Fibonacci Algorithmus entwerfen.
Für den Algorithmus hat mein weniger Hirnschmalz noch ausgereicht.
Allerdings stoße ich auf ein mekrwürdiges Problem bzw. einen Javabug(?).
Also der Algorithmus gibt für die ersten Fibonacci-Folgeglieder auf jeden Fall die richtigen Ergebnisse aus.
Dann allerdings genau ab dem Wert 47 bekomme ich negative Werte :bahnhof: .
Warum dass denn? Das Ginge ja nur, wenn der Wert a[i-2] negativ ist und an sich ist es generel unmöglich, dass einer der Vorgänger Werte negativ ist.
Hier mal die Ergebnisse für F(46) und F(47)
1836311903
-1323752223

Wie gesagt, wenn jemand weiß, ob es sich hierbei nur um einen Javabug handelt, dann wäre ich über Aufklärung dankbar. Wenn das am Algo liegen sollte( auch wenn ich das nicht nachvollziehen könnte, zumindest bis jetzt nicht) dann wäre ich auch hier für jeden Hinweis dankbar.

Und noch generel eine Frage. Vielleicht gibt es hier ja Laufzeit Experten. Was wäre hier denn ein gutes Maß für eine Laufzeitberechnung? Die Anzahl der Additionen? Die wäre ja in dem Fall Linear, oder sollte mans eher von den Bitvalues abhängig machen. Die werden ja bei großen Eingabelängen relativ schnell groß.

public class FibNonRec {
	
	public static int getFibonacciValue(int x){
		int[] a= new int[x+1];
		a[0]=0;
		a[1]=1;
		for(int i=2;i<=x;i++){
			a[i]=a[i-1]+a[i-2];
		}
		return a[x];
	}
	public static void main(String[] args){
		System.out.println(getFibonacciValue(46));
	
		System.out.println(getFibonacciValue(47));
	}
}

 

[SlaterB]

public class Test
{
    public static void main(String[] args)
        throws Exception
    {
      System.out.println(Integer.MAX_VALUE);
    }
}

 

[Marco13]

Ja, long statt int hilft schonmal. Die Werte, die Long aufnehmen kann, sind so groß, dass die Berechnung schon langweilig werden könnte - obwohl die Laufzeit linear ist (was ist so schlimm oder falsch daran?)

 

[0001001]

Falls du beliebig große Zahlen berechnen willst, bleibt dir wohl nur der Weg über BigInteger. Hier ein iterativer Algorithmus zur Berechnung der Fibonacci Zahlen:

	public BigInteger calcFib(BigInteger n){
		BigInteger zero = BigInteger.ZERO;
		BigInteger one  = BigInteger.ONE;
		
		if (n.equals(zero)){
			return zero;
		}
		if (n.equals(one)){
			return one;
		}

		BigInteger i  = one;
		BigInteger a  = zero;
		BigInteger b  = one;

		while (i.compareTo(n) == -1) {
			BigInteger temp = b;
			b = b.add(a);
			a = temp;
			i = i.add(one);
		}
		return b;
	}

 

[Gast]

Super,
danke schonmal, dann lags also doch an Java .

 

[Leroy42]

danke schonmal, dann lags also doch an Java .

Das kann ich jetzt nicht so stehen lassen! :noe:

Das hat mit Java an sich gar nichts zu tun.

Die Begrenztheit der int-Werte ist in fast jeder Sprache
(C, C++, Pascal, Fortran, Prolog, APL, Modula II, ...) anzutreffen

 

[SlaterB]

hier ging es auch weniger um 'Java vs C' sondern um 'dummes Programm vs menschlicher Fehler'