Factorial calculation algorithms

Eventually, at some point in your coding career, you’ll need to calculate the factorial of a number.

This, of course, with most modern programming languages shouldn’t be a problem… unless you need to calculate the factorial of any real number, even if it is a fractional number.

The factorial of any whole positive number is defined as:

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

Such definition can be easily implemented through various methods and it’s often one of the most basic problems presented to amateur programmers to illustrate the implementation of recursive functions, For/Next cycles and Do/While loops.

Nowadays, memory resources are quite abundant thus they don’t (usually) represent an issue to consider. So, which algorithm should you use?
Recursion, loops, look-up tables…?

Let’s explore some of the most common algorithms to calculate the factorial of any positive number:

Recursion

Public Function FactRecursive(value As Double) As Double
    If value <= 1 Then Return 1
    Return value * FactRecursive(value - 1)
End Function

Quite probably the simplest of the algorithms. Unfortunately, we all known how dangerous a recursive function can be, as if unattended, you’ll be faced with a plethora of errors such as the uncatchable StackOverflow Exception.
Also, this implementation is the slowest of them all.

While Loop

Public Function FactWhile(value As Double) As Double
    Dim result As Double = 1
    While value >= 2
        result *= value
        value -= 1
    End While

    Return result
End Function

The While loop algorithm pretty much describes what a factorial is: “in mathematics, the factorial of a non-negative integer, n, is the product of all positive integers less than or equal to n“.

For/Next Loop

Public Function FactFor(value As Double) As Double
    Dim result As Double = 1

    For value = value To 2 Step -1
        result *= value
    Next

    Return result
End Function

Quite similarly to the While loop, the For/Next loop follows the factorial definition to calculate the factorial of any positive integer.

So, which one should we use?

That will depend on many factors (such as the optimization capabilities of the compiler) as each algorithm will have its merits and flaws.

The thing is that when doing math in a computer, you will always have to compromise between speed and accuracy.
All aforementioned algorithms will provide the correct answer for any positive integer, but which one is the fastest? Which one consumes the least memory?
Download the sample application (link at the bottom) to test each algorithm and see how it performs on your machine.

Gamma Function

Now… how about calculating the factorial of a fractional positive number?
Well, there’s a function for that and it’s called the Gamma function.

$n! = \gamma(n+1)$

I won’t go into any detail about this algorithm since its implementation is nothing trivial, as it is defined as an integral with an infinite range ( $\Gamma \left( x \right) = \int\limits_0^\infty {s^{x - 1} e^{ - s} ds}$ ) so it requires some quite complex and clever coding…

It is by far, the slowest algorithm and you should avoid using it, unless you really need to calculate the factorial of non-integer numbers.

Here’s a simple VB.NET console application that demonstrates all algorithms, including the gamma function to support the calculation of factorials of non-integer positive numbers.

FactorialAlgorithms (1404 downloads )

NOTE: I did not write the gamma function’s code. It was originally written by Stephen L. Moshier for the Cephes Math Library.

May201525

xfx

0