0

My program allows to find fibonacci numbers at a certain position n using stack but when I type in a position after 76, the numbers start to get a single number off and larger from there. Here is my arithmetic:

for (int i = 2; i < nth; i++)
{

    if (nth == 1)
        return 1;
    else if (nth == 2)
        return 1;
    else
    n1 = fibStack.top();
    fibStack.pop();
    n2 = fibStack.top();
    fibStack.pop();

    temp = n1 + n2;
    fibStack.push(n2);
    fibStack.push(n1);
    fibStack.push(temp);

}

I used double type and precision to output correctly. The correct output at 83 is: 99194853094755497 What my code outputs is: 99194863094755488

Zack Maguffin
  • 45
  • 4
  • 3
    "I used double type and precision to output correctly" - if you're trying to get exact results with doubles, you've completely misunderstood what a double is. Get an arbitrary-precision arithmetic library. – user2357112 Apr 12 '17 at 17:25
  • 2
    Your going to need a BigInt library. The 75th fib number is 1,304,969,544,928,657 where 18,446,744,073,709,551,615 is the most a unsigned 64bit number can hold. – NathanOliver Apr 12 '17 at 17:27
  • 1
    Doubles are based on finite precision and approximation. Almost every operation you can do with doubles involves rounding and discarding precision. – user2357112 Apr 12 '17 at 17:28
  • 1
    [What Every Computer Scientist Should Know About Floating-Point Arithmetic](https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html) – Caleb Apr 12 '17 at 17:28
  • The issue is that a double (IEEE) contains a 52 bit mantissa with an assumed leading 1 in front of it. This effectively makes a double the equivalent of a 53 bit unsigned integer (or a 54 bit signed integer), except that it can represent ± 2^53 exactly. There's no way to represent (2^53)+1, the next largest number is (2^53)+2. Assuming fib(0) = 0, then fib(78) == 8944394323791464 is the largest exact double Fibonacci number (it fails for fib(79)). Using a 64 bit unsigned integer would allow up to fib(93) == 12200160415121876738. – rcgldr Apr 12 '17 at 20:18

0 Answers0