 Efficient Force Function Evaluation Methods
June 9, 1996
45
As a general rule, if the computer has to add up a long list of numbers, the pro-
grammer should make sure that the numbers with the smallest absolute value are added
together first. There shouldn't be a running total kept, instead when two numbers are
added together, the result should just be put back into the list and the two numbers should
be deleted. The computer should then try to add the next two smallest numbers together,
and the process repeats until there is just one number left in the list.
The result is that even the "simple" particle-particle evaluation method must be
made more complicated than it might be first expected to be. This additional sorting of the
terms in the evaluation of the force function would make the Particle-Particle method an
method. Most of the more sophisticated evaluation methods do something akin
to a sort on the stars and end up adding the forces in such a way that these rounding errors
are reduced, although they do that more for reasons of efficiency than for accuracy.
4.2 Distant Stars Can Be Grouped Together
Consider the case shown in FIGURE 24., instead of calculating the force to each
star in a distant cluster of stars, it is much more efficient to calculate the center of mass of
the cluster and apply the force function to the center of mass. Since the calculation of the
center of mass only requires summing the positions and masses, and doesn't require the
expensive division and square root evaluation, this can save a lot of CPU time. It can save
even more if this same center of mass information can be used for other stars that are also
a long ways away from the cluster.
Replacing the cluster of stars with just the center of mass is only an approximation
though, a certain amount of error will be created by doing this. The more distant the
cluster and the more tightly packed the cluster is, the less the error will be. Deciding what
should be considered "distant" and how tightly packet a set of stars is before it is consid-
ered a cluster are very important details that must be considered by any method that uses
this technique. The error created by cluster the stars is somewhat offset by the reduced
rounding error, so it is possible that this technique can actually increase the accuracy of
f()
.
Sources: (18:4-6)
O n
2
n
log
(
)
Center of Mass
d
cm
Star
FIGURE 24. A Star and a distant cluster of stars