CODEWITHSUNDEEP
pythonnumpyfactorial
Matt
Matt

Reputation: 26971

Computing factorials efficiently with Python and Numpy

In python / numpy - is there a way to build an expression containing factorials - but since in my scenario, many factorials will be duplicated or reduced, wait until I instruct the run time to compute it.

Let's say F(x) := x!

And I build an expression like (F(6) + F(7)) / F(4) - I can greatly accelerate this, even do it in my head by doing 

(F(6) * (1 + 7)) / F(4)
 = 5 * 6 * 8
 = 240

Basically, I'm going to generate such expressions and would like the computer to be smart, not compute all factorials by multiplying to 1, i.e using my example not actually do 

(6*5*4*3*2 + 7*6*5*4*3*2) / 4*3*2

I've actually started developing a Factorial class, but I'm new to python and numpy and was wondering if this is a problem that's already solved.

Upvotes: 4

Views: 2198

Answers (2)

Hugh Bothwell
Hugh Bothwell

Reputation: 56634

As @Oleg has suggested, you can do this with sympy:

import numpy as np
import sympy as sp

# preparation
n = sp.symbols("n")
F = sp.factorial

# create the equation
f = (F(n) + F(n + 1)) / F(n - 2)
print(f)               # => (factorial(n) + factorial(n + 1))/factorial(n - 2)

# reduce it
f = f.simplify()
print(f)               # => n*(n - 1)*(n + 2)

# evaluate it in SymPy
# Note: very slow!
print(f.subs(n, 6))    # => 240

# turn it into a numpy function
# Note: much faster!
f = sp.lambdify(n, f, "numpy")
a = np.arange(2, 10)
print(f(a))            # => [  8  30  72 140 240 378 560 792]

Upvotes: 4

Spencer Brett
Spencer Brett

Reputation: 236

Maybe you could look into increasing the efficiency using table lookups if space efficiency isn't a major concern. It would greatly reduce the number of repeated calculations. The following isn't terribly efficient, but it's the basic idea.

cache = {1:1}
def cached_factorial(n):
    if (n in cache):
        return cache[n]
    else:
        result = n * cached_factorial(n-1)
        cache[n] = result
        return result

Upvotes: 3

Related Questions