1

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.

6
  • 5
    The max value of an unsigned long is 18446744073709551615. You're hoping to store a value that's larger than that, which won't work. I suggest you look at BigInteger. Commented Mar 18, 2021 at 7:52
  • So, I only have to change ulong for BigInteger? Commented Mar 18, 2021 at 8:01
  • Yes, that's correct. Commented Mar 18, 2021 at 8:02
  • 1
    Side note: there's no need to store all fibonacci numbers in an array; two numbers are enough Commented Mar 18, 2021 at 8:08
  • Thanks, the solution was really easy at least. Commented Mar 18, 2021 at 8:11

2 Answers 2

7

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]);
     }
3

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

1
  • Thanks!. I come from python and all related to data types is kinda new for me. Commented Mar 18, 2021 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.