README.md

An algebraic alternative to FPSan: the residue homomorphism $\mathbb{Z}[1/2] \to \mathbb{F}_p$

Working notes. Audience: us. Builds on understanding-fpsan.md.

0. The one-sentence difference from FPSan

FPSan encodes a float by a scrambling bijection $\varphi$ of its bit pattern and then does arithmetic in the payload ring $\mathbb{Z}/2^{w}$. That map is not a ring homomorphism: $\varphi(x{+}y) \neq \varphi(x){+}\varphi(y)$. The ring laws hold because the payload operations are the ring operations and the leaves behave like free generators — FPSan realizes (an approximation of) the free commutative ring/exponential-ring on the program's inputs. Scrambling is what makes the leaves look free: the only coincidences are the ones forced by the axioms.

The idea here is the opposite. Make the encoding itself a ring homomorphism, so the model computes the true value of the expression, reduced into a finite field. Instead of the free algebra on the inputs, we get the actual element of $\mathbb{Q}$ the program denotes, fingerprinted mod $p$.

That single change — free model $\to$ value model — is the whole story, and every property below is a consequence of it.

1. The map

Finite binary floats are dyadic rationals: a finite float32 is $m\cdot 2^{e}$ with $m,e\in\mathbb{Z}$ and $\lvert m\rvert \lt 2^{24}$ (significand incl. implicit bit; sign folded into $m$), $e \in [-149, 104]$. They live in

$$\mathbb{Z}[1/2] ;=; {, a/2^k : a\in\mathbb{Z},,k\ge 0 ,} ;=; \mathbb{Z}\big[\tfrac12\big],$$

the localization of $\mathbb{Z}$ at the powers of $2$ — "$\mathbb{Z}$ with $2$ inverted." For any odd prime $p$, $2$ is a unit mod $p$, so there is a unique ring homomorphism

$$\varphi_p : \mathbb{Z}[1/2] \longrightarrow \mathbb{F}_p, \qquad \varphi_p!\left(\tfrac{a}{2^k}\right) = \bar a \cdot (\bar 2^{-1})^{k} \bmod p,$$

forced by $1\mapsto 1$ and $\tfrac12 \mapsto \overline{2}^{-1}$. It is a genuine homomorphism: it respects $+,-,\times$ on the nose.

It is cleaner to name the largest domain. Let $\mathbb{Z}{(p)}$ be the localization of $\mathbb{Z}$ at the prime $p$ — the fractions $a/b$ with $p\nmid b$. It is a local ring with maximal ideal $p\mathbb{Z}{(p)}$ and residue field $\mathbb{Z}{(p)}/p\mathbb{Z}{(p)} \cong \mathbb{F}_p$. Then

$$\mathbb{Z}[1/2] ;\subset; \mathbb{Z}_{(p)} ;\xrightarrow{\ \text{residue}\ }; \mathbb{F}_p$$

and $\varphi_p$ is just the restriction of the residue map. The point of the larger domain: division by any float whose residue is nonzero lands back in $\mathbb{Z}_{(p)}$, even when the exact quotient (e.g. $1/3$) is not dyadic. $\mathbb{F}_p$ being a field is what makes division total.

The model. Carry, for each value, its residue $r=\varphi_p(v)\in\mathbb{F}_p$. Evaluate $+,-,\times,\div$ as field operations on residues. The residue of an expression is then $\varphi_p$ of its exact (un-rounded) rational value, so two expressions with the same exact value get the same residue — automatically, for every identity true over $\mathbb{Q}$, not just the ones we thought to build in. That is strictly more than FPSan's free model honors.

We restrict attention to compact 32-bit encodings throughout. Two variants are developed in §8: a single prime $p$ just below $2^{32}$, and a composite $n=pd$ (still $\lt 2^{32}$) that buys an exact exponential. A working prototype of both lives in algebraic_fpsan_generic.hpp + algebraic_demo.cpp.

2. The central dichotomy: free model vs. value model

This deserves to be made sharp, because it decides everything and it cuts both ways.

• FPSan = free. Inputs are scrambled into algebraically-independent generators; the model is the free (exponential) ring on them. Two expressions match iff they are provably equal from the axioms alone. Consequences: $2{+}2$ does not match $4$; $x{\cdot}(1/x)$ does not match $1$ in general; $a{+}a$ does not match $2a$. The model is blind to the actual numerical values of the leaves.
• $\varphi_p$ = value. Leaves are their true residues; the model is the actual element of $\mathbb{Q}$. Two expressions match iff they have the same exact value (mod $p$). So $2{+}2 = 4$, $x/x = 1$, $a{+}a = 2a$, $(a{+}b)^2 = a^2{+}2ab{+}b^2$, constant-folding, common-subexpression — all match.

Neither dominates universally:

• On the algebraic fragment (polynomials/rational functions of the inputs), the true values have many relations ($2{+}2=4$ really is $4$), so the value model is the faithful one and the free model over-discriminates (it would flag value-preserving rewrites as differences).
• On transcendentals the situation flips — see §6 — because transcendental values are algebraically independent, so freeness becomes the faithful choice there.

So the honest framing of this whole note: $\varphi_p$ is the right tool for the algebraic core of a float program; FPSan-style freeness is the right tool for the transcendental parts; and the interesting object is the hybrid (§8).

3. Injectivity and collisions

We give up injectivity ($p \lt 2^{32}$). Three separate questions hide under "how bad are collisions."

(a) Collision with zero — the one that would hurt — does not happen. $\varphi_n(m\cdot 2^e)=0 \iff n\mid m \iff m=0$, because $\lvert m\rvert \lt 2^{24}$ and the modulus $n \gt 2^{24}$ (both variants: $n\approx 2^{32}$ for 1b, $\approx 2^{31}$ for CRT). So the only finite float with residue $0$ is $\pm 0.0$ — the crucial design constraint that keeps $0$ honest and the zero/infinity story (§7) clean. Nothing nonzero ever silently becomes zero. (This is about residue-$0$; the CRT variant separately has nonzero zero-divisors — §6, §8 — a distinct, division-only issue.)

(b) Leaf collisions (two distinct floats, same residue) are common but mostly harmless. With $N\approx 2^{32}$ finite floats dropped into $p\approx 2^{32}$ residues, occupancy is Poisson($\approx 1$): a constant fraction of floats share their residue with another float. (The image $\bar m,\bar 2^{,e}$ is a union of $\sim 250$ scaled copies of the significand interval — structured, but spread across $\mathbb{F}_p$.) This only matters for a literal-substitution bug: replacing input float $x$ by a different $y$ with $\varphi_p(x)=\varphi_p(y)$. For the main use case — comparing re-orderings / refactors of the same computation on the same inputs — both sides share the same leaves, so leaf collisions are irrelevant.

(c) Circuit-level false matches are fingerprinting at a random prime. Two algebraically different expressions on shared inputs collide iff $p \mid \operatorname{num}(v_A - v_B)$. The difference $v_A-v_B = N/2^k$ has $\lvert N\rvert \lesssim 2^{278}$ (significand $\lt 2^{24}$, exponent span $\sim 254$), so $N$ has at most $\sim 278/32 \approx 9$ prime factors above $2^{32}$. With $\sim 2^{26.5}$ primes in $[2^{31},2^{32}]$, a random such prime divides $N$ with probability $\lesssim 9/2^{26.5} \approx 2^{-23.5}$.

This is exactly Freivalds / Schwartz–Zippel / Rabin-fingerprint territory: checking an identity by evaluating at a random point (here, reducing mod a random prime). Consequences:

• Per comparison, false-match $\approx 2^{-24}$ to $2^{-32}$ with a 32-bit modulus. Staying compact (32-bit), the lever for more margin is repetition: $k$ runs with $k$ different primes multiply the rates (independent fingerprints / CRT). Two runs $\approx 2^{-48}$–$2^{-64}$. The sanitizer is a test tool, so spending time (extra runs) rather than space (a wider word) is the right trade — and it keeps the instrumented program's footprint unchanged (§8).
• Unlike FPSan's fixed scramble — which has a fixed set of colliding pairs that collide on every run — randomizing $p$ makes collisions non-repeatable and adversarially robust: there is no bad pair that always fools you.

The prototype confirms the rate: over 300k distinct random floats, observed leaf collisions track $\binom{N}{2}/n$ to within noise (16 vs ~10.5 at $n\approx2^{32}$, 21 vs ~21.1 at $n\approx2^{31}$).

Verdict: the loss of injectivity is essentially cosmetic for the intended use. The substantive cost is a slightly higher per-prime collision rate, bought back by repeating with another prime.

4. Scrambling: a hard trade-off, not a dial

FPSan scrambles to make leaves free. Can we keep $\varphi_p$'s homomorphism and re-introduce scrambling on top, $v \mapsto \sigma(\varphi_p(v))$? Only if $\sigma$ is a ring automorphism of $\mathbb{F}_p$ — otherwise the homomorphism (the entire point) is destroyed. But $\operatorname{Aut}(\mathbb{F}_p)$ is trivial (the Frobenius $x\mapsto x^p$ is the identity on the prime field). So you cannot scramble inside $\mathbb{F}_p$ at all. Homomorphism and value-scrambling are mutually exclusive; this is not a tunable trade-off but a dichotomy.

What plays the role of the hash seed is instead the choice of $p$. A random prime is the randomness; collisions depend on the seed exactly as in fingerprinting (§3c). So we don't lose randomization — we relocate it from "scramble the values" to "randomize the evaluation point," which is the more principled place for it and is what gives the adversarial robustness above.

What we do lose by not scrambling: diffusion as a debugging aid (FPSan's payloads look random, so a single wrong bit anywhere produces a wildly different payload that is easy to eyeball). $\varphi_p$ residues of related values are related; small structured errors can produce small residue changes. For a detector this is fine (we compare for equality); for forensics FPSan's avalanche is nicer.

5. $+,-,\times,\div$ and casts

This is where $\varphi_p$ shines.

• $+,-,\times$: exact homomorphic images; every ring identity holds for free.
• $\div$: when the modulus is prime (variant 1b), $\mathbb{F}_p$ is a field, so division is total except by residue $0$, and $x/x = 1$ holds always (any $x$ with nonzero residue — i.e. any nonzero float, by §3a). Compare FPSan, whose $\mathbb{Z}/2^{w}$ has zero-divisors and only a parity-preserving involution for "inverse": $x/x=1$ there holds only for odd payloads. The field is a clean win. Division by residue $0$ occurs iff dividing by a genuine $\pm 0.0$ → honest infinity (§7). (The composite CRT variant gives this up for a small zero-divisor rate — §8.)
• Casts / mixed precision — and a real tension (corrected). If a single modulus $n$ is shared across all widths, a value-preserving cast doesn't change the residue, so casts are the identity and mixed precision is unified. But that needs $n$ large enough for the widest type ($n>2^{53}$ for f64) — a payload as wide as the widest type, which is incompatible with the compact, per-width encodings of §8 (each width $w$ has its own $n_w<2^w$). With per-width moduli, casts are not value-faithful: widening f16$\to$f32 would need $\varphi_{n_{32}}(v)$, but the 16-bit residue carries only 16 bits about $v$ and $\varphi_{n_{16}}$ is not injective, so $v$ can't be recovered (an information barrier, not a cleverness gap). So a compact, footprint-faithful sanitizer treats casts as a defined, non-faithful convention (Inf/NaN map across, a finite residue reduces mod the destination $n$; identity at same width) — exactly like FPSan's resize. The "casts are the identity" property is real only in the one-modulus regime, which trades away compactness; §8 keeps compactness and gives this up. (Only lossy narrowing additionally rounds, which §9 abstracts away.)
• Subnormals: also dyadic, handled by the same map with no special case (FPSan punts on them).

What is lost, and it is fundamental: order, magnitude, abs, min/max, comparisons. $\mathbb{F}_p$ is not an ordered field; the residue discards size and sign-as-order entirely. FPSan loses order too (its $\varphi$ is a hash), so this is not a differentiator, but here it is structural: there is no ordered-field quotient to hope for. A reduction like max(x₁,…,xₙ) is simply not representable (it needs the total order); FPSan "solves" min/max by imposing an order on the scrambled payload — associative and reassociation-invariant, but value-infaithful (it may select the wrong element). For us, min/max/abs/comparisons are out of scope: they need a side channel (carry the actual float, or tag).

Cost. Mod-$n$ arithmetic is costlier than FPSan's free mod-$2^{w}$ wraparound (a reduction per op). With a 32-bit modulus the reduction is a single multiply-high (Barrett/Montgomery); a pseudo-Mersenne $p$ makes it a couple of adds. We stay 32-bit on purpose (§8): footprint fidelity matters more than the per-op cost for a sanitizer.

6. Transcendentals: exp is recoverable (CRT); the rest stay free

exp, log, sin, cos, sqrt, … are not rational functions, so the homomorphism says nothing directly. The question is whether we can build an exp with the right identity $\exp(a{+}b)=\exp(a)\exp(b)$, the way FPSan builds $g^{p}$.

As a function of the mod-$p$ residue, no. Such an exp would be a homomorphism $(\mathbb{F}_p,+)\to(\mathbb{F}_p^\times,\times)$; since $\gcd(p,,p-1)=1$ the only one is trivial. So variant 1b (single prime) cannot honor the exponential law — its exp is just a tagged hash token, and the prototype duly finds the law holding $0/50000$ times (i.e. never). FPSan escapes this only because $\mathbb{Z}/2^{w}$'s additive and unit groups share the prime $2$.

As a function of a second, mod-$d$ residue, yes. The value-level map $\exp:(\mathbb{Z}[1/2],+)\to(\mathbb{F}_p^\times,\times)$ does exist: pick $g$ of odd order $d$, set $\exp(1)=g$; the odd-order $2^{n}$-th roots are unique, giving the closed form $\exp(v)=g^{,v\bmod d}$, which satisfies the law exactly. The catch: it depends on $v\bmod d$, not $v\bmod p$ — it does not factor through the mod-$p$ residue (else $h(pw)=h(w)^{p}=h(w)$ forces triviality). So we must carry $v\bmod d$.

CRT keeps this compact (variant CRT). Carrying $(v\bmod p,,v\bmod d)$ is, by CRT, carrying $v\bmod n$ with $n=pd$ — one residue, one 32-bit word. With $p\equiv1\pmod d$ and $g$ of order $d$ in $(\mathbb{Z}/n)^\times$, the exponent $v\bmod d = r\bmod d$ is read straight off the single residue, and $\exp(v)=g^{,r\bmod d}$. The prototype's CRT variant honors $\exp(a{+}b)=\exp(a)\exp(b)$ exactly ($50000/50000$). So honoring exp costs neither footprint nor a second word — it costs (see §8): a composite modulus, hence zero-divisors at rate $\sim 1/p+1/d$ (observed $19/300\mathrm{k}$), and an exp whose image is only the order-$d$ subgroup, so exp results collide at $\sim 1/d$ (observed: 300k inputs → only $\approx d$ distinct exp outputs).

log is the dual of exp and works on the same channel — the earlier "forced trivial by zero / not a function of the residue" claim was wrong (it holds only for a log defined on the whole ring including $0$; on the unit group, with $\log 0$ a sentinel, a genuine homomorphism exists). Where exp embeds $\mathbb{Z}/d$ into the multiplicative order-$d$ subgroup $\langle g\rangle$, log embeds it into the additive order-$d$ subgroup ${0, n/d, 2n/d, \dots}$ (multiples of $n/d=p$, closed under mod-$n$ addition, $\cong\mathbb{Z}/d$): $$\log(r) = \tfrac{n}{d}\cdot \operatorname{dlog}_g\big(r\text{'s order-}d\text{ component}\big),$$ so $\log(xy)=\log(x)+\log(y)$ holds exactly in $\mathbb{Z}/n$ and $\log$ inverts $\exp$. The price vs exp: a discrete logarithm (cheap for the small $d$ here — brute force, or a precomputed table on device) instead of one modexp, plus it ignores input sign. Implemented in the Exp variants.

exp2/log2 ride the same channel by a base change. The base family $\exp_b(v)=g^{,Kv\bmod d}$ is, for each fixed $K$, again an additive→multiplicative homomorphism, with $\log_b$ its exact inverse (divide the discrete log by $K\bmod d$); so exp2/log2 are honored exactly in the Exp/Trig variants. The inter-base constant is $\log_2 e$ — irrational, hence no residue — so $K$ is a fixed pseudo-random unit $\bmod,d$ (the role Triton's rcpLog2 magic constant plays): each base keeps its own homomorphism and $\log$ inverse, but no numeric relation between bases is claimed. (Since $\langle g\rangle$ is the unique order-$d$ subgroup, necessarily $\exp_2(x)=\exp(x)^{K}$ — Triton has the identical $\exp=\exp_2^{,\mathrm{rcpLog2}}$ relation.) This is strictly more than Triton, which has a genuine exp2 but leaves log2 an opaque token.

sin/cos need a genuine order-$d$ rotation, which requires the circle group's order to be divisible by $d$ — i.e. $p\equiv1\pmod4$ (circle order $p-1$), not the Sophie-Germain $p=2d+1$ ($\equiv3\pmod4$, circle order $p+1$, $d\nmid p+1$). So they live in a dedicated Trigonometry variant on $p=4d+1$ primes (§8): $\cos(x)=\operatorname{Re}(\omega^{,x\bmod d})$, $\sin(x)=\operatorname{Im}(\omega^{,x\bmod d})$ with $\omega$ an order-$d$ element of $(\mathbb{Z}/n)[i]$ ($i^2=-1$) — a rotation in the $F_p$ factor, identity in the $F_d$ factor. The angle-addition formulas then hold exactly and $\cos^2+\sin^2=1$. That variant keeps exp+log too (still $d\mid p-1$), at a $\sim!\sqrt2$ smaller $d$ (more collisions) — the price of trig.

sqrt, erf, tanh, … have no usable identity and stay hash tokens — and that is correct, not a fallback: by Lindemann–Weierstrass / Schanuel, transcendental values at distinct algebraic arguments are algebraically independent, so a fresh free generator per call is the faithful model.

fragment	true-value structure	model here
algebraic ($+,-,\times,\div$)	richly related ($2{+}2=4$)	value: $\varphi_n$ residue
$\exp$	$\exp(a{+}b)=\exp(a)\exp(b)$	structured: $g^{,v\bmod d}$ (Exp/Trig)
$\log$	$\log(xy)=\log x+\log y$	structured: $\tfrac{n}{d}\operatorname{dlog}_g$ (Exp/Trig)
$\exp_2,\log_2$	base-$b$ analogues of $\exp,\log$	structured: base change $K$ on the $g$ channel (Exp/Trig)
$\sin,\cos$	angle-addition	structured: $\operatorname{Re}/\operatorname{Im},\omega^{,v\bmod d}$ (Trig variant, $p=4d{+}1$)
$\sqrt,\mathrm{erf},\dots$	algebraically independent	free: hash token

7. Zero, infinity, NaN, signs

Finite floats are in $\mathbb{Z}[1/2]$; $\pm\infty$ and NaN are not. Extend the codomain to the projective line plus an absorbing symbol:

$$\widehat{\mathbb{F}_p} ;=; \mathbb{P}^1(\mathbb{F}_p)\ \sqcup\ {\mathrm{NaN}} ;=; \mathbb{F}_p \cup {\infty} \cup {\mathrm{NaN}}.$$

• finite nonzero $\mapsto$ its residue in $\mathbb{F}_p^\times$; $\pm 0.0 \mapsto 0$; $\pm\infty \mapsto \infty$; NaN $\mapsto$ NaN.
• $\mathbb{P}^1(\mathbb{F}_p)$ gives $x/0=\infty$ for $x\neq 0$ for free, and the Möbius/IEEE-shaped rules $\infty+\text{finite}=\infty$, $\infty\cdot x=\infty$ ($x\neq0$). NaN is absorbing, and seeds the indeterminate forms $\infty+\infty,\ \infty-\infty,\ 0\cdot\infty,\ 0/0,\ \infty/\infty \mapsto \mathrm{NaN}$. With unsigned $\infty$, even $\infty+\infty$ is indeterminate — IEEE resolves it via the sign we dropped — so the model emits NaN slightly more freely than IEEE, but only at the already-non-finite fringe.

The §3a fact ($0$ is hit only by true zero) is what makes this principled: $1/x=\infty$ exactly when $x$ is a genuine zero, never because some nonzero float collided onto $0$. So $0$ and $\infty$ are honest. This is a better Inf/NaN story than FPSan, which models none of it.

Not modeled (out of scope — these compact variants carry no sign bits):

• Signed zero / signed infinity. $+0.0,-0.0\mapsto 0$ and $\pm\infty\mapsto$ one $\infty$; $\mathbb{F}_p$ has one zero, $\mathbb{P}^1$ one pole. (Negation $\varphi_n(-v)=-\varphi_n(v)$ is exact on finite values — only the $\pm0$ and $\pm\infty$ poles merge.)
• (CRT variant) division by a nonzero zero-divisor poisons to NaN, not $\infty$ — a units issue (§8), separate from the honest $1/0=\infty$.

8. The three compact variants

Everything above instantiates as one of three 32-bit designs. All carry a single residue plus the projective+NaN extension of §7; they differ only in the modulus.

Variant 1b — single prime. $n=p$ just below $2^{32}$ (the prototype uses $2^{32}-5$). $\mathbb{Z}/n=\mathbb{F}_p$ is a field: division total, $x/x=1$ always, no zero-divisors; cleanest algebra and best collision margin ($\sim2^{-32}$). No exponential law — exp and all transcendentals are hash tokens.

Variant CRT — composite $n=pd$. $p,d$ distinct odd primes, $p\equiv1\pmod d$, $n \lt 2^{32}$ (prototype: a Sophie-Germain pair near $2^{15}$, $n\approx2^{31}$). $\mathbb{Z}/n\cong\mathbb{F}_p\times\mathbb{F}_d$ — a product of fields, not a field. Buys the exact exp and log homomorphisms ($\exp(v)=g^{,v\bmod d}$, and $\log$ its dual; §6). Costs:

• zero-divisors at rate $\sim 1/p+1/d$: division by one is undefined and poisons to NaN ($x/x\ne1$ there). Observed $19/300\mathrm{k}$.
• exp/log collisions at $\sim 1/d$: their image is only the order-$d$ subgroup. Observed: 300k inputs → $\approx d$ distinct exp outputs.
• a slightly smaller algebraic modulus → marginally more leaf collisions.

Prefer $n=pd$ (two distinct primes — a product of fields) over $\mathbb{Z}/p^2$: same trick (via the order-$p$ principal units) but with nilpotents, which are algebraically uglier and less value-faithful.

Variant Trig — composite $n=pd$ on $p=4d+1$. Like CRT, but $p\equiv1\pmod4$, so the circle group (order $p-1$, divisible by $d$) admits a genuine order-$d$ rotation. It carries exp, log, and sin/cos (§6) — all on the same $d$-channel. The price is a $\sim!\sqrt2$ smaller $d$ for a given $n$ (so $\sim!\sqrt2\times$ more exp/log/leaf collisions) than the Sophie-Germain CRT variant. Opt-in for sin/cos-heavy code.

	1b (prime)	CRT ($p=2d{+}1$)	Trig ($p=4d{+}1$)
modulus	$p\approx2^{32}$	$n=pd\approx2^{31}$	$n=pd\approx2^{32}$
algebra	field; $x/x=1$	product of fields; zero-div $\sim1/p{+}1/d$	same as CRT
exp / log	✗ (tokens)	✓	✓
sin / cos	✗ (tokens)	✗ (tokens)	✓ (order-$d$ rotation)
exp/log image	—	order $d$	order $d/\sqrt2$

Both share the hybrid transcendental scheme: carry $\varphi_n(\text{exact value})$ for $+,-,\times,\div$ and casts (exact, value-faithful, precision-agnostic, honest $0/\infty/\mathrm{NaN}$); at a transcendental call, either apply the structured map ($\exp$, in the CRT variant) or mint a fresh free generator $t=H(f,r_x)$ (log, sqrt, … — and all transcendentals in 1b). Faithful by §6.

A prototype of both — algebraic_fpsan_generic.hpp and algebraic_demo.cpp — passes the ring-homomorphism, ring-law, Inf/NaN, and (CRT) exp-homomorphism checks and reports the collision / zero-divisor / exp-image statistics quoted above.

Resolved and remaining

• exp / log — resolved. $\exp(a{+}b)=\exp(a)\exp(b)$ holds via $g^{v\bmod d}$ (the worry that the prime field forbids it was about exp as a function of the mod-$p$ residue; the mod-$d$ residue, folded in by CRT, delivers it). log is its dual, into the additive order-$d$ subgroup (§6). Extra margin, if needed, comes from repeating with different prime pairs (time, not space — §3).
• sin / cos — resolved, in a dedicated variant. A genuine order-$d$ rotation needs $p\equiv1\pmod4$, so it lives in the Trig variant ($p=4d+1$), carrying exp+log+sin+cos at a $\sim!\sqrt2$ smaller $d$ (§6, §8).
• Order / min/max / abs / comparisons — open, and fundamental. $\mathbb{F}_p$ is unordered; no sign or exponent trick recovers a total order. This is the real limitation of the approach, shared with FPSan (which fakes it with payload-order, sacrificing value-faithfulness). A side channel (the actual float, or a tag) is the only route.
• Rounding — out of scope by design (§9).

9. A note on rounding (shared boundary with FPSan)

Both systems carry exact model values and never round, so both answer "are these the same up to exact algebra?" and are deliberately invariant to reassociation and to rounding-order. The sanitizer flags rewrites that change the exact value, not ones that merely reround. This is a feature (it is what lets a reduction in two orders compare equal), and it is the same boundary FPSan draws. $\varphi_n$ does not change it.

A corollary worth stating, since it surprises: overflow to $\infty$ is not modeled. The model is exact and carries no magnitude ($\mathbb{F}_p$ is unordered), so a sum of finite values is always a finite residue — never $\infty$. The only source of $\infty$ is division by a true zero. Thus 1/(sum of huge values) is an ordinary finite inverse here, where IEEE would overflow to $\infty$ and then give $0$; both behaviors are deliberate consequences of abstracting rounding and magnitude away.

10. Scorecard: FPSan vs. the three algebraic variants

A property-by-property comparison of the four shipping semantics. Any FPSan-style sanitizer replaces floating-point ops with a deterministic, reassociation-invariant fingerprint: two runs that should agree (reference vs. optimized, eager vs. fused) get identical fingerprints, and a mismatch pinpoints where the numerics diverged. Reassociation-invariance is just associativity plus commutativity (rows 6–7); the variants then differ in which further identities the fingerprint preserves. The FPSanLikeTriton column is read from Triton's FpSanitizer.cpp; the others from this prototype.

#	property / behavior	FPSanLikeTriton	FPSanAlgebraic	FPSanAlgebraicExponentials	FPSanAlgebraicTrigonometry
	— model —
1	leaf encoding	scramble bijection of the IEEE bits	residue φₙ(value)	residue φₙ(value)	residue φₙ(value)
2	ring	Z/2ʷ (w = bit width)	𝔽ₚ, p prime (a field)	Z/(p·d), p = 2d+1	Z/(p·d), p = 4d+1
3	deterministic, platform-independent	✅	✅	✅	✅
	— ring identities —
4	0 + x == x	✅ ①	✅	✅	✅
5	1 * x == x	✅ ①	✅	✅	✅
6	commutativity, associativity of +, *	✅	✅	✅	✅
7	distributivity a*(b+c) == a*b + a*c	✅	✅	✅	✅
8	x - x == 0, x + (-x) == 0	✅	✅	✅	✅
	— exact value relations (φₙ is a ring homomorphism) —
9	any rational-function identity valid for the exact (un-rounded) operand values holds of the fingerprints, within one width	❌	✅	✅	✅
10	…e.g. constant folding: 2+2 == 4, 2*3 == 6, 0.5+0.5 == 1	❌	✅	✅	✅
11	…e.g. symbolic: x+x == 2*x, (x+1)*(x-1) == x*x - 1	❌ ②	✅	✅	✅
	— division & field structure —
12	x / x == 1 for every x ≠ 0	🟡 ③	✅	🟡 ④	🟡 ④
13	(a / b) * b == a (b a unit)	🟡 ③	✅	🟡 ④	🟡 ④
14	no zero-divisors (a*b==0 ⟹ a==0 ∨ b==0)	❌	✅	❌ ⑤	❌ ⑤
	— transcendental / special functions —
15	exp(a+b) == exp(a)*exp(b)	✅	❌	✅	✅
16	exp2(a+b) == exp2(a)*exp2(b)	✅	❌	✅	✅
17	log(x*y) == log(x)+log(y)	❌ ⑥	❌	✅	✅
18	log2(x*y) == log2(x)+log2(y)	❌ ⑥	❌	✅	✅
19	exp(log(exp v)) == exp v (log inverts exp)	❌ ⑥	❌	✅	✅
20	cos(a+b) == cos a*cos b - sin a*sin b	✅ ⑦	❌	❌	✅
21	cos²x + sin²x == 1	✅ ⑦	❌	❌	✅
22	how exp/exp2 realized	✅ modular exp cˣ in Z/2ʷ	🟡 token ⑩	✅ gˣ ᵐᵒᵈ ᵈ	✅ gˣ ᵐᵒᵈ ᵈ
23	how log/log2 realized	🟡 token	🟡 token	✅ discrete log in ⟨g⟩	✅ discrete log in ⟨g⟩
24	how cos/sin realized	✅ (3,4,5) rotor in Z/2ʷ	🟡 token	🟡 token	✅ order-d rotor in (Z/n)[i]
25	sqrt, rsqrt, erf, floor, ceil, …	🟡 token	🟡 token	🟡 token	🟡 token
26	exp/exp2 image-collision rate	✅ ~2⁻ʷ (large image)	✅ ~2⁻ʷ (token)	🟡 ~1/d ≈ 1/√(2ʷ)	🟡 ~1/d ≈ 1/√(2ʷ)
	— infinity & NaN —
27	1/0 is a single unsigned ∞ (+∞, −∞ identified)	❌ ⑧	✅	✅	✅
28	1 / ∞ == 0	❌ ⑧	✅	✅	✅
29	x + ∞ == ∞, x * ∞ == ∞ (finite x ≠ 0)	❌ ⑧	✅	✅	✅
30	indeterminates ∞±∞, 0*∞, ∞/∞, 0/0 → NaN	❌ ⑧	✅	✅	✅
31	NaN is absorbing (NaN ∘ x == NaN)	❌ ⑧	✅	✅	✅
	— miscellaneous —
32	min/max/comparisons follow the IEEE numeric order	❌ ⑨	❌ ⑨	❌ ⑨	❌ ⑨
33	cross-width casts	sign-resize the payload ⑪	reduce mod dest n ⑪	reduce mod dest n ⑪	reduce mod dest n ⑪
34	subnormals	no special case ⑫	no special case ⑫	no special case ⑫	no special case ⑫
35	footprint	= the value (w bits)	= the value (w bits)	= the value (w bits)	= the value (w bits)
36	leaf-collision rate	~2⁻ʷ	~2⁻ʷ	~2⁻ʷ	~2⁻ʷ
37	collisions re-rollable: a fresh prime gives independent blind spots	❌ ⑬	✅ ⑬	✅ ⑬	✅ ⑬
38	per-op cost	mask to w bits	mod-p reduce	mod-n reduce (+ O(d) dlog for log/log2)	mod-n reduce (+ dlog)

Legend: ✅ holds exactly · ❌ does not hold · 🟡 holds with a caveat.

Notes. ① Triton's leaf scramble is tuned so embed(0.0)=0 and embed(1.0)=1; that is why the bare 0/1 identities (rows 4–5, 8) survive even though the encoding is otherwise a bit scramble that ignores values. ② x+x = 2·embed(x) but 2*x = embed(2.0)·embed(x), and embed(2.0) ≠ 2 under the scramble — so the two sides disagree. ③ Triton divides by the ring inverse of (denominator | 1), forcing the divisor odd: x/x == 1 for odd payloads, not for the ~50% that are even. Deterministic either way. ④ The Exp/Trig moduli are composite (n = p·d), so a residue is a zero-divisor at rate ≈ 1/p + 1/d; x/x on such a value poisons to NaN. Every unit (the overwhelming majority) satisfies x/x == 1. ⑤ Only FPSanAlgebraic is an integral domain; the CRT-based variants trade that for the exp/log channel. ⑥ Triton has genuine exp and exp2 but leaves log/log2 tokens, so they do not compose. The Exp/Trig variants make log/log2 the discrete-log inverses of exp/exp2. (exp2/log2 ride the same order-d channel via a fixed base change exp2(v)=g^{Kv}; log2(e) is irrational so, as with Triton's rcpLog2, no numeric relation between the bases is claimed — only each base's own homomorphism and inverse.) ⑦ Triton's cos/sin are Re/Im of (a+bi)ˣ with (a,b) = (−3/5, 4/5), a norm-1 Pythagorean rotor in Z/2ʷ — so angle addition and cos²+sin² == 1 hold. The Trig variant reproduces this on the φₙ residue, where it coexists with the exact value relations (rows 9–11). ⑧ Triton carries the IEEE ∞/NaN bit patterns as ordinary scrambled payloads and applies ring arithmetic to them, so none of the ∞/NaN laws hold; they are not modeled. The algebraic variants use the projective line ℙ¹ plus an absorbing NaN (§7). ⑨ No finite ring carries an order compatible with its arithmetic. All four compute min/max on a signed residue/payload representative — deterministic, commutative, reassociation-invariant, but not the IEEE numeric order. ⑩ token (rows 22–25): a deterministic, op-distinct scramble — equal inputs give equal outputs and distinct ops give distinct outputs, but it honors no real-math identity. This is the correct model for a function with no usable algebraic structure: by Lindemann–Weierstrass / Schanuel, transcendental values at distinct algebraic arguments are independent, so a fresh free generator per op is faithful (§6). In rows 22–25 the marker reads differently from the ✅/❌ identity rows above: ✅ flags a realization that carries a genuine identity (the rows 15–21 laws), 🟡 a bare token (supported, but structureless) — so a column's ✅s are exactly the transcendental laws it keeps. ⑪ No model is value-faithful across widths; the cast is the identity only at equal width. Triton sign-extends / truncates the (scrambled) payload — chosen so a sanitized mixed-precision program fingerprint-matches a Triton reference run that does the same. The algebraic variants reduce mod the destination modulus, which a per-width modulus forces: widening the value is information-theoretically uncomputable from the narrow residue (an information barrier, not a gap; §5). ⑫ Neither model special-cases subnormals (no flush-to-zero). A subnormal is still an exact dyadic value, so φₙ encodes it exactly like a normal and it obeys the same value relations; FPSan scrambles its bit pattern like any other. Listed because many fp tools do special-case subnormals — here nothing is needed. ⑬ The collision set — which distinct inputs land on the same fingerprint — is fixed for FPSan's single tuned scramble: the same blind spots on every run. Each algebraic prime has its own independent collision set, so the 1 and 2 variants (or any freshly drawn prime) catch a coincidental match the other missed.

Bottom line. FPSanLikeTriton tracks the structure of a computation, not its values: it nails the 0/1 ring identities by construction and ships genuine exp, exp2, and cos/sin, but no value coincidence (2+2==4) survives the scramble, and ∞/NaN are unmodeled. The algebraic variants make the encoding itself a ring homomorphism, so every rational-function identity holds within a width and the ∞/NaN story is principled — at the cost of mod-n arithmetic and a few bits of collision margin (recoverable by repeating with the 2 variant's second prime). FPSanAlgebraic is the clean field — pick it when no transcendental law is needed; FPSanAlgebraicExponentials adds the exact exp/exp2/log/log2 homomorphisms (zero-divisors as the price); FPSanAlgebraicTrigonometry adds sin/cos on top, at a ≈√2 smaller d. The one limitation shared by all four, not fixable by any sign/exponent trick, is order (min/max/comparisons): a finite ring has no compatible order.