HP Labs Technical Reports

Implicit Computation: an Output-Polynomial Algorithm for Evaluating Straight-Line Programs

Shahoumian, Troy A.

HPL-1999-25

Keyword(s): theory of computation; randomized algorithms; straight-line programs; output-polynomial algorithms

Abstract: Inputless straight-line programs using addition, subtraction and multiplication are considered. An output-polynomial algorithm is given for computing the output of such a program. The program runs in time polynomial in the length of the program and the length of its output. As a consequence, even if intermediate results are exponentially longer than the program, the output can be computed efficiently when the output's size is small. This algorithm also applies to programs with integral inputs if the size of the inputs are considered to be part of the program's size.

6 Pages

Back to Index