How do i use unsigned long long array to calculate fib(100)?

zaahm18 (63)
Hi, I wrote the program to calculate the Fibonacci numbers.

one of exercises is that to calculate 100th Fibonacci number, using int.

but the problem occurs, because overflow happens.

Then I've decided to use ULLong int but even 64-bit int cant support that, because integer of that size have maximum 18 digits and fib 100 have around 19.

So I decided to solve the problem using the array with the size of 2 and the modulo size of 1e17.

The good news is that I get is that the numbers no longer overflows, but the bad news is that I get the wrong result, I tried numerous times to solve this issue but that didn't worked for me.

Also the array with elementsize of 2 should represent 128 bit integer.
this is my code so far:
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
 
#include <deque>
#include <iostream>

    deque<unsigned long long> vec;
     void Fibonacchi(int x)
    {
        vec.clear();
        unsigned long long a = 0, b = 1, mod = 10000000000000000000;
        int carry = 0;
        vec.push_back(0);
        vec.push_back(0);
        for (int i = 0; i < x; i++)
        {
            if (vec[0] > 0)
            {
                carry++;
            }
            a = b;
            b = vec[1];
            vec[1] = a + b;
            if (vec[1] > mod)
            {
                vec[0] += (vec[1] / mod) % mod + vec[0] + carry;
                vec[1] %= mod;
            }
        }
        vec[0]--;
        vec[1] %= mod;
}
int main()
{
   Fibonacchi(100);
std::cout << vec[0]<<vec[1] << std::endl;
}


Last edited on
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
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 <vector>
#include <cmath>
using namespace std;


class BigInt
{
public:
   vector<int> digits;       // digits stored in REVERSE order;
   BigInt( int n = 0 );      // construct from integer
};

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

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

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

BigInt operator + ( BigInt a, const BigInt &b )
{
   int bsize = b.digits.size();

   for ( int i = 0, carry = 0; i < bsize || carry > 0; i++ )
   {
      if ( i < a.digits.size() ) carry += a.digits[i];
      if ( i < b.digits.size() ) carry += b.digits[i];
      int digit = carry % 10;
      carry /= 10;
      if ( i < a.digits.size() ) a.digits[i] = digit;
      else                       a.digits.push_back( digit );
   }
   return a;
}

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

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

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

int main()
{
   BigInt a = 1, b = 1;
   const int N = 100;
   cout << "1: " << a << '\n' << "2: " << b << '\n';
   for ( int n = 3; n <= N; n++ )
   {
      BigInt temp = a + b;
      a = b;
      b = temp;
      cout << n << ": " << b << '\n';
   }
   
   cout << "Check as double: " << floor( pow( 1.618033988749894848204, N ) / sqrt( 5.0 ) + 0.5 );
}


1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
11: 89
12: 144
13: 233
14: 377
15: 610
16: 987
17: 1597
18: 2584
19: 4181
20: 6765
21: 10946
22: 17711
23: 28657
24: 46368
25: 75025
26: 121393
27: 196418
28: 317811
29: 514229
30: 832040
31: 1346269
32: 2178309
33: 3524578
34: 5702887
35: 9227465
36: 14930352
37: 24157817
38: 39088169
39: 63245986
40: 102334155
41: 165580141
42: 267914296
43: 433494437
44: 701408733
45: 1134903170
46: 1836311903
47: 2971215073
48: 4807526976
49: 7778742049
50: 12586269025
51: 20365011074
52: 32951280099
53: 53316291173
54: 86267571272
55: 139583862445
56: 225851433717
57: 365435296162
58: 591286729879
59: 956722026041
60: 1548008755920
61: 2504730781961
62: 4052739537881
63: 6557470319842
64: 10610209857723
65: 17167680177565
66: 27777890035288
67: 44945570212853
68: 72723460248141
69: 117669030460994
70: 190392490709135
71: 308061521170129
72: 498454011879264
73: 806515533049393
74: 1304969544928657
75: 2111485077978050
76: 3416454622906707
77: 5527939700884757
78: 8944394323791464
79: 14472334024676221
80: 23416728348467685
81: 37889062373143906
82: 61305790721611591
83: 99194853094755497
84: 160500643816367088
85: 259695496911122585
86: 420196140727489673
87: 679891637638612258
88: 1100087778366101931
89: 1779979416004714189
90: 2880067194370816120
91: 4660046610375530309
92: 7540113804746346429
93: 12200160415121876738
94: 19740274219868223167
95: 31940434634990099905
96: 51680708854858323072
97: 83621143489848422977
98: 135301852344706746049
99: 218922995834555169026
100: 354224848179261915075
Check as double: 3.54225e+20
Last edited on
zaahm18 (63)
Thankx
dhayden (5798)
When I fix your code to compile it gets the right answer for fib(100) but fails for any other number:
1
2
3
4
5
 
    std::deque<unsigned long long> vec;
     void Fibonacchi(int x)
    {
        vec.clear();
        unsigned long long a = 0, b = 1, mod = 10000000000000000000ULL;


I think the problem is that you have to use two 64-bit values to represent a and b also. At that point, you might as well use a class. Here's a version similar to lastchance's, but with two unsigned long long like you had:

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

using namespace std;

struct BigUnsigned {
    BigUnsigned(): msd(0), lsd(0) {} // most and least significant digits
    BigUnsigned(unsigned val): msd(0), lsd(val) {}

    unsigned long long msd, lsd;

    BigUnsigned &operator+=(const BigUnsigned &rhs)
    {
	const unsigned long long mod = 10000000000000000000ULL;
	lsd += rhs.lsd;
	msd += rhs.msd;
	while (lsd >= mod) {
	    ++msd;
	    lsd -= mod;
	}
	return *this;
    }
    
    BigUnsigned operator+(BigUnsigned &rhs)
    {
	BigUnsigned result(*this);
	result += rhs;
	return result;
    }
};

ostream & operator << (ostream &os, const BigUnsigned & val)
{
    if (val.msd) os << val.msd;
    return os << val.lsd;
    
}


template<class T>
T Fib(int n)
{
    T v1{1}, v2{1};
    T last;
    for (int i=2; i<n; ++i) {
	last = v1;
	v1 = v1+v2;
	v2 = last;
    }
    return v1;
}


int
main(int argc, char **argv)
{
    int N = atoi(argv[1]);
    cout << "       As BigUnsigned: " << Fib<BigUnsigned>(N) << '\n';
    cout << "As unsigned long long: " << Fib<unsigned long long>(N) << '\n';
    cout << "            As double: " << Fib<double>(N) << '\n';
}


dhayden@DHAYDENHTZK3M2 ~/tmp
$ ./foo 17
       As BigUnsigned: 1597
As unsigned long long: 1597
            As double: 1597

dhayden@DHAYDENHTZK3M2 ~/tmp
$ ./foo 50
       As BigUnsigned: 12586269025
As unsigned long long: 12586269025
            As double: 1.25863e+10

dhayden@DHAYDENHTZK3M2 ~/tmp
$ ./foo 93
       As BigUnsigned: 12200160415121876738
As unsigned long long: 12200160415121876738
            As double: 1.22002e+19

dhayden@DHAYDENHTZK3M2 ~/tmp
$ ./foo 94
       As BigUnsigned: 19740274219868223167
As unsigned long long: 1293530146158671551      (unsigned long long overflows at 94)
            As double: 1.97403e+19

dhayden@DHAYDENHTZK3M2 ~/tmp
$ ./foo 100
       As BigUnsigned: 354224848179261915075
As unsigned long long: 3736710778780434371
            As double: 3.54225e+20

dhayden@DHAYDENHTZK3M2 ~/tmp
$ ./foo 184
       As BigUnsigned: 127127879743834334146972278486287885163
As unsigned long long: 10993266775918486379
            As double: 1.27128e+38

dhayden@DHAYDENHTZK3M2 ~/tmp
$ ./foo 185
       As BigUnsigned: 21229789606137712014223751303346572685  (BigUnsigned overflows at 185)
As unsigned long long: 3465294890923511181
            As double: 2.05697e+38


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
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
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;

const int MOD = 1000000000;
const int WMOD = 9;

class BigInt
{
public:
   vector<unsigned long long> digits;       // digits stored in REVERSE order;
   BigInt( int n = 0 );                     // construct from integer
};

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

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

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

BigInt operator + ( BigInt a, const BigInt &b )
{
   int bsize = b.digits.size();

   for ( int i = 0, carry = 0; i < bsize || carry > 0; i++ )
   {
      if ( i < a.digits.size() ) carry += a.digits[i];
      if ( i < b.digits.size() ) carry += b.digits[i];
      int digit = carry % MOD;
      carry /= MOD;
      if ( i < a.digits.size() ) a.digits[i] = digit;
      else                       a.digits.push_back( digit );
   }
   return a;
}

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

ostream &operator << ( ostream &out, const BigInt &a )
{
   out << a.digits.back();
   for ( int i = a.digits.size() - 2; i >= 0; i-- ) out << setw( WMOD ) << setfill( '0' ) << a.digits[i];
   return out;
}

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

int main()
{
   BigInt a = 1, b = 1;
   const int N = 300;
   cout << "1: " << a << '\n' << "2: " << b << '\n';
   for ( int n = 3; n <= N; n++ )
   {
      BigInt temp = a + b;
      a = b;
      b = temp;
      cout << n << ": " << b << '\n';
   }
   
   cout << "\nDirect check as double: " << floor( pow( 1.618033988749894848204, N ) / sqrt( 5.0 ) + 0.5 );
}


1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
......
298: 84885164052257330097714121751630835360966663883732297726369399
299: 137347080577163115432025771710279131845700275212767467264610201
300: 222232244629420445529739893461909967206666939096499764990979600

Direct check as double: 2.22232e+62
Topic archived. No new replies allowed.