💻 computer science

Mixing Condition Numbers and Oracles for Accurate Floating-point Debugging

The paper introduces EXPLANIFLOAT, a hybrid floating-point debugging tool that combines double-double arithmetic for condition number computation with a logarithmic oracle to handle overflow and underflow, achieving superior accuracy and speed compared to existing techniques.

Original authors: Bhargav Kulkarni, Pavel Panchekha

Published 2026-03-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bhargav Kulkarni, Pavel Panchekha

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to bake a perfect cake. You have a recipe (your computer program) and a set of measuring cups (floating-point numbers). The problem is, your measuring cups aren't perfect. They are a little bit wobbly, and sometimes they can't hold very large amounts of batter (overflow) or very tiny sprinkles (underflow).

When you bake a cake, you want to know: "Did I make a mistake in my measurements that ruined the cake?"

For a long time, computer scientists have built two different types of "detectives" to help chefs find these mistakes. This paper introduces a new detective called EXPLANIFLOAT that combines the best of both worlds.

Here is how it works, using simple analogies:

The Two Old Detectives (and why they failed)

1. The "Double-Double" Detective (The Shadow Chef)

How they worked: This detective had a second set of measuring cups that were slightly more precise than the chef's. Every time the chef measured flour, the detective measured it again with their super-cups. If the two measurements didn't match, the detective yelled, "Mistake!"
The Problem: Sometimes, the detective's super-cups had the same wobble as the chef's cups. If the chef made a tiny mistake, the detective made the exact same tiny mistake. They looked at each other and said, "Hey, we match!" and missed the error completely. It's like two people with the same bad eyesight trying to spot a flaw in a painting; they both miss it.

2. The "Condition Number" Detective (The Sensitivity Analyst)

How they worked: This detective didn't measure the ingredients again. Instead, they looked at the recipe and asked, "How sensitive is this step?"
- Analogy: If you are mixing a tiny drop of poison into a giant vat of water, a tiny mistake in the drop doesn't matter (low sensitivity). But if you are mixing a tiny drop of poison into a tiny cup of water, a tiny mistake is catastrophic (high sensitivity).
- This detective calculates a "danger score." If the score is high, they warn you.
The Problem: This detective is great at math, but terrible at handling extreme sizes. If the recipe calls for a mountain of flour (overflow) or a speck of dust (underflow), the detective gets confused and either screams "ERROR!" when it's actually fine, or stays silent when it's actually broken.

The New Detective: EXPLANIFLOAT

The authors of this paper realized: Why not hire one detective who has the sensitivity of the second one, but the super-cups of the first one, plus a special tool for extreme sizes?

EXPLANIFLOAT works in three clever ways:

1. It Uses "Sensitivity Scores" Instead of Just Comparing Numbers

Instead of just checking if the two measurements match (which can be fooled by shared errors), EXPLANIFLOAT looks at the Condition Number.

The Analogy: Imagine you are walking on a tightrope. If the wind is calm, a small wobble is fine. If the wind is a hurricane, a tiny wobble sends you flying. EXPLANIFloat calculates the "wind speed" of your calculation. If the wind is high, it warns you, even if the numbers look okay. This stops it from missing errors that the old "Shadow Chef" would have missed.

2. It Uses a "Logarithmic Oracle" for Extreme Sizes

To handle the mountains of flour (overflow) and specks of dust (underflow), EXPLANIFLOAT uses a special Logarithmic Oracle.

The Analogy: Imagine trying to measure the distance from Earth to the Sun and the size of a bacteria on the same ruler. You can't do it with a standard ruler. So, this detective uses a "Zoom Lens."
- Instead of measuring the raw number, it measures the power of the number (the exponent).
- If the chef tries to add a mountain to a speck, the detective uses the Zoom Lens to see that the mountain is so huge the speck disappears. It knows exactly when a number gets too big or too small to fit in the computer's memory, preventing the "confusion" that the old detectives had.

3. It Splits the "Danger Score"

The authors noticed that some numbers are dangerous for different reasons.

Analogy: A car crash can happen because you were going too fast (Sensitivity) or because you were driving on a slippery patch of ice (Cancellation).
EXPLANIFLOAT splits its warning system. It checks if the input is too big/small (Sensitivity) AND if the inputs are canceling each other out (Cancellation). This prevents false alarms. For example, if you subtract two huge numbers that are almost identical, the result is tiny, but the error is huge. EXPLANIFLOAT spots this specific "cancellation" danger.

The Results: The Perfect Detective

When the authors tested EXPLANIFLOAT on 546 difficult math problems:

It caught 96% of the real errors (Recall). It rarely missed a mistake.
It was right 80% of the time when it raised an alarm (Precision). It didn't waste your time with too many false alarms.
It was 4 times faster than the super-precise, slow methods used by other experts.

The Bottom Line

Think of EXPLANIFLOAT as a detective who doesn't just look at the evidence (the numbers) but understands the context (how sensitive the math is) and has a special zoom lens for extreme situations. It combines the speed of a standard calculator with the brainpower of a super-computer, making it much easier for programmers to find and fix the hidden bugs in their code without waiting hours for the computer to think.

1. Problem Statement

Floating-point arithmetic introduces subtle rounding errors that can lead to catastrophic failures in scientific computing. While automated tools exist to detect these errors, current approaches suffer from a trade-off between performance and accuracy:

Oracle-based Debuggers (e.g., EFTSanitizer): These tools use higher-precision "oracles" (like double-double arithmetic) to compute the "correct" result and compare it against the floating-point execution.
- Downside: They suffer from correlated errors. If the oracle lacks sufficient precision (e.g., in cases requiring thousands of bits), it computes the same erroneous value as the original program, leading to false negatives (missing real errors). They also struggle with overflow/underflow detection.
Static Analysis Tools (e.g., FPTaylor, Satire): These use condition numbers and error Taylor series to estimate worst-case error bounds.
- Downside: They are often too slow for dynamic debugging and cannot cleanly handle overflow and underflow, often flagging benign overflows as errors (false positives) or failing to detect them.

The Gap: No existing tool simultaneously achieves the high performance of oracle-based debuggers and the high accuracy of condition-number-based analysis, particularly regarding overflow/underflow handling.

2. Methodology: EXPLANIFLOAT

The authors introduce EXPLANIFLOAT, a hybrid debugging tool that combines the speed of double-double oracles with the robustness of condition numbers, augmented by a novel logarithmic oracle for extreme values.

A. Core Algorithm: Condition Numbers over Oracles

Instead of comparing the floating-point result to a high-precision oracle value to detect errors, EXPLANIFLOAT computes the condition number ( $\Gamma$ ) of every operation.

Mechanism: It tracks the relative error bound ( $|E_i|$ ) for each intermediate value using the formula: $|E_i| = \Gamma_{f}(x_j)|E_j| + c_i$ .
Split Condition Numbers: To improve error localization, the tool splits condition numbers into two types:
1. Stability Errors: Caused by large or small inputs (e.g., sensitivity of $\sin(x)$ for large $x$ ).
2. Cancellation Errors: Caused by inputs close to specific discrete values (e.g., $\sin(x)$ near $k\pi$ ).
Advantage: Condition numbers are inherent properties of the function and do not rely on an oracle's precision. This avoids the "correlated error" problem where the oracle fails to detect the error.

B. Handling Overflow and Underflow: Logarithmic Oracle

Condition numbers fail when overflow/underflow occurs because relative error bounds break down. EXPLANIFLOAT introduces a Logarithmic Oracle for these cases.

Representation: Values outside the standard floating-point range are represented as $(\text{sign}, \log_2(|x|))$ .
Logic:
- If an operation overflows/underflows but the final result (after subsequent operations) remains within the representable range and matches the real value, no error is raised (benign overflow).
- If the divergence between the floating-point execution (which becomes $\infty$ or $0$) and the logarithmic oracle (which tracks the true magnitude) is significant, an error is raised.
Special Cases: The tool suppresses warnings for underflows in additions where the smaller term is negligible compared to the larger term (e.g., $1 + 10^{-300}$ ).

C. Implementation: The DSL Number System

EXPLANIFLOAT uses a custom shadow memory structure called DSL (Double-double, Sign, Logarithm) for every intermediate value:
$\llbracket x \rrbracket = (\hat{x}, \hat{r}, s, \hat{e})$

$\hat{x}, \hat{r}$ : Double-double components for standard range (using the qd library).
$s, \hat{e}$ : Sign and Logarithm components for out-of-range values.
Hybrid Execution: The system dynamically switches between double-double arithmetic (for normal range) and logarithmic arithmetic (for overflow/underflow). Conversion between these modes occurs only when necessary, avoiding the overhead of arbitrary-precision libraries like MPFR.

3. Key Contributions

Condition-Number-Based Debugging: A novel algorithm that detects rounding errors by analyzing the sensitivity (condition number) of operations rather than comparing against a potentially flawed oracle.
Logarithmic Oracle: A specialized oracle using a logarithmic number system to accurately track and detect overflow/underflow without arbitrary-precision arithmetic.
DSL Implementation: A high-performance implementation using the qd library and custom range-reduction algorithms (Payne-Hanek) to support transcendental functions in double-double arithmetic, combined with logarithmic tracking.
Split Condition Numbers: A method to distinguish between "stability" and "cancellation" errors, providing more actionable feedback to developers.

4. Results

The tool was evaluated on 546 difficult benchmarks from the Herbie 2.1 suite, comparing it against a double-double oracle baseline and an arbitrary-precision baseline.

Accuracy:
- Precision: 80.0% (vs. 56.5% for double-double oracle).
- Recall: 96.1% (vs. 65.4% for double-double oracle).
- The high recall indicates it rarely misses real errors (false negatives), which is critical for debugging.
Performance:
- EXPLANIFLOAT is 4.24× faster than an arbitrary-precision baseline (using correctly-rounded interval arithmetic).
- It achieves this speedup by avoiding memory allocation and using hardware floating-point instructions for shadow operations.
Comparison:
- It significantly outperforms the oracle-based method (EFTSanitizer style) in both precision and recall.
- It approaches the accuracy of the arbitrary-precision baseline while being dramatically faster.

5. Significance

Bridging the Gap: EXPLANIFLOAT successfully merges the speed of runtime debugging with the analytical rigor of static analysis, solving the long-standing trade-off between performance and accuracy.
Robustness: By moving away from pure oracle comparison, it eliminates the "correlated error" failure mode where high-precision oracles fail to detect errors in ill-conditioned problems.
Practicality: The tool provides high-confidence warnings (high recall) with manageable false positives, making it suitable for integration into real-world development workflows.
Innovation in Number Systems: The introduction of a hybrid Double-Double/Logarithmic shadow memory system offers a new paradigm for handling the full dynamic range of floating-point computations without the heavy cost of arbitrary-precision libraries.

In summary, EXPLANIFLOAT represents a significant step forward in numeric debugging, offering a tool that is both fast enough for practical use and accurate enough to catch the most elusive floating-point errors, including those involving extreme values.