Skip to content

Re-normalize round53's rounded mantissa back into 53 bits - #1524

Closed
sergey-shandar wants to merge 5 commits into
mainfrom
claude/epic-fermi-ylt8o0
Closed

Re-normalize round53's rounded mantissa back into 53 bits#1524
sergey-shandar wants to merge 5 commits into
mainfrom
claude/epic-fermi-ylt8o0

Conversation

@sergey-shandar

@sergey-shandar sergey-shandar commented Aug 13, 2026

Copy link
Copy Markdown
Contributor

Fixes fjs/types/bigfloat/todo/round53-overflow.md (deleted here).

Problem

round53 (fjs/types/bigfloat/module.f.mjs) reduced the mantissa to 54 bits with decreaseMantissa(...)(twoPow54) and then rounded to 53 by adding the dropped bit back, but neither return path re-normalized afterwards. When the reduced mantissa was all ones, m53 = 2^53 - 1 and the round-up carried into a 54th bit, so decToBin returned a mantissa of exactly 2^53 — one bit wider than the 53 bits the function is named for:

decToBin([0x3f_ffff_ffff_ffffn, 0])   // 2^54 - 1
// before => [0x20_0000_0000_0000n, 1]   mantissa = 2^53, 54 bits
// after  => [0x10_0000_0000_0000n, 2]   mantissa = 2^52, 53 bits

The numeric value was correct (2^53 * 2^1 = 2^54); only the representation was out of range. That still matters, because the point of decToBin is to produce the IEEE-754 binary64 significand: any consumer assuming abs(m) < 2^53 — to emit the significand field, to compare two BigFloats by mantissa, or to round-trip through a number — was wrong on exactly these inputs. Both branches of the rounding decision could reach the carry.

Nothing consumes decToBin today (the JSON/DJS/JS tokenizers import only multiply and the BigFloat type), so no current caller could observe the oversized mantissa — this is a latent-contract fix, not a user-visible behavior change.

Fix

Both rounding paths now converge on one return through decreaseMantissa([m53 + up, e53])(twoPow53), which puts a carried mantissa back in range. The check lives in one place rather than being duplicated across two returns, and it reuses the same normalization helper the function already applies on the way in. The carried value is exactly 2^53, whose dropped bit is 0, so the shift needs no second rounding decision and leaves the value unchanged.

The alternative — declaring a 54-bit mantissa an acceptable output and documenting the postcondition as "value-correct, not normalized" — was rejected in the issue: it pushes normalization onto every future consumer.

The mantissa-width postcondition is now documented in JSDoc on decToBin, with the carry rationale on round53.

Proofs

New roundingCarry group in fjs/types/bigfloat/proof.f.mjs covering both carry paths and both signs, written as binary literals to match the surrounding proofs:

  • ±(2^54 - 1) (0x3f_ffff_ffff_ffffn) — the tie-to-even path (m53 = 2^53 - 1 is odd, so it rounds up), expecting [±2^52, 2], i.e. the unchanged value ±2^54;
  • ±(2^55 - 1) (0x7f_ffff_ffff_ffffn) — a non-tie carry (reducing to 54 bits drops a 1), expecting [±2^52, 3], i.e. ±2^55.

Each goes through a shared assertDecToBin helper that asserts abs(m) < 2^53 alongside the expected mantissa and exponent. The width check is deliberately on the magnitude: m < 2^53 is vacuous for a negative mantissa and would have passed against the old broken -0x20_0000_0000_0000n.

Checks

  • npx tsc — clean.
  • Full suite (npm start test) — 2535 pass, 0 fail; the pre-existing decToBin / roundingPositive / roundingNegative expectations are unchanged by the fix.
  • npm run ci-update — no drift.

🤖 Generated with Claude Code

https://claude.ai/code/session_013jmZZ85gA9r4B2fPpemvRQ

`round53` reduced the mantissa to 54 bits and then rounded to 53 by adding
the dropped bit back, without re-normalizing. When the reduced mantissa was
all ones, the round-up carried into a 54th bit and `decToBin` returned a
mantissa of exactly `2^53` — value-correct, but one bit wider than an
IEEE-754 binary64 significand.

Both rounding paths now converge on a single `decreaseMantissa(...)(twoPow53)`
return, which puts the carried value back in range; the carry is exactly
`2^53`, whose dropped bit is `0`, so no second rounding decision is needed.
The mantissa-width postcondition is documented on `decToBin`, and the proofs
cover the tie and non-tie carries for both signs, asserting on the magnitude
(`m < 2^53` is vacuous for a negative mantissa).

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013jmZZ85gA9r4B2fPpemvRQ
@cloudflare-workers-and-pages

cloudflare-workers-and-pages Bot commented Aug 13, 2026

Copy link
Copy Markdown
Contributor

Deploying with  Cloudflare Workers  Cloudflare Workers

The latest updates on your project. Learn more about integrating Git with Workers.

Status Name Latest Commit Preview URL Updated (UTC)
✅ Deployment successful!
View logs
functionalscript 42f4c4a Commit Preview URL

Branch Preview URL
Aug 13 2026, 12:43 PM

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013jmZZ85gA9r4B2fPpemvRQ

@o2alexanderfedin o2alexanderfedin left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Approving. The fix is correct, and I verified it by exhaustive/differential sweep rather than by re-running the examples in the proof.

What the change actually does

The two return sites in round53 collapse into one up expression plus a
decreaseMantissa(...)(twoPow53) on the result. I checked the collapse is
semantically identical to the old branches: up = cond ? m53 & 1n : o54 is
exactly odd on the tie path and o54 otherwise. So the only behavioural
delta is the re-normalization.

The carry case is m53 + up === 2^53 exactly, which decreaseMantissa shifts
once to 2^52 with e + 1. The dropped bit is 0, so no second rounding
decision — the JSDoc's argument holds.

Boundary inputs, derived independently

I constructed the all-ones and just-below cases myself rather than trusting the
proof's choices. Mantissa bit-widths in brackets:

input main this PR correctly-rounded double
2^54 - 2 (just below) [9007199254740991, 1] (53) same 18014398509481982
2^54 - 1 (54 ones, tie) [9007199254740992, 1] (54) [4503599627370496, 2] (53) 18014398509481984
2^55 - 1 (non-tie) [9007199254740992, 2] (54) [4503599627370496, 3] (53) 36028797018963970
2^100 - 1 [9007199254740992, 47] (54) [4503599627370496, 48] (53) 1.2676506002282294e30
99999999999999999e-17 [9007199254740992, -53] (54) [4503599627370496, -52] (53) 1

The just-below case does not carry on either side, which is the control I
wanted: the fix is not shifting unconditionally.

Exhaustive / systematic verification

Two sweeps, both against a trusted oracle.

Oracle sweep — 5,228,298 inputs (every mantissa 1..200000 at
e ∈ {0,±1,±2,±3,-5,-10}, the top 4096 and the ±2048 neighbourhood of every
power of two up to 2^70, plus 300k pseudo-random (m, e) with |m| up to 90
bits and e ∈ [-20, 20], both signs throughout). For each I asserted
abs(m) < 2^53 and that m · 2^e equals Number("<m>e<e>") — JS
string-to-number is correctly rounded half-to-even, so it is a genuine
independent oracle for this function.

main:    {checked: 5228298, widthFails: 77828, valueFails: 0}
this PR: {checked: 5228298, widthFails: 0,     valueFails: 0}

Exact differential, main vs this head — 7,989,926 inputs (top-8192 band of
every bit-width up to 80; every mantissa 1..120000 at 12 exponents; a carry hunt
over bit-widths 40..90 at 13 exponents from -40 to 40). Outputs compared as
exact rationals, not through Number:

{n: 7989926, reprDiff: 404024, valDiff: 0, wideMain: 404024, widePr: 0}

So: 404,024 inputs get a different (mantissa, exponent) pair than main, and
every one of them is one of main's oversized resultsreprDiff and
wideMain are the same set. Zero inputs change numeric value. Nothing outside
the carry case moved.

Mutation testing

Reverted just the fix in place (return [m53 + up, e53]) and ran the bigfloat
proof groups individually:

decToBin:         0/19 killed
roundingPositive: 0/7  killed
roundingNegative: 0/7  killed
roundingCarry:    4/4  killed

All four new cases are load-bearing, and the 33 pre-existing cases detect
nothing — which is the same statement as "this mutation kills nothing on
main", since main's round53 is the mutation and its suite is green
(2531/2531).

Worth noting alongside that: npm run cov reports bigfloat/module.f.mjs at
100.00 / 100.00 / 100.00 on main and on this head. The bug lived under
full line and branch coverage, so the four new value assertions are the only
thing that could have caught it.

Rest of the battery

  • npx tsc --noEmit → 0.
  • npm run prepack from a clean tree → 0.
  • npm test: 2535 pass / 0 fail, vs 2531 on main — exactly the four new cases.
  • Public surface: type-alias extract is byte-identical to main (526 entries);
    normalized const-signature diff is 0 deltas over 898 entries. decToBin's
    emitted signature is unchanged; the only .d.mts delta is the new JSDoc prose
    and proof.roundingCarry. No elided / any anywhere in bigfloat.
  • No in-repo consumer of decToBin outside its own proof, so the representation
    change is unobservable today — consistent with what the todo said.

CHANGELOG

§8.3 clean: entry present for a code change, links only /pull/1524, in
Unreleased, no released section touched, ~200 chars.

It characterises the change correctly — "no longer returns a 54-bit mantissa …
always a binary64 significand" is exactly what my differential measured, and it
does state plainly that the returned pair is different for those inputs. I
considered whether §8.4 applies and concluded it does not: the numeric value is
unchanged (valDiff: 0 over 8M inputs), there is no consumer, and the published
type surface is identical. That matches how #1522 and #1514 — both
output-correcting fixes — are worded in the same section, while #1516 took the
prefix because serialized data had to be regenerated.

If you want one more half-sentence, "the value is unchanged; only the
representation moves one bit right" would save a reader the derivation, but the
entry is fine as it stands.

One nit, non-blocking

Deleting fjs/types/bigfloat/todo/round53-overflow.md strands the link to it in
its sibling:

fjs/types/bigfloat/todo/from-decimal.md:39
- [round53-overflow](round53-overflow.md) — `decToBin`, the next stage of the
  same pipeline

Broken relative markdown links go 140 → 141, and diffing the sets shows that
one entry as the only addition. The Related bullet is also stale in substance
now that the work is done, so it wants deleting rather than repointing. Tiny,
and against a 140-link baseline, but it is the one thing this PR introduces.

Everything else checks out. The todo's four tasks are all done, including the
magnitude-based assertion it specifically warned about (m < 2^53 would have
been vacuous for the negative cases — the proof uses abs(m)).

The issue file it points at is deleted in this PR, so the bullet is both a
broken relative link and stale in substance.

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013jmZZ85gA9r4B2fPpemvRQ

Copy link
Copy Markdown
Contributor Author

Thanks for the differential sweep — the reprDiff == wideMain, valDiff: 0 result is exactly the invariant I wanted and could not have shown at that scale.

Nit fixed in feaf7e3: dropped the round53-overflow bullet from fjs/types/bigfloat/todo/from-decimal.md rather than repointing it, since the work is done. grep -rn round53-overflow --include='*.md' is now empty, so the link count should go back to the 140 baseline.

Left the CHANGELOG entry as it stands, per your read that it is fine — the "value unchanged" detail is in the PR body for anyone who needs the derivation.


Generated by Claude Code

The postcondition added with the `round53` fix said the result *is* the
binary64 significand. That holds only in the normal range: `decToBin` clamps
no exponent, so in the `0x000` range it returns a normalized 53-bit mantissa
where the encoded value keeps at most 52, and at the top it returns a finite
pair where binary64 has saturated. Re-rounding the result onto the subnormal
grid rounds a second time and can land one ulp off.

Documents what the function actually guarantees, adds two far-exponent proofs
pinning the mantissa width outside the normal range, and files the gap as
`todo/binary64-exponent-range.md` with the double-rounding counter-example.

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013jmZZ85gA9r4B2fPpemvRQ

Copy link
Copy Markdown
Contributor Author

Follow-up in 8f359a3 — the postcondition I wrote overclaimed, and I'd rather not ship it approved.

"The result is the IEEE-754 binary64 significand" holds only for biased exponent 0x001..0x7fe. decToBin clamps no exponent, so in the 0x000 range it returns a normalized 53-bit mantissa where the encoded value keeps at most 52 bits, and at the top it returns a finite pair where binary64 has already saturated:

input decToBin the actual double
1e-310 [0x12_688b_70e6_2b10n, -1082] field 0x000, 45 bits
5e-324 [0x10_3132_b9cf_541cn, -1126] field 0x000, 1 bit
1e-400 [0x12_bfcf_c0f9_23dfn, -1381] field 0x000, underflow
1e400 [0x1b_4ec7_f919_73ffn, 1276] field 0x7ff, infinity

Finishing the job by shifting that result onto the subnormal grid double-rounds. Constructed case: q = 2^44 + 1 (odd), input the exact decimal just below the tie between q and q + 1. Correct is 0x100000000001 (Number() agrees); decToBin rounds up to the tie exactly, and grid-rounding that tie half-to-even with q odd goes to 0x100000000002 — one ulp off, unrecoverable in the second step.

None of this touches the round53 fix: abs(m) < 2^53 holds at every exponent, which is what the two new farExponent proofs pin (hex literals there — those mantissas have no bit pattern worth reading). The change is the JSDoc, those proofs, and todo/binary64-exponent-range.md carrying the actual work, since a correct version has to round once with a computed bit budget rather than fix up afterwards.

CHANGELOG unchanged — nothing about the shipped behavior moved.


Generated by Claude Code

@o2alexanderfedin o2alexanderfedin left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Re-reviewed at 8f359a3. I approved this at e3f47fb; the delta since then is two commits — dropping the stale round53-overflow link and the decToBin JSDoc/postcondition correction. Still clean, and the open nit from last time is fixed.

The delta is not logic

git diff e3f47fb..8f359a3 touches four files: module.f.mjs (JSDoc only — no
statement changed), proof.f.mjs (+2 cases), a new
todo/binary64-exponent-range.md, and the two stale link lines removed from
todo/from-decimal.md. Since round53/decToBin behaviour is untouched I did
not re-run the exhaustive differential from the previous review; I did re-run the
rest of the battery.

Verified

  • npx tsc --noEmit — 0. npm run prepack from a clean tree — 0.
  • npm test2537 pass / 0 fail, vs 2531 on origin/main (28a2e99).
    +6 = the 4 cases from the first round plus the 2 new farExponent ones.
  • Public surface diff (extract.mjs + consts.mjs, both trees after prepack;
    46 KB / 65 KB of output, so not a vacuous empty compare) — byte-identical
    to main. No new export type, prefixed or otherwise.
  • Broken-link sets — 140 on both trees, and diff of the sorted sets is
    empty. That closes the nit from the last review: deleting
    todo/round53-overflow.md had stranded the link in from-decimal.md:39 and
    taken the set 140 → 141; feaf7e3 removes the reference and the set is back to
    exactly main's.
  • npm run covfjs/types/bigfloat/module.f.mjs at 100.00 / 100.00 /
    100.00
    (line/branch/function); repo total 99.94 / 98.17 / 99.73.

The two new proof cases are correct, and so is the todo

I re-derived both farExponent expectations independently (exact BigInt
scaling of 10^±n, then a half-to-even round to 53 bits written from scratch,
not the module's):

  • [1n, -320]0x1f_a017_12e8_f047n, -1116
  • [1n, 400]0x1b_4ec7_f919_73ffn, 1276 ✔ — both exactly 53 bits.

Worth stating plainly, since it is easy to assume otherwise: these two also
pass on origin/main
. They do not discriminate the round53 fix — they pin
the newly documented "width holds at every scale" contract, which is what the
comment above them says they do. The fix's discriminating cases are still the
four from the first round.

I also spot-checked binary64-exponent-range.md rather than taking it on faith,
and every checkable claim in it holds: all five rows of the table reproduce
exactly, and the double-rounding counter-example is real — with q = 2^44 + 1
and the input just below the subnormal tie point, the correctly-rounded double
is 0x100000000001, decToBin lands exactly on the tie [0x10_0000_0000_0180n, -1082], and grid-rounding that half-to-even goes to 0x100000000002, one ulp
off. The JSDoc's retraction of the binary64-exponent-range claim is therefore an
accuracy fix, not a hedge.

Conventions

CHANGELOG entry is present, links only /pull/1524, sits in Unreleased, and
describes the code change (the docs-only commits correctly get none). The new
todo/ file gets no entry, per §8.3.

Approving.

@sergey-shandar
sergey-shandar marked this pull request as draft August 13, 2026 12:27
`fjs/emergent_testing/scenarios/` — nine fixtures, the `all.ts` shim and
`run.sh` — checked that external runners (node, bun, deno) produced the right
exit status for a proof with a known outcome. Nothing ran it: no CI job or
generated workflow invoked `run.sh`, and its `fjs` branch shelled out to
`npm run fst`, a script that no longer exists, so that quarter of the matrix
reported FAIL for every fixture. An unrun harness that had already rotted a
quarter through is not coverage.

The coverage is genuinely lost rather than moved, so it is recorded instead of
discarded: `fjs/emergent_testing/scenarios.md` carries every fixture verbatim,
the harness, what each case proved, and the two traps a rebuild will hit — the
hard link that forces the shim to exist, and the discovery collision that
forces its name. `all.test.ts` stays; it is the published entry point.

Also resolves the open scenario-fixture decision in the migration issue,
retires `205.md` (about a file that no longer exists), and puts the singleton
issue on hold, since the only case that motivated it was this harness.

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_013jmZZ85gA9r4B2fPpemvRQ
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants