IEEE 754-2019、Posit 与非典型编码

• Kahan 补偿求和（compensated summation）的原理与误差界
• 朴素累加与补偿累加的误差量级对比
• 0.1 在二进制浮点中的表示误差及其累积效应

朴素累加 0.1 一百万次，误差大致按 O(n·ε) 甚至 O(n²·ε) 增长，可能达到 1e-9 到 1e-10 量级甚至更差；而 Kahan 求和将误差降到 O(ε) 量级（与累加次数几乎无关），结果误差通常可控制在 1e-15 量级（接近 machine epsilon 的量级）。Kahan 求和通过维护一个"补偿变量" c，记录每次加法中被舍入掉的那部分残差，并在下一次加法前把它加回去，从而把逐次舍入误差重新吸收进后续运算，避免累积。对 0.1 这种不能精确表示的数，Kahan 求和能显著改善总和的精度。

0.1 转换为二进制浮点是无限循环小数，本身有表示误差。朴素累加每次加法都引入舍入误差，且误差随项数线性甚至平方增长；Kahan 算法把每次被舍入掉的部分保存下来并回补，使误差不随 n 增长，误差界从 O(nε) 降为 O(ε)，这是数值稳定累加的核心思想。

• Posit 变长 regime 字段的解码复杂度
• 可变位宽对 SIMD 对齐、流水线吞吐的影响
• 与 IEEE 754 固定布局的硬件友好性对比

Posit 的核心特征是 regime 字段是变长的（用前导 1 的连续个数表示），因此每个数的 exponent 和 fraction 起始位随数值不同而变化，解码需要先统计 regime 长度（leading zeros/ones 计数）再动态移位，这一过程引入了依赖链和可变移位，难以在 SIMD 流水线中保持固定步长、固定吞吐。相比之下，IEEE 754 的符号/指数/尾数字段位置固定，可以在单条指令内完成解码，极其适合 SIMD 与流水线。Posit 虽然有利于插入/重排舍入和累加，但变长解码使得每个 lane 的处理不可合并，硬件需为最坏情况预留宽度，导致面积和延迟开销，成为其硬件落地的主要障碍。

SIMD 追求"一次指令处理多个相同布局数据"，Posit 的变长 regime 破坏了这种同构性，每个 lane 需要独立的动态移位与比较，主流水线难以用固定硬件实现，通常需要专用查表或逐元素处理，牺牲了吞吐。

• PostgreSQL numeric 的任意精度十进制表示方式
• Db2 DECFLOAT 基于 IEEE 754 decimal128 的硬件/软件实现
• 两者在精度、存储、性能上的差异

PostgreSQL 的 numeric 是任意精度十进制类型，采用"以 10000 为基、每 4 位十进制一组"的 base-10000 数组表示，精度可扩展（最多 131072 位），完全由软件实现，不绑定 IEEE 754；Db2 的 DECFLOAT 直接对应 IEEE 754-2008 的 decimal128（34 位十进制有效数字，128 位），可用 DPD/BID 编码并可借助硬件十进制指令。工程上，PostgreSQL numeric 精度更高但运算较慢、存储较大；Db2 DECFLOAT 精度固定为 34 位，但能利用硬件加速且存储紧凑。两者都面向金融等需要精确十进制语义的场景，但实现路径不同。

一个走"任意精度软件大数"路线，一个走"IEEE 754 标准十进制浮点"路线，映射的差异在于精度是否由标准限定、是否依赖硬件支持，以及存储编码方式。

• decimal64 的指数范围与有效数字
• 十进制 subnormal 的定义与边界
• 与二进制 IEEE 754 subnormal 的差异

decimal64（IEEE 754-2008）有 16 位十进制有效数字，指数范围 emax=384、emin=-383。当结果指数小于 emin 时进入 subnormal 区，此时有效数字位数逐渐减少（从 16 位逐步降到 1 位），以指数下边界为代价换取更小的尾数粒度。与二进制浮点不同，二进制 subnormal 的指数固定为 1-bias（唯一固定），尾数逐步减小；而十进制 subnormal 的有效数字位数是逐步"削去"的（每降一位指数削掉一位有效数字），且十进制没有"隐藏位"概念，subnormal 与 normal 的区分主要看指数是否低于 emin 且有效数字是否被截断。两者都牺牲精度换渐变下溢，但衰减步长与表示方式不同。

二进制 subnormal 用固定最小指数 + 减小尾数实现渐变下溢；十进制 subnormal 通过减少有效数字位数实现，边界由指数是否达到 emin 决定，且十进制编码的 subnormal 与 normal 之间没有隐式前导位差异。

• C# decimal 的 128 位结构（96 位尾数 + 符号 + 8 位刻度 scale）
• decimal128 的 113 位有效数字 + 指数编码
• 精度、范围、表示语义的差异

C# 的 decimal 用 128 位表示：96 位整数尾数（28-29 位十进制有效数字）、1 位符号和 8 位指数刻度（scale），指数刻度 0-28 表示小数点移动，尾数固定为 96 位整数，因此是"可缩放整数"表示，最大约 7.9e28；IEEE 754 decimal128 是 113 位有效数字（34 位十进制）、15 位指数，支持 subnormal、无穷、NaN 等完整 IEEE 语义。C# decimal 没有无穷/NaN 概念、指数范围小、精度在 28-29 位，且不遵循 IEEE 754 舍入规范（采用 .NET 定义），适合金融货币但对超大或极小数值支持有限；decimal128 是标准浮点十进制，精度更高、范围更大、语义更完整。

C# decimal 本质是"96 位整数 + 指数刻度"的定点思想，decimal128 是真正的十进制浮点格式，两者精度的 28 位 vs 34 位、范围、特殊值处理都不同，是标准的十进制表示变体。

• Morton code 的空间填充特性
• 8 邻域增量编码（邻居坐标加 1 即可得到相邻 Morton）
• LoD 中按比特层实现多分辨率

Morton code（Z-order）把 2D/3D 空间坐标按位交错编码成 1D 整数，天然支持 LoD：因为高位比特对应空间的大尺度划分，低位比特对应细粒度，取 Morton 码的高若干位即可得到某长度的空间网格（LoD 层级）。8 邻域编码中，水平/垂直邻居的 Morton 码可由当前码加减 2 的幂（位交错后的步长）得到，增量计算友好，适合邻域遍历与空间查询。工程上常用于空间索引、碰撞检测、体素网格、GPU 并行邻域访问，但要注意对角线邻居和跨象限的进位问题。

Morton 码的位交错结构让"分辨率"与"比特位"对应，从而实现 LoD；邻域增量编码利用坐标 +1 的位交错仅在奇数位变化、偶数位（y）不变等规律，快速计算相邻码值。

• Hilbert 曲线的高空间连续性（相邻点映射到相邻位置）
• Morton 码存在"跳变"（对角线断裂）
• 两种编码的 cache 命中率与索引复杂度权衡

Hilbert 曲线保证相邻空间点映射到相邻的一维索引，空间连续性优于 Morton，因此对空间局部性敏感的数据（如几何数据、物理模拟）能带来更高的 cache 命中率，因为相邻访问的数据在内存中也相邻。但 Hilbert 的编码/解码需要递归或状态转换，计算复杂度高于 Morton 的简单位交错；Morton 码在相邻象限边界处有对角线跳变，局部性稍差，但编码极快、并行友好。工程上在"空间局部性收益"与"编解码开销"之间取舍：局部性要求高且重排成本可接受时选 Hilbert，追求快速编码和高吞吐时选 Morton。

空间相关性即"一维距离与空间距离的近似程度"，Hilbert 更优但计算更贵；Morton 次优但编码简单、可并行，是工程上的性价比选择。

• KBN 算法相对 Kahan 的改进（更新补偿变量的时机）
• 对大小差异悬殊（大数 + 小数）输入的精度保持
• 浮点舍入误差的准确记录

Kahan-Babuska-Neumaier（KBN）算法是 Kahan 求和的改进版。Kahan 算法中，当输入是"大数 + 小数"组合时，补偿逻辑可能因舍入位置不对而失效；KBN 通过每次比较当前和与新项的大小，总是把绝对值较小的那个数记入补偿变量——即 if |s| >= |x| then c += (s-x)+t else c += (x-s)+t，从而无论接近和远离和值的项都能精确记录被舍入掉的残差。对于混合大小输入，KBN 比 Kahan 更稳健，误差保持 O(ε) 量级，适合金融合计、物理积分等需要高精度累加的场合。

Kahan 在"新项相对当前和很小"时，被舍入掉的残差可能无法被正确捕获；KBN 显式判断哪个数更大，保证补偿项始终记录实际的舍入残差，从而在混合大小输入下仍保持精度。

• 金融精确合计对误差的敏感
• Kahan 补偿累加的代码实现
• 对账系统金额一致性保证

金融合计要求金额精确到分，直接用 double 累加一千万笔小额时会产生可感知的误差。实践中当不能使用 BigDecimal 等精确类型时，用 Kahan 求和把累加误差从 O(nε) 降到 O(ε)，保证合计与逐笔明细之和一致。对账系统往往同时保留"逐笔精确金额（如长整型分）"与"高性能浮点合计"，Kahan 用于核对浮点合计与精确合的差异是否在容差内。代码上维护 sum 与补偿 c，每步 y=x-c; t=sum+y; c=(t-sum)-y; sum=t;，最后返回 sum-c 或直接累加。

金融对账的核心是"合计必须一致"，Kahan 在不牺牲性能的前提下把浮点累计误差降到可忽略，配合分级容差校验，实现既快又准的金额合计。

• Sterbenz 引理的条件与结论
• 减法结果精确（无舍入误差）的意义
• 在数值算法中用于构造精确运算

Sterbenz 引理指出：对 IEEE 754 二进制浮点数 a、b，若 b/2 ≤ a ≤ 2b（即 a/2 ≤ b ≤ 2a），则 a − b 的结果可以精确表示，无需舍入。其工程语义是：当两个数在数量级上相差不超过一倍时，它们的差是"精确"的，不引入舍入误差。这为构建精确运算提供了基础——例如在计算中点、范围收缩、误差补偿时，若保证操作数满足 Sterbenz 条件，减法结果就是精确的，可作为后续精确推算的起点。它常被用于证明某些算法的误差界，或用于实现精确的区间运算。

因为 a 与 b 相差不超过一倍，差的指数范围与两数重叠，尾数对齐后不需要舍入，总能精确表示。该性质是 Sterbenz 在浮点误差分析（如 Shewchuk 精确几何谓词）中的关键工具。

• Sterbenz 条件是否适用于 subnormal
• binary64 与 subnormal 的衔接
• 精确减法在极端尺度下的可用性

Sterbenz 条件面向 IEEE 754 浮点体系，包括 binary64 与 subnormal 数。subnormal 数在指数达到下界 emin 后减小尾数，但 Sterbenz 引理针对的是"相邻可表示数间距"的规律，其在 subnormal 区域依然成立：只要 a 与 b 满足数量级相近条件，a − b 仍精确。工程价值在于，即使在极小的数值尺度（接近下溢）下，只要操作数满足 Sterbenz 条件，减法依然不引入舍入误差，这对需要高精度数值计算的算法（在极端输入下仍需精确）很重要，也让精确减法在 subnormal 区域仍可依赖。

binary64 和 subnormal 统一遵循 IEEE 754 的舍入与表示规则，Sterbenz 条件基于"两数相对间距"而非绝对大小，因此在 subnormal 区域依然成立，保证极端尺度下的精确减法。

• Posit 总位宽 n 与指数位 es
• regime 字段的变长 Goo 编码（leading 1 个数）
• exponent 固定 es 位，fraction 为剩余位

Posit 格式记为 Posit<n, es>，n 为总位宽，es 为指数段位宽。布局为：1 位符号（S），随后变长的 regime 字段（R），再是固定的 es 位 exponent（E），剩余位为 fraction（F）。regime 是变长的：统计连续相同的位（全 0 或全 1）的个数，k 表示 useed^k 的阶码，其中 useed = 2^(2^es)；regime 后跟一个相反位作为终止符。exponent 固定 es 位为普通二进制指数，fraction 为剩余的可变位宽（因 regime 变长而变）。因此总有效数字位数随数值大小变化，远离 1 的数的 fraction 位更少，这就是 Posit 的"渐变精度"。

regime 变长是 Posit 与众不同的核心，它用连续的 0/1 串编码大范围指数，使靠近 1 的数获得更多 fraction 位（更高精度），远离 1 的数牺牲 fraction 换取更大范围，从而实现"精度集中在 1 附近"。

• Sterbenz 条件对操作数数量级的限制
• 距离计算中欧氏距离与差的精确性
• 何时可利用、何时不可用

Sterbenz 条件要求参与减法的两个数相差不超过一倍，才能保证精确。在路径压缩（如 Dijkstra 的带权距离）和 k-means 距离计算中，坐标或距离往往跨越多个数量级，两点的一个坐标差与另一个坐标差可能相差悬殊，不满足 Sterbenz 条件，此时减法会引入舍入误差。工程边界在于：只有对于"数量级相近"的中间量（如计算中点、尺度的归一化坐标差）才能依赖 Sterbenz 精确性；跨越数量级的距离累计仍需 Kahan 或精确求和来控误差。因此 Sterbenz 更多用于理论误差界与局部精确运算，而非全局距离链。

Sterbenz 是"局部精确性"工具，其前提（两数量级相近）在真实距离/路径数据中并非总能满足，工程上需结合误差补偿（Kahan）与高精度累加来覆盖其不适用区间。

• george bit（regime 类型位）的含义
• 渐变精度：远离 1 时 fraction 位减少
• 权衡范围与精度

"george bit" 指 regime 字段中用于区分正负指数类型的位（即 regime 开始处的一个标志位，决定 regime 编码的是正指数还是负指数）。Posit 的渐变精度意味着：越接近 1，regime 越短，fraction 越长，精度越高；越远离 1（极大或极小），regime 越长，fraction 越短，相对精度下降但动态范围更大。工程价值在于：许多数值应用（如神经网络权重、概率）大量数值集中在 1 附近，Posit 在这些常用区间提供更高精度，而在极端范围牺牲精度换取可表示范围，实现了"精度按需分配"，比固定尾数的 IEEE 754 更贴合实际数据分布。

george bit 提供 regime 的符号/类型信息，配合渐变精度，Posit 在 1 附近（高概率数值区）留足尾数位，远离 1 时用更短尾数换取更大范围，从而在有限位宽下获得更优的整体精度-范围折中。

• π、e、√2 都是 1 附近的数
• Posit<32,2> 在 1 附近获得更多 fraction 位
• 相对 binary32 的精度提升

π、e、√2 都接近 1（在 1 到 4 之间），处于 Posit 渐变精度的高精度区。Posit<32,2> 在 1 附近可提供约 28 位有效尾数（含隐式位，相比 binary32 固定 24 位），因此表示 π、e、√2 的相对误差比 binary32 小，精度更高。这是 Posit 在"常用数值集中在 1 附近"场景的优势：28 位有效尾数（含隐式）对 1~2 之间的数，误差约为 2^-28，而 binary32 只有 2^-24。正因如此，量化的模型或数值库用 Posit 替换 binary32 时，在同位宽下通常获得更优精度。

尾数位越多相对精度越高。π、e、√2 位于 Posit 高精度区，Posit<32,2> 比 binary32 多出约 4 位有效尾数，故精度更高，是 Posit 相对 IEEE 754 在同一位置宽下的典型优势场景。

• Posit 标准化进程（ISO/IEC 24643）
• C++ 标准库支持现状
• 第三方库与硬件支持

Posit 正在推进 ISO/IEC 24643 标准化（源自 IEEE P2777 R1），但截至当前，C++ 标准库尚未内置 Posit 类型，标准委员会仍在讨论是否及如何纳入。实践中 Posit 通过第三方库部署，如 Stillwater Universal（Universal 类）、cerl 等实现，提供类似内置浮点的运算符重载；部分硬件加速（如某些 FPGA/RISC-V 扩展）和编译器实验支持也在推进。C++ 部署现状是：无标准库默认支持，依赖第三方实现与特定后端（SIMD/查表）加速，应用集中在数值库、研究性 HPC 与低精度推理领域。

标准化与生产部署之间存在时间差，Posit 虽已进入 ISO/IEC 24643 通道，但 C++ 生态仍需第三方库落地，反映了新数值格式在主流语言标准中采纳的滞后性。

• Posit 在 1 附近的高精度
• 低比特（如 Posit16/Posit<8,0>）推理
• 用更低位宽达到与 FP32 相近精度

深度学习推理中权重与激活常集中在 0 附近或 1 附近，Posit 的渐变精度正贴合这种分布：在常用数值区间用更少位提供足够精度。Unum Computing 等公司主张使用 Posit8/Posit16 等低精度格式替代 FP16/FP32 推理，在相同或更低精度损失下显著降低带宽与存储。由于 Posit 在 1 附近相对精度高，低比特 Posit 在部分推理任务上可比 bfloat16/FP16 更优，且支持更宽动态范围（regime 提供大范围），因此被宣传为"用更低位宽逼近 FP32 精度"的推理利器。

推理精度主要取决于常用数值区间的相对精度，Posit 在 1 附近分配更多尾数位，使低比特 Posit 在保持网络精度前提下压缩数据，从而降低带宽与能耗，是其在低精度推理的核心卖点。

• BID（Binary Integer Decimal）编码原理
• DPD（Densely Packed Decimal）编码原理
• 两者在硬件/软件实现的取舍

decimal64 的 64 位中，significand 可选用两种编码：BID（Binary Integer Decimal）把有效数字当作一个大的二进制整数直接存储（如 16 位十进制数用 54 位二进制整数表示），便于用二进制整数运算器实现加减乘，适合软件实现；DPD（Densely Packed Decimal）把每 3 位十进制全局按"约 10 位"压缩存放（每 3 位十进制 0-999 用 10 位编码，10 位可表示 1024 种），保留部分十进制位模式，便于十进制运算与精确转换，硬件实现更直接。两者都是 IEEE 754 标准允许的，BID 依赖二进制 ALU 效率高，DPD 更贴近十进制语义、硬件友好。

两种编码是同一格式的两种二进制表示方案：BID 用二进制整数编码十进制有效数字，运算简单但需转换；DPD 用压缩十进制编码，保留十进制特性但压缩逻辑略复杂。选择取决于目标是复用二进制 ALU（BID）还是原生十进制运算（DPD）。

• decimal64 的 64 位布局
• 有效数字位数（16 位十进制）
• 指数范围 emax/emin

decimal64 共 64 位：1 位符号、5 位组合字段（combination field，用于携带指数高位与有效数字高位）、剩余的 significand 系数。它能表示 16 位十进制有效数字，指数范围 emax=384、emin=-383（biased exponent 编码支持），因此可表示的数量级约从 1e-398 到 1e+384。significand 的 16 位十进制有效数字按 BID 需约 54 位二进制、按 DPD 用 54 位压缩编码，加上组合字段与指数位构成 64 位。这是 IEEE 754-2008/2019 十进制浮点 trio（32/64/128）中的中间档。

decimal64 的"16 位十进制有效数字 + 指数范围 ±384"直接对应其位宽分配：组合字段携带指数与高位，其余位编码 16 位有效数字，使 decimal64 在 64 位内兼顾精度与范围。

• half-even（银行家舍入）与 half-up 的区别
• truncate 截断舍入
• 金融与应用场景的舍入选择

half-even（银行家舍入）在恰好在中间时向偶数舍入，使统计上舍入误差对称、无偏，适合金融合计、统计等需避免系统性偏差的场景；half-up 在中间时向上舍入，商业计算常用但会产生小幅正偏差；truncate 直接截断，实现简单但误差单向。工程选型：金融对账默认 half-even（IEEE 754 默认舍入）以保证误差无偏；计费/零售小计常用 half-up 符合直觉；性能敏感或误差可容忍时用 truncate（如某些量化）。选型需兼顾"误差偏向"与"业务语义"，且与数据库/法规（如银行舍入规则）保持一致。

舍入模式决定舍入误差的统计性质：half-even 无偏、half-up 有正偏、truncate 单向截断。工程选型要匹配业务（金融无偏、计费直觉）与标准（IEEE 默认 half-even），并保持前端与后端一致。

• augmented arithmetic（augmentedAddition/augmentedMultiplication）的精确两倍结果
• flag 与 trap 的异常处理机制
• 与精确运算的配合

IEEE 754-2019 引入 augmented arithmetic 运算（augmentedAddition、augmentedMultiplication），它们返回两个结果：一个舍入后的主结果和一个"补足"（tail）分量，使两结果之和/积精确等于真实运算值，便于实现精确的误差补偿。在处理上，augmented 运算仍遵循 IEEE 挂起 flag（如 inexact）机制，但通常不触发 trap（除非显式启用异常 trap），因为其目的正是"部分舍入"供软件精确重构。这与金融/精确浮点库中"用 flag 检测精度损失、用 trap 做紧急处理"的语义不同：augmented 提供精确分量的分解，而非简单丢弃误差，因此更适合构建高性能精确累加与库函数。

augmented arithmetic 把一次运算拆成"主结果+残差"，本质是精确的 error-free transformation，配合 flag 检测溢出/非精确，而 trap 用于硬性异常中断；两者在精确运算框架中承担不同角色。

• clamped 边界的摆脱 subnormal 的规范化
• 舍入模式的选择
• 两者在表示与运算层面的作用

decimal64 的"clamped"（钳制）是一种表示规范化机制：当结果因指数过小而出 subnormal 且有效数字有多余的尾零时，可把尾零去除、把指数上移回 normal 范围，即"clamp"到正常指数，从而避免不必要的 subnormal 精度损失。而 IEEE 754 舍入模式（round-to-nearest 等）决定运算结果如何舍入到可表示值。两者作用于不同层面：clamped 是结果的"表示优化"（消除尾零、回退指数），舍入是"值量化"（选最近可表示数）。工程上 decimal 运算常同时应用 clamped 规范化与指定舍入模式，以获得精简且符合规则的十进制结果。

clamped 处理 subnormal 边界与尾零，舍入处理最近表示选择；clamped 并不改变舍入模式，而是决定如何规范化表示，二者互补，共同保证十进制结果既精确又规范。

• 位交错（bit interleaving）原理
• Look-up table 分块交错加速
• 编码与解码

Morton code 把 (x, y) 的二进制位交错合并成 1D 整数：x 的每一位放到偶数位、y 的每一位放到奇数位。直接实现可逐位展开，但低效；工程上用"Look-up table"加速——把每 8 位（或 16 位）作为一个整体，通过预计算表把该 8 位序列展开成 16 位交错结果，再对每 8 位块做移位并合并。例如"Look-up table 3"（或 3 次应用掩码移位法）用若干次"移位+掩码+或"的位运算把 32 位坐标的各位展开到对应间隔，比逐位循环快得多。解码同理用反向表还原 x、y。

位交错本质是"把位分散到间隔位置"，查表法利用预计算把 8 位块一次展开成 16 位，配合掩码移位合并，避免逐位循环，是 Morton 编码的高效工程实现。

• row-major 的 2D 布局
• Morton（Z-order）的空间局部性
• OLAP 范围查询的扫描效率

row-major 按行连续存储，对"整行扫描"或"按某列连续查询"友好，但对二维矩形范围查询（如二维分区、空间过滤）会跨多行产生大量非连续访问，cache 局部性差。Morton code 把二维空间按 Z 序连续映射到一维，使空间相邻的点在存储中尽量相邻，因此对二维范围查询（如数据立方体、星型模型的维度过滤）能显著提升 cache 与预取命中率，减少随机访问。其代价是列投影/整列扫描退化为非连续访问。工程上 OLAP 若以二维空间过滤为主，Morton 更优；若以整列/整行聚合为主，row-major 更优。

空间局部性取决于访问模式与存储布局的匹配：row-major 匹配行序扫描，Morton 匹配二维空间邻接查询。OLAP 范围查询的"空间连续性"需求决定了 Morton 的收益。

• Z-order 曲线的 GPU 并行访问
• 位交错在 GPU 上的高效实现
• 空间局部性与并行吞吐

在 GPU 上，Z-order curve（Morton 序）常用于纹理、Octree、Sparse Voxel 等数据结构，把二维/三维空间映射到一维线性存储，使并行线程访问空间相邻数据时也访问相邻内存，提升缓存利用与 coalescing（合并访问）效率。位交错在 GPU 上可通过并行位运算（如 mask-shift 序列）或查表并行处理，所有线程对各自坐标执行相同交叉逻辑，数据并行度高。工程价值在于：既获得空间局部性（相邻数据簇访），又保持 SIMT 高吞吐（无分支、固定步长），适合 GPU 渲染、路径追踪、体素遍历等场景。

GPU 的合并访存与缓存局部性同构，Z-order 位交错让空间邻接映射到线性邻接，同时位运算天然数据并行，兼顾局部性与吞吐，是 GPU 空间数据结构的理想选择。

• row key 排序与空间局部性
• Morton 编码把二维（如地理、时间+维度）压成有序 1D key
• 范围扫描与热点

Bigtable/HBase 的行按 row key 字典序存储与扫描，适合一维范围查询。Morton code 把二维数据（如经度+纬度、时间+ID）编码成 1D key，使空间相邻的记录在排序后相邻，从而把"二维范围查询"转化为"一维连续扫描"，提升范围扫描效率与缓存局部性。工程价值在于：无需额外索引即可用有序 key 支持二维空间/组合维度查询，数据分布均匀时避免热点。但需注意若数据集中在某空间区域，Morton 会造成 key 前缀相同导致热点分片，需结合 salt/散列前缀平衡负载。

Morton 把二维局部性映射进 row key 的排序顺序，使扫描与空间查询匹配；同时要处理数据偏斜带来的前缀热点，通常通过加盐或 rehash 均衡分布。

• 补偿变量的更新公式
• 舍入差（error-free transformation）的捕获
• 逐步误差抵消的代数原理

Kahan 求和的补偿变量 c 记录每次加法中被舍入掉的部分。对每步 t = sum + x; y = t - sum; c = (t - y) - x（或 (sum - (t - x)) + x - (t - sum) 变体），c 精确等于这次加法丢失的残差。其代数机理是：浮点加法 t = fl(sum + x) 的舍入误差 e = (sum + x) - t 可以精确地由 (t - sum) - x 重构（因为 t、sum、x 满足 Sterbenz 类条件，误差可精确表示）。下一轮把 c 加回去，就把上一步丢失的残差重新置入，使累计误差不随项数线性增长。这是"误差自由变换"（error-free transformation）在累加中的体现。

补偿变量捕获的是"本轮加法未被表示的部分"这个精确残差，下一轮把它纳入运算，从而让舍入误差被"反哺"而非累积，误差界从 O(nε) 降到 O(ε)。

• double-double 用两个 double 表示高精度
• 大数 + 小数的精度保留
• 与朴素 double 的对比

朴素 double 中 1e17 + 1.0 会因二进制 double 精度（约 2^-52 相对，绝对单位约 16）而丢失 1.0 的贡献（1.0 < 半个 ULP）。double-double arithmetic 用两个 double（hi, lo）表示一个数，hi 为主要值、lo 捕获残差，能表示约 106 位有效精度。累加 1e17 + 1.0 + 1.0 时，主 double 保留 1e17，次 double 保留 +1.0 的残差，从而完整记录 1.0 的累加，避免被大数吞没。工程价值在于以"相对廉价的两倍 double 运算"获得接近四倍精度的效果，适合高精度累加而无需 BigDecimal。

double-double 通过"主值+残差"双分量扩展有效位数，把小于单 double ULP 的小量保存在次分量中，从而在大数累加小数时保护精度。

• 并行规约的误差累积
• Kahan 补偿在每个局部累加的应用
• 全局误差控制

并行规约（reduction）把数组分块并行累加，每块用 Kahan（compensated summation）局部精确累加，再做树状合并。相比朴素并行累加，每块内误差从 O(nε) 降到 O(ε)，合并阶段误差也受控，整体误差接近串行 Kahan 的量级。工程价值在于：既能利用多核/SIMD 并行提速，又保持数值精度，常用于大规模数组求和、范数计算、矩阵归约等 HPC 场景。需注意合并阶段的顺序与补偿，确保最终结果与精确值误差可控。

并行规约的误差来自"分块内累加"与"子树合并"两处，对每块和合并点都用 Kahan 补偿，可把并行误差降到与串行补偿相近，兼顾性能与精度。

• 中点算式与溢出/精度问题
• Sterbenz 条件保障 hi - lo 精确
• 避免 lo+hi 溢出

传统中点 mid = (lo + hi) / 2 可能因 lo+hi 溢出而失败；改用 mid = lo + (hi - lo) / 2 时，由于 lo ≤ hi，有 (hi - lo)/2 ≤ hi 且 hi - lo ≥ 0，两数 hi 与 lo 满足 Sterbenz 条件（相差不超过一倍），因此 hi - lo 精确无舍入，中点计算稳定。工程价值：既避免溢出，又保证插值/中点计算的精度，广泛用于二分查找、bsearch 类算法、数值方法的区间中点。是 Sterbenz 条件在算法中的经典应用。

Sterbenz 保证 hi−lo 精确（两数同号且相差不超一倍），使中点无精度损失；同时规避 lo+hi 的溢出风险，是二分正确性的基础。

• 精确几何谓词（orient2d、incircle）的符号判定
• 误差自由变换（Sterbenz 条件）构造精确误差
• 符号决策的鲁棒性

Shewchuk 的精确几何谓词（如 orient2d、incircle）用于判定点是否在线的哪一侧、点是否在圆内等，需要绝对的符号正确性。算法利用误差自由变换（error-free transformations，其中 Sterbenz 条件保证的两数差精确）将每次运算的舍入误差精确分离出来，再用自适应精确算术（先浮点估计，若误差可能翻转符号则用更高精度扩展）重构真实符号。Sterbenz 条件保证了"相近数相减精确"，从而能可靠地逐层累加误差项，最终对几何谓词给出确定性符号，避免浮点近似导致的拓扑错误。

精确谓词的核心是把"舍入误差"变成可精确追踪的"误差项"，Sterbenz 条件使这类误差分离精确可行，自适应策略在多数情况下用快速浮点、仅在必要时升级精度，保证符号判定鲁棒且高效。

• Priest 的 two-sum 误差自由变换
• Sterbenz 条件保障误差精确
• doubledouble 的高精度运算

Priest 的双重数（doubledouble）与 Knuth 的 TwoSum 算法用误差自由变换把一次浮点加法拆成"主值 + 精确残差"，残差的计算依赖 Sterbenz 条件：当 sum 与加数满足数量级关系时，b = (sum - a) - x 能精确重构舍入误差。这些误差项被保存在双精度表示的低分量中，构成 doubledouble 的高精度抬升。协同上，Sterbenz 条件为误差自由变换提供"精确性保障"，而 doublesingle/doubledouble 利用这些精确残差扩展有效位数，是 Shewchuk、Bailey 等精确算术库的基础，用于高精度累加与几何谓词。

Doubledouble 的价值在于"把舍入误差显式化并保存"，而落实这一点需要 Sterbenz 条件保证误差重构精确，二者前后衔接，构成精确算术的底层机制。