Print first n Fibonacci Numbers

[DragonOsman]

I need to write a program that prints the first n Fibonacci numbers (it also has to find the largest Fibonacci number that can fit into an int, but I'll worry about that later).

Here's my code (the program currently crashes after printing 0 and 1):

// chapter5ex11.cpp : Defines the entry point for the console application.
// Osman Zakir
// 1 / 2 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 5 Exercise 11
/**
 * Write a program that writes out the first so many values of the Fibonacci
 * series, that is, the series that starts with 1 1 2 3 5 8 13 21 34. The next
 * number of the series is the sum of the two previous ones. Find the largest
 * Fibonacci number that fits in an int.
 */

#include "../../std_lib_facilities.h"

int fibonacci(int number);

int main()
{
	cout << "How many Fibonacci numbers do you want to see?\n";
	int number = 0;
	cin >> number;
	cin.ignore();

	for (int i = 0; i < number; ++i)
	{
		cout << fibonacci(i) << ' ';
	}
	cout << '\n';
	keep_window_open();
}

int fibonacci(int number)
{
	if (number <= 1)
	{
		return number;
	}
	return fibonacci(number - 1) + fibonacci(number + 1);
}

Edit: I think I found the problem. It apparently stopped working because of the recursive function. I don't understand why, though.

Anyway, I found an iterative solution on another website that works for me as an alternative. I wrote my fibonacci() function using that:

// chapter5ex11.cpp : Defines the entry point for the console application.
// Osman Zakir
// 1 / 2 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 5 Exercise 11
/**
 * Write a program that writes out the first so many values of the Fibonacci
 * series, that is, the series that starts with 1 1 2 3 5 8 13 21 34. The next
 * number of the series is the sum of the two previous ones. Find the largest
 * Fibonacci number that fits in an int.
 */

#include "../../std_lib_facilities.h"

int fibonacci(int number);

int main()
{
	cout << "How many Fibonacci numbers do you want to see?\n";
	int number;
	cin >> number;
	cin.ignore();

	for (int i = 0; i < number; ++i)
	{
		cout << fibonacci(i) << ' ';
	}
	cout << '\n';

	int largest = fibonacci(46);
	cout << "The largest Fibonacci number that can be represented as an integer "
		<< "on a computer is " << largest << '\n';
	keep_window_open();
}

int fibonacci(int number)
{
	int previous = 1;
	int current = 1;
	int next = 1;
	for (int i = 3; i <= number; ++i)
	{
		next = current + previous;
		previous = current;
		current = next;
	}
	return next;
}

I wonder if my method of finding the largest Fibonacci number that can fit in an int is good? And by the way, in case anyone's wondering, this is where I found the iterative version of the function: http://www.sanfoundry.com/cpp-program-find-fibonacci-numbers-iteration/.

[cire]

Edit: I think I found the problem. It apparently stopped working because of the recursive function. I don't understand why, though.

int fibonacci(int number)
{
	if (number <= 1)
	{
		return number;
	}
	return fibonacci(number - 1) + fibonacci(number + 1);
}

When do you think number <=1 will be true when you're doing fibonacci(number+1)?

I wonder if my method of finding the largest Fibonacci number that can fit in an int is good?

You didn't present code that accomplishes that.

Here's an alternate approach that relies on integer values wrapping around when overflow occurs:

#include <iostream>

int main() {
    using int_type = int;   // also try different types such as long long or unsigned int variants

    int_type prev[] = { 0, 1 };

    std::size_t n = 1;

    int_type next;
    while (next = prev[0] + prev[1], next >= prev[1])
    {
        prev[0] = prev[1];
        prev[1] = next;

        ++n;
    }

    std::cout << '\n' << prev[1] << " is the largest fibonacci number respresentable.\n";
    std::cout << "It is number " << n << " in the series.\n";
}

[lastchance]

Have a play with different integer types:

#include<iostream>
#include<vector>
#include<limits>
using namespace std;


//typedef int                INT;      // uncomment ONE of these to choose an integer type
  typedef unsigned long long INT;      //
//typedef size_t             INT;      //


INT fib( int N )                       // returns just Nth Fibonacci number (having computed all previous ones!)
{
   INT a = 1, b = 1;
   INT temp;

   for ( int i = 3; i <= N; i++ )
   {
      temp = a + b;
      a = b;
      b = temp;
   }
   return b;
}


void fib( int N, vector<INT> &f )      // overloaded function returns vector of first N Fibonacci numbers
{
   INT a = 1, b = 1;
   INT temp;

   f.clear();
   f.push_back( a );
   f.push_back( b );

   for ( int i = 3; i <= N; i++ )
   {
      temp = a + b;
      a = b;
      b = temp;
      f.push_back( b );
   }
}


INT fibMax( INT &maxinteger, int &N )  // returns maximum integer of this type, maximum N and maximum fib()
{
   maxinteger = numeric_limits<INT>::max();

   INT a = 1, b = 1;
   INT temp;

   N = 2;
   while ( b <= maxinteger - a )
   {
      temp = a + b;
      a = b;
      b = temp;
      N++;
   }
   return b;
}


int main()
{
   int N;
   cout << "Input N (>2):";    cin >> N;
   cout << "fib(N) = " << fib( N ) << endl;

   vector<INT> f;
   fib( N, f );
   cout << "\nSequence of i, fib(i) is:\n";
   for ( int i = 1; i <= N; i++ ) cout << i << "   " << f[i-1] << endl;        // care with array index


   int Nmx;
   INT imx;
   INT fibmx = fibMax( imx, Nmx );
   cout << "\nMaximum value of this type of integer is " << imx << endl;
   cout << "Largest N, fib(N) = " << Nmx << ",  " << fibmx;
}

Or, if you want really large Fibonacci numbers:

#include<iostream>
#include<cmath>
using namespace std;

double fib( int N )
{
   double X = 0.5 * ( 1.0 + sqrt( 5.0 ) );       // golden mean
   double Y = 1.0 - X;
   return ( pow( X, N ) - pow( Y, N ) ) / ( X - Y );
}

int main()
{
   for ( int i = 1; i <= 500; i++ ) cout << "fib(" << i << ") = " << fib( i ) << endl;
}

[DragonOsman]

You didn't present code that accomplishes that.

Are you sure I didn't? Look at my code again. The largest Fibonacci number that can fit into an int is the 46th one. Now look here:

int largest = fibonacci(46);

That's line 30 in the code I posted earlier.

I mean, yeah, I didn't do any actual math to find it but just looked at the program's output and found what the limit was that the numbers started to get into the negative numbers' range at.

For some reason, it just won't start do it as

0 1 1 2 3 ...

It always starts at 1 and then does everything else as it should be, and it prints 1 three times at the beginning instead of twice, so it's like this:

1 1 1 2 3 ...

[lastchance]

The largest Fibonacci number that can fit into an int is the 46th one. Now look here:
int largest = fibonacci(46);
That's line 30 in the code I posted earlier.

I'm not sure that 46 is one of those particularly memorable numbers ... ! (But then I turned to Wikipedia: https://en.wikipedia.org/wiki/46_(number) )


The Fibonacci sequence starts
a b a+b (b+a+b) ....
and exactly which sequence you get depends on how you set the "seeds" a and b.

Some people (myself included, because then the only repeat is at the start) prefer
1 1 2 3 5 8 ....
and others prefer
0 1 1 2 3 5 ....

In your code

int fibonacci(int number)
{
	int previous = 1;
	int current = 1;
	int next = 1;
	for (int i = 3; i <= number; ++i)
	{
		next = current + previous;
		previous = current;
		current = next;
	}
	return next;
}

it is clear that the seeds are 1 and 1, giving the first series (starting 1 1 2 3 ...). Moreover, the for loop will only run at all if number is >=3. Hence, if number = 0, 1, or 2 then this function will just return 1 (the initial value of next). (From its form, I think this function is really only expecting number to be 1,2,3 ... etc, not 0).

In your main() routine:

	for (int i = 0; i < number; ++i)
	{
		cout << fibonacci(i) << ' ';
	}

the first three values of i sent to fibonacci are 0, 1, 2 ... and so your function returns 1, 1, 1 ... as you have coded!

[DragonOsman]

The 46th Fibonacci seems to be the highest that can fit into an int, since I've noticed that it's after that point that the numbers start getting negative. That largest number is 1, 836, 311, 903.

Anyway, how do I fix the problem you've addressed here? Out of previous, next and current, which ones are the seeds? And do I set the seeds as 0 or as 1? Or should one be 1 and the other 0?

But the exercise starts for the series that starts with

1 1 2 3 5 8 13 21 34

I guess I should leave it as it is. I just want to know how to have it start from 0, just for reference.

[lastchance]

I just want to know how to have it start from 0, just for reference. 

The layout of your code makes this a little difficult, actually. I think you only have to change the initialisation of previous and start the for loop correctly in main().

The seeds are previous and current. You should really only call the function for number = 1, 2, 3, ...

I have had to put standard headers in to allow it to run in cpp shell for you to try online.

fib(46) is not the largest representable int if your series starts from 0. On my system the largest Fibonacci number representable as an int is 1836311903 (which isn't what your code produces if the first value is 0). The value can, in principle, depend on your compiler and OS. You can get larger values from unsigned long long.

#include<iostream>
using namespace std;

int fibonacci(int number);

int main()
{
	cout << "How many Fibonacci numbers do you want to see?\n";
	int number;
	cin >> number;
	cin.ignore();

	for (int i = 1; i <= number; ++i)       // <==== START AT 1, NOT 0
	{
		cout << fibonacci(i) << ' ';
	}
	cout << '\n';

	int largest = fibonacci(46);            // <==== NOT CORRECT WITH YOUR SEED
	cout << "The largest Fibonacci number that can be represented as an integer "
		<< "on a computer is " << largest << '\n';
}

int fibonacci(int number)
{
	int previous = 0;    if ( number <= 1 ) return previous;      // <==== change this one
	int current = 1;
	int next = 1;
	for (int i = 3; i <= number; ++i)
	{
		next = current + previous;
		previous = current;
		current = next;
	}
	return next;
}

[integralfx]

The n^th Fibonacci number is given by the sum of the n-1^th Fibonacci number and the n-2^th Fibonacci number.

int fibonacci(int number)
{
	if (number <= 1)
	{
		return number;
	}
	return fibonacci(number - 1) + fibonacci(number + 1);
}

Your code, on the other hand, calculates the n^th Fibonacci number by the sum of the n-1^th and n+1^th number. It also goes into an infinite recursion, until number overflows or the stack overflows.

This is probably what you are looking for.

int fib( int n )
{
    if( n <= 0 ) return -1;
    if( n == 1 || n == 2 ) return 1;
    return fib( n - 1 ) + fib( n - 2 );
}

After about the 43rd number, it takes an increasingly long time to calculate, at least on cpp.sh. Also, as mentioned above, the result will overflow when n = 47.

[cire]

I mean, yeah, I didn't do any actual math to find it but just looked at the program's output and found what the limit was that the numbers started to get into the negative numbers' range at.

Correct. Your code does not find it, but you can find it by inspecting your program's output. By contrast, the code I posted does find it - no inspection required.

[DragonOsman]

@lastchance: So since my code starts it at 1, fibonacci(46) is the largest representable int? If it had started at 0 with my code, it would've been different? Makes sense.

@cire: How should I find the highest Fibonacci number in my code, then? Will using the max() method of numeric_limits work here?

[lastchance]

Cire's approach compares the new value with the old and correctly adjudges it overflowing and stops looping when the new value is smaller than the old. Note that it does NOT rely on going negative, simply SMALLER.
while (next = prev[0] + prev[1], next >= prev[1])

In my, slightly different, approach I (indirectly) needed to establish whether a+b was going to exceed maxinteger (which I needed to have found first):
while ( b <= maxinteger - a )


However, if you look for NEGATIVE values ... then, although it will work for an int, it will not work if you decided to use unsigned int (or even unsigned long long) in order to get larger values.

[DragonOsman]

So if, in main, I put the return value of my Fibonacci function into a variable and check it to see if it's greater than or equal to MAXINT or to numeric_limits<in>::max(), will it work?

Edit: Never mind, it didn't work.

[48T7M4Gy]

Still checking but it seems to work once the -ve results are included in test condition.

#include <iostream>
#include <limits>

int fibonacci(const int);

int main()
{
    int i = 0;
    int fib_no = 0;
    
    
    while ( (fib_no = fibonacci(i)) && fib_no > 0 && fib_no < std::numeric_limits<int>::max())
    {
        std::cout << '\t' << fib_no;
        i++;
    }
    std::cout << '\n';
    return 0;
}

int fibonacci(const int no_steps)
{
    int count = 0;
    int temp = 0;
    
    int previous = 0;
    int current = 1;
    
    while( count < no_steps )
    {
        temp = current;
        current = current + previous;
        previous = temp;
        
        count++;
    }
    return current;
}

1	1	2	3	5	8	13	
21	34	55	89	144	233	377	
610	987	1597	2584	4181	6765	10946	
17711	28657	46368	75025	
121393	196418	317811	514229	
832040	1346269	2178309	3524578	
5702887	9227465	14930352	24157817	
39088169	63245986	102334155	165580141	
267914296	433494437	701408733	
1134903170	1836311903

Program ended with exit code: 0

[48T7M4Gy]

Checks out OK because next number in series is 2971215073

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html

[lastchance]

So if, in main, I put the return value of my Fibonacci function into a variable and
check it to see if it's greater than or equal to MAXINT or to numeric_limits<in>::max(), will it
work? 

No. By definition, it will never be bigger than numeric_limits<int>::max() - it will wrap around at this point. You can detect this (in main()) if you find one Fibonacci number to be SMALLER than the previous one (effectively what @Cire was doing). If you use int as integer type then this will be negative, so OK, in that case, you can check from that. However, if you decide to use unsigned int (or unsigned long, or unsigned long long) as integer type then there never will be negative numbers, so I feel that SMALLER THAN is a better test than NEGATIVE in general.

[48T7M4Gy]

#include <iostream>
#include <limits>

int fibonacci(const int);

int main()
{
    int i = 0;
    int fib_no = 0;
    int required_fibonacci_number;
    
    std::cout << "What Fibonnaci number do you want?: ";
    std::cin >> required_fibonacci_number;
    
    if ( (fib_no = fibonacci(required_fibonacci_number - 1) ) && fib_no > 0 && fib_no < std::numeric_limits<int>::max() )
        std::cout << fib_no << '\n';
    else
        std::cout << "Limit of <int> exceeded\n";
    
    while ( (fib_no = fibonacci(i)) && fib_no > 0 && fib_no < std::numeric_limits<int>::max())
    {
        std::cout << i + 1 << '\t' << fib_no << '\n';
        i++;
    }
    std::cout << '\n';
    
    return 0;
}

int fibonacci(const int no_steps)
{
    int count = 0;
    int temp = 0;
    
    int previous = 0;
    int current = 1;
    
    while( count < no_steps )
    {
        temp = current;
        current = current + previous;
        previous = temp;
        
        count++;
    }
    return current;
}

[48T7M4Gy]

* Write a program that writes out the first so many values of the Fibonacci
* series, that is, the series that starts with 1 1 2 3 5 8 13 21 34. The next
* number of the series is the sum of the two previous ones. Find the largest
* Fibonacci number that fits in an int.

[DragonOsman]

I got it. Here:

// chapter5ex11.cpp : Defines the entry point for the console application.
// Osman Zakir
// 1 / 2 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 5 Exercise 11
/**
 * Write a program that writes out the first so many values of the Fibonacci
 * series, that is, the series that starts with 1 1 2 3 5 8 13 21 34. The next
 * number of the series is the sum of the two previous ones. Find the largest
 * Fibonacci number that fits in an int.
 */

#include "../../std_lib_facilities.h"

int fibonacci(int number);

int main()
{
	cout << "How many Fibonacci numbers do you want to see?\n";
	int number;
	cin >> number;
	cin.ignore();

	int largest = 0;
	int i = 0;
	int fib;
	while ((fib = fibonacci(i)) && fib > 0 && fib < numeric_limits<int>::max())
	{
		if (i <= number)
		{
			cout << fibonacci(i) << ' ';
		}
		largest = fibonacci(i);
		++i;
	}
	cout << '\n';
	cout << "largest Fibonacci number for an int is " << largest << '\n';
	keep_window_open();
}

int fibonacci(int number)
{
	int previous = 1;
	int current = 1;
	int next = 1;
	for (int i = 3; i <= number; ++i)
	{
		next = current + previous;
		previous = current;
		current = next;
	}
	return next;
}

Thanks, Kemort.

[48T7M4Gy]

http://www.cplusplus.com/articles/DE18T05o/

Detecting overflow:

Division and modulo can never generate an overflow.

Addition overflow:
Overflow can only occur when sign of numbers being added is the same (which will always be the case in unsigned numbers)
signed overflow can be easily detected by seeing that its sign is opposite to that of the operands.

Let us analyze overflow in unsigned integer addition.

Consider 2 variables a and b of a data type with size n and range R.
Let + be actual mathematical addition and a$b be the addition that the computer does.

If a+b<=R-1, a$b=a+b
As a and b are unsigned, a$b is more or equal to than both a and b.

If a+b>=R a$b=a+b-R
as R is more than both a and b, a-R and b-R are negative
So, a+b-R<a and a+b-R<b
Therefore, a$b is less than both a and b.

This difference can be used to detect unsigned addition overflow. a-b can be treated as a+(-b) hence subtraction can be taken care of in the same way.

[48T7M4Gy]

http://stackoverflow.com/questions/18195715/why-is-unsigned-integer-overflow-defined-behavior-but-signed-integer-overflow-is