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 an array 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.
There are actually two basic approaches to this technique:- Calculate and store all values within a given range in advance, and then retrieve them from the array as needed. This approach is best if there is a relatively small number of values and we know all or most of them will be needed frequently.
- Only calculate values as they are needed, but store those values for future use. Then when a value is needed, return the previously calculated value if it exists, or calculate and store it for future use if not. This approach is more suitable if a very large range of values may be needed, or if only a small subset of values in a range are likely to be needed.
Deciding which approach to use is potentially tricky, and if you absolutely must squeeze the optimum performance from your software it might even need some kind of sophisticated runtime monitoring and adaptive behaviour. However, that is way beyond the scope of this little project!
What Are We Going to Code?
This project consists of a small library implementing memoization of factorials up to a given maximum, with the choice of either pre-calculation or on-demand calculation. It will provide the following:
- A struct to hold the lookup table and the maximum number the factorial of which it does or can hold
- A factorials_calculate function to calculate all values to a given maximum (approach 1)
- A factorials_allocate function to allocate memory to a given maximum, but not actually calculate the factorials (approach 2)
- A factorials_output function to print the lookup table, for demonstration and debugging purposes
- A factorials_get function. This will calculate, store and return factorials which have not yet been calculated, or just return ones which have. Can be used with both factorials_calculate and factorials_allocate.
- A factorials_free function to free the lookup table's memory
Starting to Code
Create a new folder, and then create these empty files.
- main.c
- memoizationfactorials.h
- memoizationfactorials.c
Open memoizationfactorials.h and enter or paste the following. You can download the source code as a zip or from Github if you prefer.
Source Code Links
memoizationfactorials.h
#include<stdlib.h> #include<stdbool.h> #include<stdio.h> #include<math.h> //-------------------------------------------------------- // STRUCT factorials //-------------------------------------------------------- typedef struct factorials { int max; int* calculated; } factorials; //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- bool factorials_calculate(factorials* facs, int max); bool factorials_allocate(factorials* facs, int max); void factorials_output(factorials* facs); int factorials_get(factorials* facs, int n); void factorials_free(factorials* facs);
That's the header file finished, but leave it open if you want to refer to it. Now open memoizationfactorials.c and we'll start to implement the functions. After the #includes the first function is factorials_calculate.
memoizationfactorials.c (part 1)
#include<stdlib.h> #include<stdbool.h> #include<stdio.h> #include<string.h> #include<math.h> #include"memoizationfactorials.h" //-------------------------------------------------------- // FUNCTION factorials_calculate //-------------------------------------------------------- bool factorials_calculate(factorials* facs, int max) { facs->calculated = malloc(max * sizeof(int)); if(facs->calculated != NULL) { facs->max = max; int prev = 1; facs->calculated[0] = 1; for(int i = 1; i <= max; i++) { facs->calculated[i] = i * prev; prev = facs->calculated[i]; } return true; } else { return false; } }
In factorials_calculate we first call malloc to obtain the required memory. If it's not NULL, we set the struct's max property, initialize a prev variable to use as a multpilier in the loop, and then set the factorial of 0 to 1. (I am afraid my knowledge of mathematics is minimal, and explaining why 0! = 1 is beyond my abilities.)
Then within a for loop we calculate the next factorial by multiplying the current number by the previous factorial, then update prev.
Now let's write factorials_output, which simply iterates the lookup table, outputting n and n!. I have also tacked the factorials_output function on here.
memoizationfactorials.c (part 2)
//-------------------------------------------------------- // FUNCTION factorials_output //-------------------------------------------------------- void factorials_output(factorials* facs) { puts(" n n!\n---------------"); for(int i = 0; i <= facs->max; i++) { printf("%3d%12d\n", i, facs->calculated[i]); } } //-------------------------------------------------------- // FUNCTION factorials_free //-------------------------------------------------------- void factorials_free(factorials* facs) { free(facs->calculated); }
We've now got enough code to calculate and print a pile of factorials, so open main.c and enter the following.
main.c (part 1)
#include<stdio.h> #include"memoizationfactorials.h" //-------------------------------------------------------- // FUNCTION main //-------------------------------------------------------- void main(void) { puts("-----------------------------"); puts("| codedrome.com |"); puts("| Memoization of Factorials |"); puts("-----------------------------\n"); // calculate all values to max in advance factorials facs1; bool success = factorials_calculate(&facs1, 9); if(success) { factorials_output(&facs1); puts(""); factorials_free(&facs1); } }
Compile and run the code with the following in Terminal.
Compiling
gcc main.c memoizationfactorials.c -std=c11 -o main
Running
./main
Program Output
----------------------------- | codedrome.com | | Memoization of Factorials | ----------------------------- n n! -------------- 0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880
Having used factorials_calculate we can then use the struct's calculated property directly to obtain factorials. We'll now go on to implement factorials_allocate, and then factorials_get. Go back to memoizationfactorials.c and add the following code.
memoizationfactorials.c (part 3)
// -------------------------------------------------------- // FUNCTION factorials_allocate // -------------------------------------------------------- bool factorials_allocate(factorials* facs, int max) { facs->calculated = calloc(max, sizeof(int)); if(facs->calculated != NULL) { facs->max = max; return true; } else { return false; } }
This is straightforward but note that we use calloc instead of malloc. The reason for this is that unlike malloc, calloc will set all the memory it allocates to 0. We'll use the 0 values as flags to indicate that a particular factorial has not yet been calculated. Now enter the factorials_get function.
memoizationfactorials.c (part 4)
//-------------------------------------------------------- // FUNCTION factorials_get //-------------------------------------------------------- int factorials_get(factorials* facs, int n) { int fac = facs->calculated[n]; if(fac == 0) { if(n > 0) { fac = n; for(int i = n - 1; i > 1; i--) { fac*= i; } } else { fac = 1; } facs->calculated[n] = fac; } return fac; }
In factorials_get we first pick up the relevant value from the lookup table. If it hasn't yet been calculated it will be 0, so we then calculate it and set the value in the lookup table for future use.
The library is now complete so all that remains is to add code to main to test the new functionality. I have included the whole of the main function below, including the existing code.
main.c (part 2)
//-------------------------------------------------------- // FUNCTION main //-------------------------------------------------------- void main(void) { puts("-----------------------------"); puts("| codedrome.com |"); puts("| Memoization of Factorials |"); puts("-----------------------------\n"); // calculate all values to max in advance factorials facs1; bool success = factorials_calculate(&facs1, 9); if(success) { factorials_output(&facs1); puts(""); factorials_free(&facs1); } // allocate and get: calculate and store values as requested factorials facs2; success = factorials_allocate(&facs2, 9); if(success) { factorials_output(&facs2); puts(""); factorials_get(&facs2, 3); factorials_get(&facs2, 5); factorials_get(&facs2, 7); factorials_output(&facs2); puts(""); factorials_free(&facs2); } }
In the new code we call factorials_allocate and then factorials_output to show all the factorials are 0. Then we call factorials_get a few times to calculate some values. Obviously this function returns the value but these are not used here. If we then call factorials_output again you can see that the factorials for 3, 5 and 7 have been set, and are ready for re-use. The program output now looks like this, with just the output for the new code shown.
Program Output
----------------------------- | codedrome.com | | Memoization of Factorials | ----------------------------- n n! -------------- 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 n n! -------------- 0 0 1 0 2 0 3 6 4 0 5 120 6 0 7 5040 8 0 9 0