Fibinacci Algorithm help

[Vindifreek]

#include <iostream>
using namespace std;

int fibinacci(int n)
{
    int u=0;
    int v=1;
    int i,t;

    for(i=2; i<n; i++)
    {
        t=u+v;
        u=v;
        v=t;
    }
    return v;
}

int main()
{
    int pos;
    int a;

    cout << "This program will allow you pin point a specific position in the Fibinacci Sequence." << endl;
    cout << "Please enter the position that you would like.";
    cin >> pos;
    a = fibinacci(pos);
    cout << a;
}

This is my code for the algorithm im working on and when the placement reaches 48 or above the numbers become negative. Was wondering what is happening. i thought it might be because I have the variables set as Int and I set them as long double and float and on down the list but nothing I did helped. Anyone have any suggestions?

[namcs]

Hi Vindifreek, how large is the 47th Fibonacci number? Is it near to long limit?
If the number is too large (which is likely this case), you will have to use an array of 0..9 to represent your number.

[shacktar]

Yep, this is an overflow problem. Max int (signed) is 2,147,483,647 (2³¹-1) and fibonacci 48 overflows that. You can use unsigned int which has a maximum of 4,294,967,295 (2³²-1) but that'll overflow at fibonnaci 52. You could use a long long (max 2⁶⁴-1) which will give you some elbow room, but it's only a matter of time before that overflows as well. If you don't want to overflow, you may consider storing the answers to fibonacci as strings.

[Vindifreek]

How would I save the result as a string I know ive done it before but for the life of me I cant remember.

[m4ster r0shi]

Check this out -> http://www.cplusplus.com/forum/lounge/32041/

[Vindifreek]

I used itoa and it made it a little bigger but not much I guess there is just a limit that I cant get past.

[namcs]

If you simply store the result in string and then convert back to number then there's no point. If you use array, I think there's no limit for fibonacci series because using array you can store millions digits.

[packetpirate]

You could also use a BigInt library:

https://mattmccutchen.net/bigint/

[shacktar]

@Vindifreek what I meant with using a string is then the maximum number depends on the max length of the string. If you use a string (or probably better, an array of digits), then you wouldn't use the whole number directly (because it would still cause an overflow). What you would do is deal with one digit at a time. For the addition, first you'd add up the last two digits (and carry over to the next one), then, you would add up the next two digits (taking into account the carry-over), and so on. With this method, you'd be limited only by RAM. You could, theoretically, dump digits to a file if there's too many and only deal with a fraction of them at a time.