Precise solution to Factorial Function and Fibonacci series in C#

Perhaps the worst implementation of the factorial function in C# that you can find is the following:

static int Factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * Factorial(n - 1);
}

You should know that it can only give results for n = 12, Factorial (12) = 479001600, for 13 it is already wrong: 1932053504, when the correct value is 6227020800. Complex issue derived from type precision (note 1).

A much more decent approximation is the following:

static ulong Factorial64(uint number) {
    return number switch {
        < 2 => 1,
        _ => number * Factorial64(number - 1)
    };
}

However, it is not the best either, it only supports up to n = 20. So what is the correct solution? As always C# has an ace up its sleeve.

Factorial Function

The most accurate solution for the Factorial function written in C# uses System.Numerics, and it is as follows.

static BigInteger Factorial(uint n) {
    if (n <= 1) {
        return 1;
    }
    BigInteger result = 1;
    for (BigInteger i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

I have not used recursion, since it imposes some limitations, for example, the recursive function gives overflow exceptions for n> ~ 7000. The above code I have tested up to n = 100,000, which is quite outrageous as it returns a number of 456,574 characters.

Here is a somewhat demanding test. The result is not printed because it does not make much sense, I added a function to return the partial number, and the length in characters of this.

FATORIAL TEST
--------------
Factorial(10000) => 2846259680... | LEN: 35660
Factorial(20000) => 1819206320... | LEN: 77338
Factorial(30000) => 2759537246... | LEN: 121288
Factorial(40000) => 2091692422... | LEN: 166714
Factorial(50000) => 3347320509... | LEN: 213237
Factorial(60000) => 1564137708... | LEN: 260635
Factorial(70000) => 1176812415... | LEN: 308760
Factorial(80000) => 3097722251... | LEN: 357507
Factorial(90000) => 1580119154... | LEN: 406799
Factorial(100000) => 2824229407... | LEN: 456574

The Fibonacci series

Something similar happens with the Fibonacci series, where what we commonly find on the Internet is solutions is with an integer type, int, which gives an admissible limit up to n = 20, and 93 for a long integer (not recursive), Let's look at this incorrect code:

static int FibonacciBadApproach(int number) {
    if (number <= 2)
        return 1;
    else
        return FibonacciBadApproach(number - 1) + FibonacciBadApproach(number - 2);
}

The recursive version of this function is not effective. In fact, it is fatal. In a better approximation using ulong, instead of int, performance degrades incrementally with numbers greater than 40.

The ideal solution for the Fibonacci series, which supports huge numbers, is as follows:

public static BigInteger Fibonacci(uint number) {
    BigInteger a = 0, b = 1, result = 0;
    for (uint i = 0; i <= number; i++) {
        if (i <= 1)
            result = i;
        else {
            result = a + b;
            a = b;
            b = result;
        }
    }
    return result;
}

The answers are practically immediate. Let's look at a test.

FIBONACCI TEST
Fibonacci(10000) => 3364476487...9947366875 | LEN: 2090
Fibonacci(20000) => 2531162323...1213093125 | LEN: 4180
Fibonacci(30000) => 1904243567...7097960000 | LEN: 6270
Fibonacci(40000) => 1432600165...1107826875 | LEN: 8360
Fibonacci(50000) => 1077773489...2373553125 | LEN: 10450
Fibonacci(60000) => 8108303504...4195920000 | LEN: 12539
Fibonacci(70000) => 6100037380...2268286875 | LEN: 14629
Fibonacci(80000) => 4589178984...3534013125 | LEN: 16719
Fibonacci(90000) => 3452530277...1293880000 | LEN: 18809
Fibonacci(100000) => 2597406934...3428746875 | LEN: 20899

Conclusions

As expected, it is possible to write in C# precise functions for Factorial and Fibonacci, although it is rare to find them in Internet or documentation.

Recursion shows short and elegant code, but does not always give reliable results.

Annexed

The test code was as follows:

static void FactorialTest() {
    Console.WriteLine("FACTORIAL TEST");
    try {
        for (uint i = 10_000; i <= 100_000; i += 10_000) {
            Console.WriteLine("Factorial({0}) => {1}", i, Friendly(Factorial(i)));
        }
    } catch {
        Console.WriteLine("Has stopped.");
    }
    Console.WriteLine("END");
}

static void FibonacciTest() {
    Console.WriteLine("FIBONACCI TEST");
    try {
        for (uint i = 10_000; i <= 100_000; i += 10_000) {
            Console.WriteLine("Fibonacci({0}) => {1}", i, Friendly(Fibonacci(i)));
        }
    } catch {
        Console.WriteLine("Has stopped.");
    }
    Console.WriteLine("END");
}

static string Friendly(BigInteger number) {
    var s = number.ToString();
    return s.Length switch {
        <= 32 => s,
        _ => $"{s[0..10]}...{s[^10..]} | LEN: {s.Length}"
    };
}

P.S. Please add a FV to this post if it is helpful to you.

Update: 22-09-21

(1) The reason for this inconsistency is as follows. In languages like C++ or C#, possibly more, when the maximum possible of a numeric type is exceeded, it returns to the beginning and continues. It is like the hands of a clock. Look at this test:

int maxInt = int.MaxValue, nextInt = maxInt + 1;

Console.WriteLine("maxInt: {0} | (maxInt + 1) = {1}", maxInt, nextInt);
// OUTPUT
// maxInt: 2147483647 | (maxInt + 1) = -2147483648

Harvey Triana's Blog