6.4.1 Efficiency issues

Don't worry about efficiency until you have the algorithm working. Once you have the algorithm working, you can start to consider these issues. On a powerful processor, you may need to worry much about code efficiency. However, with an 8-bit processor that has no division instructions, some hassle in optimization can mean dramatic improvement of performance.

Let us review algorithm 1. $\frac{v^2}{2{a_\mathrm{max}}} \ge D$ is a fairly expensive operation. First, $v^2$ involves multiplication. The killer part is division by $2{a_\mathrm{max}}$. Division is a bit more expensive than multiplication.

Let's deal with one problem at a time. To avoid division, we can change the comparison as follows:

$$\frac{v^2}{2{a_\mathrm{max}}} \ge D \Rightarrow$$ (6.7)

$$v^2 \ge 2D{a_\mathrm{max}}$$ (6.8)

This is true because ${a_\mathrm{max}}$ is a positive quantity.

But, doesn't this still involves two multiplications in $2D{a_\mathrm{max}}$?

In general, the answer is yes. If ${a_\mathrm{max}}$ is a constant, then we can roll $2{a_\mathrm{max}}$ into a single constant to get rid of one multiplication. $D$ is a variable, so we cannot roll this into a constant.

However, we can still do some tricks to avoid having to multiply $D$ to $2{a_\mathrm{max}}$ every time. Remember what $D$ represents: it is the number of steps to perform. This means most of the time, $D$ is incremented or decremented by 1. This is useful, because now we can use a variable for a scaled $D$. Whenever we decrement 1 from $D$, we subtract $2{a_\mathrm{max}}$ from the scaled version. Note that we still need to multiply when we reset $D$ to an arbitrary number.

How about the computation of $v^2$? It certainly appear that we cannot easily get rid of the multiplication here.

Once again, think of what $v$ represents. This is the frequency of stepping ${f_{\mathrm{step}}}$. Most of the time, if not all, ${f_{\mathrm{step}}}$ is only incremented or decremented by 1 (in the acceleration logic). This is a very useful fact because we can now eliminate multiplication.

If we know $(v-1)^2$, we can compute $v^2$ as follows:

$$(v-1)^2 = v^2 -2v + 1$$ (6.9)

$$v^2 = (v-1)^2 + 2v - 1$$ (6.10)

$$= (v-1)^2 + v + v - 1$$ (6.11)

See, no multiplications! Using a similar technique, you can also derive $(v-1)^2$ using no multiplication from $v^2$.

Although this optimization can save you a lot of processing time, you do need to track quite a few more properties in the structures. As a result, I recommend the use of abstract data types so that you use a single function to increment/decrement $v$. This same function is also responsible to track a separate variable for $v^2$. The same applies to $D$ and its scaled version.