How to create Fibonacci Sequence in Java

Question

I really suck at math. I mean, I REALLY suck at math. I'm trying to make a simple fibonacci sequence class for an algorithm I'll be using. I have seen the python example which looks something like this:

a = 0
b = 1
while b < 10:
    print b
    a, b = b, b+a

The problem is that I can't really make this work in any other language. I'd like to make it work in Java, since I can pretty much translate it into the other languages I use from there. This is the general thought:

    public class FibonacciAlgorithm {

 private Integer a = 0;

 private Integer b = 1;

 public FibonacciAlgorithm() {

 }

 public Integer increment() {
  a = b;
        b = a + b;
  return value;
 }

 public Integer getValue() {
  return b;
 }
}

All that I end up with is doubling, which I could do with multiplication :( Can anyone help me out? Math pwns me.

Answer 1

The line

a, b = b, b+a

Doesn't easily translate. It's something like this. You could simplify it. This is the literal meaning.

t1 = b
t2 = b+a
a = t1
b = t2

Answer 2

I'd do it this way:

public class FibonacciAlgorithm {

    private int a = 0;

    private int b = 1;

    public FibonacciAlgorithm() {

    }

    public int increment() {
        int temp = b;
        b = a + b;
        a = temp;
        return value;
    }

    public int getValue() {
        return b;
    }
}

This keeps it as close to your original Java code as possible.

[Editor's note: Integers have been replaced with ints. There is no reason to use Integers for this.]

Answer 3

public Integer increment() { a = b; b = a + b; return value; }

Is certainly wrong. I think switching the first two lines should do the trick

Answer 4

You need to store the value of either a or b in a temporary variable first;

    public Integer increment() 
    {                
            int temp = a;
            a = b;
            b = temp + b;
            return value;
    }

Answer 5

Java integers can only store the first 46 Fibonacci numbers, use a lookup table.

Answer 6

I'll just translate your earlier code:

public void fibb(int max) {
  int a = 0;
  int b = 1;
  while (a < max) {
    System.out.println(a);
    int temp = a + b;
    a = b;
    b = temp;
  }
}

Answer 7

Don't you want to create a function to return the nth Fibnoacci number? This is how I remember it being taught when I was a kid:

public int Fibb(int index) {
if (index < 2)
    return 1;
else
    return Fibb(index-1)+Fibb(index-2);
};

Given the definition being the first pair of Fibbonaci numbers are 1 and everything else is based off of that. Now, if you merely want to print out the Fibonaccis a loop may be simpler which is what a lot of the other replies cover.

Answer 8

The main problem with your Python-to-Java translation is that Python's assignment statement up there is executed all at once, while Java's are executed serially. Python's statement is equivalent to saying this:

Make a list out of 'b' and 'a + b'
Make another list out of references to 'a' and 'b'
Assign all the elements from the second list to the first one

(It might actually be a tuple, I'm not exactly fluent in Python.)

So the 'b' and 'a+b' resolve to values before they are assigned. You can't do that kind of multiple-simultaneous assignment in Java.

In general, a statement in Python like

var1, var2, ...varN = expression1, expression2, ...expressionN

is going to translate in Java to

temp1 = expression1;
temp2 = expression2;
...
tempN = expressionN;
var1 = temp1;
var2 = temp2;
...
varN = tempN;

This way all the expressions resolve to values before the assignments happen, and none of the assignments have side effects on the expressions.

If I were doing this for real I'd probably do the lookup table and store longs (since Fibonacci numbers grow vaguely exponentially and I'd want to go past 46). The iterative form, like you have, will take O(N) to calculate the Nth Fibonacci value; the typical recursive formulation will take as many function calls as the returned value. Fibonacci practically begs for the answers to be cached somewhere, and this would make the recursive form much more feasible.

Answer 9

There was a recursive solution posted above, but this solution is tail recursive so it grows linearly.

public class Fibonacci {
    public long fibonacci(int number) {
        return fib(0,1,number);
    }

    private long fib(long result, long next, int n) {
        if (n == 0)
            return result;
        else
            return fib(next, result+next, n-1);
    }
}

Answer 10

i'll do this

fib = 100;
for(int a = 1, b = 0;a <= fib;a += b, b = (a-b)) {
    System.out.print(a + ",");
}