# example of straight-line program

SLPs can be used to shorten computations of algebraic expressions.

For example: The product $5^{19}$ may be evaluated in fewer than 19 multiplication.

Let $f_{0}(x)=x$ and $f_{i+1}(x)=f_{i}(x)\cdot f_{i}(x)$, for $i\in\mathbb{N}$. Evidently

 $f_{i}(x)=x^{2^{i}},\qquad\forall i\in\mathbb{N}.$

However, we do not evaluate $f_{i}(5)$ as $5^{i}$. For instance, to compute $f_{3}(5)=5^{8}$ we follow the program. Expand the first the expression from the left first until we reach an $f_{0}(x)$ term:

 $\displaystyle f_{3}(5)$ $\displaystyle=$ $\displaystyle f_{2}(5)\cdot f_{2}(5)$ $\displaystyle=$ $\displaystyle(f_{1}(5)\cdot f_{1}(5))\cdot f_{2}(5)$ $\displaystyle=$ $\displaystyle((f_{0}(5)\cdot f_{0}(5))\cdot f_{1}(5))\cdot f_{2}(5).$

Now evaluate the terminal parts and store all the intermediate results:

 $\displaystyle f_{0}(5)$ $\displaystyle=$ $\displaystyle 5,$ $\displaystyle f_{1}(5)$ $\displaystyle=$ $\displaystyle f_{0}(5)\cdot f_{0}(5)=5\cdot 5=25,$ $\displaystyle f_{2}(5)$ $\displaystyle=$ $\displaystyle f_{1}(5)\cdot f_{1}(5)=25\cdot 25=625,\textnormal{ and }$ $\displaystyle f_{3}(5)$ $\displaystyle=$ $\displaystyle 625\cdot 625=390625.$

The total number of multiplications here was 3, rather than 8.

Then $x^{19}$ can be encoded as an SLP using the binary number for 19.

First, write 19 in binary (base 2):

 $19=1\cdot 2^{4}+0\cdot 2^{3}+0\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0},$

or rather $10011$ in the usual binary notation.

 $\begin{split}\displaystyle\mathcal{F}(x)&\displaystyle=f_{4}(x)^{1}\cdot f_{3}% (x)^{0}\cdot f_{2}(x)^{0}\cdot f_{1}(x)^{1}\cdot f_{0}(x)^{1}\\ &\displaystyle=f_{4}(x)\cdot f_{1}(x)\cdot f_{0}(x).\end{split}$

Remark. To evaluate this SLP we had to store intermediate values that were ultimately not part of the final answer. In this example the final answer was much larger than the intermediate steps and so we are free to assume that any memory used in the process was far less than what was required for the final outcome. However, it is entirely possible that evaluating an SLP will at times use far more memory than required by the final product and may therefore be infeasible.

Title example of straight-line program ExampleOfStraightlineProgram 2013-03-22 16:16:18 2013-03-22 16:16:18 Algeboy (12884) Algeboy (12884) 7 Algeboy (12884) Example msc 20A05 msc 20-00 msc 08A99