Optimization & Efficiency

Short Segments

Optimization Tip:
Chop Out Needless Roots

We often write mathematical expressions in programs just as they appear in textbooks. But efficiency sometimes dictates that we modify these "natural" expressions. For example, the square root function, sqrt, is time consuming and can frequently be eliminated from real-world applications. Consider the calculation of distance between two points, given their Cartesian coordinates:

dx = a.x - b.x;
dy = a.y - b.y;
dist = sqrt(dx*dx + dy*dy);

If we are identifying the nearest neighbor, we don't have to calculate dist. It is enough to find the smallest value of the "cheaper" quantity

dist_squared = dx*dx + dy*dy;

The fragment in Listing 1 shows both sets of calculations. On my machine, the first set took 1.9 seconds; the second set (no square root) took 1.0 seconds — a speed-up of nearly a factor of 2. In many applications the coordinates will be integers, so eliminating the sqrt will eliminate all use of floating-point for an even greater speed gain.

We can use the central idea of this optimization in some field calculations as well. In this case, the "optimization" consists of keeping roots out of expressions where they don't belong in the first place. For example, gravitation varies as 1/(distance squared), so don't make the mistake of calculating distance first and then squaring it! Use the formula for dist_squared above.

A similar but smaller gain can be realized when the field varies as a different power of distance. Some models of nuclear forces use a term proportional to distance to the sixth power. In this case we can take advantage of the equivalence pow(x, y) == pow(x**2, y/2) and calculate the field using pow(dist_squared, -3.0) instead of pow(dist, -6.0). On my machine, this substitution bought me 0.7 seconds out of 8.9 — a speedup of 8%. o

Thanks to Evan Manning <manning@alumni.caltech.edu> for contributing this tip.