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.

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**

This document is best viewed as n-body.pdf because the translation to html was buggy.