用延迟分数对实现高精度计算，避免溢出且节省内存。
Quotient Tree Arithmetic: Deferred-Division Computation with Bounded Symbolic Depth and Cross-Subtree Cancellation
- 数值以延迟分数对形式存储，运算后才计算比值。
- 单次除法仅引入0.5个单位误差，远低于传统方法的线性增长。
- 适合机器学习训练，可防梯度消失并压缩模型存储。
我们提出商树算术（QTA），一种将数值表示为延迟商对 (N, D) 的计算基础，其比值仅在指定的物化边界处惰性求值。该框架适用于任意域：使用 IEEE 754 双精度作为精确整数容器，可在 2^53 精度窗口内实现精确有理数运算；任意双精度则扩展至包括 exp(x)、sqrt(x) 等机器学习激活函数在内的超越值。三个结构定理支撑 QTA：(1) 深度增长有界：每次运算最多增加树深 1，经 m 次操作后树大小为 O(m)，无组合爆炸；(2) 跨子树消去：出现在分子与分母中的相同子树可通过引用身份直接消去，无需计算，支持超越值一次计算、多次共享；(3) 延迟稳定性：仅在物化边界执行一次浮点除法，引入误差不超过 0.5 ULP，优于传统急切计算的 O(m) ULP。应用于机器学习训练时，可结构性防止梯度下溢至零；通过链式法则记录的张量坍缩实现梯度计算成本恒定；共享权重批处理压缩使图存储从 O(BLd) 降至 O(L+Bd)（B 为批量大小，L 为层数，d 为维度）；已知分母情况下，用试除法替代 O(log n) 的 GCD，实现 O(1) 复杂度。我们提出向量化硬件归一化指令（RatCleanup）用于 SIMD 并行有理对约简。代数基础为环在其乘法集上的局部化，连接到代数结构理论，同时扎根于硬件原生的 IEEE 算术。
原文摘要 · Abstract (English)
We introduce Quotient Tree Arithmetic (QTA), a computational substrate in which values are represented as deferred quotient pairs (N, D) whose ratio is evaluated lazily at a designated materialization boundary. The framework applies to any domain: IEEE 754 doubles used as exact integer containers give exact rational arithmetic within the 2^53 exactness window; arbitrary IEEE doubles extend coverage to transcendental values including machine learning activations such as exp(x) and sqrt(x). Three structural theorems underpin QTA. (1) Bounded Depth Growth: each arithmetic operation increases tree depth by at most 1, giving O(m) tree size after m operations with no combinatorial explosion. (2) Cross-Subtree Cancellation: subtrees appearing in both numerator and denominator positions cancel via reference identity without arithmetic, including transcendental values computed once and shared. (3) Deferred Stability: a single IEEE division at the materialization boundary introduces at most one-half ULP of rounding error, versus O(m) ULP for eager evaluation. For machine learning training, QTA provides: structural prevention of gradient underflow to zero; O(1)-cost gradient computation via chain-rule tape collapse when intermediate activations are reference-identical; shared-weight batch compression reducing DAG storage from O(BLd) to O(L+Bd) for a batch of B examples through L layers; and tracked factor cancellation replacing O(log n) GCD with O(1) trial division when denominators are known. We propose a vectorized hardware normalization instruction (RatCleanup) for SIMD-parallel rational pair reduction. The algebraic foundation is the localization of a ring at its multiplicative set, connecting QTA to algebraic structure theory while grounding it in hardware-native IEEE arithmetic.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。