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