Why does C# say that the fibonacci of 93 is less than 0?

Question

So I ran a code that generates fibonacci numbers and when i==93 I get -6246583658587674878. What is the reasoning for this?

-6246583658587674878

long fib(long x){
    long a = 1;
    long b = 0;
    long c = 0;

    for(int i = 0; i <= x-1; i++) {
        c=a+b;
        a=b;
        b=c;
    }

    return c;
}

for(int i = 0; i < 420; i++) {
    if(fib(i) > long.MaxValue) break;
    Console.WriteLine($"fibonacci of {i} is {fib(i)}");
}

Presumably that number is larger than `long.MaxValue`. You should read about "two's complement" to see why it's negative. You'll get a higher ceiling with `ulong` but you'd need to use `BigInteger` to go higher still. — jmcilhinney, Apr 01 '23 at 05:01
Does this answer your question? [What is an integer overflow error?](https://stackoverflow.com/questions/2641285/what-is-an-integer-overflow-error) — Progman, Apr 01 '23 at 08:09

score 2 · Answer 1 · answered Apr 01 '23 at 05:01

if(fib(i) > long.MaxValue) break;

This will not work as you expected, when the addition overflows, the overflowed bits will be quietly truncated, so F93 (12200160415121876738) becomes -6246583658587674878. https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/operators/arithmetic-operators#integer-arithmetic-overflow

If you want to compute F93 correctly, since all fibonacci numbers are positive, you can use ulong, the max value of ulong is 18446744073709551615 which is greater than F93.

If you want to detect the overflow, you need to use checked operator to throw an exception:

c=checked(a+b);

And catch it with a try-catch statement:

try
{
    fib(i);
}
catch(OverflowException)
{
    break;
}

score 2 · Answer 2 · answered Apr 01 '23 at 05:12

Quick answer:

if(fib(i) > long.MaxValue)

will never return true. This is because a long can never hold a value above long.MaxValue. Your best bet here to detect integer overflow is actually to do: if(fib(i) < 0)

Long answer:

https://en.wikipedia.org/wiki/Integer_overflow

https://en.wikipedia.org/wiki/Two%27s_complement

A long only contains 64 bits, if you perform a calculation that results in a larger number the result ends up looping back around.

So let's start by talking about unsigned long (which only holds positive numbers). This can hold up to 2^64-1 (or UInt64.MaxValue). If you have 2^64-1 and you add 1 to it you will get all zeros (plus a carry flag, see https://en.wikipedia.org/wiki/Carry_flag, but that will be ignored in this case). Likewise if you have 0 and you subtract one you will get all 1s (ie. UInt64.MaxValue).

Now with signed numbers two's complement comes into play. The idea behind two's complement is: since 0 - 1 == 1111...111 then let's just say that 1111...111 represents -1. 1111...110 is then -2, 1111...101 is -3, etc. With two's complement the max positive number is 0111...111 (2^63-1, or Int64.MaxValue) and the minimum negative number is 1000...0000 (-2^63-1, or Int64.MinValue). Notice then that if you have Int64.MaxValue (0111...111) and you add 1 you will roll over to Int64.MinValue (1000...000).

So what happened to you is the factorial value got too big and it rolled over into negative numbers. There is a solution: remember that carry flag I mentioned briefly above? That can be used to continue the calculation into another 64bit register. I've never personally had cause to do calculations this large in c# but from a brief search it looks like BigInteger is what does this for you: https://learn.microsoft.com/en-us/dotnet/api/system.numerics.biginteger?view=net-7.0

BigInteger fib(long x){
    BigInteger a = 1;
    BigInteger b = 0;
    BigInteger c = 0;

    for(int i = 0; i <= x-1; i++) {
        c=a+b;
        a=b;
        b=c;
    }

    return c;
}

for(int i = 0; i < 420; i++) {
    Console.WriteLine($"fibonacci of {i} is {fib(i)}");
}

Why does C# say that the fibonacci of 93 is less than 0?

2 Answers2