CODEWITHSUNDEEP
javarecursioniterationfibonacci
user1937976
user1937976

Reputation: 19

Algorithm to calculate Fibonacci sequence implemented in Java gives weird result

When I run Countdown.class I get the following output:

263845041
-1236909152
-973064111
2084994033
1111929922
-1098043341
13886581
-1084156760
-1070270179
2140540357

Blast Off!

The numbers before "Blast Off!" ought to be the first 10 Fibonacci numbers. My source code is as follows.

    public class Fibonacci {

  public static long fib(int n) {
    if (n <= 1) return 1;
    return fib(n-1) + fib(n-2);
  }

  public static long fastfib(int n) {
    int a = 0;
    int b = 1;
    int c = 0;

    for (int i = 0; i <= n; n++) {
      c = a + b;
      a = b;
      b = c;    
    }

    return c;
  }

}

and the class that implements the fastfib method is:

public class Countdown {

  public static void countdown(int n) {
    if (n == 0) System.out.println("Blast Off!");
    else {
      System.out.println(Fibonacci.fastfib(n));
      countdown(n - 1); 
    }
  }

  public static void main(String[] args) {
    countdown(10);
  }
}

Upvotes: 2

Views: 2451

Answers (4)

gustavo.a.hansen
gustavo.a.hansen

Reputation: 156

You should user BigInteger insted of long

import java.math.BigInteger;

public class Fibonacci {

public static BigInteger fib(BigInteger n) {
    int result = n.compareTo(BigInteger.valueOf(1)); // returns -1, 0 or 1 as this BigInteger is numerically less than, equal to, or greater than val.
    if (result != 1) return BigInteger.valueOf(1);

    return fib(

            n.subtract(
                    BigInteger.valueOf(1).add
                        (n.subtract
                                (
                                        BigInteger.valueOf(-2)
                                )
                        )
                    )
                );
}

public static BigInteger fastfib(int n) {
    BigInteger a = BigInteger.valueOf(0);
    BigInteger b =  BigInteger.valueOf(1);
    BigInteger c =  BigInteger.valueOf(0);

    for (int i = 1; i < n; i++) {
        c = a.add(b);
        a = b;
        b = c;    
    }

    return c;
}

}

Upvotes: 0

amit
amit

Reputation: 178411

Though your fastfib() method returns long, the calculations are done on ints.

You are encountering integer overflow.

Make sure to declare a,b,c as longs and NOT as ints. If you want even larger numbers (that are out of range for longs as well) - you might want to have a look on BigInteger (and use it).

EDIT: As mentioned by @ExtremeCoders in comment, there is another issue in the code in your for loop:
for (int i = 0; i <= n; n++) should be for (int i = 0; i <= n; i++), you want to increase i - not n.

Upvotes: 11

irrelephant
irrelephant

Reputation: 4111

In addition to the other answers,

for (int i = 0; i <= n; n++) {

should be

for (int i = 0; i <= n; i++) {
//                      ^ that's an i

Upvotes: 4

Abhinav Manchanda
Abhinav Manchanda

Reputation: 6631

Change the datatypes of a,b and c to long, and it will start working fine. Your numbers are crossing the limits for int.

Upvotes: 0

Related Questions