Information Technology Reference
In-Depth Information
Algorithm 6.5
Simpson's Rule with One Loop.
Simpson
(
a
,
b
,
f
,
n
)
h D
ba
n
s
1
D 0
s
2
D 0
for
i D 1;:::;n
if
i<n
x D a C
ih
s
1
s
1
C f.x/
end if
x D a C .i
2
/h
s
2
s
2
C f.x/
end for
s
6
h.f .a/ C f.b/C 2s
1
C 4s
2
/
return
s
Compiler Optimization Issues
Why do we split the computations in Simpson's rule into two sums, expressed as
two loops in Algorithm
6.4
? We could get away with one loop as demonstrated in
Algorithm
6.5
. The single loop now needs an if-test to avoid adding contributions
to
s
1
when
i D n
. Unfortunately, if-tests inside loops tend to reduce the com-
piler's possibilities for optimization. Two plain loops are therefore normally much
more efficient than one loop with an if-test. The loss of speed introduced by if-tests
inside loops depends on the actual code, the programming language, the compiler,
problem-dependent parameters, and so on. In the present case, one can argue that
function calls also reduce compiler optimizations in the same way as an if-test, so
Algorithm
6.5
may not be much less efficient than Algorithm
6.4
. However, we can
hardly avoid calling
f.x/
in numerical integration, but the if-test is easy to avoid.
We should mention here that one way to avoid the if-test in Algorithm
6.5
is to
remove the test and simply subtract the extra term
f.aC
nh
/
from
s
1
.
Another aspect of the current discussion is that some smart compilers will avoid
function calls as a part of the optimization; the body of the code for
f.x/
is inserted
directly in the loop as an expression. For example, if we integrate
f.x/D x
sin
x
,a
smart compiler can translate the code, e.g., in the following way:
...
for
i D 1;:::;n
...
x D a C.i
1
2
/h
s
2
s
2
C1Cx
sin
x
...