I recently posted an article on memoization of factorials and mentioned that another possible use for memoization was with trigonometric values. In this article I will do just that, but this project is significantly more complex than the previous one for factorials.
Memoization is the process of calculating and storing values which are needed repeatedly rather than calculating them each time they are needed, thus potentially increasing efficiency. 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.
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. There is plenty of scope for experimentation to find the optimum solution.
To be complete we also need to provide methods to return cosine and tangent. Both can easily be calculated from the sine, as will be demonstrated when we get to implementing the functions.
Create a new folder and within it create the following empty files.
- trigonometricmemoization.py
- main.py
Open trigonometricmemoization.py and type or paste this code. You can download the source code as a zip or clone/download from Github if you prefer.
Source Code Links
trigonometricmemoization.py
import math class TrigonometricMemoization(object): """ Stores sines of 0 to 90 degrees in a list. These are used as the basis of calculating and returning sines, cosines and tangents of any angle. """ def __init__(self): """ Calculates sines of 0 to 90 degrees and appends them to a list. """ self.memoized_sines = [] degrees_in_radian = 180.0 / math.pi for d in range(0, 91): self.memoized_sines.append(math.sin(d / degrees_in_radian)) def sine(self, degrees): """ Calculates sine of any angle from values stored in list. """ 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 and degrees_shifted <= 180): degrees_shifted = 90 - (degrees_shifted - 90) # now get the sine from the memoized lookup table sine = self.memoized_sines[degrees_shifted] # negate if angle was 180-360 if(sine_negative): sine*= -1 return sine def cosine(self, degrees): """ Cosine can easily be calculated from sine by shifting 90 degrees. """ return self.sine(degrees + 90) def tangent(self, degrees): """ Tangent is calculated using the sine and cosine from the other two methods. """ try: sine = self.sine(degrees) cosine = self.cosine(degrees) return sine / cosine except: return math.nan
The __init__ function simply creates an empty list and then adds the sines of 0° to 90°. The math.sin function takes radians so the degrees need to be converted.
Next we have the rather complex sine method. This carries out the 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.
The cosine method is straightforward - the cosine of an angle is the same as the sine shifted by 90°.
The tangent method perhaps needs a bit of explanation: the tangent is the ratio of the side opposite the angle to the side adjacent to the angle and is calculated by dividing the sine by the cosine. However, for 90° and subsequent angles calculated by adding 180° tangent is undefined as it would involve division by 0. To handle this I have used try/except ("it is better to ask for forgiveness than permission") and returned math.nan in the except block. Python's math.tan returns garbage values in these circumstances so I think I can claim my implementation is better!
That's trigonometricmemoization.py finished so we will move on to writing a main function to test and demonstrate the code. In main.py paste the following.
main.py
import math import trigonometricmemoization def main(): print("-----------------------------") print("| codedrome.com |") print("| Trigonometric Memoization |") print("-----------------------------\n") degrees_in_radian = 180.0 / math.pi tm = trigonometricmemoization.TrigonometricMemoization() print("-" * 70) print("| Degrees | Sines | Cosines | Tangents |") print("-" * 70) for d in range(-720, 721, 15): print("| {:7d} ".format(d), end="") print("| {:7.4f} | {:7.4f}".format(math.sin(d / degrees_in_radian), tm.sine(d)), end="") print(" | {:7.4f} | {:7.4f}".format(math.cos(d / degrees_in_radian), tm.cosine(d)), end="") if( ((d - 90) % 180) != 0): print("| {:7.4f} | {:7.4f} |".format(math.tan(d / degrees_in_radian), tm.tangent(d))) else: print("| ~ | {:7.4f} |".format(tm.tangent(d))) print("-" * 70) main()
Firstly we set up a degrees_in_radian value, create an instance of TrigonometricMemoization, and print a heading for a table of values. As you probably know, in Python you can multiply strings to create a string with the original string repeated a number of times. I have used this here to draw horizontal lines for the table.
We then have a for loop from -720° to 720°; I have used an interval of 15 to keep the size of the table reasonable. In the loop we print the angle along with the sine, cosine and tangent of that angle, once using Python's own math functions and again with our TrigonometricMemoization class. For the tangent I have first checked for angles for which the tangent is undefined to avoid calling Python's tan function on them, instead just printing the tilde character "~".
Now the coding is finished we can run it with this command.
Running
python3.7 main.py
The output is rather long of course so I'll only show a small part of it.
Program output (partial)
----------------------------- | codedrome.com | | Trigonometric Memoization | ----------------------------- ---------------------------------------------------------------------- | Degrees | Sines | Cosines | Tangents | ---------------------------------------------------------------------- | -720 | 0.0000 | 0.0000 | 1.0000 | 1.0000| ~ | nan | | -705 | 0.2588 | 0.2588 | 0.9659 | 0.9659| 0.2679 | 0.2679 | | -690 | 0.5000 | 0.5000 | 0.8660 | 0.8660| 0.5774 | 0.5774 | | -675 | 0.7071 | 0.7071 | 0.7071 | 0.7071| 1.0000 | 1.0000 | | -660 | 0.8660 | 0.8660 | 0.5000 | 0.5000| 1.7321 | 1.7321 | | -645 | 0.9659 | 0.9659 | 0.2588 | 0.2588| 3.7321 | 3.7321 | | -630 | 1.0000 | 1.0000 | -0.0000 | 0.0000| ~ | nan | | -615 | 0.9659 | 0.9659 | -0.2588 | -0.2588| -3.7321 | -3.7321 | | -600 | 0.8660 | 0.8660 | -0.5000 | -0.5000| -1.7321 | -1.7321 | | -585 | 0.7071 | 0.7071 | -0.7071 | -0.7071| -1.0000 | -1.0000 | | -570 | 0.5000 | 0.5000 | -0.8660 | -0.8660| -0.5774 | -0.5774 | | -555 | 0.2588 | 0.2588 | -0.9659 | -0.9659| -0.2679 | -0.2679 | . . .
As you can see all the values match except where tangent is undefined: the Python column show "~" whereas the TrigonometricMemoization class column shows "nan".