Iterative Fibonacci algorithm giving me a wrong re

Question

I am using the iterative fib algorithm that I have copied below. I have found this algorithm on Rosetta code and it gives me the correct answer up until fib(46). After that it the values are wrong. Does anyone know why this is the case?

long long fibb(int n)
{
    int fnow = 0, fnext = 1, tempf;
    while(--n > 0) {
        tempf = fnow + fnext;
        fnow = fnext;
        fnext = tempf;
    }
    return fnext;   
}

Output:

Fib(46) = 1836311903            <---- Correct
Fib(47) = 18446744092385799393   <---- Wrong (Correct Answer is: 2971215073)

Answer 1

Notice that you are using temporary variables of type int in your code rather than type long long int. This means that if you get to the point where you're dealing with sufficiently large Fibonacci numbers, you'll get an integer overflow in your code. In particular, the 47th Fibonacci number is 2,971,215,073, which is too large to fit in a signed 32-bit integer, so you'll get an overflow.

Changing your temporary variables to type long long int (or, better yet, uint64_t) should fix this.

Answer 2

You have to use long long also for fnow, fnext, and tempf, try:

long long int fnow = 0, fnext = 1, tempf;

Answer 3

Make your variables long long instead of int. 'int' depending on the machine could be 64, 32, 16 or 8-bits.

If you want to specify the size of the integer yourself and make a portable code then make use of uint8_t, uint16_t, etc or int8_t, int16_t, etc. The 'u' stands for unsigned. This is a part of the stdint.h library!