Tensions in Practice: A fixed accumulation order in tension with regrouping freedom¶
Finite precision · four ordered values
Add the ordered values 1000, 1, 1 and −1000. In exact arithmetic their sum is 2. In this toy decimal system every addition rounds to three significant digits. A left fold returns 0; pairing the first two and last two values returns 1. The second grouping permits two initial additions at once, but regrouping is no longer an identity-preserving transformation of the computed result.
Keep one accumulation contract
Use the same simple serial fold and its reproducible rounding behavior.
Allow parallel grouping
Combine independent pairs simultaneously when the numerical contract permits the resulting variation.
Why these aims pull against each other
The intended real-number operation associates; the implemented rounded operation does not. Removing serial dependencies can change intermediate rounding and the final answer.
Choose an arrangement to see what changes and what remains difficult.
Finite illustrative comparisons. Text states carry the meaning; color is not a measured score or universal preference.
What this choice protects
What it costs
When it fits
Compare the arrangements
Left fold
Evaluate ((1000+1)+1)−1000, rounding after every addition to three significant decimal digits.
| Additions | Outputs | |
|---|---|---|
| Round 1 | 1000 + 1 | 1000 |
| Round 2 | 1000 + 1 | 1000 |
| Round 3 | 1000 − 1000 | 0 |
| Final | Exact sum: 2 | Computed: 0 |
- What it protects
- A fixed left-fold rule needs one running accumulator and preserves this specified result across regrouping choices by forbidding them.
- What it costs
- The three additions are dependent, and the two small contributions are lost in this example.
- When it fits
- A fixed serial accumulation contract matters and its numerical error is acceptable for the task.
Illustration note: Editorial arithmetic, not IEEE-754 emulation: round to nearest, ties to even, after each addition. No shown operation is a tie. The task is stipulated to allow absolute error up to 2 for this finite input only.
Allow pairs
Choose (1000+1)+(1−1000), with the same rounding rule and operand order.
| Additions | Outputs | |
|---|---|---|
| Round 1 | Two pairs1000 + 1; 1 − 1000 | 1000; −999 |
| Round 2 | 1000 − 999 | 1 |
| Round 3 | No work | Done |
| Final | Exact sum: 2 | Computed: 1 |
- What it protects
- With two addition workers, the dependency depth is two rounds instead of three.
- What it costs
- Extra parallel resources and partial results are needed; this result differs from the left-fold contract, and arbitrary regrouping cannot promise that contract’s answer.
- When it fits
- The numerical contract explicitly allows this example’s error and grouping variation, and parallel overhead is worthwhile.
Illustration note: The balanced schedule is one allowed grouping, not a proof that all groupings meet an error budget. It happens to be closer here; regrouping is not a universal accuracy improvement.
What this illustration does—and does not—establish
Associativity: Associativity in theory versus floating-point in practice supplies rounding-sensitive grouping. The four-value decimal example exposes actual intermediate values without changing operand order.
- Both shown computations follow the same declared arithmetic correctly; neither equals the exact sum.
- A fixed balanced tree can also be reproducible. The conflict is freedom to change grouping versus preserving a particular accumulation contract.
- Rounds are dependency levels under assumed workers, not measured elapsed time.
- Compensated or higher-precision summation is outside this two-option illustration.
Source entries
Associativity
Associativity: Associativity in theory versus floating-point in practice supplies the conflict examined here.
Associativity in theory versus floating-point in practice
Real-valued arithmetic is associative mathematically ($a + b + c$ is unambiguous); IEEE-754 floating-point arithmetic is *not* associative due to rounding — $(a + b) + c$ may differ from $a + (b + c)$ in the last bits.
Structural Tensions
Associative operations support flexible grouping, enabling parallel reduction and optimization.