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}$ wefollow the program. Expand the first the expression from the left first until wereach 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 thatwere ultimately not part of the final answer. In this example the final answerwas much larger than the intermediate steps and so we are free to assume thatany memory used in the process was far less than what was required for the finaloutcome. However, it is entirely possible that evaluating an SLP will at timesuse far more memory than required by the final product and may therefore beinfeasible.