example of straight-line program

SLPs can be used to shorten computations of algebraic expressions.

For example: The product 519 may be evaluated in fewer than 19 multiplication.

Let f0(x)=x and fi+1(x)=fi(x)fi(x), for i. Evidently


However, we do not evaluate fi(5) as 5i. For instance, to compute f3(5)=58 we follow the program. Expand the first the expression from the left first until we reach an f0(x) term:

f3(5) = f2(5)f2(5)
= (f1(5)f1(5))f2(5)
= ((f0(5)f0(5))f1(5))f2(5).

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

f0(5) = 5,
f1(5) = f0(5)f0(5)=55=25,
f2(5) = f1(5)f1(5)=2525=625, and
f3(5) = 625625=390625.

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

Then x19 can be encoded as an SLP using the binary number for 19.

First, write 19 in binary (base 2):


or rather 10011 in the usual binary notation.


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