I recently posted articles on memoization of factorials and calculating sines and cosines with Taylor polynomials. It seems logical to combine the two principles and write a library to memoize the trigonometric values sine, cosine and tangent.
If you just need a few values then this approach is overkill, but some applications require very heavy use of trigonometry and so need all the optimization they can get. In particular 3D graphics consist of large numbers of triangles, the positioning and rendering of which requires some serious use of trigonometry.
This project is by no means definitive, and there is plenty of scope for making it more versatile and even for testing variations for optimum efficiency. What it does do, however, is introduce the idea of memoization as well as running through a few thought processes involved in minimizing the amount of data which needs to be stored in memory.
Before we start coding I'll run through how we can reduce the actual number of values we need to calculate and store to an absolute minimum. Firstly look at this sine wave for +/- 1440° (+/- 26.4 radians), courtesy of Wolfram Alpha.
The sine can be calculated of any real number but the plot above demonstrates that the values repeat every 360°, so to start with we can memoize only the sines of 0 to 360°, shifting angles outside this range left or right into the range of values we have. This range is shown between the two red lines.
But we can go further. The sines of 180° to 360° are just the negative of those for 0°-180° so can easily be calculated from the lower range. We therefore only need the sines between the red lines in this plot.
But let's take it even further. The sine wave for 0° to 180° is symmetrical about 90°, so the sines of values from 90° to 180° can easily be calculated from those for 0° to 90°. That's as far as we can take it, so we will code our library to memoize the sines of 0° to 90°, and to use these as a basis for calculating the sines of any angle. The final range is shown in the last plot.
Of course the extra work needed to calculate the sine etc. of any angle from just this limited range of memoized values might outweigh the benefits. As I mentioned above there is plenty of scope for experimentation to find the optimum solution.
To be complete we also need to provide functions to return cosine and tangent. Both can easily be calculated from the sine, as will be demonstrated when we get to implementing the functions.
Coding
The library will consist of the following functions.
- bool memoize_trigonometric() - this will calculate and store the sines of 0° to 90°
- double memoized_sine(int degrees)
- double memoized_cosine(int degrees)
- double memoized_tangent(int degrees)
- double free_memoized_trigonometric() - frees up the memory used to memoize values
Create a new folder and within it create the following empty files.
- main.c
- memoizationtrigonometric.h
- memoizationtrigonometric.c
Open memoizationtrigonometric.h and type or past this code. You can download the source code as a zip or from Github if you prefer.
Source Code Links
memoizationtrigonometric.h
#include<stdbool.h> #define M_PI 3.14159265358979323846264338327 #define DEGREES_IN_RADIAN (180.0 / M_PI) double* memoized_sines; // -------------------------------------------------------- // FUNCTION PROTOTYPES // -------------------------------------------------------- bool memoize_trigonometric(); double memoized_sine(int degrees); double memoized_cosine(int degrees); double memoized_tangent(int degrees); void free_memoized_trigonometric();
That's the header file finished so we can move on to implementing the functions in memoizationtrigonometric.c. Open that file and past the #includes and the first function.
memoizationtrigonometric.c (part 1)
#include<stdlib.h> #include<stdbool.h> #include<stdio.h> #include<string.h> #include<math.h> #include"memoizationtrigonometric.h" // -------------------------------------------------------- // FUNCTION memoize_trigonometric // -------------------------------------------------------- bool memoize_trigonometric() { memoized_sines = malloc(91 * sizeof(double)); if(memoized_sines != NULL) { for(int d = 0; d <= 90; d++) { memoized_sines[d] = sin(d / DEGREES_IN_RADIAN); } return true; } else { return false; } }
The memoize_trigonometric function calculates and stores the sines of angles from 0 to 90°. I have used malloc here instead of hard-coding an array of 91 elements to leave the door open to alternative implementations. Firstly, pre-calculating only values for 0 to 90° might be over-optimization, so we could write some test code to see if, for example, values of 0 to 360° might be better. Secondly, we could add a couple of arguments to memoize_trigonometric to specify the range of values we need, and finally we could increase the granularity of the values, for example calculating sines to 0.5. 0.25 etc.. Also, using malloc means the memory can be freed when it is no longer needed rather than having an array left in memory.
We can now move on to the first trigonometric function, memoized_sine.
memoizationtrigonometric.c (part 2)
// -------------------------------------------------------- // FUNCTION memoized_sine // -------------------------------------------------------- double memoized_sine(int degrees) { int degrees_shifted; double sine; bool sine_negative = false; // get an angle between -360 and 360 using modulus operator degrees_shifted = degrees % 360; // move negative angles by 360 into the positive range if(degrees_shifted < 0) degrees_shifted += 360; // if angle is in the 180-360 range shift it to the 0-180 range // and record that we need to negate the sine if(degrees_shifted > 180) { degrees_shifted-= 180; sine_negative = true; } // if degrees_shifted is 90-180 we need to "mirror" it into the 0-90 range if(degrees_shifted > 90 && degrees_shifted <= 180) { degrees_shifted = 90 - (degrees_shifted - 90); } // now get the sine from the memoized lookup table sine = memoized_sines[degrees_shifted]; // negate if angle was 180-360 if(sine_negative) { sine*= -1; } return sine; }
This function carries out the rather fiddly process of shifting any angle into the 0-90 range, as per the comments. Fortunately the equivalent functions for cosine and tangent basically use the sine function, so are far simpler. Let's write those functions, and free_memoized_trigonometric.
memoizationtrigonometric.c (part 3)
// -------------------------------------------------------- // FUNCTION memoized_cosine // -------------------------------------------------------- double memoized_cosine(int degrees) { return memoized_sine(degrees + 90); } // -------------------------------------------------------- // FUNCTION memoized_tangent // -------------------------------------------------------- double memoized_tangent(int degrees) { if( (degrees % 90) != 0) { double sine = memoized_sine(degrees); double cosine = memoized_cosine(degrees); return sine / cosine; } else { return NAN; } } // -------------------------------------------------------- // FUNCTION memoize_trigonometric // -------------------------------------------------------- void free_memoized_trigonometric() { free(memoized_sines); }
The memoized_cosine is straightforward - the cosine of an angle is the same as the sine shifted by 90°.
The tangent perhaps needs a bit of explanation: it is the ratio of the side opposite the angle to the side adjacent to the angle, but if the angle is 90° then the length of the adjacent side is 0. (We then have the bizarre phenomenon of a triangle which looks like a straight line and has no area!) The value of tan for 90° is therefore opposite/0, but as division by 0 is undefined tan(90°) is also undefined and so we return NAN (not a number). I can therefore claim that my implementation is better than the C library's own which returns erratic garbage values. (My pocket calculator displays Math ERROR.)
That's memoizationtrigonometric.c finished so we will move on to writing a main function to test and demonstrate the code. In main.c paste the following.
main.c
#include<stdio.h> #include<math.h> #include<time.h> #include<locale.h> #include<stdlib.h> #include<stdbool.h> #include"memoizationtrigonometric.h" //-------------------------------------------------------- // FUNCTION main //-------------------------------------------------------- int main(void) { puts("-----------------------------"); puts("| codedrome.com |"); puts("| Memoization Trigonometric |"); puts("-----------------------------\n"); if(memoize_trigonometric()) { // sines puts("Sines\n-----"); for(int i = -720; i <= 720; i+=15) { printf("%6d%12lf%12lf\n", i, sin(i / DEGREES_IN_RADIAN), memoized_sine(i)); } // cosines puts("Cosines\n-------"); for(int i = -720; i <= 720; i+=15) { printf("%6d%12lf%12lf\n", i, cos(i / DEGREES_IN_RADIAN), memoized_cosine(i)); } // tangents puts("Tangents\n--------"); for(int i = -720; i <= 720; i+=15) { if( (i % 90) != 0) { printf("%6d%12lf%12lf\n", i, tan(i / DEGREES_IN_RADIAN), memoized_tangent(i)); } else { printf("%6d%12s%12lf\n", i, "~", memoized_tangent(i)); } } free_memoized_trigonometric(); } return EXIT_SUCCESS; }
Basically what we have here are three loops, outputting the sines, cosines and tangents of a range of angles using both the C library's functions and our own. (Note that the C library functions take radians, so the degrees are converted.) Feel free to change the ranges and increments if you wish. All we need do now is to compile and run the program, so in the terminal run the following.
Compiling and running
gcc main.c memoizationtrigonometric.c -std=c11 -lm -o main ./main
The output is rather long of course, so I'll only show a small part of it.
Program output
----------------------------- | codedrome.com | | Memoization Trigonometric | ----------------------------- Sines ----- -720 0.000000 0.000000 -705 0.258819 0.258819 -690 0.500000 0.500000 -675 0.707107 0.707107 -660 0.866025 0.866025 -645 0.965926 0.965926 -630 1.000000 1.000000