Repository navigation
Evaluate GMP/MPFR-free arithmetic without weakening exact predicates #140
Description
Problem
CDT++ currently uses GMP/MPFR for two separate contracts:
- Geometry uses
CGAL::Exact_predicates_inexact_constructions_kernelfor robust Delaunay predicates, including adversarial near-degenerate and co-spherical inputs. We need exact predicates where topology depends on their sign, but we have not isolated which GMP/MPFR components this kernel actually requires in the pinned CGAL 6.2 configuration. - The action and Metropolis-Hastings paths directly use
CGAL::Gmpfrand MPFR at 256-bit precision. Existing tests require distinctions that collapse when converted todoubleand positive probabilities below thelong doublerange. CGAL::Gmpzfis also exposed throughSettings.hppand a utility conversion path; its production necessity should be confirmed.
PR #139 exposed an operational cost: clean macOS, Linux, and CodeQL builds failed while building MPFR because libtool 2.6.2 was incompatible with MPFR-generated files expecting 2.5.4. Restoring the compatible pin fixes CI, but the incident gives us a concrete reason to revisit the backend decision from #102.
Goal
Determine whether CDT++ can remove or reduce its GMP/MPFR dependency in favor of faster or simpler CGAL-supported arithmetic options without weakening:
- exact geometric predicates required for valid Delaunay topology;
- deterministic behavior on near-degenerate and co-spherical inputs;
- 256-bit action-calculation accuracy;
- Metropolis-Hastings behavior for extremely small nonzero probabilities.
Do not conflate exact predicates, exact constructions, and high-precision transcendental calculations. They may need different backends.
Evaluation plan
- Inventory every production and test-only GMP/MPFR use and map it to the property it provides.
- Enumerate the exact CGAL predicates on which CDT++ topology depends, including orientation and side-of-sphere decisions.
- Verify which arithmetic backends and kernel configurations are officially supported by the pinned CGAL 6.2 release.
- Compare at least:
- the current EPICK plus GMP/MPFR configuration;
- a GMP-free exact-predicate configuration using CGAL-supported built-in or Boost.Multiprecision types, if available;
- a hybrid configuration that changes the geometric backend while retaining high-precision action arithmetic;
- a replacement for the action/probability backend only if it supports the required transcendental functions, precision, rounding policy, and sub-
long doublebehavior.
- Benchmark representative configurations for:
- clean dependency and build time;
- incremental compile time and binary size;
- triangulation construction and insertion;
- move preparation/execution and representative simulation throughput;
- peak memory.
- Compare correctness against the current implementation as an oracle before considering any migration.
Correctness gates
- Existing near-degenerate and co-spherical EPICK fixtures remain unchanged.
- Deterministic reference fixtures and scientific observables remain unchanged within explicitly justified tolerances.
- Action values that are distinct at 256-bit precision remain distinguishable.
- Acceptance probabilities that are positive below the
long doublerange remain positive at the decision boundary. - Supported compiler, sanitizer, CodeQL, and CI configurations build from a clean dependency cache.
Acceptance criteria
- A decision table maps each GMP/MPFR use to its required guarantee, supported alternatives, and measured tradeoffs.
- Candidate backends are supported by CGAL 6.2 documentation rather than relying on incidental implementation details.
- Benchmarks are reproducible and include clean-build cost, runtime, and memory.
- Exact-predicate and scientific-numerics results meet all correctness gates.
- GMP/MPFR removal is recommended only when an alternative is at least as correct and demonstrates a meaningful build, runtime, portability, or maintenance benefit.
- The final decision and rationale are documented. Any production migration is split into separately scoped implementation work.
Related work
- Follow-up to Modernize CGAL 6.2 integration for current best practices #102, which established the existing kernel and exact-arithmetic decision criteria.
- Motivated by the MPFR/libtool clean-build failures diagnosed in fix(ci): require reviewed Dependabot merges and refresh tooling #139.
This issue is an evaluation spike and does not by itself authorize a backend migration or make the v1.0.0 release depend on that migration.
Activity
test(arithmetic): evaluate Boost alternatives to GMP and MPFR