為什麼浮點數在幾何決定論中會失敗：改用整數算術的理由

在計算幾何的世界中，僅僅一比特的差異，就可能導致操作成功與災難性失敗之間的區別。對於許多開發者來說，假設是相同的程式碼搭配相同的輸入，無論在何種機器上執行，都會產生相同的結果。然而，正如 exact-poly 的創作者所發現的，當涉及浮點數時，情況並不總是如此。

在偵錯多邊形重疊測試時，作者發現一個判斷頂點是凸頂點還是凹頂點的函數，在本地端運作正常，但在伺服器上卻失敗了。罪魁禍首並非邏輯錯誤，而是不同架構處理浮點運算的方式。在 x86 上，編譯器使用融合乘加（Fused Multiply-Add, FMA）來減少捨入步驟；而在 WASM 上則不然。這種捨入上的微小差異導致靠近零的頂點符號發生翻轉，進而引發連鎖反應，完全改變了多邊形的分解結果。

IEEE 754 可重現性的幻象

許多開發者認為 IEEE 754 相容性可以確保行為的一致性。實際上，該標準主要定義了浮點數如何儲存，而非它們在不同執行環境中的行為。幾種機制可能會導致可重現性洩漏：

  • 中間暫存器： x87 FPU 通常以 80 位元精度保留數值，僅在溢位至記憶體時才進行捨入，而 ARM 或 WASM 可能不會。
  • 融合乘加 (FMA)： fma(a, b, c) 以單一捨入步驟執行乘法與加法，產生的結果比分開執行更精確，但也與分開執行不同。
  • 重組關聯性 (Reassociation)： 使用如 -ffast-math 等標記的編譯器可能會將 (a + b) + c 改寫為 a + (b + c)，這會改變捨入順序。
  • 非正規化數 (Denormals)： 「歸零標記 (flush-to-zero)」可能會根據程序被靜默切換，從而改變次正規數的處理方式。

正如一位評論者所指出的，雖然某些環境（如透過 strictfp 或 StrictMath 的 JVM）試圖保證嚴格的可重現性，但浮點算術的基本性質仍然是一種近似值。對於需要絕對決定論的應用程式——例如鎖步式（lockstep）遊戲模擬或 ZK 證明生成——這些近似值是不夠的。

凸分解中的「一比特」問題

在幾何學中，cross_sign(A, B, C) 函數是決策的主要訊號。它決定了轉向是左轉、右轉還是共線。當三個點幾乎共線時，一台機器可能會回傳 +1e-12，而另一台則回傳 -2e-13。

這種符號翻轉至關重要，因為凸分解是一個離散過程。一個頂點要麼是凹頂點，要麼不是。如果符號翻轉，另一個頂點就會被識別為凹頂點，導致不同的起始切割點，進而產生完全不同的分解圖形。

解決方案：精確整數算術

為了在 x86、ARM 和 WASM 之間實現位元對位的完全一致，exact-poly 完全放棄了浮點數，轉而使用整數。透過將座標映射到固定比例（例如，在測地學中，1 單位 = 1 微米），該函式庫確保了外積的符號是一個位元邏輯問題，而非近似值問題。

管理整數預算

整數算術需要仔細選擇比例。使用 i64::MAX（約為 $9.2 imes 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