Floats Don't Agree with Themselves

The author recounts a frustrating debugging experience where a polygon-overlap test produced different results on local and server environments despite identical code and input. This discrepancy stemmed from the non-deterministic behavior of floating-point arithmetic, specifically how IEEE 754 defines storage but leaves intermediate computation details (like FMA contraction or x87 register precision) up to implementation, leading to single-bit differences that cascade into divergent geometric decompositions.

• The Core Problem: Floating-point behavior varies across architectures (x86 vs. WASM/ARM), toolchains (LLVM's FMA usage), and flags (-ffast-math, denormal handling), causing operations like cross products to flip signs near zero. This breaks discrete geometric algorithms like convex decomposition.
• The Solution: Integer Arithmetic: The exact-poly library eschews floats entirely, using i64 for coordinates and i128 for intermediate calculations (like cross products) to ensure exact, reproducible results.
• Scaling and Precision: Users must choose a SCALE (e.g., micrometers for geodesy) at compile time. This allows for precise calculations within i64 bounds (up to 9.2 × 10^18), with i128 providing sufficient headroom for products.
• Exact Invariants: The library maintains exact equality for properties like area conservation, a feat impossible with floating-point numbers due to inherent rounding.
• Convex Decomposition: It employs a cascade of algorithms (ExactPartition, Bayazit, EarClip + Hertel-Mehlhorn) for convex decomposition. If one fails, the next tries, with a 'rotation' heuristic as a last resort.
• Integer-Specific Pitfalls: The article details unique challenges of integer geometry, such as correctly handling midpoints (round_div2), snapping Steiner points, and careful bookkeeping of synthetic vertices.
• Limitations: exact-poly explicitly rejects self-intersecting polygons, polygons with holes, and excessively large inputs, prioritizing determinism over universal applicability.
• Guaranteed Determinism: The library promises bit-for-bit identical output across diverse compilation targets—from browsers (WASM) to servers (x86_64), embedded systems, and even ZK circuit IRs—by eliminating all float dependencies.
• Robust Testing: Tests are property-based, emphasizing invariants like area conservation, and include regression tests for past edge cases and maximum coordinate overflow.

The author concludes that while floats offer precision, integer arithmetic offers agreement and determinism, which is crucial for applications requiring consistent results across distributed systems or varied hardware. The algorithms are well-established, but their re-implementation using integer math under i128 is the key to solving these long-standing reproducibility issues.