Python: Is math.factorial memoized?

Question

I am solving a problem in three different ways, two are recursive and I memoize them myself. The other is not recursive but uses math.factorial. I need to know if I need to add explicit memoization to it.

Thanks.

Answer 1

Search for math_factorial on this link and you will find its implementation in python:

http://svn.python.org/view/python/trunk/Modules/mathmodule.c?view=markup

P.S. This is for python2.6

Answer 2

Python's math.factorial is not memoized, it is a simple for loop multiplying the values from 1 to your arg. If you need memoization, you need to do it explicitly.

Here is a simple way to memoize using dictionary setdefault method.

import math
cache = {}
def myfact(x):
    return cache.setdefault(x,math.factorial(x))
print myfact(10000)
print myfact(10000)

Answer 3

Python's math.factorial is not memoized.

I'm going to guide you through some trial and error examples to see why to get a really memoized and working factorial function you have to redefine it ex-novo taking into account a couple of things.

The other answer actually is not correct. Here,

import math
cache = {}
def myfact(x):
    return cache.setdefault(x,math.factorial(x))

the line

return cache.setdefault(x,math.factorial(x))

computes both x and math.factorial(x) every time and therefore you gain no performance improvement.

You may think of doing something like this:

if x not in cache:
    cache[x] = math.factorial(x)
return cache[x]

but actually this is wrong as well. Yes, you avoid computing again the factorial of a same x but think, for example, if you are going to calculate myfact(1000) and soon after that myfact(999). Both of them gets calculated completely thus not taking any advantage from the fact that myfact(1000) automatically computes myfact(999).

It comes natural then to write something like this:

def memoize(f):
    """Returns a memoized version of f"""
    memory = {}
    def memoized(*args):
        if args not in memory:
            memory[args] = f(*args)
        return memory[args]
    return memoized

@memoize
def my_fact(x):
    assert x >= 0
    if x == 0:
        return 1
    return x * my_fact(x - 1)

This is going to work. Unfortunately it soon reaches the maximum recursion depth.

So how to implement it?

Here is an example of truly memoized factorial, that takes advantage of how factorials work and does not consumes all the stack with recursive calls:

# The 'max' key stores the maximum number for which the factorial is stored.
fact_memory = {0: 1, 1: 1, 'max': 1}

def my_fact(num):
    # Factorial is defined only for non-negative numbers
    assert num >= 0

    if num <= fact_memory['max']:
        return fact_memory[num]

    for x in range(fact_memory['max']+1, num+1):
        fact_memory[x] = fact_memory[x-1] * x
    fact_memory['max'] = num
    return fact_memory[num]

I hope you find this useful.

EDIT:

Just as a note, a way to achieve this same optimization having at the same time the conciseness and elegance of recursion would be to redefine the function as a tail-recursive function.

def memoize(f):
    """Returns a memoized version of f"""
    memory = {}
    def memoized(*args):
        if args not in memory:
            memory[args] = f(*args)
        return memory[args]
    return memoized

@memoize
def my_fact(x, fac=1):
    assert x >= 0
    if x < 2:
        return fac
    return my_fact(x-1,  x*fac)

Tail recursion functions in fact can be recognized by the interpreter/compiler and be automagically translated/optimized to an iterative version, but not all interpreters/compilers support this.

Unfortunately python does not support tail recursion optimization, so you still get:

RuntimeError: maximum recursion depth exceeded

when the input of my_fact is high.

Answer 4

I'm late to the party, yet here are my 2c on implementing an efficient memoized factorial function in Python. This approach is more efficient since it relies on an array-like structure (that is list) rather than a hashed container (that is dict). No recursion involved (spares you some Python function-call overhead) and no slow for-loops involved. And it is (arguably) functionally-pure as there are no outer side-effects involved (that is it doesn't modify a global variable). It caches all intermediate factorials, hence if you've already calculated factorial(n), it will take you O(1) to calculate factorial(m) for any 0 <= m <= n and O(m-n) for any m > n.

def inner_func(f):
    return f()


@inner_func
def factorial():
    factorials = [1]

    def calculate_factorial(n):
        assert n >= 0
        return reduce(lambda cache, num: (cache.append(cache[-1] * num) or cache),
                      xrange(len(factorials), n+1), factorials)[n]

    return calculate_factorial