8
\$\begingroup\$

I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.

There is the casual way to compute factorials:

\$n! = \prod\limits_{k=1}^n k\$

public static BigInteger fact(BigInteger n)  => n == 0 ? 1 : n*fact(n - 1);

The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.

Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.

From what I understood, the equation would look something like this :

\$\prod\limits_{i=1}^{\frac{n}{2}}( \sum\limits_{z=0}^i (n - z\times2))((\lceil{\frac{n}{2}\rceil})\$ (if n is odd)\$)\$

The idea is to reduce the number of multiplications by half.

public static BigInteger Factorial(int n)
{
    BigInteger sum = n;
    BigInteger result = n;
    for (int i = n - 2; i > 1; i -= 2)
    {
        sum = (sum + i);
        result *= sum;
    }

    if (n % 2 != 0)
        result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);

    return result;
}

I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.

I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).

\$\endgroup\$
5
\$\begingroup\$

\$0! = 1\$, which is a case not handled by the code.

The method should throw an ArgumentOutOfRangeException if n is negative.

You could also replace this

if (n % 2 != 0)
    result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);

with this

if (n % 2 != 0)
    result *= n / 2 + 1;

if you find it clearer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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