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

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?

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.