javaLover javaLover - 1 month ago 7
C++ Question

precision error in summation addition/subtraction (of mass)

How to cache summation of all floating point values in a certain list in a way that can avoid precision error?

Example



I have mass of many physic shapes :
m1
,
m2
,
m3
,...

Those shapes join together into a big body with mass
M
=
m1
+
m2
+
m3
+....

I have to request mass of the big body frequently, so I cache
M
.

Now, I have responsibility to update
M
as appropriate.

When I add a shape with mass =
mi
:-

M += mi;


When I remove a shape with mass =
mi
:-

M -= mi;


Problem



After program add/remove shapes for some time,

M
become far and far away from the correct summation. (
m1
+
m2
+
m3
+....)

As a result, my program finally executes abnormally.

No doubt, the symptom will show faster if mass ratio of some pair
mi
and
mj
is very low or very high.

Question



How to professionally alleviate this numerical issue?

In other words :-

Should I never cache the summation,
M
, in the first place?

Should I recalculate the summation every time (in a brute force style) after a small shape was added/removed, or (may be) just before some callers request
M
?

I have read https://en.wikipedia.org/wiki/Kahan_summation_algorithm, it can only postpone the issue.

Answer

If you know the range of masses, you could consider using fixed point arithmetic, and using int64_t which will give you 19.5 digits of accuracy, and as long as you never overflow, summation and subtraction can be done in any order and always be precise.

Comments