iTranslated by AI

The content below is an AI-generated translation. This is an experimental feature, and may contain errors. View original article
⚔️

C# Quest: Defining Equality and the Challenge of Precision Errors (Part 2)

に公開
C#
誤差
浮動小数点
精度
有効桁
idea

Read the first part here

Chapter 5: The Wall of Precision

The traveler climbed the creaking stairs, heading to the second floor.
Beyond the door awaited a vessel without a visible bottom.

The charm was crafted.
The trap of comparison would no longer claim them.

...Or so they thought.

But deep within the mansion, the traveler encountered a strange calculation.

5.1 The "1" That Won't Aggregate

The traveler stopped in front of the vase.

"Small numbers get swallowed."
They had thought that was just a metaphor.

But here—in this mansion, it was no mere metaphor.

double a = 1e16;
double b = a + 1.0d;

Console.WriteLine(a.ToString("G17"));
Console.WriteLine(b.ToString("G17"));
Console.WriteLine(a == b ? "equal" : "NOT equal");
Console.WriteLine((b - a).ToString("G17"));

Right before the traveler's eyes, this happened:

a (G17): 10000000000000000
b (G17): 10000000000000000
a==b   : equal
delta  : 0

The traveler gasped.

"...I added 1, yet it didn't increase?"

Mathematically, it certainly should have increased.
But in this vase, that "1" couldn't reach the markings.

The single drop that should have been added was never recorded.

5.2 The Ceiling of Significant Digits

The traveler peered into the vase.
The bottom was nowhere to be seen. It was infinitely deep.

"If it can hold an infinite amount, surely it can mark an infinite amount."

The moment they thought that, the traveler realized:
Not overflowing and being able to register every increment are different things.

The markings on this vase are not infinite.

double does not store real numbers as they are.
It represents a "nearby value" using a limited number of bits.

In other words—

There is a limit to the precision that can be expressed.

This limit is what we call significant digits.

The precision of double is, roughly speaking, about 15 to 16 digits.
Any finer detail beyond that cannot be marked.

If truly large values dominate the scene,
smaller numbers may not reach the markings and won't remain in the result.
That is the nature of significant digits.

The traveler understood.

The enemy on this continent is not the correctness of the calculations.
What stood in their way first was the vessel of precision.

5.2.1 Countermeasures: If You Cannot Mark It, Change How You Mark It

The traveler organized their countermeasures:

  • Change the order of addition (add from smallest to largest)
    → Do not collide small values with a large sum.
  • Subtract a reference point (make the difference the protagonist)
    → Accumulate the "amount of change" rather than the absolute value.
  • Use integers if possible (for counts, iterations, sequences, etc.)
    → Choose expressions that match the "meaning of the number."

In this mansion, numbers do not become infinitely granular.
If that is the case, the only choice is to change how you fight.

Note: Changing the order can change the result (→§5.3).

5.2.2 Lost Significant Digits Cannot Be Recovered

The traveler noticed another trap.

There was a smaller vessel with coarser markings in this mansion: float.

If double is a vessel with 15-16 digits of precision, float can only mark about 7 digits at most.

And what is terrifying is this:
Once precision is lost to float, it does not return.

Even if you convert it to double later, you cannot rest easy.
Just making the vessel larger does not make the markings finer.

The traveler tested this:

double da = 12345678.123456789;
float  f  = (float)da;
double db = f;

Console.WriteLine($"da (G17): {da.ToString("G17")}");
Console.WriteLine($"db (G17): {db.ToString("G17")}");
Console.WriteLine($"da==db  : {(da == db ? "equal" : "NOT equal")}");
Console.WriteLine($"diff    : {Math.Abs(da - db).ToString("G17")}");
Console.WriteLine($"f (G9)  : {f.ToString("G9")}");

The result was this:

da (G17): 12345678.123456789
db (G17): 12345678
da==db  : NOT equal
diff    : 0.12345678918063641
f (G9)  : 12345678

The display shows more digits as expected of double.
But—that doesn't mean it was "marked" correctly.

float can only mark about 7 digits.
Therefore, everything from the 8th digit onward is unreliable.

The traveler understood. This was not a calculation issue.

The vessel itself had changed.

5.2.3 Mixed Precision (Rounding to the Lowest Common Denominator)

An important concept regarding significant digits is this:

When values with different significant digits are mixed, the reliability of the result matches the one with the fewest significant digits.

For example, consider the following addition:

  0.123456789012345
+)0.1111111
-------------------
  0.234567889012345

Here, 0.1111111 is only known up to the 7th decimal place.
In other words, the 8th decimal place and beyond are unknown.

When you add them in this state, the visual result shows fine digits.
However—the 8th decimal place and beyond cannot be guaranteed.

Therefore, the only "valid data" in this calculation extends to 0.2345678.

Since the values are certain only up to the 7th place, the result cannot be guaranteed beyond the 7th place either.

Even if there are high-precision values present, if lower-precision ones are mixed in, the result aligns with the lower precision.

When float is involved, this phenomenon actually occurs in real code.

5.3 Changing the Order of Operations Changes the Result (Incompatibility)

The traveler pondered:

"If so, I should devise the order. If I mix them before they get swallowed—"

However, that idea immediately hit another wall.

Changing the order can change the result.

The traveler tested this:

double a = 1e16;
double b = -1e16;
double c = 1;

Console.WriteLine((a + b) + c);
Console.WriteLine(a + (b + c));

The results are not necessarily the same.

  • (a + b) + c can result in 1.
  • a + (b + c) can result in 0.

The traveler caught their breath. Even though the same three numbers are being added.

In other words—
Even if you think you have "improved" the formula, it can become incompatible.

5.3.1 "Optimization" Can Change Numerical Results

What is even more troublesome is that the order may change unintentionally.

  • You changed how the formula is grouped during refactoring.
  • You accelerated the aggregation process, changing the order of addition.
  • The order of addition is no longer guaranteed due to parallelization or SIMD.

All of these have the potential to change the result.

The traveler realized:

"Making it faster" is sometimes incompatible with "protecting the same result."

Therefore, if you are going to change the order, there is something you must decide first:

Where do you draw the line for what is considered 'the same'?

Column: Design as Deciding the Order

If a truly large value dominates, small numbers may not reach the markings and might not remain in the result. That is the concept of significant digits.

Therefore, "which order to perform the calculation" is not just a preference. It is design.

If you know the range (scale) of the values, you must take them into account when deciding the order of calculation.

5.4 The Method to Overcome the Wall of Precision

There is no magic to break the wall of precision. However, there are ways to walk without hitting it.

  • Change the units (mm to μm, Yen to Sen, etc.)
  • Align the scales (do not mix values that are too large and too small)
  • Fix the order of addition (for operations requiring compatibility)
  • Use integers if possible (for counts, number of times, serial numbers, etc.)

The traveler learned this.

What they fought in this chapter was precision.

But—
The enemy does not end here.

Chapter 6: Errors Multiply

Even after crossing the infinite vessel, the mansion did not end. In the depths of the second floor, a quieter room remained.

There is no sound.
There is no wind.
Yet—the floor creaks, just slightly.

The traveler realizes.

There are no traps here.
There are no visible enemies.

Yet, it is being chipped away, surely and steadily.

6.1 Rounding Errors Always Occur

The traveler lined up the same numbers on the desk.

double x = 0.1;
double y = 0.2;
double z = x + y;

Console.WriteLine(z.ToString("G17"));
Console.WriteLine(z == 0.3 ? "equal" : "NOT equal");

The result can be like this:

  • 0.30000000000000004
  • And NOT equal

The traveler was no longer surprised. As learned in Chapter 5.

double is not the real number itself.
It marks a nearby value on a limited scale.

Therefore—

Rounding always occurs

What is important here is not "whether rounding occurs" or not.

It is how much it occurs.

6.2 Cumulative Error (Addition and Iterative Calculations)

The horror of this room begins quietly.

A single deviation is small.
It is invisible unless you strain your eyes.

But—it piles up.

The traveler tried this:

double sum = 0.0;

for (int i = 0; i < 10; i++)
{
    sum += 0.1;
}

Console.WriteLine(sum.ToString("G17"));
Console.WriteLine(sum == 1.0 ? "equal" : "NOT equal");

The result can be like this:

  • 0.99999999999999989
  • And NOT equal

The traveler understood.

An error is not an "enemy to be defeated in one blow."
It multiplies.

Additions.
Iterative calculations.
Loops.
Aggregation.

The longer the processing, the more the discrepancy grows while slightly changing its shape.

6.3 The Secret Technique to Suppress Errors

At the back of the room, there were characters carved into the wall. It was something left behind by someone who had fought here before.

Errors cannot be erased.
But their multiplication can be stopped.

(1) Fix the addition order (Protect compatibility)

If you need the "same result" for aggregation or verification, aligning the order is the first step.

  • Order changes due to parallelization
  • Order changes due to SIMD
  • Order changes due to implementation changes

In this mansion, just changing the order changes the result.
Therefore, the order becomes part of the specification.

(2) Align the scales (Align digits before calculating)

If you mix large and small numbers, the small numbers are easily chipped away.

Change units.
Subtract a reference point.
Use the difference from the average.

Align the playing field before the "scale" goes wild.

(3) The concept of compensated summation (Kahan)

The traveler found a strange note in a desk drawer.

Keep the lost parts separately

With just that, the multiplication can sometimes be suppressed.

You don't need to memorize the detailed implementation. Just the name is enough.

Kahan compensation summation.

A technique to "pick up the fragments that fall off during every addition."

(4) Choose decimal (Only when necessary)

There are other vessels in this world. If you need "decimal accuracy" like for monetary amounts, it is worth choosing.

However, it is not a panacea.
It is heavy. It is slow. It is handled differently.

Therefore—
Only use it when necessary.

The traveler engraved this secret technique into their heart.

6.4 Final Battle: The Meaning of the Engraving

The traveler looked up at the writing on the wall once more.

Expect errors, and tolerate them.
If you cannot tolerate them, pay the price in effort.

At first, it looked like just an aphorism. But now, they understood.

The enemy in this room is invisible.
You cannot cut it.
You cannot defeat it.

Even so—it increases.

The traveler faced the desk. They performed the same calculation all over again.

But this time,
while picking up the fallen fragments.

6.4.1 If you can tolerate it, do so

Errors are not "bugs."
They are a specification of this world.

So first, think about this:

  • How much deviation can you tolerate? (Tolerance range)
  • How far must they match? (Compatibility)

If you can tolerate it, then that is fine. That is the strongest position.

6.4.2 If you cannot tolerate it, pay the price (Compensated summation)

However, there are times when you simply cannot tolerate it.

  • Discrepancies increase in long iterative calculations
  • Too many additions
  • Verification requires "exact equality"

In such cases, pay the price in effort.

The traveler found an old note in the drawer.

Keep the lost parts separately

That was—compensated summation (Kahan).

6.4.3 Kahan compensated summation (with explanatory comments)

// Kahan summation
// Continues to pick up "fractions lost due to rounding" in a separate variable to suppress the multiplication of cumulative errors.
// The point is not just to update the "sum", but to carry over the dropped fragment c to the next addition.
static double SumKahan(double[] xs)
{
    double sum = 0.0; // Total
    double c   = 0.0; // Compensation (accumulation of parts lost to rounding)

    foreach (var x in xs)
    {
        // Subtract the part lost previously (c),
        // and "add it back" to this addition
        double y = x - c;

        // Perform the addition here (rounding occurs at this moment)
        double t = sum + y;

        // (t - sum) is the "amount actually added to sum this time"
        // Subtract y from that to get the "fragment dropped this time"
        c = (t - sum) - y;

        // Update total
        sum = t;
    }

    return sum;
}

The traveler understood.

Errors cannot be erased.
But their multiplication can be suppressed.

They didn't change the formula.
Only the way they pile them up.

Column: Kahan compensated summation is powerful but not a panacea

Kahan compensated summation is a powerful means to suppress the "cumulative error of addition," but it is not a panacea.

  • It is difficult to parallelize due to sequential dependency (because the compensation value is carried over to the next)
  • It is not directly effective for rounding errors in multiplication or complex expressions (it works for the rounding errors of addition)
  • Neumaier might be more stable for large amounts of data

Compensated summation is not a "magic to erase errors," but should be used strategically as a weapon to suppress the multiplication of errors.

6.4.4 Conclusion: The victory condition is not "zero"

The traveler repeated the same addition one last time to verify.

== final battle: naive vs kahan (sum 0.1 many times) ==
expected: 1000000
naive   : 999999.99983897537
kahan   : 1000000

Errors cannot be erased.
But their multiplication can be suppressed.

And what remains at the end is exactly as the engraving on the wall says:

Expect errors, and tolerate them.
If you cannot tolerate them, pay the price in effort.

The traveler reached for the door. The errors haven't disappeared. But—they no longer run wild.

That was enough.

Epilogue: The Operators are Correct

The operators are correct.
What is wavering is the premise of this world and the vessels themselves.

In the land of integers, remainders could be kept.
In this continent, even remainders are divided.

The values exist.
But they are not perfect.

Therefore, what is needed is
not to pray for correctness.

Define boundaries, aggregate judgments, and choose a form that does not break even in a wavering world.

The traveler learned that.

Beyond the door, lands yet unseen spread out.
But they will not stop anymore.
What should stop is—the code.

The traveler walked away quietly.

Discussion