2 CRs and their Cost Index

Before returning to the problem of simplifying CR expressions, let us briefly define the needed CR concepts. Our following definition of CR expressions follows the concepts introduced in [#!me:thesis!#] which are generalizations of the respective concepts used in earlier work on CRs (see, e.g., [#!us:issac94!#] or [#!me:hisc!#]).

Definition 1   Let ${\cal R}$ be a ring with identity. Let ${\cal R_F}$ be a set of symbols for allowable ${\cal R}^m \rightarrow {\cal R}$ functions and ${\cal X}$ be a set of allowable variables $\{x_1, x_2, \ldots, x_n\}$. The set ${\cal CR}$ of CR expressions over $({\cal R_F}, {\cal X})$ is the minimal set of terms such that

(i)

${\cal R} \subset {\cal CR}$,

(ii)

for any $x_k \in {\cal X}; \Phi_0, \Phi_1, \ldots, \Phi_l \in {\cal CR}; \odot_1, \ldots, \odot_l \in \{{\mbox{\texttt{+}}}, {\mbox{\texttt{*}}}\}$ the term $\{ \Phi_0, \odot_1, \Phi_1, \odot_2, \ldots, \odot_l, \Phi_l \}_{x_k} \in {\cal CR}$, and

(iii)

for any $f \in {\cal R_F}; \Psi_1, \Psi_2, \ldots, \Psi_{m} \in {\cal CR}$ the term $f \Psi_1 \Psi_2 \ldots \Psi_{m} \in {\cal CR}$

CR expressions of the form $\{ \Phi_0, \odot_1, \Phi_1, \odot_2, \ldots, \odot_l, \Phi_l \}_{x_k}$ are also called Chains of Recurrences (CRs).

Moreover, if $\Phi \in {\cal CR}$ then we define the value of $\Phi$, denoted by $V(\Phi)$, to be a function $V(\Phi): {\bf N}^n \rightarrow {\cal R}$ which is recursively defined by

$$\begin{array}{lc} V(\Phi)({\bf i}) \!\!\!\!&\!\!\!\! \mbox{Co... ...box{ } \Phi \!=\! f \Psi_1 \Psi_2 \ldots \Psi_{m} \end{array}$$

Since ${\cal R}$ is a ring with identity, the summation and product of elements of ${\cal R}$ is always well defined. If it is clear from the context, we will often simply write $\Phi$ instead of $V(\Phi)$ and ${\cal CR}$ instead of ${\cal CR}({\cal R_F}, {\cal X}_n)$. Furthermore, we define the set $X(\Phi)$ of variables contained in $\Phi$ by

$$X(\Phi) \!= \!\left\{\!\!\!\! \begin{array}{ll} {x_k} \cup \... ...{ if } \Phi \!=\! f \Psi_1 \ldots \Psi_{m} \end{array}\right.$$

and the dimension $D(\Phi)$ of $\Phi$ by the cardinality of $X(\Phi)$, i.e., $D(\Phi) = \vert X(\Phi)\vert$.
If $\Phi = \{ \Phi_0, \odot_1 \Phi_1, \odot_2, \ldots, \odot_l, \Phi_l\}_{x_k}$ is a CR, then we call

• $\Phi_0, \ldots, \Phi_l$ the coefficients of $\Phi$
• $l = L(\Phi)$ the length of $\Phi$
• $\Phi$ regular, if $x_k \not\in X(\Phi_0)\cup X(\Phi_1) \cup \ldots \cup X(\Phi_{l-1})$
• $\Phi$ simple, if $\Phi$ is regular and $x_k \not\in X(\Phi_{l})$
• $\Phi$ polynomial, if $\Phi$ is regular and $\odot_1= \cdots =\odot_l = {\mbox{\texttt{+}}}$
• $\Phi$ exponential, if $\Phi$ is regular and $\odot_1= \cdots =\odot_l = {\mbox{\texttt{*}}}$

and will frequently use the following abbreviations

• $\Phi$ for $\Phi({\bf i})$
• indexed lower-case Greek letters (like $\varphi_j$) for CR coefficients for which $x_k \not\in X(\Phi_k)$.
• $\varphi_j$ for $\varphi_k({\bf i})$
• $\{ \Phi_0, \odot_1, \ldots, \odot_l, \Phi_l\}$ and $\Phi(i)$ if $\Phi$ is a one - dimensional CR

In addition, we extend the concepts of regular, simple, and polynomial CRs to CR expressions, by calling a CR expressions $\Phi$ regular/simple/polynomial if all the CRs contained in $\Phi$ are regular/simple/polynomial and, for polynomial CR expressions, all the (function) symbols f_k contained in $\Phi$ are constants, or contained in $\{+, -, \cdot\}$.

The following definition of the Cost Index (CI) extends the previous definition given [#!us:issac94!#]: Instead of defining the CI as an operation count of the evaluation of one - dimensional CR expressions, we use a weighted operation count of the evaluation efficiency of multi - dimensional CR expressions.

Definition 2   Let $\Phi$ be a CR expression over ${\cal CR}({\cal R_F}, {\cal X}_n)$ and let $W: {\cal R_F} \rightarrow {\bf R}$ be a map which assigns each $f \in {\cal R_F}$ a real number (which is called the weight of f) such that W(f) = 0 if f is a constant and W(+) = 1 (where + is the symbol for addition). Furthermore, let ${\bf m} \in {\bf N}^n$ and $m = \prod_{i=1}^{n}m_i$. Then we recursively define the Cost Index (CI) of $\Phi$ by $CI(\Phi) =$


$\begin{array}{ll} 0 & \!\!\!\mbox{if } \Phi \in {\cal CR} \\ \displaystyle... ...Psi_i)} & \!\!\!\mbox{if } \Phi \!= \!f \; \Psi_1 \ldots \Psi_{m} \end{array}$

In other words, we may consider the CI of a CR expression as an approximate measure of the average time (w.r.t. one addition) spent in the inner-most loop of a CR evaluation.

If we assume that the execution times of the basic arithmetic operations (i.e., the operations computing the value of $f(r_1, \ldots, r_{m})$) were largely independent of their arguments, then we can assign a weight to each arithmetic operation such that it approximates the execution time of the operation relative to the speed of one addition. For example, for double floating point operations, we measured the following relative and averaged execution times.

 

Table: Measured average relative execution times of double operations on a SparcStationII and HP 9000/735

SparcStationII
add	mult	div	sqrt	exp	log	pow	sin	tan	asin	atan	sinh	tanh
1.0	1.1	3.1	22.3	26.5	20.3	77.5	21.3	27.1	32.7	38.8	25.8	33.1
HP 9000/735
add	mult	div	sqrt	exp	log	pow	sin	tan	asin	atan	sinh	tanh
1.0	1.0	3.3	5.9	9.3	25.1	124.0	9.9	26.3	30.6	34.1	33.14	38.1

 

As the table indicates, the relative weights may vary greatly from platform to platform.

If we furthermore assume that the execution time of the evaluation algorithm considered is directly proportional to the weighted operation count of the basic arithmetic operations, then we can use the Cost Index of a CR expression as a relative measure of its evaluation efficiency.

However, supposing that the execution times of the basic arithmetic operations are largely independent of their arguments is a strong assumption. First, it is definitely not true for arbitrary precision arithmetic since the execution times of arbitrary precision operations clearly depend on the size of the operands. Secondly, even in fixed precision arithmetic the execution times of most basic arithmetic operations are not truly independent of their arguments. For example, consider the operation pow(x,y). If y is an integer, then we do not need to use a numeric approximation to obtain the value of x^y, but can use a repeated squaring procedure (see [#!knuth:v2!#], Section 3.4) which requires at most $2\lfloor \log y \rfloor$ multiplications and one division.

Unfortunately, there seems to be no realistic alternative to this assumption, since we can not exactly predict the operands of the basic arithmetic operations at simplification time. Therefore, we can only try to approximate the real execution times as much as possible, by

1.

estimating the size of the operands for arbitrary precision arithmetics

2.

using an average of the execution times for numeric approximations

3.

approximating the execution time of special cases (like xⁿ, where it is known at simplification time that n is an integer) by a separate estimate