Memoization of Factorials

I am currently working on an article about calculating sines and cosines using Taylor Polynomials. These make heavy use of factorials so I started thinking about ways to streamline the process.

This post consists of a simple project using memoization with a lookup table to pre-calculate factorials and store them for future use.

Many algorithms and other processes make heavy and repeated use of values which need to be calculated, often in a way which is expensive in terms of memory and/or time. It therefore makes sense to develop some sort of mechanism whereby the values which are or are likely to be needed frequently are calculated only once. The use of factorials in calculating trigonometric functions mentioned above is one example. In a future article I'll extend the principle to calculating and storing sines and cosines themselves, but of course there are many other common examples.

When considering factorials the broad outline of memoization using a lookup table is simple and obvious: just use a list of integers the highest index of which is the highest number we want the factorial of. The factorial of a given number is therefore set and retrieved using the number as the array's index.

What Are We Going to Code?

This project consists of a small class implementing memoization of factorials up to a given maximum. Factorials are calculated in __init__ and stored in a list. There is also a method to get an individual factorial.

Starting to Code

Create a new folder and then create these empty files.

  • factorialsmemoization.py
  • main.py

Open factorialsmemoization.py and enter or paste the following. You can download the source code from the Downloads page or clone/download the Github repository if you prefer.

factorialmemoization.py

import math

class FactorialMemoization(object):

    """
    Memoizes factorials of integers up to the n argument of init.
    Provides get method to retrieve memoized factorials.
    """

    def __init__(self, n):

        """
        Stores factorials of numbers from 0 to n in list.
        """

        self.factorials = []
        self.memoized_to = n
        prev = 1

        # 0! = 1 (yeah, really)
        self.factorials.append(1)

        # Multiplying by previous factorial is much more efficient
        # than calculating each factorial individually
        for i in range(1, n + 1):
            self.factorials.append(i * prev)
            prev = self.factorials[i]

    #-----------------------------------------------------

    def get(self, n):

        """
        Return factorial from list or raise ValueError if outside memoized range.
        """

        if(n < 0 or n > self.memoized_to):
            raise ValueError("Factorial requested is outside of memoized range")
        else:
            return self.factorials[n]

The __init__ methos takes as an argument the maximum number to calculate factorials of. We then create an empty list, store the maximum in self.memoized_to, and initialize a variable called prev to 1; its purpose will become clear in a moment.

We then append the factorial of 0 which is 1 to the list before entering a loop to calculate the rest. Note that this loop starts at 1 as we have already set 0. Within the loop we set the next factorial to the previous multiplied by the current number, hence setting prev to 1 to start with. We then set prev to the current factorial.

Finally we have the get method which checks whether the requested factorial is out of range, raising an exception if so. If n is valid it returns the relevant value from the list.

That's factorialmemoization.py finished so we can move on to main.py.

main.py

import factorialmemoization

def main():

    """
    Demonstrate FactorialMemoization class.
    """

    print("-----------------------------\n| code-in-python.com        |\n| Memoization of Factorials |\n-----------------------------\n")

    fm = factorialmemoization.FactorialMemoization(8)

    try:

        # test beyond memoized range to demonstrate exception
        for n in range(0, 10):

            print("{:d}:  ".format(n), end="")

            print("{:d}".format(fm.get(n)))

    # If we call get outside memoized range it raises ValueError
    except ValueError as e:

        print(e)

#-----------------------------------------------------

main()

After importing the module created above we enter the main function which first creates an instance of the FactorialMemoization class with n set to 8. We then enter a loop to print out factorials of 0 to 10 - I have deliberately overrun the range to demonstrate the exception handling.

Run the program with the following in Terminal...

Running

python3.6 main.py

...which will give you the following output.

Program Output

-----------------------------
| code-in-python.com        |
| Memoization of Factorials |
-----------------------------

0:  1
1:  1
2:  2
3:  6
4:  24
5:  120
6:  720
7:  5040
8:  40320
9:  Factorial requested is outside of memoized range

As you can see we get the correct factorials up to 8 but then hit an exception with 9 which is beyond the calculated range.

Please follow this blog on Twitter for news of future posts and other useful Python stuff.