CODEWITHSUNDEEP
c#algorithmoverflowfibonacci
Jose Avalos
Jose Avalos

Reputation: 11

Error from the 94th Fibonacci number in C#

I am calculating Fibonacci numbers in C# and I am getting wrong numbers since the number 94.

This is my code.

    static void Main(string[] args)
    {
        string N = Console.ReadLine();
        ulong n = ulong.Parse(N);
        ulong[] fibonacci = new ulong[n+1];
        fibonacci[0] = 0;
        if (n == 1)
        {
            fibonacci[1] = 1;
        }
        if (n>=2)
        {
            fibonacci[1] = 1;
            for (ulong i = 2; i < n+1; i++)
            {
                fibonacci[i] = (ulong)fibonacci[i-1] + (ulong)fibonacci[i-2];
            }
         }
     }

     Console.WriteLine(fibonacci[n]);

I am ok until the 93th number which is 12200160415121876738, but I am getting 1293530146158671551 with the 94th, the real one is 19740274219868223167.

I don't know what could be wrong with my code.

Upvotes: 1

Views: 560

Answers (2)

elldora
elldora

Reputation: 361

I think you don't need to store the number of N in the ulong type! It can be stored as an int as well! The most massive part is to store the value of the Nth Fibonacci number. You can calculate it more concise without considering a large array for constructing the last number!

public static void Main(string[] args)
    {
        string N = Console.ReadLine();
        int n = int.Parse(N);
        BigInteger[] fibonacci = new BigInteger[3];
        fibonacci[0] = 0;
        fibonacci[1] = 1;
        fibonacci[2] = 1;
        
        if (n>=3)
        {
            for (int i = 3; i < n+1; i++)
            {
                fibonacci[0]=fibonacci[1];
                fibonacci[1]=fibonacci[2];
                fibonacci[2]=fibonacci[1]+fibonacci[0];
            }
         }
         Console.WriteLine(fibonacci[2]);
     }

Upvotes: 7

ProgrammingLlama
ProgrammingLlama

Reputation: 38777

The maximum value of ulong is 18,446,744,073,709,551,615.

You're trying to store 19,740,274,219,868,223,167, which is larger than that. By default a ulong won't throw an exception when it overflows, but you can force it to by adding a checked { } around the code:

checked
{
    fibonacci[i] = (ulong)fibonacci[i-1] + (ulong)fibonacci[i-2];
}

Then running your code, sure enough, we get:

System.OverflowException: Arithmetic operation resulted in an overflow.

Fortunately, there is a type in .NET for working with really big integers. It's called BigInteger.

Changing your code to use it is relatively trivial:

string N = Console.ReadLine();
ulong n = ulong.Parse(N);
BigInteger[] fibonacci = new BigInteger[n+1];
fibonacci[0] = 0;
if (n == 1)
{
    fibonacci[1] = 1;
}
if (n>=2)
{
    fibonacci[1] = 1;
    for (ulong i = 2; i < n+1; i++)
    {
        fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
    }
 }

Your code now works as expected and outputs:

19740274219868223167

Even changing the input to 900 still works:

54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800

Try it online

Upvotes: 3

Related Questions