Computer Science Canada

Fibonacci Sequence

Author:  randint [ Wed Dec 28, 2011 11:25 am ]
Post subject:  Fibonacci Sequence

This program will calculate the nth term of the Fibonacci Sequence (n is the user's input)

Author:  Zren [ Thu Dec 29, 2011 2:02 am ]
Post subject:  RE:Fibonacci Sequence

Java:

for (int i = 2 ; i < input ; i++) {
    temp [i] = temp [i - 1] + temp [i - 2];
    answer = temp [i];
}


Why are you setting the answer variable for every iteration? Imaging if the desired term was 100000. You'd wast time assigning a variable 99999 times. Just because the operation itself might be fast, doesn't mean you should abuse it.

Also, what happens when you ask for a term of 0.

Author:  randint [ Thu Dec 29, 2011 11:13 am ]
Post subject:  Re: Assigning Variable and Fibonacci Sequence v. 2

Well, we have gigabytes of RAM on our computers, right? These things are integers after all (I'm uploading a version with long integers in this reply), and addition is fast as you said.
Long numbers allow larger input for the number (in integers, if the input is greater than 48, the answer is no longer accurate but with long integers, this limit can be extended to 161, which is more than tripled. But the use of float or double is inappropriate in this situation, given sequences are only for natural numbers, which are positive integers).

Author:  DemonWasp [ Thu Dec 29, 2011 1:50 pm ]
Post subject:  RE:Fibonacci Sequence

If you want to be able to extend to arbitrary values (and you should!) read about BigInteger: http://compsci.ca/v3/viewtopic.php?t=13193

Author:  Zren [ Thu Dec 29, 2011 7:36 pm ]
Post subject:  RE:Fibonacci Sequence

It wasn't the fact you were remembering more, it was that you were wasting time overriding a variable tons of time. Basically I was pushing you into assigning the variable after you have calculated the targeted term bacause you never use that partially calcuated 'answer'.

Java:

for (int i = 2 ; i < input ; i++) {
    temp [i] = temp [i - 1] + temp [i - 2];
}
answer = temp[input - 1];


~

After you've checked out the limit DW mentioned, you'll find your next limit would be your RAM. The following is for if you needed to tackle those higher terms, or if you just wanted to know your limitations.

From your comment on RAM. If your goal was to calculate the term of 1 000 000, you'd probably find that you'll run out of memory. A primitive long is 64 bits (8 bytes) of data. So your temp array (if the target term was only 100 000) would be around ~800 Mb. ((100 000 * 64 bits) / 8 [-> bytes]) / 1 024 [-> Mb] = 781.25 Mb. So your next maximum term would be round 500 000 if you had 3Gb of RAM (less because of OS + etc).

Now if you start using BigNum, which is an object, you'll reach that limit even faster as the size of the object would be larger as it first has the overhead of being an Object. The actual size of the object increases as the value itself gets bigger. Just turning the data types into the Long object would double the size into 16 bytes (further reading).

So long as your only goal is to calculate just one number of the fibinacci sequence, and you don't need to remember all the terms up to that point, you really only need to remember the last 2 term values at any given time. If your program's goal was to get more than one term of the sequence (not all at once), then storing the calculations for later use (like you are) would be ideal.

Author:  DemonWasp [ Fri Dec 30, 2011 8:24 am ]
Post subject:  RE:Fibonacci Sequence

Zren: KiloBytes before MegaBytes. The hypothetical array of 100 000 longs is only 800 000 B = 781.25 KB.

Author:  randint [ Fri Dec 30, 2011 6:43 pm ]
Post subject:  RE:Fibonacci Sequence

Well...there is a huge problem with BigInteger or BigDecimal, because it is an object, you cannot use it as array indexes or in for loops (I do not know how enhanced for loops work), these things, also, will have problem when you are comparing the numeric values of different BigInteger objects, and arithmetic is even more painful. I am currently not considering this as an option as it brings about too many problems. Now you see the advantage of using primitives, yes, I always wondered, what if a double is not enough for a programmer to hold some numeric value (larger than Double.MAX_VALUE but less than Double.POSITIVE_INFINITY), you cannot create a primitive yourself as that would be considered redesigning the entire language, which needs a lot of time and work. But then, these arbitrary integers and decimals come into play, which means you are not using the normal way to do math in these things, so I think primitives are still better no matter what (as long as for loops and arrays are required).


: