C++

Forum

 
 
Fibonacci number

closed account (9G3v5Di1)
Write a program that will display the nth Fibonacci number. Create a function that will generate the nth Fibonacci number. Fibonacci numbers are numbers from the Fibonacci sequence which follows the pattern of 1, 1, 2, 3, 5, 8, 13, 21, 33, 54…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
  #include <stdio.h> 
#include <iostream>
#include "_pause.h"

using namespace std;

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

  cout << "Enter nth number of fibonacci: ";
  cin >> n;

  printf("%d", fib(n)); 

  cout << endl;
  
  std::cin.get();
	_pause();
  return EXIT_SUCCESS; 
}


Line 12,
 Enter nth number of fibonacci: 8
(8-1) + (8-2) = 13


but in my program,
 Enter nth number of fibonacci: 8
21


how come?
PS: I know fibonacci so don't worry

In line 21, how do I change it to cout? I still haven't learned about printf so it better be cout. Please help

Edit: Okay so line 21 could be just cout << fib(n); , but what does %d mean?
Last edited on
kbw (9488)
The first few numbers are here: https://en.wikipedia.org/wiki/Fibonacci_number#List_of_Fibonacci_numbers

So the 8th number is 21. I'm not sure why you think it's 13.

closed account (9G3v5Di1)
If I entered 9, how does the computation work?
closed account (E0p9LyTq)
In line 21, how do I change it to cout?


std::cout << fib(n) << ' ';
kbw (9488)
Well, you're algorithm doesn't work for fib(2).
closed account (E0p9LyTq)
PS: I know fibonacci so don't worry

Your function doesn't work for all numbers. Such as 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
unsigned long long fib(unsigned long n)
{
   unsigned long long minusTwo = 1;
   unsigned long long minusOne = 1;
   unsigned long long answer   = 2;

   if (n < 3)
   {
      return 1;
   }

   for (n -= 3; n; n--)
   {
      minusTwo = minusOne;
      minusOne = answer;
      answer   = minusOne + minusTwo;
   }

   return answer;
}

There is a limit to how large a starting number can be entered. With a large enough starting number even an unsigned long long won't contain the entire Fibonacci number.
closed account (9G3v5Di1)
My function works for 2.

Fibonacci starts at 0,1,1,2,3,5,8,13.. and so on

So counting from 0 to the second 1, 0,1,2. I got the correct answer.
Thomas1965 (4571)
The original code is correct for numbers from 0 to 20.
https://en.wikipedia.org/wiki/Fibonacci_number#List_of_Fibonacci_numbers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
// https://github.com/catchorg/Catch2
#define CATCH_CONFIG_MAIN
#include "catch.hpp"
#include <stdint.h>

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

TEST_CASE("Fibonacci test 1 - 5")
{
  CHECK(fib(0) == 0);
  CHECK(fib(1) == 1);
  CHECK(fib(2) == 1);
  CHECK(fib(3) == 2);
  CHECK(fib(4) == 3);
  CHECK(fib(5) == 5);
}

TEST_CASE("Fibonacci test 6 - 10")
{
  CHECK(fib(6) == 8);
  CHECK(fib(7) == 13);
  CHECK(fib(8) == 21);
  CHECK(fib(9) == 34);
  CHECK(fib(10) == 55);
}
TEST_CASE("Fibonacci test 11 - 20")
{
  CHECK(fib(11) == 89);
  CHECK(fib(12) == 144);
  CHECK(fib(13) == 233);
  CHECK(fib(14) == 377);
  CHECK(fib(15) == 610);
  CHECK(fib(16) == 987);
  CHECK(fib(17) == 1597);
  CHECK(fib(18) == 2584);
  CHECK(fib(19) == 4181);
  CHECK(fib(20) == 6765);
}


All tests passed (21 assertions in 3 test cases)


There is a limit to how large a starting number can be entered. With a large enough starting number even an unsigned long long won't contain the entire Fibonacci number.
True. Any number type will eventually overflow.

Fibonacci number are also defined for negative numbers so an unsigned type is not a solution.
lastchance (6980)
I'm not sure that this is a good use of recursion. The way that you are setting up, (a) you are re-computing the same thing many times (which could be overcome by memoisation); (b) each call to fib() puts two function pointers on the stack; i.e. exponential growth - I'm not sure which will blow up first: the stack or the Fibonacci number you are trying to represent.

Why don't you do it the easy ways: either push_back to a vector, keep a rolling sequence of the last three, or use the analytical solution.
Thomas1965 (4571)
I guess it's just an exercise for recursion.
An iterative approach would probably faster.
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;

unsigned long long fib1( int n )   // rolling sequence of 3 
{
   if ( n <= 1 ) return n;
   unsigned long long a = 0, b = 1, c = a + b;
   for ( int i = 3; i <= n; i++ )
   {
      a = b;
      b = c;
      c = a + b;
   }
   return c;
}


unsigned long long fib2( int n )   // use a vector
{
   if ( n <= 1 ) return n;
   vector<unsigned long long> F(n+1);
   F[0] = 0;   F[1] = 1;
   for ( int i = 2; i <= n; i++ ) F[i] = F[i-1] + F[i-2];
   return F[n];
}



unsigned long long fib3( int n )   // exact solution of difference equation
{
   const double phi1 = 0.5 * ( sqrt( 5 ) + 1 ), phi2 = phi1 - 1;
   if ( n <= 1 ) return n;
   int s = 1;   if ( n % 2 ) s = -1;
   unsigned long long F = 0.5 + ( pow( phi1, n ) - s * pow( phi2, n ) ) / ( phi1 + phi2 );
   return F;
}


int main() 
{
   int nmax = 60;
   #define SP << setw( 15 ) << 
   for ( int n = 0; n <= nmax; n++ )
   {
      cout SP n << ':' SP fib1( n ) SP fib2( n ) SP fib3( n ) << '\n';
   }
}
Thomas1965 (4571)
@lastchance,
interestingly all 3 version run in the same time.
Had to use DEBUG mode since release mode shows 0ns 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
#pragma warning(disable: 4624 4715)
// https://github.com/catchorg/Catch2
#define CATCH_CONFIG_MAIN
#include "catch.hpp"
#include <stdint.h>
#include <vector>

const int fib_numbers[] = { 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765};
const int N = sizeof(fib_numbers) / sizeof(fib_numbers[0]);

unsigned long long fib1(int n)   // rolling sequence of 3 
{
  if (n <= 1) return n;
  unsigned long long a = 0, b = 1, c = a + b;
  for (int i = 3; i <= n; i++)
  {
    a = b;
    b = c;
    c = a + b;
  }
  return c;
}

unsigned long long fib2(int n)   // use a vector
{
  if (n <= 1) return n;
  std::vector<unsigned long long> F(n + 1);
  F[0] = 0;   F[1] = 1;
  for (int i = 2; i <= n; i++) F[i] = F[i - 1] + F[i - 2];
  return F[n];
}

unsigned long long fib3(int n)   // exact solution of difference equation
{
  const double phi1 = 0.5 * (sqrt(5) + 1), phi2 = phi1 - 1;
  if (n <= 1) return n;
  int s = 1;   if (n % 2) s = -1;
  unsigned long long F = 0.5 + (pow(phi1, n) - s * pow(phi2, n)) / (phi1 + phi2);
  return F;
}


TEST_CASE("Fib1")
{
  BENCHMARK("Fib1");
  for (int i = 0; i < N; i++)
  {
    CHECK(fib1(i) == fib_numbers[i]);
  }
}

TEST_CASE("Fib2")
{
  BENCHMARK("Fib2");
  for (int i = 0; i < N; i++)
  {
    CHECK(fib2(i) == fib_numbers[i]);
  }
}

TEST_CASE("Fib3")
{
  BENCHMARK("Fib3");
  for (int i = 0; i < N; i++)
  {
    CHECK(fib2(i) == fib_numbers[i]);
  }
}


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Catch2_Demo.exe is a Catch v2.0.1 host application.
Run with -? for options

-------------------------------------------------------------------------------
Fib1
-------------------------------------------------------------------------------
benchmark name                                  iters   elapsed ns      average
-------------------------------------------------------------------------------
Fib1                                            10000       161137        16 ns
-------------------------------------------------------------------------------

Fib2
-------------------------------------------------------------------------------
benchmark name                                  iters   elapsed ns      average

-------------------------------------------------------------------------------
Fib2                                            10000       160828        16 ns
-------------------------------------------------------------------------------
Fib3
-------------------------------------------------------------------------------
benchmark name                                  iters   elapsed ns      average
-------------------------------------------------------------------------------
Fib3                                            10000       161446        16 ns
=============================================================
All tests passed (63 assertions in 3 test cases)
lastchance (6980)
How does the recursive version do in the same tests?
Thomas1965 (4571)
Exactly the as the others.
lastchance (6980)
I'm surprised. The recursive version will calculate the same things many more times than the others.

There is an error in your testing of number 3, BTW
1
2
3
4
5
6
7
8
 
TEST_CASE("Fib3")
{
  BENCHMARK("Fib3");
  for (int i = 0; i < N; i++)
  {
    CHECK(fib2(i) == fib_numbers[i]);    // <=== should be fib3(i)??
  }
}
Thomas1965 (4571)
Oh yes, same old problem with copy and paste.
Fixed it, but all 4 tests still the same 16ns.
JLBorges (13770)
For reasonably large n, the recursive version would be much slower.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include <iostream>
#include <ctime>
#include <cassert>

unsigned long long fib_recursive( unsigned int n )
{ return n<2 ? n : ( fib_recursive(n-1) + fib_recursive(n-2) ) ; }

unsigned long long fib_iterative( unsigned int n )
{
    if( n<2 ) return n ;

    unsigned long long a = 0, b = 1, c = a + b;
    for( unsigned int i = 3; i <= n; ++i )
    {
        a = b;
        b = c;
        c = a + b;
    }

  return c;
}

int main()
{
    volatile unsigned long long v = 0 ;

    const auto a = std::clock() ;
    v = fib_iterative(40) ;
    const auto b = std::clock() ;
    v -= fib_recursive(40) ;
    const auto c = std::clock() ;

    std::cout << "iterative: " << (b-a) * 1000.0 / CLOCKS_PER_SEC << " millisecs\n"
              << "recursive: " << (c-b) * 1000.0 / CLOCKS_PER_SEC << " millisecs\n" ;
    
    assert( v == 0 ) ;
    return v ;
}

echo && echo && g++ -std=c++17 -O3 -Wall -Wextra -pedantic-errors main.cpp && ./a.out 
echo && echo =========== && echo && clang++ -std=c++17 -stdlib=libc++ -O3 -Wall -Wextra -pedantic-errors main.cpp -lsupc++ && ./a.out


iterative: 0.002 millisecs
recursive: 508.902 millisecs

===========

iterative: 0.003 millisecs
recursive: 1047.91 millisecs

http://coliru.stacked-crooked.com/a/8fab6b3940c7b400
lastchance (6980)
Agreed: recursion takes for ever here. I think there are quite big - and informative - differences between the other methods too. (I've simplified fib3.)

You will have to turn NUMREPEATS down to 1 if you want to run it in c++ shell, or it will time out as a result of that recursion.

g++ -std=c++17 -O3 -Wall -pedantic -pthread main.cpp && ./a.out
Rolling sequence of 3: 102334155   in 0.0004 ms
Vector:                102334155   in 0.0037 ms
Analytical solution:   102334155   in 0.0003 ms
Recursion:             102334155   in 575.945 ms

http://coliru.stacked-crooked.com/a/bd0c25c226b68a2d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <ctime>
using namespace std;

unsigned long long fib1( int n )       // rolling sequence of 3
{
   if ( n <= 1 ) return n;
   unsigned long long a = 0, b = 1, c = a + b;
   for ( int i = 3; i <= n; i++ )
   {
      a = b;
      b = c;
      c = a + b;
   }
   return c;
}


unsigned long long fib2( int n )       // use a vector
{
   if ( n <= 1 ) return n;
   vector<unsigned long long> F(n+1);
   F[0] = 0;   F[1] = 1;
   for ( int i = 2; i <= n; i++ ) F[i] = F[i-1] + F[i-2];
   return F[n];
}


unsigned long long fib3( int n )       // (based on) exact solution of difference equation
{                                      // this expression should give nearest integer
   constexpr double sqrt5 = sqrt( 5 );
   const double phi = 0.5 * ( 1.0 + sqrt5 );     // golden ratio
   if ( n <= 1 ) return n;
   unsigned long long F = 0.5 + pow( phi, n ) / sqrt5;
   return F;
}


unsigned long long fib4( int n )
{                            
   return n <= 1 ? n : fib4( n - 1 ) + fib4( n - 2 );
}


int main() 
{
// int nmax = 60;
// #define SP << setw( 15 ) <<
// for ( int n = 0; n <= nmax; n++ )
// {
//    cout SP n << ':' SP fib1( n ) SP fib2( n ) SP fib3( n ) << '\n';
// }
   const int N = 40;
   const int NUMREPEATS = 100;
   int f1, f2, f3, f4;

   clock_t t0 = clock();
   for ( int r = 0; r < NUMREPEATS; r++ ) f1 = fib1( N );
   clock_t t1 = clock();
   for ( int r = 0; r < NUMREPEATS; r++ ) f2 = fib2( N );
   clock_t t2 = clock();
   for ( int r = 0; r < NUMREPEATS; r++ ) f3 = fib3( N );
   clock_t t3 = clock();
   for ( int r = 0; r < NUMREPEATS; r++ ) f4 = fib4( N );
   clock_t t4 = clock();
   
   double factor = 1000.0 / ( CLOCKS_PER_SEC * NUMREPEATS );
   cout << "Rolling sequence of 3: " << f1 << "   in " << ( t1 - t0 ) * factor << " ms\n";
   cout << "Vector:                " << f2 << "   in " << ( t2 - t1 ) * factor << " ms\n";
   cout << "Analytical solution:   " << f3 << "   in " << ( t3 - t2 ) * factor << " ms\n";
   cout << "Recursion:             " << f4 << "   in " << ( t4 - t3 ) * factor << " ms\n";
}

Last edited on
Topic archived. No new replies allowed.