Information Technology Reference
In-Depth Information
Saving Arithmetic Operations
Examining the algorithm above, we see that the factor
h
appears in all terms. This
is perhaps even more obvious from the mathematical formula (6.1). We can avoid
n
multiplications by
h
through a factorization of (6.1). We can also be more careful
with the factor
1=2
; division is often slower than multiplication (perhaps by a factor
of 4, depending on the hardware). A computationally more efficient version of (6.1)
therefore reads
Z
b
(
)
0:5.f .a/C f.b//C
n
X
iD1
hD
b a
n
:
f.x/dx h
f.aC ih/
;
(6.2)
a
To really see why (6.2) is more efficient than (6.1) we can count the number of oper-
ations: additions, subtractions, multiplications, divisions, and
f.x/
function calls.
We fi n d t h a t ( 6.1)has
2n
multiplications,
2n
additions, three divisions, and
n C 1
function calls. The formula in (6.2) implies
nC1
multiplications,
2n
additions, one
division, and
nC1
function calls. If
f.x/
is a complicated function requiring many
arithmetic operations, such as sin
x
or
e
x
, evaluation of
f
will dominate the work
of the algorithm. In that case there are minor differences between (6.1)and(6.2);
the total work is well approximated by
n C 1
calls to the function
f
.
It is common to introduce
floating-point operation
(FLOP) as a synonym for
addition, subtraction, multiplication, or division. However, this can be mislead-
ing on some hardware where division is significantly slower than the three other
operations. Counting one multiplication/division and one addition/subtraction as a
single floating-point operation is also common, because modern CPUs often have
the possibility of running pieces of a compound expression in parallel.
We can avoid
n1
multiplications
ih
in (6.2) by incrementing the function argu-
ment by
h
in each pass in the for loop used to compute the sum. The mathematical
pseudo code incorporating this trick in (6.2) is expressed in Algorithm
6.2
. The total
work is now one multiplication,
2n
additions, one division, and
nC1
function calls.
Algorithm 6.2
Optimized Trapezoidal Integration.
trapezoidal
(
a
,
b
,
f
,
n
)
h D
ba
n
s D 0
x D a
for
i D 1;:::;n1
x x C h
s s Cf.x/
end for
s s C 0:5.f .a/C f.b//
s hs
return
s
