# 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}},\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:

${f}_{3}(5)$ | $=$ | ${f}_{2}(5)\cdot {f}_{2}(5)$ | ||

$=$ | $({f}_{1}(5)\cdot {f}_{1}(5))\cdot {f}_{2}(5)$ | |||

$=$ | $(({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:

${f}_{0}(5)$ | $=$ | $5,$ | ||

${f}_{1}(5)$ | $=$ | ${f}_{0}(5)\cdot {f}_{0}(5)=5\cdot 5=25,$ | ||

${f}_{2}(5)$ | $=$ | ${f}_{1}(5)\cdot {f}_{1}(5)=25\cdot 25=625,\text{and}$ | ||

${f}_{3}(5)$ | $=$ | $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{array}{cc}\hfill \mathcal{F}(x)& ={f}_{4}{(x)}^{1}\cdot {f}_{3}{(x)}^{0}\cdot {f}_{2}{(x)}^{0}\cdot {f}_{1}{(x)}^{1}\cdot {f}_{0}{(x)}^{1}\hfill \\ & ={f}_{4}(x)\cdot {f}_{1}(x)\cdot {f}_{0}(x).\hfill \end{array}$$ |

*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 |
---|---|

Canonical name | ExampleOfStraightlineProgram |

Date of creation | 2013-03-22 16:16:18 |

Last modified on | 2013-03-22 16:16:18 |

Owner | Algeboy (12884) |

Last modified by | Algeboy (12884) |

Numerical id | 7 |

Author | Algeboy (12884) |

Entry type | Example |

Classification | msc 20A05 |

Classification | msc 20-00 |

Classification | msc 08A99 |