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 lowercase 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 f_{k} 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 innermost 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
x^{y}, 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 x^{n},
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 