1

I have just started learning C++ and here is my C++ code for generating fibonacci sequences. 

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(true){
        cout << "Enter the number of terms upto which a the fibonocci sequence should be generated: ";
    cin >> n;
    cout << "------------------------" << endl;
    long long fib1 = 1;
    long long fib2 = 1;
    long long fibnext;
    cout << 1 << " " << fib1 << endl << 2 << " " << fib2 <<endl;

    for (int i =1; i <= n-2; ++i){
        fibnext = fib1 + fib2;
        fib1 = fib2;
        fib2 = fibnext;
        cout << i+2 << " " << fibnext << endl;
    }
    }
return 0;
}

This code produces correct numbers up to the 92nd term, but goes wrong in the 93rd term. I have no idea why. My guess is that it's related to the data type of fib1, fib2 and fibnext. How can I make my code correct so that it generates the sequence up to any number?

EDIT:

I generated the first 100 terms and here is the result:

Enter the number of terms upto which a the fibonocci sequence should be generated: 
100
------------------------
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 -6246583658587674878
94 1293530146158671551
95 -4953053512429003327
96 -3659523366270331776
97 -8612576878699335103
98 6174643828739884737
99 -2437933049959450366
100 3736710778780434371
wingerse
  • 3,670
  • 1
  • 29
  • 61
  • 3
    it's because the precision of primitive integer types is limited. `long long` is guaranteed to have at least 64 bits, but it's usually no more. You will need to use some sort of a bignum/bigint implementation (preferably an already-existing library) in order to have infinite (rather, arbitrary) precision. – The Paramagnetic Croissant Nov 23 '14 at 18:12
  • 1
    could you give us example of the output? It is highly likely that your variables have overflown, because 93-rd fibonacci number is pretty much huge] – Kokozaurus Nov 23 '14 at 18:13
  • 2
    Use an arbitrary precision math library: http://stackoverflow.com/questions/2568446/the-best-cross-platform-portable-arbitrary-precision-math-library – indiv Nov 23 '14 at 18:13
  • 2
    The 93rd Fibonacci number is the largest one that fits in 64 bits, but it requires an unsigned type to do so. – molbdnilo Nov 23 '14 at 18:22
  • Thanks, I saw this GMP lib , I will use it later – wingerse Nov 23 '14 at 18:49
  • You can use to help with overflow errors http://www.cplusplus.com/reference/climits/ – Ben Nov 23 '14 at 18:51

1 Answers1

5

Have a look at the following table of values:

     4660046610375530309 - 92nd Fibonacci number
     9223372036854775807 - largest 64-bit two's complement, 2^63 - 1
    12200160415121876738 - 93rd Fibonacci number
    18446744073709551615 - largest 64-bit unsigned, 2^64 - 1

As you can see, a 64-bit two's complement type (which is almost certainly what the long long type is in your case) has enough capacity to store the 92nd Fibonacci number, but the 93rd one is too large for it.

So what you're seeing is overflow, where the number wraps around into the negative space (what is actually happening is undefined behaviour where there is no guarantee that you will see any particular result, it's just that overflow to negative is a common occurrence).

If you want to calculate Fibonacci numbers beyond the 92nd, you'll need a "wider" data type, one able to handle larger numbers. Switching to unsigned long long will allow to to calculate the 93rd (see the fourth entry in above table, the limit of the unsigned 64-bit variant) but nothing beyond that.

It won't go negative any more (since it's unsigned) but it will still give an erroneous result since the 94th seems to be smaller than the 93rd, something that's clearly impossible in the Fibonacci sequence where each term is the sum of the two previous terms, always positive:

:
92 7540113804746346429
93 12200160415121876738
94 1293530146158671551    <<<--- ???
95 13493690561280548289

For larger values, you can switch to an arbitrary-precision (colloquially referred to as "bignum") mathematical library such as MPIR.

By way of example, here's your original code modified to use MPIR and output the first thousand Fibonacci numbers:

#include <mpir.h>
#include <iostream>

// Helper function for checked output.

void OutZ(int num, mpz_t &x) {
    static char textX[10000]; // can handle up to fib(47846)
    if (gmp_snprintf(textX, sizeof(textX), "%Zd", x) >= sizeof(textX)) {
        std::cout << "*** ERROR: Number was too big, need more space\n";
        exit(1);
    }
    std::cout << num << " " << textX << '\n';
}

int main() {
    // Initialise all MPIR integers to specific values.

    mpz_t fib1, fib2, fib3;

    mpz_init_set_ui(fib1, 1);          // fib1 = 1
    mpz_init_set_ui(fib2, 1);          // fib2 = 1
    mpz_init(fib3);                    // fib3 = 0

    // No need for helper, these first two are well-known.

    std::cout << "1 1\n2 1\n";

    // Now do the rest of them.

    for (int i = 3; i <= 1000; ++i) {
        mpz_add(fib3, fib1, fib2);     // fib3 = fib1 + fib2
        mpz_set(fib1, fib2);           // fib1 = fib2
        mpz_set(fib2, fib3);           // fib2 = fib3

        OutZ(i, fib3);
    }

    return 0;
}

The final few lines of that are (after about 0.01 seconds, so not too bad efficiency-wise):

999 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626
1000 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

and you can verify the final one by asking Wolfram Alpha to give you fib(1000):

Result:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953