Did the rounding decide it?¶

Level: 301 · deep dive

One line: Interval arithmetic does not make a rounded count exact — it tells you whether your rounding could have changed the answer, and because its error is one-sided, a verdict of decided is a proof while undecided is only an admission about the scale you chose.

This repo already has four pages about being exact. What a float actually stores is where exactness ends; scaling the denominator away is how to get it back when the denominators can be listed in advance; what i128 is exact about is the ceiling on doing it with a wider integer; when the denominators compound is the case where no fixed width is enough. Between them they answer what is the exact answer, and what does exactness cost.

None of them answers the question you actually have at 2 a.m. with a rounded count in front of you: I rounded. Did that change who won?

The gap, precisely¶

The compounding-weights page states the honest position on rounding:

if the rule specifies the scale, then the rounded answer is the correct answer by definition rather than an approximation of one

That is right, and it is the reason a published rule can specify "to four decimal places" without lying. But read the condition. It holds when the rule fixes the scale. It says nothing about the far more common case where you fix the scale — you picked i64 and a scale of 10⁶ because it looked comfortable, and now a margin has come in at 1/504 and someone wants to know whether your choice, rather than the the data, selected the answer.

The method that cluster offers for that is: run an exact count too, and compare. Which works, and is exactly what that page's kata does — find the coarsest rounding that still reproduces the exact leaders. But notice it needs an exact count to reproduce. In the unbounded case that page is about, there isn't one; that is the whole reason you were rounding.

Interval arithmetic gets the same verdict with no exact count anywhere in the program.

The mechanism, which is smaller than it sounds¶

Stop storing each rounded term as a number. Store the bracket it is guaranteed to lie in:

let lo = (value.n * scale).div_euclid(value.d);          // floor
let hi = if divides { lo } else { lo + 1 };              // ceil

lo ≤ exact·scale ≤ hi, always. Add brackets by adding their ends, and the sum brackets the true sum. Then the only claim you ever make is a comparison of ends:

if a.lo > b.hi  { Decided(A) }        // A's worst case beats B's best case
else if b.lo > a.hi { Decided(B) }
else { Undecided }                    // the brackets overlap; this scale cannot say

There is no floating point here and no rounding mode to argue about. Decided means the two projects' possible ranges do not touch, which is a fact about arithmetic, not an estimate.

Verified output of interval_arithmetic.rs — regenerated by tools/run_examples.py, never hand-typed.

=== the count is the same; only the question changes ===
  six reviewers, weights 5/10 5/9 5/8 5/7 5/6 5/5
  a rounded count answers 'who won'. it always answers.
  intervals answer 'is that answer mine, or the rounding's'.

=== dataset 1 -- the one that is exactly tied ===

  Alpha vs Bravo (the canonical round 2)
    exact: Alpha 1205/168  vs  Bravo 1205/168   -> tie
       scale      rounded count says               intervals say
          10    Bravo      71-72      [    71,    74] [    70,    74]  undecided
         100    Bravo     717-718     [   716,   719] [   715,   719]  undecided
        1000    Bravo    7172-7173    [  7172,  7174] [  7171,  7174]  undecided
       10000    Bravo   71726-71727   [ 71725, 71727] [ 71724, 71727]  undecided
      100000    Bravo  717262-717263  [717261,717263] [717260,717263]  undecided

    The exact answer is a TIE, so no scale can honestly name a leader.
    The rounded count names Bravo anyway -- at every scale, and it does
    not waver as the scale refines. That is the part worth sitting with:
    this is not noise that averages out, it is the half-up rule leaning
    the same way every time. Refining the scale buys more digits of a
    wrong answer. The intervals overlap at every scale, and so decline.

=== dataset 2 -- a real margin, and a small one ===

  Petra vs Quinn (margin 1/504)
    exact: Petra 15/2  vs  Quinn 3779/504   -> Petra
       scale      rounded count says               intervals say
          10    Petra      75-74      [    74,    76] [    74,    78]  undecided
         100      tie     750-750     [   749,   751] [   748,   752]  undecided
        1000    Petra    7500-7498    [  7499,  7501] [  7497,  7500]  undecided
       10000    Petra   75000-74980   [ 74999, 75001] [ 74979, 74982]  DECIDED: Petra
      100000    Petra  750000-749801  [749999,750001] [749801,749804]  DECIDED: Petra

    Here there IS a leader, and the intervals find it -- but only once
    the scale is fine enough to separate 1/504 from the slack.

=== the coarsest scale that PROVES it ===
  intervals first PROVE it at scale : 504
  below that, the rounded count got the answer wrong at 184
  of the 503 coarser scales -- right most of the time, which is
  exactly what makes it untrustworthy: you cannot tell which run
  you are looking at without the answer you were trying to compute.

  And refining is NOT monotone: 1207 scales above 504 still
  come back undecided, the highest at 2917. Each term's bracket
  depends on whether that scale divides that denominator, so a finer
  scale can widen the total slack. Search for a scale that decides;
  do not assume the next power of ten will.

=== the property that makes it usable: the error is one-sided ===
  40,000 (dataset, scale) pairs checked against the exact answer
    said DECIDED            : 18290
    ...and was right        : 18290   <- every time. never a wrong leader.
    said undecided anyway   : 1710   <- exact answer existed; bounds too loose
  SOUND but not COMPLETE: 'decided' is a proof, 'undecided' is an admission
  that this scale cannot tell you -- never a claim that nobody can.

The dataset that is confidently wrong forever¶

The first run is the cluster's canonical round-2 dataset, whose exact totals are 1205/168 each — a real tie, which is why that dataset exists.

Watch what the rounded count does with it. It names Bravo. At every scale, and it does not waver as the scale refines: 71–72, then 717–718, then 7172–7173, then 71726–71727. If you had only that column you would conclude the count was converging on a stable answer.

It is converging. The thing it is converging on is an artifact of round-half-up, which leans the same way on every term. This is bias, not noise — the failure does not average out, and refining the scale buys you more digits of a wrong answer, with rising confidence. The intervals overlap at every scale and decline to name anyone, which is the only correct behaviour available.

The dataset that has a leader, and needs a proof¶

The second run has a genuine margin of 1/504 — about 0.002. Here the intervals do eventually return DECIDED: Petra, but not until the scale is fine enough that 1/504 clears the accumulated slack.

Two findings from that search are worth more than the technique itself:

The rounded count is right most of the time, which is what makes it untrustworthy. Below the scale that proves it, the rounded count got the answer wrong at 184 of the 503 coarser scales — so it was right at 319 of them. A method that is right 63% of the time and silent about which run you are looking at is worse than one that is wrong always, because you cannot tell the good runs from the bad without the answer you were trying to compute.

Refining is not monotone. 1,207 scales above the first successful one still come back undecided, the highest at 2,917. Each term's bracket is a full unit wide unless that scale happens to divide that term's denominator, so a finer scale can widen the total slack. The practical consequence: search for a scale that decides — do not assume the next power of ten will.

Sound, not complete¶

Over 40,000 (dataset, scale) pairs checked against the exact answer:

it said DECIDED 18,290 times and was right 18,290 times;
it said undecided on 1,710 pairs where an exact leader did exist.

Those two lines are the whole character of the technique, and they are not symmetric. It can be too cautious. It cannot be wrong. In the vocabulary: the method is sound (everything it asserts is true) but not complete (it does not assert everything true). One-sided error is what makes a conservative method usable — you can build on Decided without checking it, and Undecided costs you work rather than correctness.

The word to avoid is "inconclusive as in useless". Undecided is a specific, true, useful claim: this scale cannot separate them — never nobody can.

Where you have met this before¶

The same shape underwrites a risk-limiting audit: an RLA either confirms the reported outcome or escalates toward a full hand count, and its guarantee is not that it always confirms but that it will not certify a wrong leader — the worst it can do is unnecessary work. Do not push the analogy too hard; an RLA's guarantee is statistical, sampling reviewers to a stated risk limit, while everything on this page is deterministic and proves its verdict outright. What transfers is the design: three outcomes rather than two, with the third one being escalation rather than a guess. The kata is that design, and the bug it starts from is what happens when you build it with only two.

When to reach for it¶

Not always, and not instead of the cluster:

Denominators enumerable in advance? Scale them away and be exact. Nothing here applies; you never rounded.
Rounding because a rule told you to? Then the rounded answer is correct by definition, and the interesting question is compliance, not error.
Rounding because you chose a width, and a result is close? This page. Bracket the terms and find out whether your choice or the reviewers decided it.
Need the exact value, not just the answer? Intervals will not give it to you. They answer an ordering question — which is, usefully, the only question an dataset actually asks.

One distinction worth keeping straight, because the two failures sound alike: the compounding-weights page is about a scaling denominator that grows because each round is built from the last round's weights. A rational's denominator growing under gcd — the i128 page's subject — is a different mechanism with a similar smell. Related failure modes, not the same one.

If you are coming from another language¶

Python. fractions.Fraction is the exact route and needs no bracket at all, which is why this technique is rarer there — if exactness is one import away, "was my rounding decisive" is a question you can dodge until Fraction gets too slow. When it does, you hand-roll the same two integers here, because the standard library has no interval type either. decimal is not it: Decimal gives you a declared precision and a rounding mode, so it tells you how it rounded but never how far the true value could be from what it stored.
ABAP. TYPE p DECIMALS n gives you the rounding and hides the bracket — the value is stored to the declared scale and the discarded remainder is gone, with no record of which way or how far. That is fine for money, where the scale is the law. It is not fine when the scale was your decision, and the habit to add is carrying both ends: two packed fields, one rounded down and one up, compared at the end. Rust does not give you the interval type either; what it gives you is that lo and hi can be one struct the compiler keeps together, so no caller can read one end and forget the other.

Practice¶

The audit that has to know when to stop. Five wards, one rounded count each. Write an audit that certifies a ward when the intervals prove its leader and escalates when they do not — starting, as everyone does, with while undecided { scale *= 10 }.

Run that on Ward 1 before reading further. Then work out why no budget fixes it, and what the third outcome has to be.

Solution

interval_arithmetic_kata.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.

//! Kata solution: the audit that has to know when to stop.
//!
//! An audit certifies a rounded count when the intervals prove it, and escalates
//! when they do not. The obvious escalation is "refine the scale and try again",
//! and on one of these five races that loop never returns -- because no scale can
//! separate an exact tie, and the loop has no way to say so.
//!
//!   rustc --edition 2024 interval_arithmetic_kata.rs -o /tmp/iak && /tmp/iak

use std::cmp::Ordering;

#[derive(Clone, Copy, PartialEq, Eq)]
struct Ratio {
    n: i128,
    d: i128,
}

fn gcd(a: i128, b: i128) -> i128 {
    let (mut a, mut b) = (a.abs(), b.abs());
    while b != 0 {
        let t = a % b;
        a = b;
        b = t;
    }
    a.max(1)
}

impl Ratio {
    fn new(n: i128, d: i128) -> Self {
        let g = gcd(n, d);
        Ratio { n: n / g, d: d / g }
    }
    fn add(self, o: Ratio) -> Self {
        Ratio::new(self.n * o.d + o.n * self.d, self.d * o.d)
    }
    fn sub(self, o: Ratio) -> Self {
        Ratio::new(self.n * o.d - o.n * self.d, self.d * o.d)
    }
    fn scale(self, k: i128) -> Self {
        Ratio::new(self.n * k, self.d)
    }
    fn cmp(self, o: Ratio) -> Ordering {
        (self.n * o.d).cmp(&(o.n * self.d))
    }
    fn text(self) -> String {
        if self.n == 0 { "0".to_string() }
        else if self.d == 1 { format!("{}", self.n) }
        else { format!("{}/{}", self.n, self.d) }
    }
}

fn bracket(v: Ratio, scale: i128) -> (i128, i128) {
    let num = v.n * scale;
    let lo = num.div_euclid(v.d);
    let hi = if num.rem_euclid(v.d) == 0 { lo } else { lo + 1 };
    (lo, hi)
}

fn bounds(scores: &[i128], weights: &[Ratio], scale: i128) -> (i128, i128) {
    let (mut lo, mut hi) = (0, 0);
    for (&s, &w) in scores.iter().zip(weights) {
        let (l, h) = bracket(w.scale(s), scale);
        lo += l;
        hi += h;
    }
    (lo, hi)
}

fn exact(scores: &[i128], weights: &[Ratio]) -> Ratio {
    scores.iter().zip(weights).fold(Ratio::new(0, 1), |acc, (&s, &w)| acc.add(w.scale(s)))
}

/// What an audit is allowed to conclude. Three outcomes, not two -- the third is
/// the whole fix, and the reason the naive loop cannot be repaired by looping harder.
#[derive(Debug, PartialEq)]
enum Audit {
    Certified(&'static str, i128), // leader, and the scale that proved it
    HandCount,                     // no scale in budget separated them
}

struct Race {
    name: &'static str,
    a: (&'static str, &'static [i128]),
    b: (&'static str, &'static [i128]),
}

const BUDGET: [i128; 8] = [10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000];

fn audit(r: &Race, weights: &[Ratio]) -> Audit {
    for scale in BUDGET {
        let (alo, ahi) = bounds(r.a.1, weights, scale);
        let (blo, bhi) = bounds(r.b.1, weights, scale);
        if alo > bhi {
            return Audit::Certified(r.a.0, scale);
        }
        if blo > ahi {
            return Audit::Certified(r.b.0, scale);
        }
    }
    Audit::HandCount
}

fn exact_leader(r: &Race, weights: &[Ratio]) -> &'static str {
    match exact(r.a.1, weights).cmp(exact(r.b.1, weights)) {
        Ordering::Greater => r.a.0,
        Ordering::Less => r.b.0,
        Ordering::Equal => "tie",
    }
}

fn main() {
    let weights: Vec<Ratio> = [5, 4, 3, 2, 1, 0].iter().map(|&s| Ratio::new(5, 5 + s)).collect();

    let races = [
        Race { name: "Ward 1", a: ("Alpha", &[0, 0, 1, 1, 1, 5]), b: ("Bravo", &[0, 3, 1, 1, 5, 0]) },
        Race { name: "Ward 2", a: ("Petra", &[1, 3, 4, 0, 1, 2]), b: ("Quinn", &[0, 2, 1, 2, 4, 1]) },
        Race { name: "Ward 3", a: ("Rosa", &[5, 4, 5, 4, 5, 4]), b: ("Sami", &[1, 1, 0, 1, 0, 1]) },
        Race { name: "Ward 4", a: ("Tariq", &[3, 3, 2, 2, 4, 1]), b: ("Vera", &[2, 4, 3, 1, 3, 2]) },
        Race { name: "Ward 5", a: ("Wes", &[0, 1, 2, 3, 4, 5]), b: ("Yuki", &[5, 4, 3, 2, 1, 0]) },
    ];

    println!("=== the slate, and what is actually true ===");
    println!("  {:<8} {:<14} {:>12} {:>12}  {:>10}", "race", "contest", "exact A", "exact B", "margin");
    for r in &races {
        let (ea, eb) = (exact(r.a.1, &weights), exact(r.b.1, &weights));
        let margin = if ea.cmp(eb) == Ordering::Less { eb.sub(ea) } else { ea.sub(eb) };
        println!("  {:<8} {:<14} {:>12} {:>12}  {:>10}",
                 r.name, format!("{} v {}", r.a.0, r.b.0), ea.text(), eb.text(), margin.text());
    }

    println!("\n=== the naive escalation: `while undecided {{ scale *= 10 }}` ===");
    println!("  Run it on Ward 1 with a counter instead of a prayer:");
    let r = &races[0];
    let mut scale: i128 = 10;
    let mut spins = 0;
    while spins < 30 {
        let (alo, ahi) = bounds(r.a.1, &weights, scale);
        let (blo, bhi) = bounds(r.b.1, &weights, scale);
        if alo > bhi || blo > ahi {
            break;
        }
        spins += 1;
        if let Some(next) = scale.checked_mul(10) { scale = next } else { break }
    }
    println!("    spun {spins} times, reached scale {scale}, still undecided");
    println!("    it is not slow -- it does not terminate. The exact answer is a");
    println!("    tie, and no scale separates a tie. A loop whose only two states");
    println!("    are 'decided' and 'try harder' cannot represent that.");

    println!("\n=== the fix is a third outcome, not a bigger budget ===");
    println!("  {:<8} {:<14} {:>10}  {:<24} {}", "race", "contest", "true", "audit says", "check");
    let mut certified = 0;
    let mut wrong = 0;
    let mut escalated = 0;
    for r in &races {
        let truth = exact_leader(r, &weights);
        let result = audit(r, &weights);
        let shown = match result {
            Audit::Certified(w, s) => format!("certified {w} at 1/{s}"),
            Audit::HandCount => "escalate: hand count".to_string(),
        };
        let check = match result {
            Audit::Certified(w, _) => {
                certified += 1;
                if w == truth { "ok" } else { wrong += 1; "WRONG WINNER" }
            }
            Audit::HandCount => {
                escalated += 1;
                if truth == "tie" { "correct to refuse" } else { "conservative" }
            }
        };
        println!("  {:<8} {:<14} {:>10}  {:<24} {}", r.name, format!("{} v {}", r.a.0, r.b.0), truth, shown, check);
    }

    println!("\n=== what the audit is allowed to claim ===");
    println!("  certified          : {certified}");
    println!("  certified wrongly  : {wrong}   <- the number that must stay 0");
    println!("  escalated          : {escalated}");
    println!("  An escalation is never a failure of the method. It is the method");
    println!("  declining to certify something it cannot prove -- which on Ward 1");
    println!("  is not conservatism at all, but the only correct answer there is.");
    println!("  Cost is one-sided too: the worst an audit can do is unnecessary work.");
}

Verified output of interval_arithmetic_kata.rs — regenerated by tools/run_examples.py, never hand-typed.

=== the slate, and what is actually true ===
  race     contest             exact A      exact B      margin
  Ward 1   Alpha v Bravo      1205/168     1205/168           0
  Ward 2   Petra v Quinn          15/2     3779/504       1/504
  Ward 3   Rosa v Sami        9511/504      349/126    2705/168
  Ward 4   Tariq v Vera         285/28     5197/504      67/504
  Ward 5   Wes v Yuki         3095/252     4465/504     575/168

=== the naive escalation: `while undecided { scale *= 10 }` ===
  Run it on Ward 1 with a counter instead of a prayer:
    spun 30 times, reached scale 10000000000000000000000000000000, still undecided
    it is not slow -- it does not terminate. The exact answer is a
    tie, and no scale separates a tie. A loop whose only two states
    are 'decided' and 'try harder' cannot represent that.

=== the fix is a third outcome, not a bigger budget ===
  race     contest              true  audit says               check
  Ward 1   Alpha v Bravo         tie  escalate: hand count     correct to refuse
  Ward 2   Petra v Quinn       Petra  certified Petra at 1/10000 ok
  Ward 3   Rosa v Sami          Rosa  certified Rosa at 1/10   ok
  Ward 4   Tariq v Vera         Vera  certified Vera at 1/100  ok
  Ward 5   Wes v Yuki            Wes  certified Wes at 1/10    ok

=== what the audit is allowed to claim ===
  certified          : 4
  certified wrongly  : 0   <- the number that must stay 0
  escalated          : 1
  An escalation is never a failure of the method. It is the method
  declining to certify something it cannot prove -- which on Ward 1
  is not conservatism at all, but the only correct answer there is.
  Cost is one-sided too: the worst an audit can do is unnecessary work.

Po polsku¶

Arytmetyka przedziałowa (interval arithmetic) jest w polskich materiałach tematem z metod numerycznych i służy tam zwykle do oszacowania błędu wartości: chcemy wiedzieć, w jakich granicach leży wynik. Ta strona zadaje pytanie węższe i praktyczniejsze — nie „ile dokładnie wynosi suma”, tylko „czy to moje zaokrąglenie wybrało zwycięzcę”. Węższe pytanie ma tańszą odpowiedź: wystarczy porównać końce dwóch przedziałów, a dokładny wynik nie musi się pojawić nigdzie w programie. Tym ta strona różni się od sąsiednich (skalowane liczby całkowite, i128), które kupują dokładność — tutaj dostajemy werdykt bez dokładnego zliczenia.

Mechanizm mieści się w dwóch liczbach. Zamiast zaokrąglonej wartości trzymamy przedział: dolny koniec to div_euclid, czyli podłoga, a górny to ten sam wynik plus jeden, chyba że dzielenie było bez reszty. Przedziały dodaje się po końcach, więc suma też jest przedziałem, a jedyne twierdzenie, jakie program kiedykolwiek wypowiada, brzmi a.lo > b.hi — najgorszy przypadek A bije najlepszy przypadek B. Żadnych liczb zmiennoprzecinkowych i żadnego sporu o tryb zaokrąglania.

Najciekawsza obserwacja dotyczy jednak samego zaokrąglania. W szkole uczy się zaokrąglania „połówek w górę” i traktuje się je jak regułę neutralną; księgowość zna „zaokrąglanie bankierskie” (banker's rounding) właśnie dlatego, że neutralna nie jest. Wybory z tej strony pokazują to dosadnie: przy dokładnym remisie zaokrąglone zliczenie wskazuje Bruna — i to na każdej skali, ani razu się nie wahając, bo reguła „w górę” przechyla każdy składnik w tę samą stronę. To błąd systematyczny, a nie przypadkowy, więc się nie uśrednia: zagęszczanie skali kupuje kolejne cyfry złej odpowiedzi wraz z rosnącą pewnością siebie. Przedziały w tym samym miejscu po prostu się nakładają i odmawiają wskazania kogokolwiek.

Na koniec para pojęć, którą warto nazwać po polsku, bo pochodzi z logiki, nie z numeryki: metoda jest poprawna (sound — wszystko, co stwierdza, jest prawdą), ale nie zupełna (complete — nie stwierdza wszystkiego, co prawdziwe). Błąd jest jednostronny, więc Decided wolno traktować jak dowód, a Undecided trzeba czytać dosłownie: „ta skala ich nie rozdziela”, nigdy „nikt tego nie rozstrzygnie”. Wynikają z tego dwie rzeczy praktyczne. Zagęszczanie skali nie jest monotoniczne — drobniejsza skala potrafi poszerzyć luz, jeśli nie dzieli mianowników — więc skali trzeba szukać, a nie zakładać, że kolejna potęga dziesiątki załatwi sprawę. I pętla while undecided { scale *= 10 } przy dokładnym remisie nigdy się nie kończy; lekarstwem nie jest większy budżet, tylko trzeci wynik — eskalacja do ręcznego przeliczenia. Dokładnie na tym stoi risk-limiting audit, na który nie ma utartej polskiej nazwy, więc tego akurat szukaj po angielsku.

Szukaj po polsku: arytmetyka przedziałowa · błąd systematyczny zaokrągleń · zaokrąglanie bankierskie · rust interval arithmetic · sound but not complete · risk-limiting audit