Does the order of floating-point addition matter for accurate accumulation?

Floating-Point Accumulation: Precision and Ordering

When accumulating floating-point numbers, the order in which they are added can have a significant impact on the precision of the result.

Ascending Order for Improved Precision

Your intuition is correct. Adding numbers in ascending order typically improves precision. Consider a scenario with single-precision floats:

• An extreme case: 1 billion values of 1 / (1 billion), plus one value of 1.

If the 1 is added first, the sum becomes 1 due to loss of precision. Adding the other values has no impact.

If the small values are added first, they accumulate somewhat, but after a certain point, they also lose precision.

Negative Values and Inaccuracy

However, ascending order can become inadequate if negative numbers are involved. Consider the following values: 1, -1, 1 billionth.

Only two orders produce the correct result (1 billionth): 1, -1, 1 billionth or -1, 1, 1 billionth. For the remaining orders, the result is inaccurate.

Advanced Accumulation Techniques

For extreme cases, more advanced techniques are necessary:

• Running Totals by Magnitude: Divide the values into groups based on magnitude and calculate totals for each group. Combine these totals in ascending order, effectively using an arbitrary-precision type.

Relevance to Real-World Programming

While this issue may not seem directly relevant to practical programming, it can arise in specific scenarios:

• When accumulating small, insignificant values and a few large values, precision may be compromised.
• When dealing with heavy tails (numerous small values that may not individually affect the sum) or loss of precision due to additive combinations of small values.

The above is the detailed content of Does the order of floating-point addition matter for accurate accumulation?. For more information, please follow other related articles on the PHP Chinese website!