 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
Fibonacci Sequence        Author Message
randint Posted: 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)

Fibonacci_Sequence.java
Description:
 Fibonacci Sequence program Filename:  Fibonacci_Sequence.java
Filesize:  974 Bytes    Zren  Posted: 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. randint Posted: 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).

Fibonacci_Sequence.java
Description:
 The Second Version of Fibonacci Sequence calculator Filename:  Fibonacci_Sequence.java
Filesize:  1016 Bytes DemonWasp Posted: 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 Zren  Posted: 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. DemonWasp Posted: 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. randint Posted: 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). Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Page 1 of 1  [ 7 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: