Approximating the exponential function

The garden has frozen over and I have caught a cold. It is hard to do difficult work. Thus I continue to find fast approximations of transcendental functions. This is more fun than solving crossword puzzles.

The exponential function is not periodic like the sine and cosine, but we can use a similar method. For any x we have exp(x)=exp(n)*exp(x-n). If n is the largest integer smaller than x, then 0≤x-n≤1 and we need two tables. One is for exp(n) of integers n with a value of exp(n) larger than the smallest number and smaller than the largest number JavaScript can handle. This makes a table of about 1500 elements. The second table is for exp(x), with 0≤x-n≤1. Its size depends on the desired precision. For more details see the code of http://bookofgames.ch/fastSin.html.

What is the accuracy? The exponential function varies strongly and it is more reasonable to look at its relative error. Using a table of 1000 elements for exp(x), we get a relative error of 0.00025 for the simple nearest point approximation. The linear interpolation is better with an error of only 6e-8. That’s good enough for most calculations. Because (d²exp(x)/dx²)=exp(x) we can again improve the linear interpolation to get a quadratic approximation. Its error is only 4e-12.

The timing for 100 million function evaluations is again very interesting. Chrome seems to be a bit faster than Chromium. It takes about 1 second for the empty loop. Evaluating the original Mat.exp() function takes additional 10 seconds. Our approximations are about four times faster. The simple approximation takes 2.1 seconds, the linear interpolation 2.4 seconds and the “quadratic” approximation 2.6 seconds.

Again, Firefox is faster. Doing the empty loop takes only 0.3 seconds. The Math.exp() needs only 2.5 seconds more and is four times faster than in Chrome! The approximations are five times faster. The simple approximation takes 0.3 seconds, the linear interpolation 0.5 seconds and the “quadratic” approximation 0.7 seconds.

It seems best to use Firefox and the linear approximation.

This entry was posted in programming and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s