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
__init__ and stored in a list. There is also a method to get an individual factorial.
The project consists of the following files:
You can clone/download these from the Github repository.
Let’s look at factorialsmemoization.py first.
__init__ method 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.
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…
…which will give you the following output.
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.