example of straight-line program
SLPs can be used to shorten computations of algebraic expressions.
For example: The product may be evaluated in fewer than 19 multiplication.
Let and , for . Evidently
However, we do not evaluate as . For instance, to compute we follow the program. Expand the first the expression from the left first until we reach an term:
Now evaluate the terminal parts and store all the intermediate results:
The total number of multiplications here was 3, rather than 8.
Then can be encoded as an SLP using the binary number for 19.
First, write 19 in binary (base 2):
or rather 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|
|Date of creation||2013-03-22 16:16:18|
|Last modified on||2013-03-22 16:16:18|
|Last modified by||Algeboy (12884)|