5 Examples

We conclude this section by illustrating the suggested heuristic simplification procedures. In Table 3 we give examples which are very similar to those used in [#!me:sigsam!#] to measure and demosntrate the evaluation speed of our implementation of the CR method.

  

Table 3: Examples of simplifications of CR expressions

Column 1 shows the elementary expressions we used as input and column 2 shows their respective CIs (by extending the definition of the CI for CR expressions in the obvious way to elementary expressions). Column 3 shows the CR expression obtained from the CR construction and heuristic simplification, and column 4 shows their respective CIs. We assumed that we work over a regular grid of 10,000 or $100\times 100$ evaluation points and that we used the weights obtained for a Sun-SparcStationII of table 2.

We furthermore assumed that expressions of the form xⁿ were always evaluated using the <tex2html_verb_mark>57<tex2html_verb_mark> operation for elementary expressions and using a repeated squaring procedure for CR expressions.

For row 2 we used the expanded form of (x-1)¹⁰+1 as input, i.e. $x^{10} - 10 x^9 + {10 \choose 2} x^8 \cdots - 10x$ and for row 3 we used the Horner representation of (x-1)¹⁰+1 as input, i.e. $(\ldots((x -10)x + {10 \choose 2})x \ldots -10)x$. Likewise, for rows 5 and 6, we used the expanded input ${y}^{3}{x}^{4}-4{y}^{3}{x}^{3}+3{y}^{2}{x}^{4}+ \cdots +6{x}^{2}+3y-4x+2$ and the Horner representation $2+ (-4+ (6+ (-4+x )x )x )x+ (\ldots + (\ldots + (\ldots + (\ldots + \ldots x)y)y)y$.

All CR expressions in column 3 are optimal, i.e., the heuristic simplification algorithm returned the same results as the exhaustive search algorithms. This illustrates that especially for relatively simple examples (like the ones above), the results of the heuristic simplification algorithm are usually as good as those from the exhaustive search algorithm (only much more efficient).

Notice also that the CR method does not result in a decrease of the CI for the example in row 9, i.e., the input expression does not allow CR simplifications.