CODEWITHSUNDEEP
c++
ram singh
ram singh

Reputation: 41

Precision error in addition while calculating large Fibonacci numbers

My program calculates the following Fibonacci sequences:

But clearly, if I add last two digits of number 77th and 78th number it should 1, I cannot understand this problem

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

Upvotes: 2

Views: 110

Answers (2)

StuartLC
StuartLC

Reputation: 107277

By using long double as your cumulative data type, you are opening yourself up to the precision limits of the type, which is usually around 17 digits.

Since fibonacci numbers are all positive integers, I would instead use a unsigned long long to represent the integers - this is good for a signed integer representation of 2^64-1, i.e. at least 19 digits of precision.

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

Which returns the correct answer, 14472334024676221

IdeOne example here

However, beyond 19 digits, you'll need to resort to a Big Integer representation library, or roll your own.

Upvotes: 4

Akhaim
Akhaim

Reputation: 152

When working with number sequences such as Fibonacci numbers, if one uses an approach where one tries to store a number in a sequence in a specific type, such as long long or unsigned long long, eventually it will become impossible to store large values, so one needs to change the strategy. In that case, for example, strings could be used to store digits of a large number, and any operation you perform would have to be digit-wise. Also, issue similar to the one you have has been addressed in this question here

Upvotes: 1

Related Questions