A lookup table for fast Python math

EDIT: the UnivariateSpline class from Scipy is much faster!

Numerical programming frequently requires the use of look-up tables. A look-up table is a collection of pre-computed values. When given an “x” value, the table returns a pre-computed “y” value. Look-up tables can be used to speed up numerical codes, when it is faster to look up a value in the table than it is to compute the value. They are also used when the data in the table cannot be computed–for example, experimental data or averaged results from an ensemble of Monte Carlo simulations. Another application is to compute a value when a function cannot be solved algebraically. Assume that you have a formula for a function q(h). You need the value of h for a given value of q, but the formula cannot be algebraically solved to get h(q). Instead, choose a range of h values, compute the function q(h), and store each value in a look-up table. Now you can get h(q) for any value stored in the table. The major limitation of a look-up table is that it cannot return valid results for any value of q which is outside the range of those stored in the table. Depending on its implementation, the table may be able to interpolate to return values between known points.

Scipy includes a handy lookup table class, but it’s sort of hidden. Here is an example of how to create a lookup table using interp1d:

from scipy.interpolate import interp1
from numpy import *

ddeltah = L/1000.
h_sampled = arange(0., L+deltah/10, deltah)
q_sampled = q(h_sampled,L,D,1e-4)
h_interp = interp1d(q_sampled, h_sampled, kind='linear')
print h_interp(0.514234)

First, create a Numpy array h_sampled to store the h-values for the lookup table. The function q(h,L,D,dt) is not shown, but it takes an array of h values and returns a floating-point array of q values in the range from 0 to 1. These two arrays are then used to construct the lookup table. The table uses linear interpolation to compute values between the known points. Higher-order interpolations can be used, but I don’t need them in this case. Higher-order interpolations can introduce distortions for certain types of data, so they are best avoided unless you really understand the data being fitted. Below is a plot illustrating the results of a look-up table:

The solid line is the function h(q), the black dots are the values stored in the lookup table, and the red triangles are values interpolated from the lookup table. The function h(q) was approximated with a lookup table that was created by computing q(h) with an evenly spaced array of h values. Notice how the points stored in the table are spaced more closely together for smaller values of q. This is a consequence of using a linear “h” spacing with a nonlinear function. You could work around this by using a non-uniform array of “h” values to create the lookup table. This is another reason to understand the function you are approximating, instead of blindly placing values into the table.

If you want to understand more about how lookup tables work, or don’t want to install SciPy, check out this interpolated lookup table class. I wouldn’t use it for serious math, since it doesn’t use Numpy and is probably not very fast.


2 thoughts on “A lookup table for fast Python math

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.