c++ - 计算大斐波那契数时的精度误差

Question

我的程序计算以下斐波那契数列:

• 77th 5527939700884757

• 78th 8944394323791464

• 79th 14472334024676220

但是很明显，如果我把第 77 和 78 个数字的最后两位相加，它应该是 1，我无法理解这个问题

long double iterative_fib(int n){
   long double firstNumber = 0;
   long double secondNumber = 1;
   long double thirdNumber = 0;

   for (int i = 0;i <n-1;i++)
   {
       if ( n == 0)
       {
           cout << "The fibonacci number is: " << n;
       }
       else
       {
           thirdNumber = firstNumber + secondNumber;
           firstNumber = secondNumber;
           secondNumber = thirdNumber;
       }
   }
   return thirdNumber;
}

Answer 1

通过使用 long double作为您的累积数据类型，您正在向该类型的精度限制敞开大门，通常在 17 digits 左右。 .

由于斐波那契数都是正整数，我会改用 unsigned long long表示整数 - 这对于 2^64-1 的有符号整数表示很有用，即至少 19 位精度。

unsigned long long iterative_fib(int n){
   unsigned long long firstNumber = 0;
   unsigned long long secondNumber = 1;
   unsigned long long thirdNumber = 0;

   for (int i = 0; i < n-1; i++)
   {
       thirdNumber = firstNumber + secondNumber;
       firstNumber = secondNumber;
       secondNumber = thirdNumber;
   }
   return thirdNumber;
}

返回正确答案，14472334024676221

IdeOne example here

但是，超过 19 位数字，您将需要求助于 Big Integer representation图书馆，或推出自己的。