🔢 mathematics

Robustness of Double-Word Addition Algorithms under Overlapping Inputs

This paper establishes the robustness and error bounds of double-word addition algorithms when input components overlap, demonstrating that Fast2Sum remains exact under specific conditions and showing that a simplified multiplication–addition kernel on AVX-512 hardware achieves significant throughput gains with minimal impact on accuracy.

Original authors: Yuanyuan Yang, Xinyu Lyu, Sida He, Xiliang Lu, Ji Qi, Zhihao Li

Published 2026-09-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuanyuan Yang, Xinyu Lyu, Sida He, Xiliang Lu, Ji Qi, Zhihao Li

Original paper licensed under CC BY 4.0 (https://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

Modern computers speak a language of numbers that is both powerful and imperfect. When a processor calculates a value, it must fit that number into a fixed space, much like trying to pour a gallon of water into a quart-sized jug. The excess spills over, and the computer keeps only what fits, discarding the rest. This process, known as rounding, is the standard way machines handle real-world quantities, but it introduces tiny errors with every single calculation. For most daily tasks, these errors are invisible. However, in fields like weather forecasting, aerospace engineering, or complex financial modeling, these small mistakes can accumulate, eventually distorting the final result enough to matter. To combat this, scientists have developed methods to represent numbers with greater precision by using two standard computer numbers working together as a single, larger unit. This technique, called double-word arithmetic, allows for a more accurate representation of reality, but it requires careful handling to ensure the two parts of the number stay aligned correctly.

The core challenge lies in how these paired numbers are added together. Imagine two people carrying a heavy load, where one person holds the main weight and the other carries the remainder. If the load shifts, the person with the main weight might suddenly become lighter than the one with the remainder, or the two might overlap in a way that confuses the balance. In the world of high-precision computing, this "overlap" happens when the small part of one number is large enough to interfere with the main part of another. Traditionally, algorithms designed to add these pairs required a strict order: the main part of the first number had to be larger than the main part of the second. If this order was violated, the computer had to perform extra, expensive steps to reorganize the numbers before adding them. This reorganization, known as normalization, is computationally costly and can slow down complex calculations significantly.

A team of researchers from Huawei Technologies and Wuhan University has investigated whether these strict ordering rules are always necessary. They focused on two specific methods used to add these double-word numbers: a faster, simpler method they call "fast addition," and a more rigorous, slower method called "accurate addition." The "fast" approach is popular because it uses fewer computer operations, making it much faster, but it was generally thought to be risky when the inputs overlapped or when the numbers were nearly equal in size but opposite in sign, a situation known as cancellation. The researchers set out to determine exactly how much overlap these methods could tolerate before they began to produce incorrect results. They did not just guess; they built a mathematical proof to show the precise conditions under which the faster method remains reliable.

Their findings reveal that the "fast" method is far more robust than previously believed, but only within specific limits. They proved that even when the inputs overlap, the method remains mathematically exact in many common scenarios, provided the overlap does not exceed a clearly defined boundary. Specifically, they identified a sufficient condition: as long as the small parts of the numbers do not exceed a certain fraction of the main parts, the fast method works perfectly without needing the extra reorganization steps. However, they explicitly warn that this robustness does not hold under arbitrary cancellation. If the numbers cancel each other out to a severe degree, the error can become large, and the method does not guarantee a uniform relative-error bound in those extreme cases. In scenarios where the cancellation is not severe, the error introduced by the fast method remains incredibly small, growing only at a rate that is negligible for most practical purposes. In fact, their analysis showed that in standard computer formats, the error is often close to a tiny fraction of the machine's precision, far smaller than the errors found in standard single-precision calculations.

The researchers also examined the "accurate" method, which is designed to be precise but is more complex. They found that this method, too, remains stable under overlapping conditions, but it requires a slightly different set of rules to ensure the final result is correct. Crucially, they demonstrated that by understanding these boundaries, engineers can safely skip the expensive reorganization steps in many real-world applications, provided the inputs stay within the proven safe zones. To test this theory, they implemented a version of a common mathematical operation called multiplication-addition, where they deliberately skipped the final reorganization step and used the faster addition method instead. They ran this on a modern computer processor designed for high-speed parallel processing. The results were striking: the modified code ran approximately 84 percent faster than the traditional, fully reorganized version.

Despite this massive speed increase, the accuracy of the results barely changed in their random experiments. When they measured the difference between the fast, unorganized results and the true mathematical values, the error was so small that it was barely distinguishable from the error in the slower, more careful method. This suggests that for many high-performance computing tasks, such as evaluating complex mathematical functions or simulating physical systems, the strict requirement to reorganize numbers after every step is unnecessary, as long as the inputs do not fall into the specific "severe cancellation" regime where the fast method is known to fail. The researchers also confirmed that these fast methods maintain a specific property useful for safety-critical applications: they consistently round in a predictable direction, either always slightly up or always slightly down. This predictability is essential for interval arithmetic, a technique used to guarantee that a calculated range contains the true answer, ensuring that no possible error is left unaccounted for.

The study does not claim that the fast method is perfect in every single situation. There are specific, extreme cases where the numbers cancel each other out almost completely, and in those rare instances, the fast method can produce larger errors. However, the researchers provided a clear map of where these dangerous zones lie and showed that for the vast majority of practical inputs, the fast method is safe. They also noted that their results rely on the computer not encountering extreme values that would cause the numbers to overflow or underflow, which are standard limitations in any floating-point calculation. By proving that the "fast" addition algorithm is robust under a wide range of overlapping inputs, the team has provided a solid theoretical foundation for speeding up high-precision computing without sacrificing reliability. This work allows software developers to make informed decisions, choosing the faster path with the confidence that the mathematical guarantees still hold, effectively bridging the gap between the need for speed and the demand for precision.

Technical Summary: Robustness of Double-Word Addition Algorithms under Overlapping Inputs

Problem Statement
Double-word arithmetic represents real quantities as unevaluated sums of two working-precision floating-point numbers ( $x_h + x_l$ ) to achieve higher precision than standard hardware formats. While normalized expansions (where $|x_l| \le u|x_h|$ ) are well-understood, intermediate computations often produce "overlapping" expansions where the low component is not strictly smaller than the high component. Restoring normalization after every operation is computationally expensive.

Two fundamental addition algorithms exist for double-word arithmetic: "non-normalized addition" (Algorithm 4) and "accurate addition" (Algorithm 5), both derived from the QD library. Non-normalized addition is faster but traditionally advised against when operands have opposite signs due to potential cancellation and lack of uniform error bounds. Accurate addition is more robust but requires more operations. The core problem addressed is determining the conditions under which these algorithms remain robust—specifically, when their internal normalization steps (using Fast2Sum) remain exact or bounded—despite overlapping inputs and potential cancellation between high components.

Methodology
The authors analyze these algorithms within an ideal radix-2 floating-point model with unbounded exponents and precision $p$ . They utilize standard error-free transformations (Fast2Sum, 2Sum, 2Prod) and define specific overlap parameters ( $o_x, o_y$ ) such that $|x_l| \le o_x u |x_h|$ and $|y_l| \le o_y u |y_h|$ .

Key analytical tools include:

Modified Fast2Sum Analysis: The authors prove a sufficient condition (Lemma 3.1) under which Fast2Sum remains exact even when the conventional magnitude ordering ( $|a| \ge |b|$ ) is violated, provided a "trailing-bit" condition holds ( $uls(a) \ge ulp(b)$ ).
Robustness Proofs: They establish that under explicit overlap bounds ( $o \le (8u)^{-1} - 2$ ), the normalization steps in both non-normalized and accurate addition remain exact in round-to-nearest (RN) and satisfy one-sided $O(u^2)$ bounds in directed rounding (RD/RU), provided severe cancellation ( $r(x_h, y_h) > 1/2$ ) is avoided or handled.
Error Analysis: The paper derives piecewise relative-error bounds for non-normalized addition, distinguishing between non-severe cancellation ( $r \le 1/2$ ) and severe cancellation regimes. For directed rounding, a comparison-based variant of accurate addition (Algorithm 6) is analyzed to separate second-order error bounds from one-sided properties.
Application to MAA: The analysis is applied to a Multiplication-Addition (MAA) kernel where the final normalization of double-word multiplication is omitted before applying non-normalized addition.
Numerical Experiments: Benchmarks were conducted on an AVX-512 platform (Huawei FusionServer) using matrix multiplication (GEMM) to measure throughput and componentwise forward error.

Key Contributions

Robustness under Overlap: The authors prove that non-normalized addition and accurate addition remain robust for a broad, explicitly parameterized range of overlaps. Specifically, the normalization steps in both algorithms are exact in RN and satisfy second-order bounds in directed rounding, provided the overlap is bounded independently of $u$ and severe cancellation is avoided.
Relaxed Fast2Sum Condition: A new sufficient condition is established for Fast2Sum to be exact without requiring the standard magnitude ordering of operands, relying instead on the relationship between the least significant bit of the larger operand and the unit in the last place of the smaller operand.
Error Bounds for Non-Normalized Addition: A detailed error analysis shows that in RN, non-normalized addition has a relative-error bound of $4u^2 + O(u^3)$ in the absence of severe cancellation. Binary64 examples demonstrate errors close to $3u^2$ .
Directed Rounding Variant: For a comparison-based variant of accurate addition in directed rounding, an explicit finite-precision bound of $(3o + 15)u^2 + O(u^3)$ is derived, where $o$ is the overlap parameter.
One-Sided Error Property: The paper formally records the one-sided error property of these addition kernels under directed rounding, which is critical for interval arithmetic applications.
MAA Optimization: The study analyzes an MAA kernel that omits the final normalization of double-word multiplication. Theoretical analysis suggests that while this increases the overlap parameter, the componentwise forward error remains small in well-conditioned scenarios (e.g., polynomial evaluation).

Results

Theoretical: The analysis confirms that non-normalized addition is a viable alternative to accurate addition in many contexts, provided the overlap is bounded and severe cancellation is not present. The derived bounds are explicit and depend on the overlap parameter $o$ .
Experimental: On an AVX-512 platform, an implementation of MAA that omits multiplication normalization and uses non-normalized addition achieved a throughput improvement of approximately 84% compared to a fully normalized accurate addition approach.
Accuracy: Numerical experiments on random inputs showed that the measured componentwise forward error changed only slightly when omitting normalization or using non-normalized addition. However, the authors emphasize that these random tests do not establish worst-case safety; the theoretical overlap and cancellation hypotheses must still be satisfied for guaranteed bounds.
Vectorization: The use of the vrangepd instruction (AVX-512) to replace conditional branches in Fast2Sum yielded performance improvements of 6–15% in double-double GEMM operations.

Significance and Claims
The paper claims to separate three distinct issues often conflated in double-word arithmetic: the exactness of normalization, componentwise forward error, and relative error under cancellation. It provides a rigorous justification for using the faster "non-normalized" addition in scenarios where inputs overlap, provided specific conditions on overlap magnitude and cancellation are met.

The authors modestly claim that their results allow for significant performance gains (up to 84% in specific MAA kernels) without a substantial loss in componentwise accuracy for well-conditioned problems. They explicitly state that their findings do not claim a uniform relative-error bound for non-normalized addition under arbitrary cancellation, nor do they assert that the unmodified QD accurate-add algorithm satisfies the derived directed-rounding bounds without the specific comparison-based modification. The significance lies in enabling high-performance, high-precision arithmetic on modern SIMD hardware by relaxing strict normalization requirements while maintaining provable error bounds.

More like this