Skip to content

feat: add a stable vector-angle primitive for downstream spherical metrics #249

Description

@acgetchell

Summary

Implement a reusable, numerically stable unsigned angle-between-vectors primitive in la-stack and ship it in the next release, v0.4.7. Delaunay will adopt the released API in v0.8.3 instead of maintaining its own generic angle calculation.

The ownership boundary is deliberate: la-stack owns vector scaling, norms, angle evaluation, and numerical errors. Delaunay retains spherical coordinate/radius invariants, radius compatibility, and conversion from angle to arc length.

Prerequisite: Rust 1.99 baseline

  • Complete chore: upgrade to Rust 1.99 and audit numerical/codegen impact #251 before finalizing the implementation or benchmark evidence in this issue.
  • Develop and validate this API against the completed Rust 1.99 / LLVM 23 baseline that v0.4.7 will actually ship.
  • Treat any Rust 1.98 measurements or codegen observations as historical context only.
  • If the stable-angle implementation materially exercises norm/reduction code whose behavior or performance changed under 1.99, use the refreshed 1.99 evidence when selecting the final formulation.
  • Record relevant Rust 1.99 performance/codegen observations in PERFORMANCE.md where they affect the chosen implementation.

Scientific motivation and reproducer

A scientific-correctness audit found that Delaunay's former clamped acos(dot) calculation erased small separations and could give nonzero self-distance. A local fix and independent regressions currently exist in the Delaunay worktree, pending publication.

Let t = f64::from_bits(0x3e10_0000_0000_0000), exactly 2^-30. Embed these planar directions in any larger ambient dimension:

  • x = [1, 0], y = [1, t]: the exact angle is atan(t), which rounds to approximately 9.313225746154785e-10 radians. The normalized dot product rounds to 1, and acos returns zero.
  • x = y = [1, 1]: after ordinary binary64 normalization, the former calculation returns approximately 2.1073424255447017e-8 radians instead of zero.
  • x = [1, 0], y = [-1, t]: the angle is pi - atan(t), approximately 3.1415926526584705, but the former calculation returns pi.

Reference: W. Kahan, "How Futile Are Mindless Assessments of Roundoff in Floating-Point Computation?" (January 11, 2006), Section 12, "Mangled Angles," pp. 46-48:
https://people.eecs.berkeley.edu/~wkahan/Mindless.pdf

API and implementation scope

  • Provide a checked f64 operation returning an unsigned angle in radians in [0, pi]. Describe its rounded numerical semantics and exceptional regimes; do not claim an exact predicate or certified/correctly rounded result without proof.
  • Reuse existing vector/error conventions. Establish explicit typed behavior for zero vectors, empty inputs, non-finite coordinates, and unequal ambient lengths.
  • Support allocation-free borrowed input suitable for Delaunay's runtime D + 1 coordinate slices. A fixed-size Vector entry point should share the numerical implementation where appropriate. Do not impose the stack-matrix dispatch limit on vector angles.
  • Handle arbitrary operand magnitudes, independently of sphere radius or equal-norm assumptions. The downstream implementation assumes validated spherical inputs and must not be copied unchanged into a general-purpose API.
  • Consider Kahan's norm-weighted half-angle identity with scale-safe norm reductions. In the downstream fix, weighted difference/sum norms d and s give angle = atan2(2ds, (s-d)(s+d)), algebraically equivalent to 2atan2(d,s). The doubled-angle form avoids losing a representable subnormal full angle when its half rounds to zero. Establish range safety for the general input domain before adopting this evaluation.
  • Keep this rounded operation usable without requiring exact arithmetic solely to evaluate the angle. Preserve checked input boundaries and forbid unsafe or relaxed floating-point shortcuts.

Acceptance criteria

  • chore: upgrade to Rust 1.99 and audit numerical/codegen impact #251 is complete and the final implementation/benchmark evidence is based on the Rust 1.99 / LLVM 23 baseline.
  • Document the public contract, units, domain, error behavior, and numerical limitations.
  • Add independent known-angle and bounded integer cross/dot planar oracles rather than only comparing wrappers around the new implementation.
  • Cover parallel, identical, opposite, nearly parallel, nearly antipodal, orthogonal, mixed-scale, large, tiny, signed-zero, and subnormal cases; cover shape and invalid-input errors.
  • Preserve the smallest positive representable angle where the fixture's analytical answer is that value, including f64::from_bits(1) and nearby subnormal values.
  • Exercise ambient lengths 3 through 6 needed by spherical intrinsic dimensions 2 through 5, plus the general API's documented dimension boundaries. Test symmetry and positive rescaling without assuming an intermediate norm is representable.
  • Keep fixture parsing and independent correctness checks outside timed benchmark regions. Compare equivalent stable computations, not the inaccurate acos path, and report adapter overhead separately from kernel cost.
  • Run la-stack's required validation and publish the API in a release before downstream adoption is unblocked.

Downstream context: SphericalMetric::try_distance in src/topology/spaces/spherical.rs and tests/spherical_metric_scientific.rs in acgetchell/delaunay. The current downstream correction passed just check, 125 focused tests, and 786 doctests; those results are evidence for the local spherical fix, not validation of a future general-purpose upstream implementation.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    apienhancementNew feature or requestrustPull requests that update rust codevalidation

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions