Fib迭代Fibonacci算法给我一个错误的结果(47) [英] Iterative Fibonacci algorithm giving me a wrong result after fib(47)

问题描述

我正在使用下面复制的迭代fib算法.我在Rosetta代码上发现了该算法，直到fib(46)为止，它给了我正确的答案.之后，它的值是错误的.有人知道为什么会这样吗?

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;   
}

输出:

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

推荐答案

请注意，您在代码中使用的是类型为int的临时变量，而不是类型为long long int的临时变量.这意味着，如果要处理足够大的斐波那契数，将在代码中产生整数溢出.特别是，第47个斐波那契数是2,971,215,073，该数字太大而无法容纳带符号的32位整数，因此会出现溢出.

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.

更改临时变量的类型为long long int(或者更好的是，uint64_t)应该可以解决此问题.

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

这篇关于Fib迭代Fibonacci算法给我一个错误的结果(47)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！