Thread: Find the largest Fibonacci that fits in an int: It's running extremely slowly...

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    32

    Find the largest Fibonacci that fits in an int: It's running extremely slowly...

    It's running unbelievably slowly. Can you help suggest the way to improve the code in a simple way (simple code, 'coz I'm still at a very beginning level)? Thanks a lot.

    Code:
    // Exercise 11 - Chapter 5
    // Write out the fist so many values of the Fibonacci series
    // i.e.  1 1 2 3 5... the next number is the sume of the 2 previous ones
    // Find the largest Fibonacci number that fits an int
    
    #include "std_lib_facilities.h"
    #include <limits.h>
    
    int Fibonacci (int n)
    {
    	if (n==1||n==2) {
    		return 1;
    	}
    	return Fibonacci(n-1) + Fibonacci(n-2);
    }
    
    int main()
    {
    	int n;
    	cout << "Enter how many values of the Fibonacci series you wish to print out: \n";
    	cin >> n;
    	cout << "The first " << n << " values of the Fibonacci series is: \n";
    	// print the first n values of the Fibonacci series
    	for (int i=1; i<=n; ++i)
    		cout << Fibonacci(i) << endl;
    	
    	// find the largest Fibonacci number that fits in an int
    	int k = 1;
    	int count_Fib = 0;
    	while (Fibonacci(k)<INT_MAX) {
    		++count_Fib;
    		++k;
    		cout << "k = " << k << "\tcount_Fib = " << count_Fib << endl;
    	}
    	
    	cout << "Final k = " << k << endl;
    	cout << "Final count_Fib = " << count_Fib << endl;
    	cout << "Fibonacci(k) = " << Fibonacci(k) << endl;
    	cout << "The largest Fibonacci number for an int is " << Fibonacci(count_Fib) << endl;	
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    That's because you're recalculating all previous answers numerous times to get each new answer, including all the work it took to calculate those answers as well.

    It's another Schlemiel the painter's Algorithm, I'm afraid.

    Can you think of a non-recursive solution that involves only one addition for each new result?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by pantera
    It's running unbelievably slowly.
    It might just be running in an effectly infinite loop. The problem is that the only surefire way for Fibonacci(k)<INT_MAX to evaluate to false is for Fibonacci(k) to be equal to INT_MAX. A quick check shows that the most common values of INT_MAX do not appear in the Fibonacci sequence that you are dealing with.

    Anyway, if you think about it, you are trying to "find the largest Fibonacci number that fits in an int" by storing the smallest Fibonacci number that does not fit into an int into an int variable... which is contradictory.

    One way to solve this is to subtract from INT_MAX one of the two numbers that are to be summed. If the difference is less than the other number, then the previous Fibonacci number is the largest that fits in an int.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to combine these working parts??
    By transgalactic2 in forum C Programming
    Replies: 0
    Last Post: 02-01-2009, 08:19 AM
  2. Debug Error Really Quick Question
    By GCNDoug in forum C Programming
    Replies: 1
    Last Post: 04-23-2007, 12:05 PM
  3. Game Won't Compile
    By jothesmo in forum C++ Programming
    Replies: 2
    Last Post: 04-01-2006, 04:24 PM
  4. Replies: 2
    Last Post: 03-24-2006, 08:36 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM