Fastest way to compute a factorial in a numba nopython function

Viewed 1602

I have a function that I want to compile with numba, however I need to calculate a factorial inside that function. Unfortunatly numba doesn't support math.factorial:

import math
import numba as nb

@nb.njit
def factorial1(x):
    return math.factorial(x)

factorial1(10)
# UntypedAttributeError: Failed at nopython (nopython frontend)

I saw that it supported math.gamma (which could be used to calculate the factorial), however contrary to the real math.gamma function it doesn't return floats that represent "integral values":

@nb.njit
def factorial2(x):
    return math.gamma(x+1)

factorial2(10)
# 3628799.9999999995  <-- not exact

math.gamma(11)
# 3628800.0  <-- exact

and it's slow compared to math.factorial:

%timeit factorial2(10)
# 1.12 µs ± 11.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit math.factorial(10)
# 321 ns ± 6.12 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

So I decided to define my own function:

@nb.njit
def factorial3(x):
    n = 1
    for i in range(2, x+1):
        n *= i
    return n

factorial3(10)
# 3628800

%timeit factorial3(10)
# 821 ns ± 12.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

It's still slower than math.factorial but it's faster than a math.gamma based numba function and the value is "exact".

So I'm looking for the fastest way to compute the factorial of a positive integer number (<= 20; to avoid overflow) inside a nopython numba function.

1 Answers
Related