I needed the inverse factorial function for my previous post. I was sure I’d written a post on computing the inverse factorial, and intended to reuse the code from that earlier post. But when I searched I couldn’t find anything, so I’m posting the code here for my future reference and for anyone else who may need it.
Given a positive number x, how can you find a number n such that n! = x, or such that n! ≈ x?
Mathematical software tends to work with the gamma function rather than factorials because Γ(x) extends x! to real numbers, with the relation Γ(x+1) = x!. The left side is often taken as a definition of the right side when x is not a positive integer.
Not only do we prefer to work with the gamma function, it’s easier to work with the logarithm of the gamma function to avoid overflow.
The Python code below finds the inverse of the log of the gamma function using the bisection method. This method requires an upper and lower bound. If we only pass in positive values, 0 serves as a lower bound. We can find an upper bound by trying powers of 2 until we get something large enough.
from scipy.special import gammaln
from scipy.optimize import bisect
def inverse_log_gamma(logarg):
assert(logarg > 0)
a = 1
b = 2
while b < logarg:
b = b*2
return bisect(lambda x: gammaln(x) - logarg, a, b)
def inverse_factorial(logarg):
g = inverse_log_gamma(logarg)
return round(g)-1
Note that the inverse_factorial function takes the logarithm of the value whose inverse factorial you want to compute.
For example,
inverse_factorial(log(factorial(42))))
returns 42.
Working on the log scale lets us work with much larger numbers. The factorial of 171 is larger than the largest IEEE double precision number, and so inverse_factorial could not return any value larger than 171 if we passed in x rather than log x. But by taking log x as the argument, we can calculate inverse factorials of numbers so large that the factorial overflows.
For example, suppose we want to find the value of m such that m! is the closest factorial to √(2024!), as we did in the previous post. We can use the code
inverse_factorial(gammaln(2025)/2)
to find m = 1112 even though 1112! is on the order of 102906, far larger than the largest representable floating point number, which is on the order of 10308.
When n! = x does not have an exact solution, there is some choice over what value of n to return as the inverse factorial of x. The code above minimizes the distance from n! to x on a log scale. You might want to modify the code to minimize the distance on a linear scale, or to find the largest n with n! < x, or the smallest n with n! > x depending on your application.
Related posts
The post Computing inverse factorial first appeared on John D. Cook.