Fibonacci's 150 member

Hello.I have some problem. I musc count fibonacci's 150 member. As i know borders of int isn't enought so here we need BigInt.I have ready project of counting but i need to include bigint here and here i need help.

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
#include <iostream>

using namespace std;

class Fibonacci{
public:
    int a, b, c;
    void generate(int);
};

void Fibonacci::generate(int n){
    a = 0; b = 1;
    cout << a << " " <<b;
    for(int i=1; i<= n-2; i++){
        c = a + b;
        cout << " " << c <<endl;;
        a = b;
        b = c;
    }
}

int main()
{
    cout << "Hello world! Fibonacci series" << endl;
    cout << "Enter number of items you need in the series: ";
    int n;
    cin  >> n;
    Fibonacci fibonacci;
    fibonacci.generate(n);
    system("pause");
    return 0;
}


also i have working class of BigInt and want to include here.
Last edited on
Dagr wrote:
i need to include bigint

What about "unsigned long long" instead?
Last edited on
What about "unsigned long long" instead?


Because it's
9969216677189303386214405760200
Uh!... (back down) :-/
> also i have working class of BigInt and want to include here.

Something like this. This uses boost::multiprecision::cpp_int
http://www.boost.org/doc/libs/1_64_0/libs/multiprecision/doc/html/index.html
Your working class of BigInt could be used in a similar manner.

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
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp> // include the header
// link with the library if it is not a header-only libray

namespace Fibonacci {

    using big_int = boost::multiprecision::cpp_int ;

    void generate( unsigned int n ) {

        big_int a = 0 ;
        big_int b = 1 ;
        std::cout << "\n1. " << a << "\n2. " << b << '\n' ;

        for( unsigned int i = 2 ; i < n ; ++i ) {

            const big_int c = a+b ;
            std::cout << i+1 << ". " << c << '\n' ;
            a = b ;
            b = c ;
        }
    }
};

int main()
{
    std::cout << "Hello world! Fibonacci series\n"
                 "Enter number of items you need in the series: ";
    unsigned int n;
    std::cin  >> n;

    Fibonacci::generate(n);
}

http://rextester.com/BKVL68001
If you start the series 1 1 2 3 5 8 ... then the 150th Fibonacci number is
9969216677189303386214405760200 (see code below)

If you start the series 0 1 1 2 3 5 ... then the 150th Fibonacci number is
6161314747715278029583501626149 (you would have to modify the code below)

This uses a VERY cut-down version of a BigInt library, but it's all that is needed here (construct and add two big integers).

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
using namespace std;


//====== Definitions ===================================================


class BigInt                 // VERY cut-down big-integer class
{
public:
   vector<int> digits;       // note: digits stored in REVERSE order
   BigInt( int N = 0 );      // construct from int
};


BigInt operator+( const BigInt &a, const BigInt &b );
ostream &operator<<( ostream &stream, const BigInt &a );


//====== Functions =====================================================


BigInt::BigInt( int n )
{
   if ( n == 0 )
   {
      digits.push_back( 0 );
   }
   else
   {
      while ( n > 0 )
      {
         digits.push_back( n % 10 );
         n /= 10;
      }
   }
}


//-------------


BigInt operator+( const BigInt &a, const BigInt &b )
{
   BigInt result = a;

   int last = b.digits.size() - 1;

   int i = 0;
   int carry = 0;
   while ( i <= last || carry > 0 )
   {
      if ( i < result.digits.size() ) carry += result.digits[i];
      if ( i < b.digits.size()      ) carry += b.digits[i];
      int digit = carry % 10;
      carry /= 10;
      if ( i < result.digits.size() ) result.digits[i] = digit;
      else                            result.digits.push_back( digit );

      i++;
   }

   return result;
}


//-------------


ostream &operator<<( ostream &stream, const BigInt &a )
{
   for ( int i = a.digits.size() - 1; i >= 0; i-- ) stream << a.digits[i];
   return stream;
}


//======================================================================


int main()
{
   BigInt first = 1;                   // Currently set for series    1 1 2 3 5 ...
   BigInt second = 1;                  // Change to   0 1 1 2 3 5 ... if preferred

   cout << 1 << ": " << first  << endl;
   cout << 2 << ": " << second << endl;

   for ( int i = 3; i <= 150; i++ )
   {
      BigInt temp = first + second;
      first = second;
      second = temp;
      cout << i << ": " << temp << endl;
   }
}


1: 1
2: 1
3: 2
4: 3
5: 5
6: 8

....... lots of lines ...

148: 3807901929474025356630904134051
149: 6161314747715278029583501626149
150: 9969216677189303386214405760200
Topic archived. No new replies allowed.