Source: context/adr/005-exact-decimal-arithmetic.md
On this page
- ADR 005 — Exact decimal arithmetic: a three-level numeric tower for formulas
- What the user decided
- The decision this ADR writes down
- Context
- How a number flows today
- What is already wrong, measured
- What ADR 009's exact accumulator fixes, and what it does not
- The crates
- Decision
- 1. Three levels: exact decimal, exact bounded fraction, inexact binary
- 2. The stored type: CellValue::Number(Num)
- 3. What is exact on entry
- 4. How exactness propagates
- 5. Division, AVG and POW
- 6. Comparison, and the end of FLOAT_EQ_EPSILON
- 7. NaN and the infinities live only at the inexact level
- 8. SUM and the other aggregates
- 9. Display, edit text and typed scale
- 10. .improv persistence and migration
- 11. The wire
- 12. The seams
- 13. The crate: rust_decimal
- 14. The numeric tower is its own crate
- Option (d) for question 2: bounded exact fractions
- The number
- Operations
- Sums: the one real design choice
- The file and the wire
- Measured
- Where (d) beats (a), and where it does not
- Folded in: what changed in the clauses when the answer became (d)
- Alternatives rejected
- Migration
- Open questions
- Relations to other ADRs
- Consequences
- Appendix: the measurements
ADR 005 — Exact decimal arithmetic: a three-level numeric tower for formulas
Status: proposed. Only the user accepts an ADR. All sixteen numbered questions are answered (question 16 last, in revision 8, K = 8); the ADR waits for the user's "Approved". · Ticket: improvise-l2b8 (parent improvise-felo) · Direction from: the user, 2026-09-22 (below) · Relates to: ADR 009 (incremental evaluation, improvise-felo.4, PR #309), which now carries an exact f64 accumulator; ADR 007 (stable identities), whose new file-version literal this ADR may share · Governed by: context/design-principles.md §3 and §5
"Formulas should default to decimal math (ideally following Scheme's numeric tower rules for promotion)."
— the user, 2026-09-22, recorded on improvise-l2b8
Numbering. This is the ADR that improvise-l2b8 claimed as 005 before ADR 007 was written. improvise-8tk5 and improvise-80rm say "ADR 005" in their titles only because ADR 007 was first filed under this number. They belong to ADR 007, not to this document.
Citations. Every file:line below is at gh/main b639266b. Line numbers are dated, so re-derive them before citing this document elsewhere. "ADR 009" means the head of PR #309 at 4973845f (revision 6; it was 25ebf641 through revision 5).
Revision 2 answers the adversarial review of 1fe3a85d (a BLOCK) and the four ChatGPT Codex findings on the same head. The review's two blocking points are both correct, and both were reproduced here before the text changed: an exact SUM was not independent of order at the 28-digit bound (clause 8 now sums exactly in a wide integer), and rust_decimal's conversion to f64 is not correctly rounded (clause 4 now names one that is). Questions 1–9 keep their numbers; 10 and 11 are new.
Revision 3 adds option (d) to question 2, at the user's request: "I think (d): exact fractions with a size limit. should be added." It is specified and measured in Option (d) for question 2. The recommendation for question 2 changes from (a) to (d), in a hybrid form: the decimal arm stays, and a bounded fraction arm is added only for the values (a) would have made inexact. The clauses below are still written to (a). That section lists what changes in them if the user answers (d). Question 12 is new.
Revision 4 moves the numeric tower into its own workspace crate, at the user's direction: "I think ADR 005 should implement the math operations in a separate crate". That is new clause 14. Clause 2 and the migration now place Num there, not in improvise-core. It also adds questions 13–15: where the fraction bound applies (13), the crate's name (14), and where ADR 009's ExactSum lives (15). The same revision answers the review of e4acf643 (BLOCK D1 and D2, and its should-fix list) and Codex's P2 on aligning CSV entry with PR #321.
Revision 5 folds in the user's answers to questions 1–12, which they left inline on e4acf643 at 06:49–06:57 UTC on 2026-09-25. Revision 4 missed them, and that was the review of 87ae21ca's first blocking point. They are quoted in What the user decided, and the clauses are now written to them: three levels, option (d), exact comparison plus an EQUAL(a, b, epsilon) function, a string encoding on the wire, and n/d read as a fraction only where the type is forced. The same revision answers the rest of that review (B2–B4, D1's correction, question 13, the crate homes). Questions 10 and 13–15 stay open, and nothing is renumbered.
Revision 6 folds in the user's answers to questions 10, 13, 14 and 15, left inline on 33833f28 at 17:45–17:48 UTC on 2026-09-25: the 320-bit decimal partition and option (a) for question 10, (b) for question 13, numtower for question 14, and (a) for question 15. It answers the review of 33833f28 (issuecomment-5836990563):
- N1. The number language's gate is now the finite results of
f64::from_str, so it is #321's gate.nan,infand1e999stay text at import, as improvise-jc95 decided. Reversing jc95 is named as the rejected alternative (clause 3). - N2. Entry tries the fraction arm before f64, so a typed value is exactly as exact as the same value computed (clause 3).
- The should-fix items:
raw_value's cost to the import pipeline is stated (clause 12, step 5); the stale text is corrected; the ceiling is sized to the grouped read; and the exact read's cost is now measured. It is about 50× the revision 5 estimate, which is why question 16 is new.
It also corrects when a last-bit miss is visible to =. The bound is on the terms, not the total, as ADR 009 now says at 4973845f (Codex on #309).
Revision 7 folded in the user's first answer to question 16, left inline on b232c5a9 at 03:37 UTC on 2026-10-09: "let's do k = 32". It made K 32, option (a). Revision 8 supersedes that answer (below). Every question 1–16 was then answered, and the ADR stayed proposed until the user says "Approved". The change is confined to the value of K and the text that waited on it; the figures that depend on K were re-derived from the appendix's own measurements and none is new (question 16's "Re-derived" notes list them, now for K = 8). The revision also adds "Relations to other ADRs", a note on what ADRs 007, 008 and 009 ask of this one since it was written. It changes none of the user's decisions, and it lists the places where the other ADRs' text and this one's disagree.
Revision 8 folds in the user's second answer to question 16, a PR-conversation comment at 04:04 UTC on 2026-10-09: "Ok, let's drop K back to 8". It supersedes "let's do k = 32": K is 8, option (b), which was the recommendation of question 16. The earlier answer stays on the record, quoted in "What the user decided". The user gave no reason for the change, and this ADR does not supply or guess one. Every dependent figure was re-derived from the appendix's own measurements (question 16 lists them), and none is new. The K = 8 cutoff is still the second exception to "exact iff it fits" (question 13), and still overrides representability.
#What the user decided
The user answered inline on e4acf643, one comment per question. Each answer is quoted verbatim, with what it changed.
1. The tower's shape.
"I think, with bounded fractions, we need at least 3"
Decided: three levels. Exact decimal, exact bounded fraction and inexact f64 (clauses 1 and 2).
2. Non-terminating exact division.
"(d)"
Decided: option (d), bounded exact fractions, in the hybrid form. A non-terminating quotient that fits is exact (clause 5, and the option (d) section, now normative).
3. A tolerance on inexact =.
"Exact comparison everywhere but add
equal(a,b,epsilon)to formula language"
Decided: no tolerance on =. A new formula function, EQUAL(a, b, epsilon), is the explicit tolerant comparison (clause 6). It replaces the earlier "an APPROX if it is ever wanted".
4. The .improv spelling of an inexact finite number.
"
#iworks"
Decided: #i (clause 10).
5. The version literal.
"share with ADR 007"
Decided: share ADR 007 clause 10's new literal, unconditionally (clause 10).
6. JSON import precision, and the wire.
"I think we either have to add our own encoding as strings on the wire or use arbitrary precision: the round trip through f64 seems dangerous (unless maybe we tag f64s as exact somehow like NaN boxing)"
Decided: no value crosses as a JSON number, and no number is recovered by a round trip through f64.
- The wire spells every number as a string in its own encoding (clause 11).
- JSON import reads each number's source lexeme, not the f64
serde_jsonmade of it (clause 12). - NaN boxing is not needed once the encoding is a string: the string carries the exactness.
serde_json'sarbitrary_precisionstays rejected, for a reason the string encoding does not remove: it breaks serde's buffered deserialization of numbers. The workspace has an internally tagged enum (improvise-wasm-client/src/render.rs:86) and a#[serde(flatten)](gp-tree/src/data.rs:64), and the feature is unified across the workspace. So the lexeme is read withserde_json'sraw_valuefeature, which is additive and changes nothing else.
7. Comparing an exact value with an inexact one.
"Exactly, but add
equal(a,b,epsilon)to formula language."
Decided: exact comparison, with the same EQUAL function as question 3 (clause 6).
8. The dependency.
"yes, this seems fine."
Decided: yes. One figure changed after the answer, and it is flagged here.
- The user answered against option (a)'s +15.4 KB gzipped for
rust_decimalalone. - Under (d),
numtoweralso carriesnum-rationalandnum-bigint. The probe measured those at about +20.8 KB gzipped on their own; together withrust_decimalthey are unprobed (clause 14). - If that changes the answer, question 8 reopens.
9. Version skew on the wire.
"yeah, accept and add a ticket for handshake version."
Decided: accept the skew. The handshake version is filed as improvise-szi8.
10. The exact-sum accumulator.
"Don't we need a much bigger accumulator (2000ish bits) to handle exact accumulation generically?"
That was a question back to the ADR, answered with numbers in clause 8, "How wide, generically". In short:
- Decimals need 320 bits, because their range is small.
- f64 values need about 2,100 bits. That is ADR 009's accumulator.
- Fractions have no fixed generic width. Combining k arbitrary
i128denominators needs up to 127·k bits. The user's ~2,000 bits is exactly k = 16.
Then, on 33833f28, on the line "decimals need 320 bits":
"320bits is fine"
and on option (a):
"(a)"
Decided: (a). A 320-bit decimal partition, a 256-bit numerator per fraction group, and a read that combines at most K groups in a bigint rational and then applies the stored bound. One figure changed after the answer, and it is flagged here: the exact read was an estimate of 16–34 µs at K = 32, and it measures 0.67–1.9 ms in the worst case (option (d), "What that costs"). K is a constant inside numtower, not a format or wire fact, so its value was split out as question 16 rather than reopening this one. The user decided K = 8 there (first K = 32, then K = 8; the later answer governs).
11. The MIN/MAX tie-break.
"Yeah, exact."
Decided: prefer the exact value (clause 8).
12. Typing a fraction.
"keep as text for type inference from strings because of dates, read as fraction in places where the type is forced."
Decided: n/d is text wherever a type is inferred, and a fraction wherever the type is forced. So a typed or imported 3/4 whose type is being guessed stays text, which keeps dates. A column the user has forced to a measure reads 3/4 as a fraction. Clause 12 defines the one number language this uses.
13. Where the fraction bound applies.
"(b)"
Decided: (b). The bound applies to the stored result, and every intermediate inside one formula evaluation is unbounded up to the ceiling. The ceiling is the first of two exceptions to "exact iff it fits", sized to the grouped read (question 13). The second, added by revision 7, is the K cutoff on a SUM, K = 8 since revision 8 (question 13, "The K cutoff").
14. The numeric crate's name.
"this is fine"
Decided: numtower (clause 14).
15. Where ADR 009's ExactSum lives.
"(a)"
Decided: (a), in numtower, beside the exact decimal accumulator. ADR 009's seam crate adapts it to zset's group trait through a newtype, and numtower can land holding ExactSum alone, ahead of this ADR (clause 14).
16. The value of K. The user answered twice. Both are quoted verbatim.
First, inline on b232c5a9, on question 16's options (2026-10-09T03:37:34Z, comment 4226381911):
"let's do k = 32"
Then, in a PR-conversation comment (2026-10-09T04:04:36Z, comment 6074029223):
"Ok, let's drop K back to 8"
Decided: (b), K = 8. The later answer governs, and the first is superseded, not deleted. K = 8 is the recommendation of question 16, and not the value revision 5 proposed and question 10 was answered with. The worst-case exact read is 52–127 µs (52 µs is the lcm method, the one numtower uses; 127 µs reduces after every add). The combined numerator is at most K·127 + 256 = 1,272 bits (before the up to 3 carry bits of summing 8 terms), which the proposed 8,192-bit ceiling clears by 6,920, enough to absorb them. A SUM over more than 8 distinct non-decimal denominators is inexact, and the cutoff overrides representability (question 13). K remains a constant inside numtower, so it can still be tuned later against the evaluator benchmark without a new ADR.
#The decision this ADR writes down
- Three levels (decided, question 1). A number is an exact decimal, an exact bounded fraction (an
i128numerator and denominator), or inexact (an f64). There are no unbounded rationals. They were measured, and they fail on the most ordinary pivot-table question, the sum of ratios (clause 1). - Exact is the default. Every number a person types, every number in a
.improvfile, every CSV or JSON number and every formula literal is exact when it fits either exact arm: a decimal first, then a bounded fraction (clause 3). - Exactness is lost only in named places.
+,-,*and/keep it: a quotient is a decimal when it terminates and fits, and otherwise a bounded fraction (decided, question 2).POWkeeps it for an integer exponent. A non-integer exponent, a result that fits in neither exact form, and any inexact operand make the result inexact. That is Scheme's contagion rule. - The epsilon goes.
=and!=compare exactly, and the division-by-zero guard tests for exactly zero. The two still share one predicate, which is the property gotcha 17 exists to keep. A tolerant comparison is explicit:EQUAL(a, b, epsilon)(decided, questions 3 and 7; clause 6). - The stored type is
CellValue::Number(Num), whereNumisExact(Decimal),Fraction(Box<Ratio<i128>>)orInexact(f64). The crates arerust_decimalandnum-rational.Numand everything numeric live in a problem-agnostic workspace crate of their own,numtower(decided, question 14; clause 14). - Each kind of number has its own exact accumulator. ADR 009's f64 accumulator makes
SUMover inexact values order-free, and this ADR does not re-specify it. The exact values get a wide fixed-point integer of their own (clause 8), becauserust_decimal's own addition rounds at its bound and so is not order-free there. What this ADR adds beyond summation is everything the f64 accumulator cannot reach: per-cell arithmetic, typed money-like values, exact comparison, and showing a typed value back as it was typed. Clause 8 states the boundary, and the measurement behind it.
#Context
#How a number flows today
Every number is an f64 from the moment it is parsed until the moment it is drawn.
| where | what | file:line |
|---|---|---|
| the stored type | CellValue::Number(f64), serialized through wire_f64 | crates/improvise-core/src/model/cell.rs:116-122 |
| non-finite tokens | nonfinite_token / parse_nonfinite (inf, -inf, nan) | cell.rs:63-82 |
| the wire adaptor | JSON number when finite, token string when not (improvise-55v2) | cell.rs:84-114 |
| editor seed | CellValue::edit_text: Rust's shortest round-trip spelling (improvise-umi4) | cell.rs:137-145 |
| screen spelling | Display: integer, else {:.4} | cell.rs:148-161 |
| cell aggregation | apply_agg over &[f64]; aggregate_cell_values filters as_f64 | crates/improvise-core/src/model/types.rs:20-44 |
| formula aggregation | eval_agg, values.iter().sum() in store order | types.rs:57-87 |
| the epsilon | FLOAT_EQ_EPSILON = 1e-10 (improvise-0bf) | types.rs:16 |
| record-level eval | eval_expr: lv + rv, lv / rv behind the epsilon, lv.powf(rv) | types.rs:229-282 |
| comparison | eval_bool: (lv - rv).abs() < FLOAT_EQ_EPSILON | types.rs:314-315 |
| the cached twin | eval_expr_cached, the same arithmetic again | types.rs:1090-1104, 1156-1157 |
| formula literal | Expr::Number(f64), from number = ASCII_DIGIT+ ("." ASCII_DIGIT*)? \| "." ASCII_DIGIT+: no sign, no exponent, no digit bound, and 1. and .5 are legal | crates/improvise-formula/src/ast.rs:35, formula.pest:105-108, parser.rs:192 |
| typed input | typed(): text.parse::<f64>(), else text (improvise-j7v6) | crates/improvise-protocol/src/resolve.rs:1438-1446 |
| display | round_half_away scales by 10^d in f64, then format! | crates/improvise-core/src/format.rs:125-160 |
.improv write | format_number: integer, else shortest Display, else {:?} | crates/improvise-io/src/persistence/format.rs:38-54 |
.improv grammar | number = "-"? digits ("." digits)? (exponent)? | crates/improvise-io/src/persistence/improv.pest:110-112 |
.improv read | parse_number_cell: s.parse() into f64 | crates/improvise-io/src/persistence/parse.rs:141-146 |
| CSV field | i64, else f64, into a serde_json::Number | crates/improvise-io/src/import/csv_parser.rs:167-186 |
| import measures | read back with as_f64, which drops an exact i64 of more than 15 digits | crates/improvise-io/src/import/wizard.rs:425 |
| record fingerprint | hashes a number's bits, not its PartialEq (ADR 001's record tier) | crates/improvise-command/src/ui/app.rs:231-250 |
| JSON import | serde_json::Value, numbers already f64 (float_roundtrip) | src/main.rs:365, crates/improvise-command/src/ui/effect.rs:1151, 1280 |
| import collisions | the "sum" policy adds in f64, in record order (improvise-cgqt) | crates/improvise-io/src/import/wizard.rs:307, 330 |
| the wire | ModelCommand::SetCell { value: CellValue }, CellDisplay::value, SetYanked | crates/improvise-protocol/src/reduce.rs:33, 88-92; render.rs:88-104 |
| gp seam | cell_text: a number crosses as text, n.to_string() | crates/improvise-gp/src/dataset.rs:50-56 |
grep -rn 'CellValue::Number' --include='*.rs' . finds 672 occurrences in 47 files, tests and benches/ included. That is the blast radius of any change to the stored type.
#What is already wrong, measured
The measurements in this ADR were taken on an Apple M4 Max (64 GB), rustc 1.98.1, release builds, by a scratch program described in the appendix. They were not committed, for the reason the appendix gives.
Per-cell arithmetic is wrong in the last place, and the user sees it.
0.1 + 0.2is0.30000000000000004, and ten0.1s sum to0.9999999999999999.1234.56 - 1234.55is0.009999999999990905, and100.10 - 100is0.09999999999999432.
A display format hides most of this. It does not hide it from =, from an editor, or from the next formula.
Display rounding is wrong for a typed value. format.rs:127-136 rounds by scaling the f64. A typed 1.005 is stored as 1.00499999999999989…, so at two places the grid shows 1.00. A person who typed 1.005 and asked for two places expects 1.01. Half-away-from-zero on the decimal gives 1.01. 2.675, 0.125 and 1.115 happen to agree on both paths. The review found more that miss: 1.015 draws 1.01, 1.025 draws 1.02 and 0.285 draws 0.28. So the bug is real but intermittent, which is the worst kind for a spreadsheet. It is filed on its own as improvise-felo.9, because it can be fixed without this ADR: round the shortest round-trip spelling as a decimal.
SUM depends on order, and on how far it is from what was typed. SUM over 18,000 typed two-place decimals (0.01 to 999,999.99, seed 1):
- the forward and the reverse f64 fold differ by 5.0e-5;
- the forward fold is 5.3e-5 from the exact decimal total (1.4e-4 at 90,000 cells);
- the decimal sum (
rust_decimal) is identical in both orders for this data. It is not identical in general: at the 28-digit boundrust_decimalrounds, and then order matters again (clause 8).
ADR 009's own measurement found the same thing with five-place values: the eager sum is up to 5.8e-10 from the exact decimal sum, above FLOAT_EQ_EPSILON at 7 of 8 checkpoints (improvise-l2b8's comment). Gotcha 18 recorded the order dependence as a real bug (improvise-shyt), fixed by pinning iteration order rather than by removing it.
The epsilon is a patch, and it does not scale. It was chosen because it "absorbs accumulated f64 rounding noise" (context/code/core.md §4). But one ulp of 1,000,000 is 1.16e-10. So once a value is above about 2¹⁹ (524,288), a one-ulp error in it is already larger than the epsilon, and = sees it. Below about 1e-10, the epsilon calls different numbers equal.
#What ADR 009's exact accumulator fixes, and what it does not
ADR 009 now proposes a superaccumulator: a fixed-point integer wide enough for every finite f64. It sums f64 values exactly and rounds once, when the sum is read. It makes SUM independent of order, and its retraction exact, without this ADR. That changes what this ADR is for, so it was measured rather than assumed.
The question: after a perfect f64 accumulator, does the sum of typed decimals equal the typed total? The stand-in for the accumulator was an exact rational sum of the stored f64 values, rounded once (appendix).
The miss rate depends on the values' distribution, not only on how many are summed, so two distributions were measured. The first is positive two-place values uniform in 0.01–999,999.99, as the rest of this ADR uses. The second is two-place values uniform in ±1,000.00. The ADR 009 agent found it with an independent Python Fraction check (about 37–40%), and it was reproduced here with the same stand-in (seed 7).
| typed two-place values summed | trials | accumulator ≠ typed total, 0.01–999,999.99 | accumulator ≠ typed total, ±1,000.00 | naive f64 fold ≠ typed total, 0.01–999,999.99 |
|---|---|---|---|---|
| 2 | 10,000 | 2,120 (21%) | 3,792 (38%) | 2,120 (21%) |
| 3 | 10,000 | 1,621 (16%) | 3,836 (38%) | 2,683 (27%) |
| 10 | 10,000 | 752 (7.5%) | 3,950 (40%) | 4,039 (40%) |
| 100 | 10,000 | 250 (2.5%) | 4,018 (40%) | 7,944 (79%) |
| 18,000 | 8 seeds | 0 | 5 of 8 seeds (the review) | (all 8: see above) |
| 90,000 | 8 seeds | 0 | 2 of 8 seeds (the review) | (all 8) |
The signed column's large-N cells were measured by the review of e4acf643, with the same generator and stand-in. It also measured signed N = 1,000: 84 of 200 trials (42%). At 18k it found 16 of 40 trials with seed 7, and 5 of 8 across seeds 1–8. So "about 40% at every length" holds out to 18k.
The accumulator helps only where the total is large beside its terms. With positive values the total grows with the count, its ulp grows with it, and the input rounding errors cancel far below that ulp. So the one rounding lands on the typed total, and over thousands of cells it always did. With signed values the total stays small, because the terms cancel. The input errors are then comparable to the total's ulp at every count, and about 40% of sums miss however many terms there are. Revision 2 said "the accumulator solves the large sum". That holds only for same-sign data, and it is corrected here. For two summands a superaccumulator is exactly +, because one f64 addition is already correctly rounded. So 0.1 + 0.2 is still 0.30000000000000004 under the accumulator.
The misses are in the last bit of the largest term, not of the total. Each stored term is off from its typed value by at most half an ulp of that term. So the exact sum of the stored terms is off from the typed total by at most about ½·Σ ulp(term), plus the total's own half-ulp at the final rounding (revision 6; revision 5 put the condition on the total, and ADR 009 made the same correction at 4973845f, from ChatGPT Codex on #309). When terms cancel, a miss can be far larger than the total's ulp:
- The large-term, small-total case.
1000000000000000.10 + (-1000000000000000.00)has a typed total of 0.10. The first term is stored as1e15 + 0.125, because the ulp at 1e15 is 0.125. So the exact sum of the stored terms is 0.125, and the miss is 0.025 on a total of 0.1. - When
=sees one today.=is an absolute1e-10(gotcha 17), so a miss can reach it only when ½·Σ ulp(term) reaches1e-10. That needs at least one term of about 2¹⁹ ≈ 5.2e5 or larger, or many terms just below it. It does not depend on the total. The ±1,000 values are far below 2¹⁹, so today's epsilon hides their misses; the positive values up to 999,999.99 pass it. - Once this ADR deletes the epsilon (clause 6), every miss is visible to
=.
A person reading a subtotal at two places usually sees the right number, because the miss is below the displayed digits unless the terms are large. The miss also shows in the editor, which opens on the shortest round-trip spelling (0.30000000000000004). That is where 16% of positive 3-term sums, and about 40% of signed sums of any length, go wrong.
So the division of labour is:
| ADR 009 accumulator | this ADR | |
|---|---|---|
SUM/AVG independent of order, exact retraction | yes, for inexact values | yes for exact values, through its own wide fixed-point accumulator; it uses ADR 009's for inexact ones (clause 8) |
a large same-sign SUM equal to its typed total | yes, measured above | yes |
a small SUM, or a signed SUM of any size, equal to its typed total | no: 16% of positive 3-term sums miss, and about 40% of signed sums | yes |
per-cell arithmetic (Revenue - Cost, * 1.1, 0.1 + 0.2) | no | yes |
exact = against a typed value, with no epsilon | only where the sum happens to round right | yes |
a typed value shown back as typed (12.50, 1.005 at two places) | no | yes |
| cost | 568 bytes per group, 2.0–3.6 ns per update, 0.6–1.1 µs per read (ADR 009's figures) | 16 bytes per value; about 5–8 ns per add, 60–110 ns per division; 40 bytes per summed group (clause 8, question 10; an estimate, not measured) |
This ADR does not re-specify the f64 accumulator. Where an inexact value must be summed, it is summed by ADR 009's accumulator, and this ADR only says so. ADR 009's "what each exact domain covers" table says that accumulator makes = against a typed decimal right "only for sums". The measurement above narrows that to large same-sign sums. ADR 009 says "no, in general" since 8ebcf889, and cites both distributions, so the two tables agree.
#The crates
Three crates were evaluated. All three build for wasm32-unknown-unknown.
rust_decimal 1.43.0 | bigdecimal 0.4.10 | num-rational 0.4.2 (BigRational) | |
|---|---|---|---|
| value | 96-bit integer and a scale up to 28 | BigInt and an i64 scale | BigInt / BigInt |
| inline size | 16 bytes, Copy, no heap | 40 bytes and a heap buffer | 64 bytes and two heap buffers |
+ - * | exact within 28 significant digits; beyond that it rounds silently (1000 + 1/3 comes back at scale 25) | always exact | always exact |
/ | rounds to 28 significant digits (1/3*3 ≠ 1) | rounds to 100 digits by default | exact |
| parsing past the bound | from_str rounds silently (30 digits come back as 28); from_str_exact refuses | exact | exact |
| to f64 | to_f64 is not correctly rounded (clause 4) | — | — |
| normal-edge deps | arrayvec, num-traits, serde | libm, num-bigint, num-integer, num-traits | num-bigint, num-integer, num-traits |
| wasm size, marginal | +35.9 KB, +15.4 KB gzipped | +77.9 KB, +30.7 KB gzipped | +59.6 KB, +20.8 KB gzipped |
| SUM, ns per element (18k / 90k) | 5.7–8.1 / 4.5–8.5 | 14.5–22.9 / 10.8–20.7 | 609–1,057 / 491–989 |
(Rev − Cost) / Rev, summed, ns per record | 65–111 / 58–112 | 2,429–5,353 | 5.3–6.8 ms, abandoned (below) |
The f64 references are 0.54–1.18 ns per element for SUM and 0.56–1.24 ns per record for the formula. Each range is two full runs. 1.5 == 1.50 and the two hash equally in rust_decimal. The wasm figures are wasm-opt -Oz over a module that already carries f64 parse and print, as the real bundle does, so they are the marginal cost. They are from a five-operation probe, not the real bundle, and the real cost should be re-read when the dependency lands (question 8).
Exact rationals fail on the sum of ratios, and it is not close. The ticket asked what bounds denominator growth. Summing (Revenue − Cost) / Revenue over random typed records, the denominator of the running sum grew as follows:
| ratios summed | 256 | 512 | 1,024 | 2,048 | stopped (20 s budget) |
|---|---|---|---|---|---|
| denominator bits | 4,699 | 9,103 | 17,015 | 31,697 | 44–55 k, after 2,936–3,741 records |
Nothing bounds it. Each new revenue brings new prime factors into the least common denominator, so it grows linearly in bits and each addition costs more than the last. At the stopping point one addition cost milliseconds. An 18,000-record average margin does not finish. That is the most ordinary question a pivot table is asked, so exact rationals as the default are rejected on measurement, not taste.
#Decision
#1. Three levels: exact decimal, exact bounded fraction, inexact binary
Scheme's tower is integer ⊂ rational ⊂ real ⊂ complex, and each level has an exact and an inexact form. Improvise keeps three levels (decided, questions 1 and 2):
- Exact decimal:
rust_decimal::Decimal. Integers are decimals with scale 0. Typed values, money and a typed scale such as12.50live here. - Exact bounded fraction: a reduced
Ratio<i128>. It holds only exact values that are not a finite decimal that fits, such as10/3(the option (d) section). - Inexact: an
f64, Scheme's flonum.
There are no unbounded rationals, for the reason measured above, and no complex numbers, because nothing produces one. The exact levels are bounded. A decimal has 28 significant digits and a magnitude below about 7.9 × 10²⁸, and a fraction has an i128 numerator and denominator. Scheme's exact numbers are unbounded, so this is the one place the tower deviates from Scheme by design. Clause 4 and question 13 say what happens at the bound.
#2. The stored type: CellValue::Number(Num)
pub enum Num {
Exact(Decimal),
Fraction(Box<Ratio<i128>>), // boxed: keeps Num at 24 bytes (option (d))
Inexact(f64),
}
pub enum CellValue {
Number(Num),
Text(String),
Error(String),
}
Num lives in the numeric crate (clause 14), and CellValue in improvise-core wraps it. The arithmetic and the contagion rules are methods on Num, in that one crate. Both evaluators (eval_expr and eval_expr_cached) call the same methods, so the rules cannot drift between them the way the epsilon once did (improvise-0bf).
A new arm beside Number(f64) was rejected. It would double every numeric match at the 672 sites, and "is this cell a number" could then be asked two ways. CellValue::as_f64 stays, as the explicitly lossy accessor for the seams that want a binary float (clause 12). It uses clause 4's correctly rounded conversion.
Expr::Number(f64) becomes Expr::Number(Num), not Expr::Number(Decimal). The formula grammar has no digit bound, so a literal such as 999999999999999999999999999999 is legal formula text and has no Decimal. It takes clause 3's order, like every other spelled number: a decimal if it fits, else a fraction if it fits (that literal is below 2¹²⁷, so it is the exact Fraction n/1), else the nearest f64. A literal is a number by the grammar, so clause 3's gate, which decides number-or-text for data, does not apply to it. A literal that overflows f64 (the formula grammar has no exponent, so a digit string of more than 309 digits) keeps today's meaning, inexact infinity, the same as an inexact overflow in *. Bounding the grammar instead was rejected, because it would make a formula that parses today stop parsing, over a limit of the representation rather than of the language. (Codex, P2 on 1fe3a85d.)
#3. What is exact on entry
Everything a person or a file spells in decimal is exact, when it fits. That covers typed input (typed()), .improv numbers, CSV fields, formula literals and pasted values.
This deviates from Scheme on purpose. Scheme reads 1.5 as inexact and needs #e1.5 for exact. Improvise reads 1.5 as exact, because a pivot table's inputs are decimals a person typed, and "decimal math by default" is the user's instruction. So Scheme's #e is improvise's default.
A spelled number is inexact only when it cannot be exact: it fits neither a Decimal nor an i128 fraction (for example 1e300, 1e-40, or a 40-digit integer). Then it reads as the nearest f64. The tokens inf, -inf and nan are inexact too, but they are clause 7's tokens, not numbers of the language (below).
The parse must refuse, not round. Decimal::from_str rounds a 30-digit input to 28 digits silently (0.12345678901234567890123456789 comes back as 0.1234567890123456789012345679). That is a rounded value calling itself exact, the one outcome clause 4 forbids. Under the order below, that input is the exact fraction 12345678901234567890123456789/10²⁹ instead.
One number language, for every entry point (revision 5, answering B4 of the review of 87ae21ca). Revision 4 said "parse with from_str_exact", but the gate that decides whether a string is a number at all accepts different strings. from_str_exact rejects 1.5e3 and accepts 1_000, and #321's number_in gate does the opposite. So the language is defined once, and the gate and the parse cannot disagree. numtower owns it.
What is a number. The gate is the strings Rust's
f64::from_straccepts and reads as a finite value (revision 6, N1 of the review of33833f28). That is #321'snumber_ingate, which drops anythingNumber::from_f64cannot hold. So a number is an optional sign; digits with an optional fraction (1.,.5); and an optional exponente/Ewith its own sign, whose value does not overflow f64.1_000is not a number, so it is text.nan,inf,infinityin any case, and a finite lexeme that overflows f64 (1e999,-1e999) are not numbers either, so they are text. That is improvise-jc95's decision, which #321'sa_nonfinite_numeric_token_stays_text_rather_than_becoming_zeropins forNaN,inf,-inf,1e999and-1e999. A finite lexeme must never read as infinity.- A lexeme that underflows (
1e-999) passes, because f64 reads it as a finite zero. It is then too small for either exact arm, and it reads as that zero, inexact. #321 treats it the same way.
- The non-finite values are clause 7's tokens, not numbers.
typed(), the.improvreader and the wire accept exactlyinf,-infandnan, the three spellingsnonfinite_tokenwrites (cell.rs:65), as inexact values. Import does not, so a CSVnanstays text, as jc95 decided. This is a behaviour change fortyped(), and it is stated: today it hands any string tostr::parse::<f64>(resolve.rs:1438), so a typedInfinityor1e999becomes infinity and a typedNaNbecomes NaN. Under this clause each is text. How it parses. A lexeme that passes the gate is parsed exactly from its digits and exponent: a mantissa and a scale shift, never through an f64. Then it takes the first arm it fits, in this order (revision 6, N2 of the same review):
- A decimal. If the exact value fits a
Decimal, it isExact, with the scale the lexeme implies:1.50has scale 2,1.5e3is1500at scale 0, and1.5e-3is0.0015. - A fraction. Otherwise, if its reduced value
m / 10^kfitsRatio<i128>, it is aFraction. So a typed1e-30is the exact1/10³⁰, and an integer betweenDecimal's maximum (about 7.9 × 10²⁸) and 2¹²⁷ is the exactn/1. This is the order clause 4 already gives arithmetic, so the same value is equally exact typed and computed:1e-15 * 1e-15was already the exact1/10³⁰. A fraction carries no scale (the option (d) section). - The nearest f64. Otherwise it is
f64::from_str's correctly rounded value,Inexact. The gate has already made it finite. - A lexeme that passes the gate is never refused. Failing to fit falls back; failing to parse cannot happen.
- A decimal. If the exact value fits a
- Zero has no sign at the exact level.
-0.0reads as exact0.0. The sign of zero is an f64 artefact. This is a behaviour change, and it is stated: an f64-0.0never survives entry as exact. n/dis a number only where the type is forced (decided, question 12).n/dmeans an optional sign, digits,/, and digits withd > 0, and it is a fraction or, once normalized, a decimal. The places where the type is forced are:- the
.improvfraction arm (clause 10); - the wire's exact arm (clause 11);
- an import column the user has forced to a measure (clause 12).
Everywhere a type is inferred it is text:
typed(), and the import analyzer deciding a column's kind. That keeps3/4as a date or a label.- the
The entry points are typed(), the .improv reader (whose number rule is a subset of the gate before the finite check), formula literals, the wire and import.
Reversing jc95 was rejected. The alternative was a gate of every string f64::from_str accepts, so that a CSV nan imports as Inexact(NaN) and a CSV 1e999 as Inexact(inf). It would make a finite lexeme read silently as infinity, which is the invented-value class jc95 closed, and it would flip #321's test. The gain, a measure column that can hold a NaN, is not worth either: a column carrying nan is shown as text in the wizard, where the user can see it (jc95's close reason).
A JSON number is read from its source lexeme, never through its f64 (decided, question 6: "the round trip through f64 seems dangerous"). serde_json normally parses a number to f64 before improvise sees it. The import therefore reads each record's values with serde_json's raw_value feature, which hands over the number's exact source text, and parses that text by the language above. So a JSON 12.50 keeps its scale, and a 20-digit JSON literal stays exact. That costs a restructuring of the import pipeline, stated in clause 12. arbitrary_precision was the other way to do this, and it stays rejected, because it breaks serde's buffered deserialization of numbers (the user's answer to question 6). Revision 4's shortest-spelling recovery of a JSON number is withdrawn.
#4. How exactness propagates
| operation | exact ∘ exact | any inexact operand |
|---|---|---|
+, -, *, unary - | exact, if the result is exactly representable; else inexact | inexact |
/ | clause 5 | inexact |
POW | clause 5 | inexact |
IS, IF | not arithmetic: IS yields exact 0 or 1 | — |
Contagion is Scheme's rule. An inexact operand makes the result inexact, and an exact result never comes from an inexact input.
"If exactly representable" needs care, because rust_decimal rounds silently. An add whose result needs more than 28 significant digits comes back rounded, with no signal. The measurement caught it: 1000 + 0.3333333333333333333333333333 returns scale 25. Overflow of the magnitude is reported (checked_add returns None), but precision loss is not. So Num's arithmetic must detect either one and return Inexact. It must never return a rounded Exact. A rounded value that calls itself exact is the one outcome this design exists to prevent.
Detection reads the scale, then checks that the dropped digits were not zeros (revision 7, Copilot on 66f317e1). The exact result of a + b or a - b has scale max(sa, sb), and of a * b has scale sa + sb. A returned scale that is smaller is a hint of rounding, not proof. 1000 + 0.333… (28 places) comes back at scale 25, and 0.1234567890123456² at 28 against an exact 32. Revision 6 demoted on the hint alone and called the zero-digit case a safe false positive. It is not safe: it breaks question 13's decided rule that a stored value is exact iff it fits. 1.2500000000000000 * 4.0000000000000000 (scale 16 each) has the exact value 5 at scale 32, which is 5·10³² as an integer and does not fit 96 bits, yet 5 fits a Decimal. So on the hint the arithmetic recomputes the exact integer result in the 256-bit integer clause 8 already uses (a product of two 96-bit mantissas is below 2¹⁹², and an aligned sum below 2¹⁹⁰), strips trailing zeros, and returns exact iff the stripped mantissa fits 96 bits at a scale of at most 28. The stored scale (flagged reading, revision 7, so the fingerprint of clause 9 is a function of the value and the operands alone): the nominal scale above capped at 28, min(nominal, 28), padded back with zeros while the mantissa still fits 96 bits, and otherwise the largest scale at which it fits. So the example is 5 at scale 28 (5·10²⁸ fits), not scale 0 and not 32. A result that never fired the hint keeps its returned scale, so the common path is unchanged. Otherwise the value is not a Decimal, and goes to the fraction arm and then f64 as below. The recompute runs only when the scale hint fires, so the common path is unchanged. This is a design for the implementer and is not measured. Division has its own test (clause 5).
This is not rare in practice, and the review showed why. Clause 10 loads an old file's 17-digit f64 spellings as exact, so 0.30000000000000004 + 1e12 needs 29 significant digits and is rounded. That is the case clause 8's accumulator exists for.
The one conversion to f64 is correctly rounded, and it is not the crate's. Demotion, mixed comparison (clause 6), as_f64 and the reading of a mixed sum (clause 8) all turn an exact value into an f64. rust_decimal's to_f64 is not correctly rounded. In 200,000 random Decimals with 96-bit mantissas and scales 0–28, it disagreed with a correctly rounded parse of the same value's text 17,392 times in the review's sample and 17,375 times in this one (about 8.7%). For example, 63294.607176721429540940386554 gives the f64 ending …144, where the nearest is …143. With mantissas of at most 15 digits there were no disagreements, but exact products and sums leave that range quickly. So Num converts through the decimal string: d.to_string(), then Rust's str::parse::<f64>, which is correctly rounded. That costs an allocation, paid only where an exact value leaves the exact level. A correctly rounded integer algorithm can replace it later, and it must agree with the string path on a property test.
So "computed in f64" above means: convert each exact operand by this conversion, then do the f64 operation. A demoted sum or product is therefore rounded twice, once per operand and once in the operation. That is deterministic, and it is the Scheme reading of an operation that could not stay exact.
#5. Division, AVG and POW
Division. Exact ÷ exact is always exact when the result fits (decided, question 2).
- It is a decimal when the quotient is a finite decimal that fits:
1 / 4 = 0.25. - Otherwise it is a bounded fraction when the reduced fraction fits
i128:1 / 3, so1 / 3 * 3is exactly1. - Otherwise it is inexact: the correctly rounded f64 of the exact quotient.
The implementation must decide termination and fit without trusting rust_decimal's division, which rounds a terminating quotient silently when it needs more than 28 places (below).
The termination test is arithmetic, not a round trip. Write a / b as the fraction (ma · 10^sb) / (mb · 10^sa), with mantissas ma, mb and scales sa, sb. The powers of ten contribute only 2s and 5s, so the quotient is a finite decimal exactly when mb / gcd(ma, mb) is 2^p · 5^q. That takes one i128 gcd over the mantissas (each below 2⁹⁶, so nothing overflows) and a loop dividing out 2s and 5s, with no rounding anywhere.
Terminating is not enough: the quotient must also fit, and that test is specified here (revision 4, answering the review of e4acf643). Clause 4's scale test covers + − × only, because a quotient's scale is not a function of its operands' scales. The review measured 1 / 2^40: it terminates, but it needs 40 fractional digits. rust_decimal returns 0.0000000000009094947017729282 at scale 28, with no signal, and an exact quotient can legitimately have scale 28 too. So the result alone cannot tell the two apart. The rule:
- Write the quotient as the reduced fraction
n / (2^p · 5^q), computing it in 256 bits, becausema · 10^sbcan reach 2¹⁹⁰. - Its exact scale is
k = max(p, q). - The quotient is an exact
Decimaliffk ≤ 28andn · 2^(k−p) · 5^(k−q)fits in 96 bits. - Otherwise, including every quotient that terminates but needs more than 28 places, it is a
Fractionwhen the reduced fraction fitsi128. - Otherwise it is inexact. The one conversion is the reduced 256-bit fraction, converted once, correctly rounded (clause 4's interval-checked rational → f64). It is not a conversion of each operand followed by an f64 division. Revision 4 said "the correctly rounded f64 … through each operand's conversion and one f64 division", which contradicted itself: two roundings are not a correct rounding. The fraction is already in hand, so it is converted once.
The direct test above is normative (revision 5, the review's correction to D1). Multiplying back with clause 4's scale detection is sound: q × b exact and equal to a implies q = a / b. But it is incomplete, because it demotes some exact quotients. 1e-28 / 0.5 = 2e-28 is exact and fits (k = 28, mantissa 2), yet q × 0.5 needs scale 29, so the check flags it. The review measured this case. If the method were left to the implementer, exactness would depend on which method was picked. So the direct test is the rule, and multiplying back is not an allowed substitute.
Scheme would answer 1/3 exactly, and so does improvise, within the bound. Unbounded rationals are ruled out by the measurement above.
AVG is SUM / COUNT under the division rule. The average of 10.00, 20.00 and 40.00 is 70/3, an exact fraction, which displays as 23.33 at two places. The average of 10.00, 20.00, 30.00 and 40.00 is exactly the decimal 25.
POW. x ^ n with exact x and an exact integer n ≥ 0 is exact (repeated multiplication, with clause 4's overflow rule). A negative integer n is 1 / x^|n|, under the division rule. The size is checked before computing. The result of (n/d)^k has about k times the operand's width, which is known in advance. An exponent whose result cannot fit, or would pass question 13's ceiling, is decided before any multiplication, so POW(x, 10^9) allocates nothing and demotes to powf at once. Any non-integer exponent, or any inexact operand, is powf, inexact. This is the ticket's "obvious candidate" for an inexact operation, and it is the only one besides division: improvise has no transcendental functions.
Division by zero is Error("div/0") for every combination of exactness, as today. The test is exactly zero, with no epsilon (clause 6).
#6. Comparison, and the end of FLOAT_EQ_EPSILON
=, !=, <, >, <= and >= compare exactly. FLOAT_EQ_EPSILON and its six uses are deleted.
- Exact with exact: exact comparison. Two decimals compare as decimals, and a fraction against a decimal or a fraction by cross-multiplying in 256 bits.
1.5 = 1.50is true, because scale is presentation (clause 9), not value. - Inexact with inexact: f64 comparison, as today but with no epsilon (decided, question 3).
- Exact with inexact: compared exactly, as values. A finite f64 is a finite binary fraction, so this is well defined. Revision 1 converted the exact operand to f64 instead, and the review showed that rule is non-transitive for ordinary values, not only at a tie: any two distinct decimals with the same nearest f64 break it.
Exact(0.1) = Inexact(0.1)andExact(0.10000000000000000001) = Inexact(0.1)would both be true, while the two exacts differ. A non-transitive=cannot order aMIN, and it cannot key a sorted map. So comparison is exact (decided, question 7). The cost is thatExact(0.1) = Inexact(0.1)is false: the f64 is0.1000000000000000055…. That is Scheme's own answer (R7RS requires=to be transitive), and it is the honest one.
Exact mixed comparison is cheap in the common case. Convert the exact operand by clause 4's correctly rounded conversion. If the result differs from the f64, it already decides the order, because rounding is monotone. Only when the decimal rounds to that very f64 is an exact tie-check needed, against the f64's exact decimal expansion, which is finite.
EQUAL(a, b, epsilon): the explicit tolerant comparison (decided, questions 3 and 7: "Exact comparison everywhere but add equal(a,b,epsilon) to formula language").
- Meaning. True iff
|a − b| ≤ epsilon, an absolute tolerance. A relative tolerance is expressible asEQUAL(a / b, 1, epsilon), so no second function is needed. - Evaluation. The subtraction, the absolute value and the
≤use the tower's own rules. So with exact operands the test is itself exact:EQUAL(0.1 + 0.2, 0.3, 0)is true. Any inexact operand makes the arithmetic inexact, but the final≤is still clause 6's exact comparison. - Errors. A negative
epsilonisError("type"). So is a non-number in any position. - Where it may appear. Wherever a comparison may: an
IFcondition (eval_bool). It is also usable as a value of1or0, asISalready is. - Spelling. It is a new keyword. Like the others it is case-insensitive (
^"EQUAL") and is followed by(, so a bareEQUALstill names an item (PEG falls through toref_expr). The writer's keyword guard (quote::quote_name) must add it, so an item literally namedEQUALis written|EQUAL|(gotcha 34). - Home. The grammar is in
improvise-formula(formula.pest, the AST) and the evaluation inimprovise-core(both evaluators). The arithmetic it calls isnumtower's. It is migration step 3.
It replaces the epsilon's one legitimate use, a tolerant test on an inexact result, by putting the tolerance in the formula where a reader can see it.
Gotcha 17's invariant survives in a new form. The epsilon was shared by = and the division guard so that IF(x = 0, a, y / x) is coherent: the condition and the guard must agree on what zero is (improvise-0bf). Under this ADR they agree because both test exactly zero. The property is "one predicate for zero", not "one epsilon".
Both assertions of the test that pins it flip. near_zero_divisor_consistent_with_equality_epsilon (types.rs:2709) and its cached twin set X = 1e-11 and assert IF(X = 0, 1, 0) is 1 and 100 / X is div/0. Under this ADR X is not zero on either side. So IsZero becomes 0, and Ratio becomes 1e13, the very output improvise-0bf called the bug. It is coherent now, because the condition and the guard agree, and the test is rewritten to assert that agreement at X = 0 and at X = 1e-11, not either old value. The name must change too, since it names the epsilon. The change reaches existing documents as well (Consequences).
#7. NaN and the infinities live only at the inexact level
An exact number is always finite. inf, -inf and nan are inexact, as in Scheme (+inf.0, +nan.0). They keep their one spelling (improvise-55v2) in the file, on the wire, and in typed(): inf, -inf and nan, and no other (clause 3). Import keeps them as text (improvise-jc95). Where they come from is unchanged: stored data, and inexact overflow in * or POW. Exact overflow becomes inexact (clause 4), and it may overflow further to inf only at the inexact level.
#8. SUM and the other aggregates
apply_agg and eval_agg partition their values by exactness:
- Exact values are summed in a wide fixed-point integer, not with
Decimal's own+. The sum is independent of order and never rounds. That removes gotcha 18's order-dependentSUMas a class for exact data, which is nearly all data. - Inexact values are summed by ADR 009's exact f64 accumulator when it lands, and by today's fold until then.
- The result is exact if every value was exact and the exact total fits the stored bound: a
Decimal, or, under option (d), ani128fraction (a sum of fractions can fit the fraction arm without fitting aDecimal). A second condition applies to fractions: if the sum holds more than K = 8 non-decimal denominator groups it reads the inexact f64 accumulator, so it is inexact even when its exact total would have fitted (clause 8's recommendation below, question 16). Otherwise it is inexact. It must not be a fold with contagion part-way through. Such a fold switches to f64 at the first inexact value in store order, so the answer would depend on where that value sits.
Why Decimal's own addition is not enough. Revision 1 said exact values were "summed exactly, as a decimal", and that is false at the 28-digit bound. The review measured it, and it was reproduced here:
(0.30000000000000004 + 1e12) - 1e12 = 0.3000000000000000 (scale 16: rounded)
(1e12 - 1e12) + 0.30000000000000004 = 0.30000000000000004 (scale 17: exact)
Under clause 4's detect-or-demote, the first order demotes to f64 part-way through and the second stays exact. So SUM over [p, 1e12, −1e12] would differ by order in both its value and its exactness. Codex found the same with Decimal::MAX: [M, 1, −1] demotes on M + 1, and [M, −1, 1] does not. And clause 10 loads old files' 17-digit spellings as exact, so the bound is reached by ordinary data, not only at 7.9 × 10²⁸. Once a maintained sum has demoted it cannot come back, so retraction breaks too.
The fix is an accumulator for the exact partition. Every Decimal is m · 10⁻ˢ with |m| < 2⁹⁶ and s ≤ 28. So at the fixed scale 28 it is the integer m · 10²⁸⁻ˢ, below 2⁹⁶ · 10²⁸ < 2¹⁹⁰. Adding and subtracting those integers is exact, associative and commutative, so the partition is a true abelian group whatever the order. Detect-or-demote is then applied once, when the sum is read:
- if the total, with trailing zeros stripped, fits a
Decimal, the result is that exact value; - otherwise it demotes, by clause 4's correctly rounded conversion of the integer over 10²⁸.
Width. For a Decimal term, a 256-bit integer holds about 2⁶⁵ unweighted terms of 2¹⁹⁰. ADR 009 feeds its aggregators consolidated Z-set deltas whose i64 weights multiply into each term, so a weighted Decimal term can reach 2²⁵³. 256 bits is therefore enough only if weights are split into chunks, as ADR 009's ExactSum already does at 2³⁰. 320 bits (five 64-bit limbs, 40 bytes) holds any i64-weighted Decimal term with 2⁶⁶ of headroom and needs no chunking.
Revision 5 corrects that bound for option (d). A Fraction whose denominator is 2^p·5^q with k ≤ 28 also joins this partition (the option (d) section), and its numerator can pass 2⁹⁶. For example POW(10, 35) is Fraction(10^35/1) with k = 0, about 2²⁰⁹ at scale 28. Such a term reaches about 2²²⁰, or 2²⁸³ weighted, so 320 bits then holds about 2³⁶ weighted terms. That is still ample: a document holds far fewer cells. But the earlier "2⁶⁶ of headroom" holds only for Decimal terms. The figures are estimates, not measured, and the partition is still far smaller than the f64 accumulator's 568 bytes.
How wide, generically (the user's question 10: "Don't we need a much bigger accumulator (2000ish bits) to handle exact accumulation generically?"). It depends on what is summed, and three answers differ by orders of magnitude:
| what is summed | exact width needed | why |
|---|---|---|
decimals (and 2^p·5^q fractions with k ≤ 28) | 320 bits, fixed | a common scale of 28 exists, and every term is below 2²²⁰ (2²⁸³ weighted) |
| f64 values | about 2,100 bits, fixed | a common unit of 2⁻¹⁰⁷⁴ exists, and the exponent range spans 2⁻¹⁰⁷⁴ to 2¹⁰²⁴. This is ADR 009's ExactSum |
| bounded fractions with arbitrary denominators | no fixed width | the common denominator is the lcm, which grows by up to 127 bits per new i128 denominator |
So the user's figure is right in two places. It is right for f64 values, which is why ADR 009's accumulator is that size. And it is right for combining 16 arbitrary fraction denominators: 16 × 127 = 2,032 bits. No fixed register handles fractions generically. That is why option (d) keeps one group per distinct denominator, where each group is an integer:
- a group's numerator is at most
i128× ani64weight × 2⁶⁴ terms, so 256 bits per group; - the only unbounded step is the read, which combines the groups over their lcm;
- with at most K = 8 groups that lcm is at most about 1,016 bits (K·127), or 2,030 at K = 16 and 4,100 at K = 32, and the combined numerator at most K·127 + 256 ≈ 1,272 bits at K = 8 (measured lcm: 988 bits for 8 random 126-bit denominators; 1,957 at 16 and 3,924 at 32; the combined numerator was measured only at K = 32, 4,053 bits).
Under question 13 (b) that read runs in a bigint rational (num-bigint), so it needs no fixed register at all. Its result is then held to the stored bound: it is exact if it fits a Decimal or an i128 fraction, and otherwise demoted by one correctly rounded conversion. Question 10 is revised to this shape.
A sum's scale is normalized. Summing 12.50 and 1.25 reads back as 13.75, with no memory of which scales went in, because tracking the largest scale would not survive retraction. That costs nothing a person can see: a sum was never typed, so there is no typed spelling to show back.
A mixed sum is rounded twice, not once. Revision 1 said "rounded once", and that was wrong. The exact part is converted to f64 (one rounding) and added into the f64 accumulator, whose read is the second. Both steps are deterministic and independent of order, which is the property that matters. One rounding is possible, by combining the two exact totals as a rational at read time. It is not proposed, because the case is rare.
COUNT is exact (an integer). MIN and MAX order by clause 6's exact comparison, which is total over the finite values. They need one tie-break: an exact and an inexact value can be equal as values, for example Exact(0.5) and Inexact(0.5), and then "the first one met" would depend on store order. The tie-break is to prefer the exact one, so the result keeps the most information (decided, question 11; Codex, P2 on 1fe3a85d). NaN is skipped, as f64::min skips it today. Text unanimity and mixed are unchanged (gotcha 7).
For ADR 009: its accumulator stays the mechanism for inexact values. The exact part is an abelian group through this clause's wide accumulator, not through Decimal addition. Revision 1 told ADR 009 that a maintained exact Sum was bit-equal to eager "with no accumulator at all", and that was false. It is bit-equal to eager on every path provided both backends use the same wide accumulator, exactly as ADR 009 already requires of its own f64 ExactSum. Z-set weights multiply into each term, and the width above allows for that.
#9. Display, edit text and typed scale
Display of an exact value rounds the decimal, half away from zero, with round_dp_with_strategy(d, MidpointAwayFromZero), then groups. So a typed 1.005 shows as 1.01 at two places. An inexact value is rounded over its shortest round-trip spelling (clause 12, "Format"). format_value and NumberFormat::number take &Num. Gotcha 8 is unchanged: rounding is view-only and never fed back.
Edit text of an exact value is its decimal with its scale. A typed 12.50 opens as 12.50, not 12.5, so a typed value is shown back as it was typed, up to canonical spelling: +1, 1e3 and 012 become 1, 1000 and 12. An inexact value keeps today's shortest round-trip spelling (improvise-umi4). A non-finite value keeps its token.
Scale is not value, but it is state. 12.5 and 12.50 are equal under =, because they are the same number. But a typed scale is kept, persisted and shown back in the editor, so it is part of what a person typed. Revision 1 concluded that rewriting 12.5 as 12.50 "does not bump the record's version". Codex showed the cost: a client holding the old spelling could then pass the stale-basis check and overwrite the newer one without being refused.
So a record's fingerprint includes the scale. It already hashes a number's bits rather than its PartialEq (app.rs:231-250), which is why -0.0 and 0.0 fingerprint differently today. Under this ADR hash_value hashes the Num's representation: exactness, mantissa and scale. So a scale-only edit bumps the record's version, and a stale client is refused. CellValue's PartialEq stays numeric, since it answers a different question: whether two values are the same number (gotcha 7's unanimity). rust_decimal hashes 1.5 and 1.50 equally, so the fingerprint cannot use the crate's Hash. It hashes the representation explicitly.
#10. .improv persistence and migration
Reading. Every number token reads as clause 3 says: a decimal if it fits, else a fraction if it fits, else the nearest f64. The grammar's number rule (improv.pest:110-112) already accepts everything a decimal needs, including an exponent. A number token that overflows f64 (1e999, which only a hand-edited file can hold) is text, as a CSV field is (clause 3). inf, -inf and nan read through the bare_value arm as clause 7's tokens, as they do today (parse.rs:268-273).
Writing. An exact decimal is written as its decimal, with its scale. An exact fraction is written n/d, with the sign on n (-10/3), through the grammar's fraction arm, which is a place where the type is forced (clause 3). An inexact finite number needs a spelling that reads back as inexact, or a save and reload would silently make it exact. The format must say which one it holds: the ticket's 1/3 against 0.333… point. It is Scheme's own marker, #i (decided, question 4): #i0.3333333333333333. The non-finite tokens are already inexact and need no marker.
Inexact stored values are rare. A ## Data line holds raw cells: typed, imported or pasted. None of them is inexact unless it was pasted from an inexact formula result, is non-finite, or is out of Decimal's range. The marker is a correctness requirement, not a common sight.
Migration: an existing number becomes the exact decimal it spells. Every existing .improv loads unchanged in the sense that matters: every value reads as the number its text names. That is a behaviour change at the 17th significant digit, and it goes toward what the text says. An old file containing 0.30000000000000004 (possible where a computed f64 was pasted and saved) loads as exactly that decimal, not as the binary fraction the old program held. No document changes in any digit a person can see.
The version literal. #i and n/d are grammar changes. An old reader would take #i0.5 or 10/3 as text (bare_value), so a file that uses either must carry a new version literal. It shares ADR 007 clause 10's new literal (decided, question 5: "share with ADR 007"): one bump, and the first line alone picks the regime, as ADR 007 decided. A file with neither spelling reads the same under both literals.
#i and n/d are recognised only under the new literal. Under the old one, a hand-written file may hold bare text #i0.5 in a data cell, and that must keep reading as text, or an old file changes meaning on load. The writer always pipe-quotes text (persistence/format.rs:224), so no file this program wrote carries it. The grammar needs only a plain sequence arm ordered before bare_value, with no predicate, so gotcha 34's trap (the generator skips predicates) does not apply.
The round-trip tests must be re-read, as the ticket says. format_number's three spellings collapse to two (decimal, #i shortest), and the grammar-walking generator gains the #i arm. The property parse(format(parse(x))) stable is unchanged, and it is now joined by exactness preserved, which the old format could not state.
#11. The wire
CellValue crosses the wire in ModelCommand::SetCell, SetYanked and CellDisplay::value. CellDisplay::text and edit_text are strings and are unaffected. So a thin client is affected, and the ticket was right to ask for confirmation rather than assume.
Every number crosses as a string in improvise's own encoding (decided, question 6: "add our own encoding as strings on the wire … the round trip through f64 seems dangerous"). No new peer ever writes a JSON number for a cell value:
| value | JSON string |
|---|---|
| exact decimal | its decimal, with its scale: "12.50" |
| exact fraction | "n/d": "10/3" |
| inexact, finite | #i and the shortest round-trip spelling: "#i0.3333333333333333" |
| inexact, non-finite | the token, as today: "inf", "-inf", "nan" |
- The string carries the exactness. So nothing is recovered from an f64, and no NaN boxing is needed. The four spellings are disjoint. A decimal has no
/and no#, and the tokens are neither. - One parser. It is
numtower's: clause 3's number language, with the wire's exact arm as a place where the type is forced, son/dis accepted there. It replaces today's untaggedwire_f64adaptor (cell.rs:84-114), which was the workspace's only#[serde(untagged)]. So the question of which untagged arm a JSON number lands in no longer arises. - A finite inexact cell's bytes change, from a number to a
#istring. That is the cost, and it is the point.
Version skew is accepted, and the handshake version is improvise-szi8 (decided, question 9). An old peer reading any new string refuses the frame, which is loud. A new peer reading an old peer's bare JSON number reads it as inexact, which is silent, and then that old peer's 0.1 compares unequal to a typed 0.1. This matters only when a deployed page talks to a ws-server of another version, and improvise-szi8 closes it at the handshake.
typed() stays the one home of text → value (improvise-j7v6). It parses by clause 3's number language, with the type inferred, so 3/4 typed into a cell stays text (decided, question 12). A browser composes exact values with no second rule.
#12. The seams
gp-tree is out of scope and needs no change. A number crosses into a fit as text (dataset.rs:50-56), which preprocess parses into f32. An exact 12.50 crosses as "12.50", and it parses to the same f32. The emitted thresholds are decimal text (improvise-gp/src/lib.rs:285-298), so they become exact literals, and exact comparison against exact data routes the same way as the f64 comparison does today, except within f32 rounding of a threshold. That boundary difference already exists between f32 and f64. scoring_known_answers.rs's bit patterns (gotcha 37c) are untouched, because gp-tree never sees a Num.
Import. Two sources, two rules. This follows Codex's P2 on 962d7f90, which aligns the contract with PR #321.
CSV. PR #321 keeps every non-empty CSV field as its verbatim text (
Value::String, carried asScalars::Text). It does so to preserve numeric-looking category identifiers. So a CSV measure is parsed from that text by clause 3's number language. #321'snumber_ingate is that language's gate, finite values only (revision 6), so the analyzer and the parse agree on every string:1.5e3is the exact1500, and1_000,nan,infand1e999are text. It keeps its significant digits and its scale, so a CSV12.50opens in the editor as12.50. It falls back to the nearest f64 only when it fits neither exact arm, never because it failed to parse.- Inferred and forced columns differ on
n/d(decided, question 12). While the analyzer is inferring a column's kind,3/4is text, so a column of dates stays a column of dates. Once the user forces a column to a measure (a wizard override, or--measure),3/4in it reads as the exact fraction3/4. - Revision 3's description of
parse_csv_field(csv_parser.rs:167-186: ani64, else anf64Number) is today's code atb639266b, and #321 replaces it. The ADR does not reintroduce that normalization. - If this ADR lands before #321, the same contract holds by reading the field's text before
parse_csv_fieldturns it into a number.
- Inferred and forced columns differ on
JSON. A JSON number is read from its source lexeme through
serde_json'sraw_value, and never through the f64as_f64(wizard.rs:425) reads today (decided, question 6; clause 3). So a JSON12.50keeps its scale, and a 19-digit integer stays exact. Revision 4's shortest-spelling rule for JSON is withdrawn.- This restructures the JSON half of the import pipeline (revision 6, from the review of
33833f28).ImportPipelinecarriesserde_json::Value(ten uses inwizard.rs, and more inanalyzer.rs), and aValue's numbers are already f64.raw_valuehands over a lexeme only to a reader that deserializes intoRawValuethrough a hand-written visitor. It does not work through aValue, or through any buffered path such as an untagged enum. So the JSON reader becomes a hand-written deserializer that keeps each number as its source text, and the pipeline carries that text to the number language, as #321 already does for CSV. - That is the restructuring revision 3 cited as a reason not to carry the text. It is paid here because the user ruled out the round trip through f64 (question 6), and this is the only way to honour that for JSON. It is migration step 5's largest part.
- This restructures the JSON half of the import pipeline (revision 6, from the review of
The collision "sum" policy (wizard.rs:307) then sums exactly, by clause 8.
Format. FormatPlan is unaffected: it chooses a format, not a value. The rounding itself moves to numtower (clause 14), and it covers all three arms:
- a decimal or fraction is rounded exactly;
- an inexact value is rounded over its shortest round-trip spelling, as a decimal. That is the fix improvise-felo.9 names, and it makes a typed-then-computed
1.005behave.
The rounding mode is a parameter, so improvise's half-away-from-zero policy (gotcha 8) stays improvise's and does not become the crate's.
#13. The crate: rust_decimal
Chosen on the table above. Three reasons:
- Size and speed. It is
Copyand 16 bytes, with no heap. So aCellValuedoes not start allocating for every number. It is about 2.5× faster thanbigdecimalon SUM, and about 40× faster on the formula workload. - Bundle. It is the smallest marginal addition to the wasm bundle.
- Bound. It is bounded, and the bound is the right size for this domain. 28 significant digits holds any money amount and any count.
bigdecimal's unbounded add costs a heap allocation for a precision no pivot table uses. Its division still rounds, so it does not buy exact division either.
Its serde support is not a reason. numtower has no serde (clause 14), and the wire spells a value in its own encoding (clause 11). Revision 5 still listed it, and that contradicted both.
The cost is three duties the crate does not do for us, each named where it applies: detecting rounding at the bound (clause 4), parsing (clause 3 parses the digits and exponent itself, because from_str rounds silently and from_str_exact rejects 1.5e3), and converting to f64 by a correctly rounded path rather than to_f64 (clause 4). A fourth is avoided rather than done: its serde deserializer accepts JSON numbers, so the wire does not use it. The wire parses its own string encoding through numtower (clause 11). num-rational's unbounded BigRational is rejected as the default on measurement (above); its bounded Ratio<i128> is the fraction arm (question 2). bigdecimal is the fallback if the bound ever matters. Other crates (fastnum, dashu) were not evaluated.
#14. The numeric tower is its own crate
At the user's direction (revision 4): "I think ADR 005 should implement the math operations in a separate crate". The numbers are a problem-agnostic workspace crate, like gp-tree and ADR 009's zset, and it knows nothing about improvise.
Name. numtower (decided, question 14). It names the idea, Scheme's numeric tower, rather than this program.
What it holds:
Num, with itsExact(Decimal),Fraction(question 2, decided (d)) andInexact(f64)arms;- the arithmetic and contagion (clause 4);
- the rounding and overflow detection: the scale test, and the
2^p·5^qtermination test (clauses 4 and 5); - the correctly rounded conversion to f64 (clause 4);
- exact comparison, the
MIN/MAXtie-break included (clauses 6 and 8); - the exact-sum accumulator: the 320-bit decimal partition, plus the per-denominator groups under (d) (clause 8);
- rounding any
Numto n places for display, with the rounding mode a parameter: exact values exactly, and inexact values over their shortest round-trip spelling (clause 12, "Format", and improvise-felo.9); - the f64 → decimal shortest-spelling conversion, which the display rounding and the
#ispelling on the wire and in the file all use; - parsing that never rounds silently: digits and exponent to an exact value, then the decimal, fraction and f64 arms in that order (clause 3);
- the canonical text of a value: the decimal with its scale,
n/d,#i…, and the non-finite tokens; - clause 3's number language, both its gate and its parse, including the forced
n/darm; - the wide integers: a fixed-width
[u64; 5]for the 320-bit accumulator, and 256-bit helpers for the division reduction and the cross-multiply. These are hand-rolled, because they sit on hot paths and must not allocate.
What it depends on (revision 5 corrects revision 4, answering B3 of the review):
rust_decimal, with default features off exceptstd;num-rational, withdefault-features = false, forRatio<i128>;num-bigint, always. Revision 4 said "only if question 13 is answered 'unbounded intermediates'", and that was false by the ADR's own text. Three paths need a bigint whatever question 13 says:- display beyond 38 places;
- converting a grouped sum's 256-bit numerator over an
i128denominator; - question 13 (b)'s widened intermediates and the grouped read.
(
num-rational's default features would pull it in anyway.)- not
serde: the wire is improvise's concern (below).
Bundle cost under (d). rust_decimal probed at +15.4 KB gzipped marginal. num-rational with num-bigint probed at +20.8 KB gzipped on its own. The two together are unprobed, and are estimated at up to about +36 KB gzipped. The user's "yes" to question 8 was given against the first figure alone. The decided-questions section flags that, and migration step 1 measures the real bundle.
All of these build for wasm32-unknown-unknown: each was built there in the size probe. The crate is added to the wasm CI job's list, and checked with cargo tree --edges normal.
The dependency direction is one way. improvise-core depends on numtower, and numtower depends on no improvise crate. It is the gp-tree/improvise-gp shape: the general thing below, the seam above.
Improvise's own concerns stay in improvise crates and call into it:
| concern | stays in | calls |
|---|---|---|
CellValue::Number(Num), as_f64, edit_text, the record fingerprint's hashing of a Num's representation (clause 9) | improvise-core (fingerprint: improvise-command) | Num's accessors for exactness, mantissa, scale and fraction parts |
the formula evaluator, FLOAT_EQ_EPSILON's deletion, aggregates' use of the accumulator | improvise-core | Num's arithmetic, comparison and accumulator |
formula literals: Expr::Number(Num) | improvise-formula | numtower's parse |
the .improv grammar arms (#i, n/d), the writer, the version literal | improvise-io | numtower's parse and canonical text; the #i prefix and the grammar are improvise's |
| serde and the wire encoding (clause 11) | improvise-core, replacing CellValue's untagged adaptor | the canonical text of every arm, and the number language to read it back |
display formats (,.2f), comma grouping | improvise-core's format.rs | numtower's round-to-n-places; the grouping stays in improvise |
typed() | improvise-protocol | numtower's number language, with the type inferred (question 12: n/d stays text) |
Where the tests live. Anything about numbers lives in numtower's own tests, where no improvise type can make them pass by accident:
- the property tests of migration step 1 (no rounded
Exact; total contagion; exact comparison is transitive;n/dnormalization); - the differential tests against an exact
BigRationaloracle: every operation's result, the f64 conversion, and the accumulator's read against a direct exact sum; - the order-independence and retraction tests for the accumulator, seeded with the review's
[0.30000000000000004, 1e12, −1e12].
Improvise's crates keep the tests about improvise:
improvise-core: the evaluator, the improvise-0bf zero predicate, and the scale-aware fingerprint;improvise-io: the grammar round trip with exactness preserved;- the protocol: which wire arm a JSON number or string lands in.
The benchmark example lives in numtower/examples/, where its dependencies are already normal ones. That is what lets it be committed at all (appendix).
ADR 009's ExactSum is an f64 superaccumulator, in the proposed zset crate. Clause 8 needs it for the inexact partition, and a mixed sum's read combines it with the exact partition. ExactSum moves into numtower (decided, question 15 (a)), the one home for exact summation. zset stays independent of numbers: it keeps its abelian-group trait, and ADR 009's seam crate (improvise-incremental, its question 2) wraps numtower's accumulators in a newtype that implements that trait. The orphan rule forbids implementing zset's trait for numtower's type anywhere else, and the newtype costs nothing. The alternative, numtower depending on zset for ExactSum, would make the number crate depend on a stream-processing crate.
numtower can land holding ExactSum alone, ahead of this ADR and independent of it. ADR 009's question 3 recommends its exact accumulator "without waiting for ADR 005". Under question 15 (a) that accumulator lives in a crate this ADR's migration creates, which would make ADR 009 wait after all. It does not have to. Nothing in ExactSum depends on Num, so numtower may first land with ExactSum and its tests only, before this ADR is accepted, and Num joins it in migration step 1. ADR 009 then depends on numtower and not on ADR 005.
#Option (d) for question 2: bounded exact fractions
The user asked for this option (revision 3): "I think (d): exact fractions with a size limit. should be added." It is specified here and measured the same way as the others: same machine (Apple M4 Max, 64 GB, rustc 1.98.1, release), same typed two-place data (0.01–999,999.99, SplitMix64), and num-rational 0.4.2's checked operations. Those reduce by the gcd on every operation.
#The number
An exact non-decimal value is a reduced fraction n/d with n and d each an i128 and d > 0. The alternative bound, i64, was measured and is too small:
| what stops being exact | i64 | i128 | rust_decimal |
|---|---|---|---|
running sum of 18k or 90k margins (Rev − Cost) / Rev, first overflowing term (1-based: the term whose addition overflows), 8 seeds | 3rd–4th | 5th–6th | not exact (a non-terminating quotient) |
1.05^k (5% compound growth) | k = 15 | k = 29 | k = 15 |
i128 doubles every horizon, for 2–3× the cost of i64 (below). A value is 32 bytes.
Decimals are a subset, and they keep their own arm. A decimal is a fraction whose denominator is 2^p · 5^q, so (d) could hold everything as fractions. It should not. A fraction has no scale, so 12.50 would need a scale field beside it. And every operation would pay the gcd, which the measurements put at 30–300× a decimal add. So the recommended shape is a hybrid:
pub enum Num {
Exact(Decimal), // typed values, money, `12.50`: scale as today
Fraction(Box<Ratio<i128>>), // exact, not a finite decimal: `10/3`
Inexact(f64),
}
A
Fractionis only ever produced where option (a) would have producedInexact:- a non-terminating quotient;
- a decimal operation that exceeds 28 digits but whose reduced fraction fits (
1.05^kfor 15 ≤ k ≤ 28).
- A
Fractionwhose denominator turns out to be2^p · 5^qand fits is normalized back toExact(Decimal), so each value has one representation. - Scale lives only on the decimal arm. Typed values are decimals, so a fraction was never typed and has no spelling to preserve. That answers "how is scale carried" without a scale field.
- The fraction arm is boxed. That keeps
Numat 24 bytes, the same as option (a); measured, an inlineRatio<i128>makes it 48. The heap allocation falls only on fraction values, which are formula results. PerAGENTS.md, theBoxhandling lives inNum's constructors, apart from the arithmetic.
#Operations
- Division stays exact.
10/3isFraction(10/3), and10/3 × 3is exactly10, which normalizes back toExact(10). Both measured. Overflow demotes at the store (question 13, decided (b); revision 7 replaced the per-operation wording, which Copilot found contradicted it). The fast path uses checked
i128arithmetic after the gcd reduction (num-rational'schecked_add/checked_mul/checked_divdo exactly this). ANonemay mean the reduced result does not fit, and may mean only that an intermediate overflowed (checked_addgoes through the lcm of the denominators) while the reduced result fits. So aNonewidens that step to a bigint rational and the stored result is tested against thei128bound: exact iff it fits, else the correctly rounded f64 of the exact fraction, which isInexact. It is deterministic. Past question 13's ceiling, the intermediate demotes (the first of the two stated exceptions).Revision 3 cited
Ratio<i128>::to_f64agreeing withBigRational's conversion. That was circular: both sharenum-rational's oneratio_to_f64routine. The review ran an independent check instead. It took 200,000 random reducedRatio<i128>s, with numerator and denominator widths from 20 to 126 bits and both signs. For each, it asked whether the exactBigRationallies inside the round-to-nearest-even interval of the returned f64. There were 0 failures. That is evidence, not proof, and migration step 1's property test uses this interval form.- Contagion is unchanged. Exact ∘ fraction is a fraction (or a decimal after normalization, or f64 on overflow). Anything with an inexact operand is inexact.
POWwith an integer exponent is exact while it fits. That is why1.05^kreaches k = 28.- Comparison is exact. Two fractions are compared by cross-multiplying in 256 bits (an
i128times ani128fits). A fraction against an f64 follows clause 6's exact rule. - Display rounds the exact fraction to the view's places, half away from zero, exactly:
n · 10^places / d, then rounded. So10/3at two places shows3.33, and2/3shows0.67. In 256 bits that holds up to about 38 places, becauseplacesis au8(parse_number_format) andn · 10^placespasses 2²⁵⁵ above that. Beyond 38 places the computation takes the bigint path. That is display only, and rare.
#Sums: the one real design choice
Clause 8's accumulator holds decimals only: an integer at the fixed scale 28. A fraction whose denominator is not 2^p · 5^q has no finite value at any fixed scale. There are three ways to sum one:
- Demote each fraction term to f64 into ADR 009's accumulator. Simple, and independent of order. But
SUM(v / 3)is then inexact, even thoughSUM(v) / 3is exact. Group by denominator. Keep one wide integer numerator per distinct reduced denominator; decimals are the one group clause 8 already has. Adding or retracting a term touches only its own group. So the state is independent of order, and retraction is exact.
How it is read is the recommendation below: exactly, in a bigint rational, when there are at most K non-decimal groups (question 13 (b)); otherwise from a maintained f64 accumulator of the groups' values, with the decimal partition converted once. Both paths are deterministic and independent of the order the terms arrived in. (Revision 5 still described a checked-
i128read here, with a fallback that summed each group's f64 at read. That contradicted the maintained accumulator below.)The cost is memory. It is O(distinct denominators) per summed group, bounded by the cells, the same order as ADR 009's multisets.
- Demote the whole sum on mixed denominators. Rejected. Whether two denominators ever met depends on nothing a user can see.
Two rules the grouping needs.
- A group whose numerator returns to 0 is dropped. A retracted denominator then cannot affect the read, and "the current groups" is a function of state alone.
- A
Fractionwhose denominator is2^p · 5^qjoins the decimal partition when its exact scalek = max(p, q)is at most 28. An example is one born from a decimal overflow with denominator10^17. At scale 28 its value is an exact integer, which the 320-bit accumulator holds. Withk > 28(for example1/2^40) it is a group of its own, keyed by its denominator like any other.
Recommendation: (2), with a bound on the exact read (revision 4, answering review BLOCK D2). Revision 3 said (2) "costs nothing where it cannot help", and that was false in exactly that case. The sum of margins has one denominator per record: 17,996 to 17,999 distinct at 18k, and 89,923 to 89,956 at 90k. So its state is O(records), and so is every read. Under ADR 009 a maintained SUM whose read is O(records) is no longer incremental: every one-cell edit would re-read 90k groups, where (a) holds a 40-byte integer and reads in O(1). The review proposed a mitigation, and it is adopted:
- Beside the non-decimal groups, keep one ADR 009 f64 accumulator of each such group's correctly rounded value. Updating a group retracts its old f64 and inserts its new one, so it stays order-free and retractable.
- The decimal partition is exempt (revision 5, B2 of the review). Revision 4's wording put every group, the decimal partition included, into the parallel accumulator, which would have charged an ordinary decimal
SUMabout 1 µs per edit where (a) pays a 40-byte integer add. The decimal partition stays in its 320-bit accumulator alone, and is converted to f64 once, at an f64 read (only when there are more than K non-decimal groups). So a pure-decimalSUMpays nothing for (d). - Read exactly only when the current number of non-decimal groups is at most K = 8 (decided, question 16; revision 8). Otherwise read the f64 accumulator, and the result is inexact. The count is a function of the current state, not of history, so the choice is independent of order.
What that costs.
- Update of a non-decimal group (an estimate): O(log D) for the group map, plus one correctly rounded conversion of the group's new value. That conversion is a 256-bit numerator over an
i128denominator, estimated at about 1 µs through a bigint rational. Plus two accumulator updates at 2.0–3.6 ns (ADR 009's figures). An update of the decimal partition is one 320-bit add. Exact read (measured in revision 6). At most K combinations of groups that hold 256-bit numerators, in a bigint rational (question 13 (b)). The worst case is K distinct denominators near
i128's size, where the lcm grows about 127 bits per group. Measured with 250-bit numerators and random 126-bit denominators, 200 reads each (appendix):K lcm bits BigRationaladd per grouplcm, then one reduce 2 252 16 µs 7 µs 8 988 127 µs 52 µs 16 1,957 448 µs 174 µs 32 3,924 1.9 ms 0.67 ms - Revision 5 estimated 16–34 µs at K = 32 from the SUM benchmark's rate. Those operands had small typed denominators, so the estimate was about 50× too low at this size. The cost grows roughly as K², because each step works on an lcm that grows linearly.
- Combining over the lcm and reducing once is 2.3–2.8× faster than reducing after every add, and it gives the same value (the benchmark asserts it).
numtower's read should do that. - Denominators a person produces (
/ 3,/ 12, a percentage) are small, and the read is then far cheaper. The table is the bound, not the common case. The value of K is 8, decided in question 16.
- f64 read: ADR 009's 0.6–1.1 µs.
- Memory is still O(distinct denominators), because the map must survive retraction to know when the count falls back under K. For a 90k-record margin sum that is about 90k × (16-byte key + 32-byte numerator + map overhead): an estimate of 6–8 MB for that one summed group, the same order as ADR 009's per-cell multisets. Not measured.
This keeps (d)'s wins, because SUM(v / 3), averages and percentages have one or a handful of denominators, and it bounds the rest. The sum of margins reads the f64 accumulator and is inexact, as under (a). Its exact combination would overflow by the 6th term anyway (below). The 32 of revisions 5 to 7 was a judgement and was not tuned. The read's measured cost above is why question 16 recommended a smaller one (K = 8). The user first chose 32 and then 8, so 52–127 µs is the accepted worst case. It is paid per read, and under ADR 009 per edit, by a maintained SUM that holds between 2 and 8 distinct non-decimal denominators near i128 size; a sum with more groups reads the f64 accumulator, and one with few or small denominators is far cheaper (the table is the bound).
#The file and the wire
.improv. A fraction is writtenn/d, with a sign onn, for example-10/3. Thenumberrule does not accept/, and an old reader would take10/3as text (bare_value), silently. So it needs a grammar arm ordered beforebare_value, and the new version literal. That is the same bump as#i(question 5), so (d) adds no second bump.- The wire. A fraction is a string
"10/3"in the exact arm of clause 11's adaptor. An old peer tries it as a non-finite token and refuses the frame, loudly. - Typing
3/4stays text. That is question 12.
#Measured
Cost per operation, 18,000 operand pairs, ns, best of 20, the range over two runs:
| add | mul | div | |
|---|---|---|---|
rust_decimal (checked) | 0.9–1.3 | 1.5–2.2 | 40–55 |
Ratio<i64>, two-place operands | 55–68 | 144–179 | 78–113 |
Ratio<i128>, two-place operands | 123–178 | 324–472 | 198–288 |
Ratio<i128>, margin operands (unrelated denominators) | 313–457 | 407–652 | 223–325 |
f64 is not in the table, because this harness's f64 loop was optimized away. The SUM figures below give f64's per-add cost. num-rational's gcd over i128 is generic. A hand-written one with a 64-bit fast path would likely be several times faster, but that was not measured.
SUM over typed two-place values, as fractions, ns per element, best of 20:
| cells | f64 | rust_decimal | Ratio<i64> | Ratio<i128> |
|---|---|---|---|---|
| 18,000 | 0.8–1.2 | 4.6–6.4 | 65–76 | 155–226 |
| 90,000 | 0.8–1.2 | 4.5–6.5 | 69–87 | 163–239 |
Both bounds held the whole sum with no overflow. The sum was the same in both orders and equal to the decimal sum. But Ratio<i128> is 25–50× slower than rust_decimal: 14–22 ms for a 90k SUM, against 0.4–0.6 ms. That is why the hybrid keeps decimals in their own arm. Under it, this SUM costs what it costs under (a).
How often realistic formulas overflow i128, 8 seeds, 18k and 90k records:
| formula | overflows |
|---|---|
(Rev − Cost) / Rev per record | never (864,000 records: 8 seeds × (18k + 90k), both bounds) |
running SUM of those margins | at the 5th–6th term in every seed, counting 1-based (i64: 3rd–4th) |
v / SUM(v) × 100 per cell (a percentage of the total) | never (0 of 144,000 and 0 of 720,000, both bounds) |
SUM(v) / N (the average) | never |
SUM(v / 3) against SUM(v) / 3 | never; equal exactly |
1.05^k | at k = 29 (i64 and rust_decimal: k = 15) |
#Where (d) beats (a), and where it does not
(d) is better:
- a non-terminating quotient stays exact:
10/3 × 3 = 10(measured), and soMargin × Revenue = Profitholds exactly; - the average over any count;
SUM(v / 3) = SUM(v) / 3;- exact comparison of ratios;
- compound growth exact to k = 28 rather than 14.
(d) is no better:
- the sum of ratios, which overflows by the 6th term and ends inexact as under (a);
- anything already exact under (a), which is nearly all typed data.
(d) costs:
- a third numeric arm;
- a grouped sum accumulator;
- a grammar arm and the wire spelling
n/d; - question 12;
- 120–650 ns per fraction operation, paid only where (a) would have demoted;
num-rationalandnum-bigintin the browser bundle: +20.8 KB gzipped on their own, and up to about +36 KB together withrust_decimal(unprobed together; clause 14).
Scale after the fraction arm (revision 5, the review's point on question 13). A result that passed through the fraction arm and normalized back to a decimal carries its minimal scale. A result that stayed decimal keeps clause 4's scale. So a × (b + c) and a × b + a × c can be = and still differ in scale. The review's example (reasoned, not run) is a = 123456789012345.6780, b = 12345678901234.5678 and c = −b + 0.0001. The first stays decimal at scale 8. In the second, a × b overflows 96 bits, so the sum comes back through the fraction arm at scale 7. The editor seed and the scale-aware fingerprint (clause 9) then differ between the two spellings. This is true under (d) whatever question 13 says. It is stated rather than fixed, because scale is presentation, and a computed value was never typed.
#Folded in: what changed in the clauses when the answer became (d)
Revision 3 listed these changes as conditional. Revision 5 makes them normative, because the user answered question 2 "(d)":
- Clause 1: three levels: exact decimal, exact bounded fraction, inexact.
- Clause 2:
Numgains the boxedFractionarm. - Clause 3: entry tries the fraction arm before f64, as arithmetic does (revision 6).
- Clause 4: a decimal operation that exceeds 28 digits tries the fraction arm before f64.
- Clause 5: a non-terminating quotient is a
Fraction.AVGis exact. - Clause 6: fraction comparison is by cross-multiplication.
- Clause 8: sums group by denominator, as above.
- Clause 10: the
n/dspelling. - Clause 11: the wire spells a fraction
"n/d". - Question 12 decided typed input:
n/dis text where the type is inferred, and a fraction where it is forced (clause 3).
#Alternatives rejected
- Exact rationals as the default (Scheme proper). Measured above: an 18,000-record average of ratios does not finish. It would be the right answer for a symbolic calculator and the wrong one for a pivot table.
- A rounded decimal that still calls itself exact (SQL
NUMERIC:1/3becomes0.3333…at 28 places, marked exact). It keeps "decimal math" true everywhere, but then "exact" means "exact except after a division". Equality, ADR 009's group law and every future reasoning about exactness would carry that exception silently. It is question 2's option (b), for the user to overrule. - Keep f64 and adopt only ADR 009's accumulator. It fixes large same-sign sums. It leaves per-cell arithmetic, small sums (16% of positive 3-term sums), signed sums (about 40% at every length), display of typed values and the epsilon exactly as they are (Context).
- Three levels (exact decimal, inexact decimal, f64). An "inexact decimal" arm for rounded quotients would add a third arm to every numeric match. It would buy only a 28-digit rather than a 17-digit approximation of a number that is not a decimal anyway.
- A new
CellValuearm besideNumber(f64). Rejected in clause 2.
#Migration
In order. Each step lands on its own, with the suite green.
The
numtowercrate, first and alone (clause 14). It holdsNumand its arithmetic, with the contagion table (clause 4) and the scale-based rounding detection. It holds the correctly rounded conversion to f64, the division andPOWrules (clause 5), exact comparison (clause 6), the exact-sum accumulator (clause 8), rounding to places, and clause 3's number language. It also holds the fraction arm and its grouped sums (question 2 is decided (d)), and the widening rule with its ceiling (question 13 is decided (b); the ceiling's value, 8,192 bits, is the steward's proposal and not the user's decision). Nothing in improvise depends on it yet, so it lands with its own tests and changes no behaviour. It may be preceded by anumtowerholding onlyExactSum, for ADR 009 (clause 14).Its property tests:
- an
Exactresult is never a rounded one (inject a silently-rounding add and watch it fail); - contagion is total;
- the conversion agrees with
str::parse::<f64>of the decimal text. Injectto_f64and watch it fail on the review's63294.60…case. The random generator spans 96-bit mantissas and scales 0–28: with 15 or fewer digits the brokento_f64agreed 200,000 times out of 200,000, so a narrower range is vacuous; - a fraction's conversion lies inside the round-to-nearest-even interval of the exact value (the review's independent form);
- exact mixed comparison is transitive;
- the accumulator is independent of order (clause 8's seed case);
- division's direct fit test:
1/2^40and1/5^30are fractions,1e-28 / 0.5is the exact decimal2e-28, and multiplying back is not used (clause 5); the number language's gate and parse agree on every generated lexeme. The seed cases are:
1.5e3(exact1500),1_000(text),-0.0(exact0.0), and3/4(text when inferred, a fraction when forced);1e999and-1e999(text: a finite lexeme never reads as infinity),nan,infandInfinity(text in the gate), and1e-999(an inexact zero);1e-30(the exact fraction1/10³⁰),0.12345678901234567890123456789(an exact fraction, not a rounded decimal), an integer betweenDecimal's maximum and 2¹²⁷ (an exactn/1), and1e-40(inexact: it fits neither arm);
- a typed value and the same value computed are equally exact:
1e-30parsed equals1e-15 * 1e-15, arm and value both; - the grouped read combines over the lcm and reduces once, and agrees with a
BigRationalsum of the groups.
The differential tests run against a
BigRationaloracle. The benchmark goes innumtower/examples/. Add the crate to thewasmCI job. Measure one whole recompute at 18,000 and 90,000 cells against today once step 3 lands, and name the machine. The arithmetic figures above are a microbenchmark, not the evaluator.- an
improvise-coredepends onnumtower, andCellValue::Number(Num)replaces the f64 across the 672 sites. This is mechanical, andas_f64keeps the seams compiling.hash_valuehashes the representation, scale included (clause 9).- Both evaluators move to
Num.FLOAT_EQ_EPSILONis deleted. The improvise-0bf tests are rewritten to assert one zero predicate (clause 6).EQUAL(a, b, epsilon)lands here: its grammar and AST inimprovise-formula, its evaluation in both evaluators, andEQUALinquote_name's keyword guard (clause 6). - Aggregates partition by exactness and use
numtower's accumulator (clause 8). Its own order-independence test is innumtower(step 1). Here the test is thatapply_aggandeval_aggroute through it: seed the review's[0.30000000000000004, 1e12, −1e12]through the evaluator.Decimal's own+must fail it. Entry points:
typed(), the import pipeline's measure read, formula literals (clauses 3 and 12). The largest part is the JSON reader: a hand-written deserializer that keeps each number's source text throughraw_value, because aserde_json::Valuehas already made it an f64 (clause 12). The import tests assert:- a CSV
12.50and a JSON12.50both keep their scale, because both are parsed from their lexeme; 1.5e3imports as the exact1500, and1_000imports as text;nan,inf,1e999and-1e999import as text, so #321'sa_nonfinite_numeric_token_stays_text_rather_than_becoming_zerostays green unchanged;typed()readsinf,-infandnanas clause 7's tokens, andInfinity,NaNand1e999as text (the stated behaviour change);3/4is text in an inferred column and the fraction3/4in a column forced to a measure.
- a CSV
- Display and edit text (clause 9). The
1.005case is the regression test, and it fails at HEAD today. If improvise-felo.9 lands first, this step reuses its test. .improv: read exact, write with scale,n/dfor a fraction,#ifor inexact finite, and ADR 007's version literal (clause 10).- The wire: the string encoding replaces the untagged adaptor (clause 11), with the retired-spelling discipline of gotcha 42: assert the error kind, not merely that an error occurred. The version handshake is improvise-szi8, separately.
#Open questions
The user answered questions 1–9, 11 and 12 inline on e4acf643, and 10, 13, 14 and 15 inline on 33833f28, and question 16 inline on b232c5a9. Each is marked decided below, and quoted in full under "What the user decided". No question is open. Nothing is renumbered.
- The tower's shape. Decided (the user): three levels: exact decimal, exact bounded fraction, inexact f64 (clause 1). The original recommendation, two levels, was written before option (d) existed.
- Non-terminating exact division. (a) inexact f64; (b) a 28-digit decimal that stays marked exact (SQL
NUMERIC); (c) an exact rational (Scheme proper); (d) an exact fraction with a size limit. Decided (the user): (d), in the hybrid form (the option (d) section). - Tolerance on inexact equality. Decided (the user): no tolerance on
=. A formula functionEQUAL(a, b, epsilon)is added instead (clause 6). It replaces this question's earlier "anAPPROX(a, b, tol)if it is ever wanted". - The
.improvspelling of an inexact finite number. Decided (the user):#i(clause 10). - The version literal. Decided (the user): share ADR 007 clause 10's literal (clause 10).
JSON import precision, and the wire. Decided (the user): no round trip through f64.
- The wire spells every number as a string in improvise's own encoding (clause 11).
- JSON import reads each number's source lexeme through
serde_json'sraw_value(clauses 3 and 12). arbitrary_precisionstays rejected, because it breaks serde's buffered deserialization of numbers under the workspace's internally tagged enum and itsflatten.- The earlier recommendation, "shortest spelling", is withdrawn.
- Mixed-exactness comparison. Decided (the user): exactly, plus
EQUAL(a, b, epsilon)(clause 6). - The dependency. Decided (the user): yes. That answer was given against
rust_decimal's +15.4 KB gzipped. Under (d),num-rationalandnum-bigintadd about +20.8 KB on their own, up to about +36 KB together (unprobed). If that changes the answer, this question reopens (clause 14). - Version skew on the wire. Decided (the user): accept it, and the handshake version is filed as improvise-szi8 (clause 11).
The exact-sum accumulator's width. Decided (the user): (a), with "320bits is fine" for the decimal partition. The value of K is split out as question 16, because the read's cost was measured after the answer. The question as it was put (revised in revision 5, after the user asked: "Don't we need a much bigger accumulator (2000ish bits) to handle exact accumulation generically?"). Clause 8's "How wide, generically" answers with numbers:
- decimals need 320 bits;
- f64 values need about 2,100 bits, which is ADR 009's
ExactSum; - fractions need no fixed width at all, because their common denominator grows by up to 127 bits per distinct
i128denominator. 2,032 bits holds 16.
Options:
- (a) a 320-bit decimal partition, plus a 256-bit numerator per fraction group, plus a read that combines at most K groups in a bigint rational and then applies the stored bound;
- (b) one fixed 2,048-bit exact register, which holds K = 16 arbitrary denominators, with no bigint on the read;
- (c)
Decimal's own+, accepting demotion that depends on order.
Recommendation: (a), with K = 32 as proposed here. Question 16 later set K = 8.
- A fixed register cannot be generic for fractions at any width.
- 2,048 bits pays 256 bytes per summed group for a combination that rarely fits the stored bound anyway.
- The bigint read is paid only when a sum holds 2 to K distinct fraction denominators: about 16–34 µs at K = 32, an estimate. (Revision 6 measured it: 0.67–1.9 ms at K = 32 in the worst case, 52–127 µs at K = 8, and the user chose K = 8. See question 16.)
- (c) breaks order-independence (revision 2).
- The
MIN/MAXtie-break. Decided (the user): prefer the exact value (clause 8). - Typing a fraction. Decided (the user):
n/dis text where the type is inferred and a fraction where it is forced (clause 3). Sotyped()and the import analyzer keep3/4as text, and a column forced to a measure reads it as a fraction. An editor opened on a fraction shows10/3, and an untouched commit writes nothing, on both front ends. The browser already skips an untouched commit (resolve.rs:1421); the TUI must be held to the same rule (the improvise-umi4 lesson). Where the fraction bound applies. Decided (the user): (b). Added in revision 4, and put as follows. Is the
i128bound checked (a) after every operation, or (b) only on the stored result, with every intermediate inside one formula evaluation unbounded? Under (b) an intermediate uses thei128fast path and widens to a bigint rational only when a step overflows. Recommendation: (b). It was the orchestrator's recommendation in a discussion with the user.The argument. Under (a), whether a result is exact depends on how the formula is written.
a × (b + c)anda × b + a × care the same number, but an intermediate can overflow in one spelling and not the other, so one is exact and the other a demoted f64. Under (b) the rule is one sentence: a stored value is exact if and only if it fits. Algebraically equal formulas give equal values. (Two stated exceptions: the ceiling below, and aSUMof more than K = 8 non-decimal denominator groups, which reads inexact by question 16 whatever its value.)The rule has two exceptions, and they are stated rather than hedged (the ceiling from revision 5, the review of
87ae21ca; the K cutoff from revision 7, Codex onbe9de2ee):- The ceiling. Widening carries a size ceiling so that a pathological expression cannot grow a bigint without limit. It must be at least K·127 + 256 bits, so that the grouped read (below) never reaches it: 1,272 bits at K = 8 (it was 4,320 at K = 32). Revision 5's example of 4,096 bits was below the K = 32 figure, and a worst-case K = 32 read would have hit it (the review of
33833f28). Proposed: 8,192 bits. That value is the steward's proposal from revision 6, commit02bcfcb1(it first appears after the user's answer "(b)", which was given against the text's 4,096-bit example), so it is not part of the user's decision, and approval of the ADR confirms it. It covers K = 8 by 6,920 bits and K = 32 as well, and costs nothing until a value is that large. A smaller ceiling would now suffice. Past it, the intermediate demotes, and by contagion the stored result is inexact even when the exact result would fit. That is spelling-dependent, so distributivity fails past the ceiling. It is the first exception to "exact iff it fits", and no ledger reaches it.POWchecks its result size before computing (clause 5), so the ceiling is never reached by allocating first. - The K cutoff, which does override representability. A
SUMholding more than K = 8 non-decimal denominator groups reads the inexact f64 accumulator, so its stored result is inexact even when the exact total would fit the bound. That is the second exception. It is a policy about the read's cost (question 16), not about whether the value is representable, and it is the consequence of the user's K = 8. Flagged reading (revision 7, restated in revision 8): the user decided K on question 16's text, which says "Above it the read is the inexact f64 accumulator", and answered question 10 (a) with "at most K groups". No "What the user decided" item says in terms that the cutoff overrides representability. That sentence is the ADR's reading of those two answers, so approval confirms it. - Not an exception: the grouped read at K groups or fewer. Revision 4 described the grouped sum's read as checked
i128, and that can overflow in an lcm step while the reduced result fits. Under (b) the read is widened like any intermediate (clause 8, "How wide, generically"), so it is exact iff its result fits. - What (b) does not change. The bound still applies at every stored value, so a calculation split across two formula cells is bounded at the cell in between. Equal values may still differ in scale after passing through the fraction arm (the option (d) section). Scale is not value.
Cost. This is an estimate, not measured on this path.
- The common case is unchanged: no intermediate overflows
i128. - Only a cell whose expression overflows
i128part-way through pays for bigint rational steps. A widened step works on operands near 256 bits, not on the SUM benchmark's small typed values: combining two such fractions measured 7–16 µs (option (d), "What that costs"). So a widened step costs microseconds, not the 490–1,060 ns revision 5 cited. - Such a cell usually demotes at the store anyway.
- The ceiling. Widening carries a size ceiling so that a pathological expression cannot grow a bigint without limit. It must be at least K·127 + 256 bits, so that the grouped read (below) never reaches it: 1,272 bits at K = 8 (it was 4,320 at K = 32). Revision 5's example of 4,096 bits was below the K = 32 figure, and a worst-case K = 32 read would have hit it (the review of
- The numeric crate's name. Decided (the user):
numtower("this is fine"). Added in revision 4, with the recommendationnumtower. It is problem-agnostic likegp-treeandzset, so it should not carry improvise's name. Where ADR 009's
ExactSumlives. Decided (the user): (a). Added in revision 4, and put as follows.- (a) In
numtower, beside the exact decimal accumulator, with ADR 009's seam crate adapting it tozset's group trait through a newtype. - (b) In
zset, as ADR 009 proposes, withnumtowerdepending onzsetto combine a mixed sum.
Recommendation: (a). Exact summation then has one home, a mixed sum's read needs no second crate, and
zsetstays free of numbers.numtowercan land holdingExactSumalone, ahead of this ADR, so ADR 009 does not wait for it (clause 14). This question is shared with ADR 009 (PR #309).- (a) In
The value of K. Decided (the user): (b), K = 8 ("Ok, let's drop K back to 8", superseding an earlier "let's do k = 32"; both quoted under "What the user decided"). Added in revision 6, and put as follows. K is the most non-decimal groups a
SUMreads exactly (question 10). Above it the read is the inexact f64 accumulator. Revision 5 proposed K = 32 on an estimate of 16–34 µs per read, and the measured worst case is 0.67–1.9 ms (option (d), "What that costs"). Under ADR 009 a maintainedSUMreads after every edit that touches it, so that is a per-edit cost, paid by each such cell.- (a) K = 32, as decided with question 10: worst case 0.67–1.9 ms per read. Chosen first, then superseded.
- (b) K = 8: worst case 52–127 µs per read. A
SUMover more than 8 distinct denominators is inexact. Chosen (the later answer). - (c) K = 16: worst case 174–448 µs per read.
Recommendation (taken in the end): (b), K = 8, with the read combining over the lcm and reducing once (the lower figure in each range). The user chose (a), then (b).
- The ceiling (question 13) stays at 8,192 bits under any of the three.
- The common sums keep exactness under K = 8:
SUM(v / 3)has one denominator, and an average or a percentage has a handful. - The sum of margins has one denominator per record, so it passes any of these Ks long before it is large, and reads inexact under each of them.
- K is a constant inside
numtower, not a format or wire fact, so it can be tuned later against the evaluator benchmark (migration step 1) without a new ADR.
Re-derived under K = 8 (revision 8), from this ADR's own measurements, with nothing new measured (the K = 32 figures of revision 7 are superseded):
- Read cost: the K = 8 row of the table, 52 µs (lcm, then one reduce) to 127 µs (reduce after every add).
numtowerreads by the first method, so the lower figure is the working number. The 16–34 µs of revision 5 stays withdrawn. - Combined width: lcm up to K·127 = 1,016 bits (measured 988), numerator up to K·127 + 256 = 1,272 bits. The combined numerator was measured only at K = 32 (4,053 bits), so 1,272 is a bound and not a measurement. It excludes the up to 3 carry bits of summing 8 terms, which the headroom below absorbs.
- Ceiling: the proposed 8,192 bits clears 1,272 by 6,920. Unchanged, so question 13's decision is untouched.
- Memory: O(distinct denominators), which K does not change (clause 8).
- Not re-derived: an end-to-end per-edit latency for a maintained
SUM. The benchmark times the read alone. Whether 52–127 µs per edit is acceptable on a page of such cells is a question for the evaluator benchmark, not a figure here.
#Relations to other ADRs
Added in revision 7. This lists what the three ADRs written since ask of this one, as read at their heads, and changes none of the user's decisions here. Each ADR is cited at the head named, and none was built or run.
ADR 007 (stable identities, accepted at revision 8; merged via #210). The points below are read from revision 8, as on gh/main. Revision 9 is not part of it: see the last bullet.
- The version literal. ADR 007 clause 10 adds a second
.improvliteral and says its exact spelling is left to the implementation. This ADR shares it (clause 10, question 5), so#iandn/dride on the same bump. ADR 007 says nothing about numbers, so nothing in its text conflicts. - Flag, ordering. If ADR 007's migration ships the new literal before this ADR's grammar arms, a reader of that literal would not know
#iorn/d, and "shared" would mean one literal with two grammars. The two should either land the literal together or this ADR's arms should be added under the literal ADR 007 has already shipped, with the old readers' behaviour on#istated. That is a merge-order matter for the implementer, not a decision the user has made. - Ids and display. This ADR's name-quoting and the formula-target handling are about names, and ADR 007 moves keys from names to ids. Numbers are not names, so clause 10's number spellings are unaffected; any clause here that quotes a category or item by name should be read as "by display name" once ADR 007 lands. Not re-read clause by clause.
- Revision 9 is a proposed amendment, not accepted (PR #326, open, head
068e4130; it needs the user's explicit approval, and its Q23–Q25 are open). Nothing in this ADR depends on it. It touches this ADR only at the edges: answers 33 and 34 (a typed name matches ids first, then displays; whitespace in a slug) bear on how a name in formula text is resolved, and answers 35 and 36 reopen Q23 (whether a measure or formula target has an id and a display of its own), which would change what "a formula target" means where this ADR names one. Read as a proposal, and re-check this ADR if #326 lands.
ADR 008 (virtualized grid, PR #308, proposed). Its Q28 answer, "bigint is fine, we don't need to reinvent integers > safe size", makes a grid position a bigint above 2^53 (its Q36 spells it as a decimal string in JSON).
- Dependency. It adds
num-biginttoimprovise-protocol, a wasm-bundle crate. This ADR already acceptsnum-bigintinnumtower(+20.8 KB gzipped fornum-rationalplusnum-bigint, probed; question 8). Ifimprovise-coredepends onnumtower(clause 2),improvise-protocolalready reachesnum-bigintthrough it, so the cost is paid once, not twice. ADR 008 says itscargo tree --edges normalcheck has not been run; neither has one here for the bundle. - Flag, a new consumer of
numtower. Positions are integers, not numbers in the tower's sense. Whether they usenumtower's type ornum-bigintdirectly is open in ADR 008. The tower'sn/dand#ispellings must not leak into a position's wire spelling.
ADR 009 (incremental evaluation, PR #309, proposed).
ExactSumlives innumtower(question 15, (a)), which ADR 009 cites.numtowercan land holding it alone, so ADR 009 does not wait for this ADR.Sumis exact only under ADR 009's question 3 (c) or under this ADR's wide accumulator. This ADR's accumulator is exact for decimals (320 bits) and for up to K = 8 fraction denominators (clause 8). For f64 terms the exact accumulator is ADR 009'sExactSum. A mixed sum is read from both (clause 8), so "exact under this ADR" holds for decimal and bounded-fraction data, not for f64 data.- The per-edit cost is a lower bound, and the larger exposure is
Eager. ADR 009 reads a maintainedSUMafter every edit that touches it. With K = 8 (question 16) the read alone is up to 52–127 µs for a cell holding several large distinct denominators (see "Re-derived under K = 8"), and the update cost comes on top. ADR 009 saysEager"pays the read on every aggregate evaluation", and today's TUI projects the whole grid every frame, so it pays one read per summed cell. Against ADR 009's budget (8 ms per operation, a 2 ms slice for a job; ADR 008 clause 11), as arithmetic from these figures and not a finding: 154 such cells at 52 µs (154 × 52 = 8.0 ms; 153 stay under) or 63 at 127 µs (63 × 127 = 8.0 ms) exceed 8 ms, and 39 at 52 µs or 16 at 127 µs exceed a 2 ms slice. At the earlier K = 32 (superseded) it was five and twelve cells per 8 ms, and one read nearly filled a slice. K = 8 is 13 to 15 times cheaper per read than 32 (0.67/0.052, 1.9/0.127). It remains a question for ADR 009'sEagerand cap design, but a far smaller one. The worst case needs 2 to 8 large distinct denominators in one sum; a sum of small denominators is far cheaper. ADR 009's ownExactSumfigures (2.0–3.6 ns per update, 0.6–1.1 µs per read) are for the f64 accumulator and are not comparable. - Flag, stale text in ADR 009. At its head it describes ADR 005's cost as
rust_decimalalone, "not a bignum, +15.4 KB", with 40 bytes per summed group. Under option (d) the crate also carriesnum-rationalandnum-bigint(up to about +36 KB together, unprobed together) and a per-denominator group map. It also givesExactSum568 bytes per group where this ADR gives the decimal partition 40 bytes; those are two different accumulators and are not a conflict.
#Consequences
- Typed values and their
+ - *are exact.0.1 + 0.2 = 0.3,1234.56 - 1234.55 = 0.01, and a typed1.005shows as1.01at two places (improvise-felo.9 may fix the last one sooner, and without this ADR). SUMover exact data is independent of order, through a 40-byte wide accumulator per group (clause 8). Gotcha 18'sSUMdrift goes as a class for exact data, not just by pinned iteration order.FLOAT_EQ_EPSILONis gone, and gotcha 17 is rewritten as "one zero predicate".Deleting the epsilon changes existing documents, not only the tests. Both assertions of the improvise-0bf test flip (clause 6). And in a document today, a formula whose inputs make an inexact residual changes answer:
A / 3 * 3 - Ais a few ulps from zero, soIF(… = 0, …)flips from true to false, and dividing by such a residual yields a huge value where it yieldsdiv/0today. Exact data is unaffected, because its residuals are exactly zero. The user decided that policy (question 3), and the escape hatch is explicit:EQUAL(a, b, epsilon)(clause 6). Plain examples of formulas that change, each with the question that causes it:- Question 3 (no epsilon): a comparison of two inexact residuals, such as
IF(POW(A, 0.5) * POW(A, 0.5) - A = 0, …), was true within the epsilon and is now false. The fix isEQUAL(…, 0, 1e-9). - Question 7 (exact mixed comparison):
IF(POW(x, 0.5) = 1.1, …)withx = 1.21. In f64,pow(1.21, 0.5)is exactly the f64 nearest 1.1, so this is true today even without the epsilon (the review measured it). It becomes false because it compares that inexact value with the exact decimal1.1. Revision 4 filed this under question 3, and that was wrong. The fix isEQUAL(POW(x, 0.5), 1.1, 1e-9). - Option (d):
IF(A / 3 * 3 = A, …)on typed data is true today within the epsilon, and it stays true, now exactly, becauseA / 3is an exact fraction. - Question 9 (version skew): an old peer's
0.1arrives as a bare JSON number and reads asInexact(0.1). That is unequal to every typed0.1, though the two look identical on screen. improvise-szi8 closes it.
- Question 3 (no epsilon): a comparison of two inexact residuals, such as
- A scale-only edit (
12.5to12.50) bumps the record's version (clause 9). Exact(0.1) = Inexact(0.1)is false, because comparison between exact and inexact is exact (clause 6, question 7).- A typed
12.50stays12.50in the editor. - Division that does not terminate, and
AVGover any count, are exact fractions within thei128bound (decided, question 2).POWwith a fractional exponent is inexact. .improvgains#i,n/dand ADR 007's version literal. Existing files load as the decimals they spell.- The wire spells every number as a string in improvise's own encoding (decided, question 6). A thin client needs no new rule, because
typed()and the number language are shared. n/dis text wherever a type is inferred and a fraction wherever it is forced (decided, question 12).nan,infand a finite lexeme that overflows f64 (1e999) are text at import, as improvise-jc95 decided.typed()narrows to the three canonical tokens, so a typedInfinity,NaNor1e999becomes text where today it is a number (clause 3).- A value typed past
Decimal's range is an exact fraction when it fitsi128(1e-30, a 30-digit integer), as the same value computed already is (clause 3). - A
SUMreads exactly over at most K distinct fraction denominators, at a worst-case cost that grows about as K² (question 16: K = 8, decided), and past K it is inexact. - Formulas gain
EQUAL(a, b, epsilon), andEQUALbecomes a keyword the writer quotes. - Costs:
Numis 24 bytes where anf64is 8, butCellValuestays 32 bytes under both (a) and (d), because itsStringarm already sets the size (the review measured it). The bundle gainsrust_decimal(+15.4 KB gzipped, probed) and, under (d),num-rationalandnum-bigint(+20.8 KB gzipped probed alone, up to about +36 KB together, unprobed together). Arithmetic is about 8× slower per add and about 100× per division than f64 (measured, microbenchmark). A 90,000-record formula that divides for every record pays about 5–10 ms in arithmetic alone. Whether the evaluator notices is migration step 1's measurement, and it is not measured here. - Not covered: the order-free sum of inexact values, which is ADR 009's accumulator; the protocol version, which is improvise-szi8; conversion functions such as
EXACT()/INEXACT(), which no ticket asks for. - Option (d)'s own consequences apply, now that it is decided: a third numeric arm, a grouped sum accumulator, the
n/dspelling, exact quotients, and a result's scale depending on whether it passed through the fraction arm.
#Appendix: the measurements
A scratch crate outside the workspace, run with cargo run --release. It was not committed. Committing it would add three decimal crates to the workspace's dev dependencies, and every cargo test --workspace would then build them, to hold a proposal's evidence. If the user accepts this ADR, migration step 1 commits the rust_decimal and fraction halves of the measurement as an example of the numeric crate (clause 14), whose normal dependencies already include what they need. So it adds no dependency beyond the ones the ADR adds.
Data. A typed value is a two-place decimal from 0.01 to 999,999.99, drawn by SplitMix64 (the same generator as ADR 009's retraction_drift.rs), and spelled as the text a person types. Each representation parses that text: f64 by str::parse, Decimal/BigDecimal by from_str, and BigRational as mantissa over 10^scale.
SUM. A fold over N parsed values, N = 18,000 and 90,000, best of 50 runs (20 for bigdecimal, 5 for BigRational), reported per element. The order check folds forward and reversed.
Formula. For N records with independent Revenue and Cost, SUM((Rev − Cost) / Rev). bigdecimal is run at its default precision (100 digits) and at 28. BigRational is summed incrementally, printing the running denominator's bit length at powers of two, and abandoned after 20 seconds.
Accumulator stand-in. Each stored f64 is converted to its exact rational (BigRational::from_float), summed exactly, and rounded once to f64. That is precisely what a correct superaccumulator returns. It is compared with the typed total, the decimal sum of the texts converted to f64 once. Small N: 10,000 trials each at N = 2, 3, 10 and 100, seed 7. Large N: seeds 1 to 8. The signed distribution draws cents uniformly from −100,000 to 100,000 (±1,000.00), with the same N, trials and seed; it was not run at large N.
Display. format.rs:127-136's round_half_away, copied verbatim, against Decimal::round_dp_with_strategy(2, MidpointAwayFromZero), for 2.675, 1.005, 0.125 and 1.115.
Wasm size. A cdylib exporting one function that parses two strings, then does (a + b) − b, divides by b and prints, in each representation. It also parses and prints an f64 in every variant, so f64 formatting is in the baseline as it is in the real bundle. Profile opt-level = "s", lto = true, codegen-units = 1, panic = "abort". Then wasm-opt -Oz --enable-bulk-memory --enable-nontrapping-float-to-int, and gzip -9 for the compressed figure.
Revision 2's checks of the review's findings, in the same scratch crate:
- B1.
(p + 1e12) − 1e12withp = 0.30000000000000004gives0.3000000000000000at scale 16.(1e12 − 1e12) + pgives0.30000000000000004at scale 17. - B2. 200,000
Decimals fromfrom_i128_with_scale, with a 96-bit mantissa and a scale drawn from 0–28 (SplitMix64, seed 11).to_f64()differed fromto_string().parse::<f64>()in 17,375 of them. The review's own sample found 17,392. - Parsing.
Decimal::from_str("0.12345678901234567890123456789")returned0.1234567890123456789012345679, andfrom_str_exactrefused it.
Everywhere this appendix converts a decimal total to f64 ("the typed total"), it does so through to_string().parse::<f64>(), the correctly rounded path, not to_f64. So the accumulator table above does not depend on the conversion B2 found wrong.
Option (d) (revision 3) uses the same crate, with num-rational 0.4.2's Ratio<i64> and Ratio<i128> checked operations. Operation costs are measured over 18,000 pairs of typed values: seeds 21 and 22 for two-place operands, and those pairs' margins for unrelated denominators. The overflow cases use seeds 1–8, drawing Revenue and Cost from seeds 2s and 2s + 1. Sizes are size_of of the three Num shapes. The to_f64 check compared Ratio<i128>::to_f64 with BigRational::to_f64 on 200,000 fractions (seed 5). That comparison is circular, because the two share one routine, so the ADR now relies on the review's independent interval check instead (option (d), "Operations"). Every figure is the range over two runs on the machine above.
The grouped read (revision 6), in the same crate. For K = 2, 8, 16 and 32, 200 reads each. A read combines K groups whose numerators are random 250-bit integers and whose denominators are random odd 126-bit integers (xorshift64, one fixed seed), sorted ascending by denominator. Two methods are timed on the same groups: BigRational addition group by group, which reduces by a gcd after every add, and an lcm accumulation with one gcd reduction at the end. The two results are asserted equal. One run on the machine above; a second run agreed within 6% (within 2.7% above K = 2). Where the text gives a range such as 0.67–1.9 ms, it runs from the lcm method to the per-add method.