为什么浮点数在几何确定性中失效：整数算术的必要性

在计算几何的世界里，一个比特的差异可能意味着操作成功与灾难性失败之间的区别。对于许多开发者来说，一个假设是：只要输入相同，无论在什么机器上运行，相同的代码都会产生相同的结果。然而，正如 exact-poly 的作者所发现的那样，当涉及浮点数时，情况并不总是如此。

在调试多边形重叠测试时，作者发现一个判断顶点是凸顶点还是凹顶点的函数在本地运行正常，但在服务器上却失败了。罪魁祸首不是逻辑错误，而是不同架构处理浮点运算的方式。在 x86 上，编译器使用 Fused Multiply-Add (FMA) 来减少舍入步骤；而在 WASM 上则不然。这种舍入上的微小差异导致靠近零的顶点符号发生翻转，从而引发多米诺效应，彻底改变了多边形的分解结果。

IEEE 754 可复现性的幻象

许多开发者认为 IEEE 754 兼容性可以确保行为的一致性。实际上，该标准主要定义了浮点数如何存储，而不是它们在不同执行环境下的行为。几种机制可能会破坏可复现性：

  • 中间寄存器： x87 FPU 通常以 80 位精度保留数值，仅在溢出到内存时才进行舍入，而 ARM 或 WASM 可能不会。
  • Fused Multiply-Add (FMA)： fma(a, b, c) 通过单个舍入步骤执行乘法和加法，产生的比单独操作更精确但结果不同的结果。
  • 重结合律 (Reassociation)： 使用 -ffast-math 等标志的编译器可能会将 (a + b) + c 重写为 a + (b + c)，从而改变舍入顺序。
  • Denormals： “清零” (flush-to-zero) 标志可能会根据进程静默翻转，从而改变次正规数 (subnormal numbers) 的处理方式。

正如一位评论者所指出的，虽然像 JVM (通过 strictfp 或 StrictMath) 这样的环境试图保证严格的可复现性，但浮点算术的本质仍然是一种近似。

对于需要绝对确定性的应用——例如锁步 (lockstep) 游戏模拟或 ZK 证明生成 (ZK witness generation)——这些近似是不够的。

凸分解中的“一位比特”问题

在几何学中，cross_sign(A, B, C) 函数是决策的主要信号。它决定了一个转向是左转、右转还是共线。当三个点几乎共线时，一台机器可能会返回 +1e-12，而另一台则返回 -2e-13。

这种符号翻转至关重要，因为凸分解是一个离散过程。一个顶点要么是凹的，要么不是。如果符号翻转，就会识别出不同的凹顶点，从而导致不同的起始切割点，并产生完全不同的分解图。使用 epsilon (例如，“在比较前舍入到微米级”) 并不能解决这个问题，因为任何 epsilon 区域最终都会捕获真实的几何形状并导致行为分叉。

解决方案：精确整数算术

为了在 x86、ARM 和 WASM 之间实现比特级的一致性，exact-poly 完全放弃了浮点数，转而使用整数。通过将坐标映射到固定比例 (例如，在测地学中，1 单位 = 1 微米)，该库确保了叉积的符号是一个位逻辑问题，而不是近似问题。

管理整数预算

整数算术需要仔细选择比例。利用 i64::MAX (大约 $9.2 \times 10^{18}$)，开发者必须在测量单位与最大坐标大小之间取得平衡。对于测地学，使用 $10^6$ 的比例可以实现微米级精度，同时在覆盖整个地球周长时仍有充足的余量。

使用 i128 防止溢出

叉积公式——$(bx - ax)(cy - ay) - (by - ay)(cx - ax)$——很容易超过 i64 的限制。为了防止这种情况，exact-poly 采用了一条严格的规则：坐标以 i64 存储，但任何乘法都在 i128 中进行。

至关重要的是，该库在减法之前扩大数值：(bx as i128) - (ax as i128)。如果先在 i64 中进行减法，可能会导致溢出，即使存储在 i128 容器中也会产生错误数据。

实现鲁棒的分解级联机制

由于没有任何一种凸分解算法对所有输入都完美，exact-poly 使用了算法的“级联”模式。如果第一个失败，下一个就会接管：

  1. ExactPartition: 一个优先考虑凹顶点的贪婪划分器。
  2. Bayazit: 一种可以插入 Steiner points (中点顶点) 的递归方法。
  3. EarClip + Hertel-Mehlhorn: 先进行三角剖分，然后通过合并步骤来减少部件数量。

如果这三种方法都失败，该库会旋转环 (改变起始顶点) 并重试。这种启发式方法之所以有效，是因为病态案例通常与特定的顶点遍历顺序有关。

处理离散数学的边缘情况

转向整数会引入连续浮点数学中不存在的新挑战：

  • 中点精度： 简单的整数除法 (a + b) / 2 会丢弃低位比特。该库使用 round_div2 来确保点不会发生漂移。
  • Steiner Point Snapping： 如果中点距离现有顶点太近，必须对其进行微调，以防止意外的共线。
  • Bookkeeping： 合成顶点必须进行标记，以确保最终输出的顶点数与输入一致，从而防止下游验证失败。

结论：共识重于精度

浮点数是为精度设计的，但整数算术是为共识设计的。当两个不同的进程必须得出完全相同的答案时，如果舍入方向不同，浮点的精度就变得无关紧要了。通过利用 i128 进行中间计算并完全避免浮点数，exact-poly 为几何操作提供了一个确定性的基础，这在任何支持 64 位整数的架构上都能保证是一致的的。

Sources