5

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.

5
  • 1
    I think there's no reason to use the class Integer. you better use int, in this case.
    – cd1
    Commented Jun 25, 2009 at 17:28
  • Simultaneous assigments are really nice. I wonder if anybody knows why they are not part of java? Commented Nov 10, 2011 at 20:39
  • @ThomasAhle probably because they're confusing as hell :) Commented Nov 10, 2011 at 23:55
  • TK Kocharan: In them selves, or some of the stuff you can do with them? I always thought they were easier to analyze, because you didn't have to worry about the order of things. Commented Nov 11, 2011 at 13:54
  • @ThomasAhle When I first saw them, it broke my logic (see above). The whole basis of this question is that I assumed that they would work a certain way, and they don't :( Commented Nov 11, 2011 at 20:08

10 Answers 10

7

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.]

2
  • Thanks! That totally solves my problem! Thanks for getting back so quickly! I was tearing my hair out with the python code. I had no idea why it would execute correctly in Python and not in Java. Thanks! Commented Jun 25, 2009 at 17:28
  • Java has no parallel assignment like Python which is why you need the temp variable. The issue is not math but a deeper understanding of what it means to have parallel assignment (S. Lott describes the meaning reasonably well). Commented Jun 25, 2009 at 17:56
4

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
2

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;
    }
1

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

0

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;
  }
}
0

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.

2
  • 1
    That algorithm takes time growing exponentially in the initial value of index, since it keeps recalculating the same numbers.
    – alicederyn
    Commented Jun 25, 2009 at 18:15
  • I didn't say it was optimal, just that this is how recursion was taught when I had Computer Science 101 in univeristy.
    – JB King
    Commented Jun 25, 2009 at 21:20
0

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.

1
  • Yeah I'll probably end up making it output Long values. Commented Jun 25, 2009 at 17:44
0

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);
    }
}
0

i'll do this

fib = 100;
for(int a = 1, b = 0;a <= fib;a += b, b = (a-b)) {
    System.out.print(a + ",");
}
1
  • This int value will overflow after the first 40 or so values. The last 60 will be overflowed values and non-sense. ;) Commented Apr 11, 2010 at 9:19
-1

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

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

1
  • It most certainly will not! You need a temporary, as stated elsewhere.
    – alicederyn
    Commented Jun 25, 2009 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.