The single biggest gain was achieved by optimizing the trigonometric and exponential functions. For the trig functions, the CORDIC method was used. (For more information on CORDIC, which is short for "COordinate Rotation DIgital Computer," see "Implementing CORDIC Algorithms," by Pitt Jarvis; www.ddj.com/architect/184408428.) CORDIC gets its name because it uses properties of rotations on a plane to calculate sines and cosines. A vector can be rotated counterclockwise by an angle q using a rotation matrix.
Equivalently, if you have two angles and such that =+, then we can first rotate by , and then by , to achieve the same effect.
The rotation by can then itself be split into further rotations by smaller and smaller angles. The benefit here comes from the fact that you can then pick a set of angles i in advance, and precompute the appropriate sines and cosines. Rather than a time-consuming and potentially inaccurate power-series calculation, the desired sines and cosines can instead be calculated by a short series of multiplications and additions. Rather than using both sines and cosines of the angles i, the cosines can be factored out:
As written, this is fine for some fixed angle theta, but what about a general angle? It can be shown that provided that:
i < i-1
i >= 0.5•i-1
then any angle can be made by adding or subtracting each i exactly once up to a precision determined by the number of angles n. Since cos(x)=cos(-x) and tan(x)=-tan(-x), the factored-out product of cosines can be stored as a constant multiplier once the angles have been determined, and the appropriate signs used for the tangents depending on the actual angle .
As a final simplifying step, if you choose the angles i such that tan(i)=2-j for some integer j, then this greatly simplifies the multiplication, as it is now just a simple shift.
We only need to handle angles in the range -/2 to /2, since the sines and cosines of larger angles only vary in sign (if at all), and restricting it to this range limits the number of iterations required.
The sine and cosine of an angle can thus be calculated simply by rotating the unit vector from the x axis by the required angle as described: The cosine and sine are the x and y coordinates of the rotated vector.
The inverse tangent can easily be calculated with the CORDIC rotation tables. This time, rather than rotating the unit vector, a vector with an x component of 1 and a y component of the value for which we want the arctan is rotated until it has a y value of 0.