Next: 3 Cost Index and Up: Effective Simplification of CR expressions Previous: 1 Introduction

# 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 be a ring with identity. Let be a set of symbols for allowable functions and be a set of allowable variables . The set of CR expressions over is the minimal set of terms such that
(i)
,
(ii)
for any the term , and
(iii)
for any the term
CR expressions of the form are also called Chains of Recurrences (CRs).

Moreover, if then we define the value of , denoted by , to be a function which is recursively defined by

Since is a ring with identity, the summation and product of elements of is always well defined. If it is clear from the context, we will often simply write instead of and instead of . Furthermore, we define the set of variables contained in by

and the dimension of by the cardinality of , i.e., .
If is a CR, then we call
• the coefficients of
• the length of
• regular, if
• simple, if is regular and
• polynomial, if is regular and
• exponential, if is regular and
and will frequently use the following abbreviations
• for
• indexed lower-case Greek letters (like ) for CR coefficients for which .
• for
• and if 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 regular/simple/polynomial if all the CRs contained in are regular/simple/polynomial and, for polynomial CR expressions, all the (function) symbols fk contained in are constants, or contained in .

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 be a CR expression over and let be a map which assigns each 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 and . Then we recursively define the Cost Index (CI) of by

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 ) 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 xy, but can use a repeated squaring procedure (see [#!knuth:v2!#], Section 3.4) which requires at most 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 xn, where it is known at simplification time that n is an integer) by a separate estimate

Next: 3 Cost Index and Up: Effective Simplification of CR expressions Previous: 1 Introduction
| ZCA Home | Reports |