Memoization of Factorials in Python

Chris Webb
Aug 31, 2020 · 3 min read
Image for post
Image for post
Image: Pixabay

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 article describes 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 and stored in a list. There is also a method to get an individual factorial.

The project consists of the following files:

  • factorialsmemoization.py
  • main.py

You can clone/download these from the Github repository.

Let’s look at factorialsmemoization.py first.

The method takes as an argument the maximum number to calculate factorials of. We then create an empty list, store the maximum in , and initialize a variable called 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 to 1 to start with. We then set to the current factorial.

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

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

After importing the module created above we enter the function which first creates an instance of the class with 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…

…which will give you the following output.

Image for post
Image for post

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.

Python In Plain English

New Python + Programming articles every day.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store