46b6b2128a
Co-Authored-By: Claude Sonnet 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01VdfEGXA7aJ6ftMsCc9PJze
2098 lines
129 KiB
Markdown
2098 lines
129 KiB
Markdown
# 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](#option-d-for-question-2-bounded-exact-fractions). **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](#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`, `inf` and `1e999` stay 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.**
|
||
> "`#i` works"
|
||
|
||
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_json` made of
|
||
it (clause 12).
|
||
- NaN boxing is not needed once the encoding is a string: the string carries the
|
||
exactness.
|
||
- `serde_json`'s `arbitrary_precision` stays 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 with `serde_json`'s `raw_value` feature,
|
||
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_decimal` alone.
|
||
- Under (d), `numtower` also carries `num-rational` and `num-bigint`. The probe
|
||
measured those at about +20.8 KB gzipped on their own; together with `rust_decimal`
|
||
they 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 `i128` denominators
|
||
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
|
||
|
||
1. **Three levels** (decided, question 1). A number is an **exact decimal**, an **exact
|
||
bounded fraction** (an `i128` numerator 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).
|
||
2. **Exact is the default.** Every number a person types, every number in a `.improv`
|
||
file, 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).
|
||
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). `POW` keeps 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.
|
||
4. **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).
|
||
5. **The stored type is `CellValue::Number(Num)`**, where `Num` is `Exact(Decimal)`,
|
||
`Fraction(Box<Ratio<i128>>)` or `Inexact(f64)`. The crates are `rust_decimal` and
|
||
`num-rational`. `Num` and everything numeric live in a
|
||
problem-agnostic workspace crate of their own, `numtower` (decided, question 14; clause 14).
|
||
6. **Each kind of number has its own exact accumulator.** ADR 009's f64 accumulator
|
||
makes `SUM` over *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), because
|
||
`rust_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.2` is `0.30000000000000004`, and ten `0.1`s sum to `0.9999999999999999`.
|
||
- `1234.56 - 1234.55` is `0.009999999999990905`, and `100.10 - 100` is
|
||
`0.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 bound `rust_decimal` rounds, 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 as `1e15 + 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 absolute `1e-10` (gotcha 17), so a miss can
|
||
reach it only when ½·Σ ulp(term) reaches `1e-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 as `12.50` live here.
|
||
- **Exact bounded fraction:** a reduced `Ratio<i128>`. It holds only exact values that
|
||
are not a finite decimal that fits, such as `10/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)`
|
||
|
||
```rust
|
||
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_str` accepts **and
|
||
reads as a finite value** (revision 6, N1 of the review of `33833f28`). That is #321's
|
||
`number_in` gate, which drops anything `Number::from_f64` cannot hold. So a number is
|
||
an optional sign; digits with an optional fraction (`1.`, `.5`); and an optional
|
||
exponent `e`/`E` with its own sign, whose value does not overflow f64.
|
||
- **`1_000` is not a number**, so it is text.
|
||
- **`nan`, `inf`, `infinity` in 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's
|
||
`a_nonfinite_numeric_token_stays_text_rather_than_becoming_zero` pins for `NaN`,
|
||
`inf`, `-inf`, `1e999` and `-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 `.improv`
|
||
reader and the wire accept exactly `inf`, `-inf` and `nan`, the three spellings
|
||
`nonfinite_token` writes (`cell.rs:65`), as inexact values. Import does not, so a
|
||
CSV `nan` stays text, as jc95 decided. This is a behaviour change for `typed()`, and
|
||
it is stated: today it hands any string to `str::parse::<f64>` (`resolve.rs:1438`), so
|
||
a typed `Infinity` or `1e999` becomes infinity and a typed `NaN` becomes 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 is `Exact`, with the scale
|
||
the lexeme implies: `1.50` has scale 2, `1.5e3` is `1500` at scale 0, and `1.5e-3`
|
||
is `0.0015`.
|
||
- **A fraction.** Otherwise, if its reduced value `m / 10^k` fits `Ratio<i128>`, it is
|
||
a `Fraction`. So a typed `1e-30` is the exact `1/10³⁰`, and an integer between
|
||
`Decimal`'s maximum (about 7.9 × 10²⁸) and 2¹²⁷ is the exact `n/1`. This is the
|
||
order clause 4 already gives arithmetic, so the same value is equally exact typed
|
||
and computed: `1e-15 * 1e-15` was already the exact `1/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.**
|
||
- **Zero has no sign at the exact level.** `-0.0` reads as exact `0.0`. The sign of zero
|
||
is an f64 artefact. This is a behaviour change, and it is stated: an f64 `-0.0` never
|
||
survives entry as exact.
|
||
- **`n/d` is a number only where the type is forced** (decided, question 12). `n/d`
|
||
means an optional sign, digits, `/`, and digits with `d > 0`, and it is a fraction or,
|
||
once normalized, a decimal. The places where the type is forced are:
|
||
- the `.improv` fraction 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 keeps `3/4` as a date or a label.
|
||
|
||
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 `Decimal`s 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`, so `1 / 3 * 3` is exactly `1`.
|
||
- 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,
|
||
because `ma · 10^sb` can reach 2¹⁹⁰.
|
||
- Its exact scale is `k = max(p, q)`.
|
||
- The quotient is an exact `Decimal` **iff `k ≤ 28` and `n · 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 `Fraction` when the reduced fraction fits `i128`.
|
||
- 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.50`
|
||
is 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)` and `Exact(0.10000000000000000001) =
|
||
Inexact(0.1)` would both be true, while the two exacts differ. A non-transitive `=`
|
||
cannot order a `MIN`, and it cannot key a sorted map. So comparison is exact (decided,
|
||
question 7). The cost is that `Exact(0.1) = Inexact(0.1)` is
|
||
**false**: the f64 is `0.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 as `EQUAL(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 `epsilon` is `Error("type")`. So is a non-number in any
|
||
position.
|
||
- **Where it may appear.** Wherever a comparison may: an `IF` condition (`eval_bool`).
|
||
It is also usable as a value of `1` or `0`, as `IS` already is.
|
||
- **Spelling.** It is a new keyword. Like the others it is case-insensitive
|
||
(`^"EQUAL"`) and is followed by `(`, so a bare `EQUAL` still names an item (PEG falls
|
||
through to `ref_expr`). The writer's keyword guard (`quote::quote_name`) must add it,
|
||
so an item literally named `EQUAL` is written `|EQUAL|` (gotcha 34).
|
||
- **Home.** The grammar is in `improvise-formula` (`formula.pest`, the AST) and the
|
||
evaluation in `improvise-core` (both evaluators). The arithmetic it calls is
|
||
`numtower`'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-dependent `SUM` as 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), an `i128` fraction (a sum of fractions can
|
||
fit the fraction arm without fitting a `Decimal`). **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` × an `i64` weight × 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, so `n/d` is accepted there. It
|
||
replaces today's untagged `wire_f64` adaptor (`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 `#i` string. 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 as `Scalars::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's `number_in` gate *is* that language's gate, finite values only
|
||
(revision 6), so the analyzer and the parse agree on every string: `1.5e3` is the
|
||
exact `1500`, and `1_000`, `nan`, `inf` and `1e999` are text. It keeps its significant
|
||
digits and its **scale**, so a CSV `12.50` opens in the editor as `12.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/4` is 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/4` in it reads as the exact fraction `3/4`.
|
||
- Revision 3's description of `parse_csv_field` (`csv_parser.rs:167-186`: an `i64`,
|
||
else an `f64` `Number`) is today's code at `b639266b`, 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_field` turns it into a number.
|
||
- **JSON.** A JSON number is read from its **source lexeme** through `serde_json`'s
|
||
`raw_value`, and never through the f64 `as_f64` (`wizard.rs:425`) reads today
|
||
(decided, question 6; clause 3). So a JSON `12.50` keeps 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`). `ImportPipeline` carries `serde_json::Value` (ten uses in
|
||
`wizard.rs`, and more in `analyzer.rs`), and a `Value`'s numbers are already f64.
|
||
`raw_value` hands over a lexeme only to a reader that deserializes into `RawValue`
|
||
through a hand-written visitor. It does not work through a `Value`, 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.
|
||
|
||
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.005` behave.
|
||
|
||
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 `Copy` and 16 bytes, with no heap. So a `CellValue` does
|
||
not start allocating for every number. It is about 2.5× faster than `bigdecimal` on
|
||
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 its `Exact(Decimal)`, `Fraction` (question 2, decided (d)) and `Inexact(f64)`
|
||
arms;
|
||
- the arithmetic and contagion (clause 4);
|
||
- the rounding and overflow detection: the scale test, and the `2^p·5^q` termination
|
||
test (clauses 4 and 5);
|
||
- the correctly rounded conversion to f64 (clause 4);
|
||
- exact comparison, the `MIN`/`MAX` tie-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 `Num` to *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
|
||
`#i` spelling 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/d` arm;
|
||
- 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 except `std`;
|
||
- `num-rational`, with `default-features = false`, for `Ratio<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 `i128` denominator;
|
||
- 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/d` normalization);
|
||
- the **differential tests** against an exact `BigRational` oracle: 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**:
|
||
|
||
```rust
|
||
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 `Fraction` is only ever produced where option (a) would have produced `Inexact`:
|
||
- a non-terminating quotient;
|
||
- a decimal operation that exceeds 28 digits but whose reduced fraction fits (`1.05^k`
|
||
for 15 ≤ k ≤ 28).
|
||
- A `Fraction` whose denominator turns out to be `2^p · 5^q` and fits is normalized back
|
||
to `Exact(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 `Num` at 24 bytes, the same as option (a);
|
||
measured, an inline `Ratio<i128>` makes it 48. The heap allocation falls only on
|
||
fraction values, which are formula results. Per `AGENTS.md`, the `Box` handling lives
|
||
in `Num`'s constructors, apart from the arithmetic.
|
||
|
||
### Operations
|
||
|
||
- **Division stays exact.** `10/3` is `Fraction(10/3)`, and `10/3 × 3` is exactly `10`,
|
||
which normalizes back to `Exact(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 `i128` arithmetic after the gcd reduction (`num-rational`'s
|
||
`checked_add`/`checked_mul`/`checked_div` do exactly this). A `None` **may** mean the
|
||
reduced result does not fit, and **may** mean only that an intermediate overflowed
|
||
(`checked_add` goes through the lcm of the denominators) while the reduced result
|
||
fits. So a `None` widens that step to a bigint rational and the **stored** result is
|
||
tested against the `i128` bound: exact iff it fits, else the correctly rounded f64 of
|
||
the exact fraction, which is `Inexact`. It is deterministic. Past question 13's
|
||
ceiling, the intermediate demotes (the first of the two stated exceptions).
|
||
|
||
Revision 3 cited `Ratio<i128>::to_f64` agreeing with `BigRational`'s conversion. That
|
||
was **circular**: both share `num-rational`'s one `ratio_to_f64` routine. The review
|
||
ran an independent check instead. It took 200,000 random reduced `Ratio<i128>`s, with
|
||
numerator and denominator widths from 20 to 126 bits and both signs. For each, it
|
||
asked whether the exact `BigRational` lies 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.
|
||
- **`POW`** with an integer exponent is exact while it fits. That is why `1.05^k`
|
||
reaches k = 28.
|
||
- **Comparison** is exact. Two fractions are compared by cross-multiplying in 256 bits
|
||
(an `i128` times an `i128` fits). 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. So `10/3` at two places shows `3.33`, and
|
||
`2/3` shows `0.67`. In 256 bits that holds up to about 38 places, because `places` is
|
||
a `u8` (`parse_number_format`) and `n · 10^places` passes 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:
|
||
|
||
1. **Demote each fraction term to f64** into ADR 009's accumulator. Simple, and
|
||
independent of order. But `SUM(v / 3)` is then inexact, even though `SUM(v) / 3`
|
||
is exact.
|
||
2. **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-`i128` read 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.
|
||
3. **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 `Fraction` whose denominator is `2^p · 5^q` joins the decimal partition when its
|
||
exact scale `k = max(p, q)` is at most 28.** An example is one born from a decimal
|
||
overflow with denominator `10^17`. At scale 28 its value is an exact integer, which
|
||
the 320-bit accumulator holds. With `k > 28` (for example `1/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 `SUM` about 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-decimal `SUM` pays 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 `i128` denominator, 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 | `BigRational` add per group | lcm, 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 written `n/d`, with a sign on `n`, for example `-10/3`.
|
||
The `number` rule does not accept `/`, and an old reader would take `10/3` as **text**
|
||
(`bare_value`), silently. So it needs a grammar arm ordered before `bare_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/4`** stays 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 so
|
||
`Margin × Revenue = Profit` holds 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-rational` and `num-bigint` in the browser bundle**: +20.8 KB gzipped on their
|
||
own, and up to about +36 KB together with `rust_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:** `Num` gains the boxed `Fraction` arm.
|
||
- **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`. `AVG` is exact.
|
||
- **Clause 6:** fraction comparison is by cross-multiplication.
|
||
- **Clause 8:** sums group by denominator, as above.
|
||
- **Clause 10:** the `n/d` spelling.
|
||
- **Clause 11:** the wire spells a fraction `"n/d"`.
|
||
- **Question 12** decided typed input: `n/d` is 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/3` becomes
|
||
`0.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 `CellValue` arm beside `Number(f64)`.** Rejected in clause 2.
|
||
|
||
## Migration
|
||
|
||
In order. Each step lands on its own, with the suite green.
|
||
|
||
1. **The `numtower` crate, first and alone** (clause 14). It holds `Num` and its
|
||
arithmetic, with the contagion table (clause 4) and the scale-based rounding
|
||
detection. It holds the correctly rounded conversion to f64, the division and `POW`
|
||
rules (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 a `numtower`
|
||
holding only `ExactSum`, for ADR 009 (clause 14).
|
||
|
||
Its property tests:
|
||
- an `Exact` result 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. Inject `to_f64`
|
||
and watch it fail on the review's `63294.60…` case. The random generator spans
|
||
**96-bit mantissas and scales 0–28**: with 15 or fewer digits the broken `to_f64`
|
||
agreed 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^40` and `1/5^30` are fractions, `1e-28 / 0.5` is
|
||
the exact decimal `2e-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` (exact `1500`), `1_000` (text), `-0.0` (exact `0.0`), and `3/4` (text
|
||
when inferred, a fraction when forced);
|
||
- `1e999` and `-1e999` (text: a finite lexeme never reads as infinity), `nan`,
|
||
`inf` and `Infinity` (text in the gate), and `1e-999` (an inexact zero);
|
||
- `1e-30` (the exact fraction `1/10³⁰`), `0.12345678901234567890123456789` (an
|
||
exact fraction, not a rounded decimal), an integer between `Decimal`'s maximum
|
||
and 2¹²⁷ (an exact `n/1`), and `1e-40` (inexact: it fits neither arm);
|
||
- a typed value and the same value computed are equally exact: `1e-30` parsed
|
||
equals `1e-15 * 1e-15`, arm and value both;
|
||
- the grouped read combines over the lcm and reduces once, and agrees with a
|
||
`BigRational` sum of the groups.
|
||
|
||
The differential tests run against a `BigRational` oracle. The benchmark goes in
|
||
`numtower/examples/`. Add the crate to the `wasm` CI 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.
|
||
2. **`improvise-core` depends on `numtower`, and `CellValue::Number(Num)`** replaces the
|
||
f64 across the 672 sites. This is mechanical, and `as_f64`
|
||
keeps the seams compiling. `hash_value` hashes the representation, scale included
|
||
(clause 9).
|
||
3. **Both evaluators** move to `Num`. `FLOAT_EQ_EPSILON` is deleted. The improvise-0bf
|
||
tests are rewritten to assert one zero predicate (clause 6). `EQUAL(a, b, epsilon)`
|
||
lands here: its grammar and AST in `improvise-formula`, its evaluation in both
|
||
evaluators, and `EQUAL` in `quote_name`'s keyword guard (clause 6).
|
||
4. **Aggregates** partition by exactness and use `numtower`'s accumulator (clause 8).
|
||
Its own order-independence test is in `numtower` (step 1). Here the test is that
|
||
`apply_agg` and `eval_agg` route through it: seed the review's
|
||
`[0.30000000000000004, 1e12, −1e12]` through the evaluator. `Decimal`'s own `+` must
|
||
fail it.
|
||
5. **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 through `raw_value`, because a
|
||
`serde_json::Value` has already made it an f64 (clause 12). The import tests assert:
|
||
- a CSV `12.50` and a JSON `12.50` both keep their scale, because both are parsed
|
||
from their lexeme;
|
||
- `1.5e3` imports as the exact `1500`, and `1_000` imports as text;
|
||
- `nan`, `inf`, `1e999` and `-1e999` import as text, so #321's
|
||
`a_nonfinite_numeric_token_stays_text_rather_than_becoming_zero` stays green
|
||
unchanged;
|
||
- `typed()` reads `inf`, `-inf` and `nan` as clause 7's tokens, and `Infinity`,
|
||
`NaN` and `1e999` as text (the stated behaviour change);
|
||
- `3/4` is text in an inferred column and the fraction `3/4` in a column forced to
|
||
a measure.
|
||
6. **Display and edit text** (clause 9). The `1.005` case is the regression test, and
|
||
it fails at HEAD today. If improvise-felo.9 lands first, this step reuses its test.
|
||
7. **`.improv`:** read exact, write with scale, `n/d` for a fraction, `#i` for inexact
|
||
finite, and ADR 007's version literal (clause 10).
|
||
8. **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.
|
||
|
||
1. **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.
|
||
|
||
2. **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).
|
||
|
||
3. **Tolerance on inexact equality.** **Decided (the user): no tolerance on `=`.** A
|
||
formula function `EQUAL(a, b, epsilon)` is added instead (clause 6). It replaces this
|
||
question's earlier "an `APPROX(a, b, tol)` if it is ever wanted".
|
||
|
||
4. **The `.improv` spelling of an inexact finite number.** **Decided (the user): `#i`**
|
||
(clause 10).
|
||
|
||
5. **The version literal.** **Decided (the user): share ADR 007 clause 10's literal**
|
||
(clause 10).
|
||
|
||
6. **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`'s `raw_value`
|
||
(clauses 3 and 12).
|
||
- `arbitrary_precision` stays rejected, because it breaks serde's buffered
|
||
deserialization of numbers under the workspace's internally tagged enum and its
|
||
`flatten`.
|
||
- The earlier recommendation, "shortest spelling", is withdrawn.
|
||
|
||
7. **Mixed-exactness comparison.** **Decided (the user): exactly**, plus
|
||
`EQUAL(a, b, epsilon)` (clause 6).
|
||
|
||
8. **The dependency.** **Decided (the user): yes.** That answer was given against
|
||
`rust_decimal`'s +15.4 KB gzipped. Under (d), `num-rational` and `num-bigint` add
|
||
about +20.8 KB on their own, up to about +36 KB together (unprobed). If that changes
|
||
the answer, this question reopens (clause 14).
|
||
|
||
9. **Version skew on the wire.** **Decided (the user): accept it**, and the handshake
|
||
version is filed as **improvise-szi8** (clause 11).
|
||
|
||
10. **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 `i128` denominator. 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).
|
||
|
||
11. **The `MIN`/`MAX` tie-break.** **Decided (the user): prefer the exact value**
|
||
(clause 8).
|
||
|
||
12. **Typing a fraction.** **Decided (the user): `n/d` is text where the type is
|
||
inferred and a fraction where it is forced** (clause 3). So `typed()` and the import
|
||
analyzer keep `3/4` as text, and a column forced to a measure reads it as a
|
||
fraction. An editor opened on a fraction shows `10/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).
|
||
|
||
13. **Where the fraction bound applies.** **Decided (the user): (b)**. Added in
|
||
revision 4, and put as follows. Is the `i128`
|
||
bound 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 the `i128` fast 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)` and `a × b + a × c` are 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 a `SUM` of 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 on
|
||
`be9de2ee`):
|
||
- **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, commit `02bcfcb1` (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. `POW` checks its result size **before** computing (clause 5), so the
|
||
ceiling is never reached by allocating first.
|
||
- **The K cutoff, which does override representability.** A `SUM` holding 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 `i128` part-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.
|
||
|
||
14. **The numeric crate's name.** **Decided (the user): `numtower`** ("this is
|
||
fine"). Added in revision 4, with the recommendation `numtower`. It is problem-agnostic like `gp-tree` and `zset`, so it should not carry
|
||
improvise's name.
|
||
|
||
15. **Where ADR 009's `ExactSum` lives.** **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 to `zset`'s group trait through a newtype.
|
||
- (b) In `zset`, as ADR 009 proposes, with `numtower` depending on `zset` to
|
||
combine a mixed sum.
|
||
|
||
*Recommendation:* (a). Exact summation then has one home, a mixed sum's read needs
|
||
no second crate, and `zset` stays free of numbers. `numtower` can land holding
|
||
`ExactSum` alone, ahead of this ADR, so ADR 009 does not wait for it (clause 14).
|
||
This question is shared with ADR 009 (PR #309).
|
||
|
||
16. **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
|
||
`SUM` reads 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 maintained `SUM` reads 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 `SUM` over 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). `numtower` reads 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 `.improv` literal and says
|
||
its exact spelling is left to the implementation. This ADR shares it (clause 10,
|
||
question 5), so `#i` and `n/d` ride 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 `#i` or `n/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 `#i` stated. 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-bigint` to `improvise-protocol`, a wasm-bundle crate. This
|
||
ADR already accepts `num-bigint` in `numtower` (+20.8 KB gzipped for `num-rational`
|
||
plus `num-bigint`, probed; question 8). If `improvise-core` depends on `numtower` (clause
|
||
2), `improvise-protocol` already reaches `num-bigint` through it, so the cost is paid
|
||
once, not twice. ADR 008 says its `cargo tree --edges normal` check 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 use `numtower`'s type or `num-bigint` directly is open in
|
||
ADR 008. The tower's `n/d` and `#i` spellings must not leak into a position's wire
|
||
spelling.
|
||
|
||
**ADR 009 (incremental evaluation, PR #309, proposed).**
|
||
- **`ExactSum` lives in `numtower`** (question 15, (a)), which ADR 009 cites. `numtower`
|
||
can land holding it alone, so ADR 009 does not wait for this ADR.
|
||
- **`Sum` is 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's `ExactSum`. 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 maintained `SUM` after 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 says `Eager` "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's `Eager` and 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 own
|
||
`ExactSum` figures (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_decimal` alone, "not a bignum, +15.4 KB", with 40 bytes per summed group. Under
|
||
option (d) the crate also carries `num-rational` and `num-bigint` (up to about +36 KB
|
||
together, unprobed together) and a per-denominator group map. It also gives `ExactSum`
|
||
568 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 typed `1.005` shows as `1.01` at two places (improvise-felo.9 may fix the
|
||
last one sooner, and without this ADR).
|
||
- `SUM` over exact data is independent of order, through a 40-byte wide accumulator per
|
||
group (clause 8). Gotcha 18's `SUM` drift goes as a class for exact data, not just by
|
||
pinned iteration order.
|
||
- `FLOAT_EQ_EPSILON` is 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 - A` is a
|
||
few ulps from zero, so `IF(… = 0, …)` flips from true to false, and dividing by such a
|
||
residual yields a huge value where it yields `div/0` today. 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 is `EQUAL(…, 0, 1e-9)`.
|
||
- **Question 7 (exact mixed comparison):** `IF(POW(x, 0.5) = 1.1, …)` with `x = 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** decimal `1.1`. Revision 4 filed this under
|
||
question 3, and that was wrong. The fix is `EQUAL(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, because `A / 3` is an exact fraction.
|
||
- **Question 9 (version skew):** an old peer's `0.1` arrives as a bare JSON number and
|
||
reads as `Inexact(0.1)`. That is **unequal** to every typed `0.1`, though the two
|
||
look identical on screen. improvise-szi8 closes it.
|
||
- A scale-only edit (`12.5` to `12.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.50` stays `12.50` in the editor.
|
||
- Division that does not terminate, and `AVG` over any count, are **exact fractions**
|
||
within the `i128` bound (decided, question 2). `POW` with a fractional exponent is
|
||
inexact.
|
||
- `.improv` gains `#i`, `n/d` and 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/d` is text wherever a type is inferred and a fraction wherever it is forced
|
||
(decided, question 12).
|
||
- `nan`, `inf` and a finite lexeme that overflows f64 (`1e999`) are text at import, as
|
||
improvise-jc95 decided. `typed()` narrows to the three canonical tokens, so a typed
|
||
`Infinity`, `NaN` or `1e999` becomes text where today it is a number (clause 3).
|
||
- A value typed past `Decimal`'s range is an exact fraction when it fits `i128`
|
||
(`1e-30`, a 30-digit integer), as the same value computed already is (clause 3).
|
||
- A `SUM` reads 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)`, and `EQUAL` becomes a keyword the writer quotes.
|
||
- **Costs:** `Num` is 24 bytes where an `f64` is 8, but **`CellValue` stays 32 bytes**
|
||
under both (a) and (d), because its `String` arm already sets the size (the review
|
||
measured it). The bundle gains `rust_decimal` (+15.4 KB gzipped, probed) and, under
|
||
(d), `num-rational` and `num-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/d` spelling, 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) − 1e12` with `p = 0.30000000000000004` gives
|
||
`0.3000000000000000` at scale 16. `(1e12 − 1e12) + p` gives `0.30000000000000004` at
|
||
scale 17.
|
||
- **B2.** 200,000 `Decimal`s from `from_i128_with_scale`, with a 96-bit mantissa and a
|
||
scale drawn from 0–28 (SplitMix64, seed 11). `to_f64()` differed from
|
||
`to_string().parse::<f64>()` in 17,375 of them. The review's own sample found 17,392.
|
||
- **Parsing.** `Decimal::from_str("0.12345678901234567890123456789")` returned
|
||
`0.1234567890123456789012345679`, and `from_str_exact` refused 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.
|