When the denominators compound¶
Level: 301 · deep dive
One line: The companion trick works because one reweighting rule's denominators can be listed before the run starts; this page is the rule where they cannot, and the useful part is not that the technique fails but how it fails — the width you need is a property of the data, not of the problem's size, so you cannot pick an integer type in advance and the only honest design is one that detects rather than assumes.
Scale the denominator away ends on a test: is this round's weight a function of an integer, or of last round's weight? The rule there is the first kind, and the whole run collapses into i128. This page takes the second kind seriously, because "the trick doesn't apply here" is where most write-ups stop and it is the least useful sentence available.
Both rules are published ones, and they are named here once, as provenance for arithmetic you can go and check: the first is Reweighted Range Voting ↗, the second Allocated Score ↗. Nothing below depends on knowing either — the two lines of algebra do all the work.
The one line of difference¶
Both rules share out a pool proportionally. Both shrink a row's weight after each round, so that whoever has already been served has less pull in the next round. They differ in one statement:
// Recomputed from state — weight is a function of an integer
weight = C / (C + spent); // `spent` is a running integer total
// Compounding — weight is a function of the weights
weight = weight * (1 - quota / allocated); // `allocated` is a sum of current weights
In the first, a row's weight at round 7 depends on nothing but a small integer, so every denominator that can ever occur is C..=(C + rounds*C) and you can take their lcm before reading a row. In the second, this round's denominator is built out of last round's, through a sum over whichever rows happened to tie at the top rating. There is no set to enumerate, because the set is not determined until the data is.
Here is that happening on a real fixture — BetterVoting's own AllocatedScore test, twelve rows and two rounds:
Verified output of compounding_weights.rs — regenerated by tools/run_examples.py, never hand-typed.
1. Where the denominator comes from
Twelve rows, two rounds, so the quota is 12/2 = 6 rows.
Alpha wins round 1 with 8 backers at the top rating — 8 units of
weight to spend a 6-unit quota, so each keeps 1 - 6/8:
round 1 -> project 0 widest weight 1/4 (3 bits)
picked: Alpha, Delta
The 4 in that 1/4 was not chosen from any fixed set. It is the total
weight of whoever happened to tie at the top rating — so round 3's
denominators would be built from round 2's weights, and so on down.
There is no set of denominators to take an lcm over.
2. Eight datasets of exactly the same size
900 rows, 18 projects, 12 rounds. Only the votes differ.
widest denominator, in bits: [31, 31, 32, 33, 39, 33, 35, 27]
min 27, max 39, spread 12 bits
Same row count, same rounds, same projects. The arithmetic the
count needs is decided by how people voted, and by nothing you know
before they vote.
3. The same dataset, counted two ways
2000 rows, 30 projects, 20 rounds. Both additions are exact;
they differ only in how big a number they build on the way.
a/b + c/d = (ad+cb)/bd -> OVERFLOWED at round 16 (widest so far 44 bits)
both over lcm(b, d) -> all 20 rounds, widest denominator 68 bits
Read those two lines together. One counted the whole dataset; the
other gave up four rounds short. And the widest number the finishing
count ever had to REPRESENT was 68 bits — barely half of i128's 127.
The failing count did not run out of room for its answers. It ran
out building `(ad+cb)/bd`, a product of two denominators that it was
about to reduce away again.
4. Far enough out, the answer itself stops fitting
2500 rows, 35 projects, 28 rounds:
cross-multiply -> OVERFLOWED at round 16 (widest so far 33 bits)
lcm -> OVERFLOWED at round 27 (widest so far 73 bits)
The better addition bought eleven rounds, not safety. No fixed width
covers an unbounded quantity, and the width this count needs is not
knowable until it has read the rows — which is why it returns an
Outcome rather than a number.
Section 1 is the whole mechanism in one number. The quota is 6 rows; Alpha has 8 units of weight at the top rating; so each of those rows keeps 1 - 6/8, and a denominator of 4 enters the run. Nothing chose 4 from a fixed menu — it is the total weight of a group whose membership depends on the data. Round 3's denominators would be built from round 2's weights the same way, and so on down.
The width you need is a property of the data¶
That would be a merely theoretical objection if the growth were predictable in practice. It is not, and section 2 is the demonstration: eight datasets, all of them 900 rows, 18 projects and 12 rounds, differing only in the numbers in them. The widest denominator the exact run needs ranges from 27 bits to 39 bits — one of those datasets needs about four thousand times the range of another of exactly the same size.
That is the sentence that decides the design. You cannot look at the problem's parameters and choose an integer type, because the parameters are not what the requirement depends on. Nor can you measure it once and hard-code the answer, for the same reason the companion lesson's kata fails: a constant derived from one dataset is a constant that the next dataset is not obliged to respect.
So the count in this example does not return a number. It returns an outcome:
enum Outcome {
/// Every round settled exactly. Carries the widest denominator it needed.
Exact { picked: Vec<usize>, peak_bits: u32 },
/// The exact answer to some step did not fit. Carries the round it died on.
Overflowed { round: usize, peak_bits: u32 },
}
Every arithmetic operation on the Ratio type returns Option, and a None anywhere propagates into Overflowed. This is the same discipline as every other Option in this library — the case with no answer gets a value rather than a lie — applied to the one place where a voting engine most wants to lie to you, because the alternative is a wrapped negative vote total nobody notices.
The intermediate is what overflows, not the answer¶
Section 3 is the part I did not expect, and it is the practically useful half of the page.
The same dataset is run twice, with two implementations of addition that are both exactly correct and differ only in the size of the number they build on the way to the same reduced answer:
// schoolbook: a/b + c/d = (ad + cb) / bd
Ratio::new(self.num * other.den + other.num * self.den, self.den * other.den)
// lcm: put both over lcm(b, d) first — never larger, usually far smaller
let l = (self.den / gcd(self.den, other.den)) * other.den;
Ratio::new(self.num * (l / self.den) + other.num * (l / other.den), l)
One of them finishes all 20 rounds. The other gives up four rounds short. And the widest denominator the finishing run ever had to represent was 68 bits — barely half of what i128 holds. The failing run never ran out of room for its answers; it ran out building a product it was about to reduce away again.
Two things follow, and both are worth carrying past this page:
- A fixed-width rational type fails much earlier than its answers require. If you benchmark or bound such a type by the size of the values it stores, you will overestimate how far it goes, possibly by a factor of two in bits — which is to say by a factor of billions in range.
checked_mulreturningNonetells you an operation failed, not that the problem is too big. The first response to an overflow in rational code should be to look at the route, not the type. Comparison is the other classic offender:a/b < c/dcross-multiplies too, and dividing the common factor out first (a*(d/g)vsc*(b/g)) moved the failure point in this example by several rounds on its own.
Where it gives out anyway, and what Rust hands you there¶
Section 4 is the honest end of the road: a dataset where both additions run out, the better one merely eleven rounds later. No fixed width covers an unbounded quantity. At that point there are exactly three answers, and it is worth being blunt that all three are trades:
- Arbitrary-precision rationals. Correct without qualification, unbounded in cost, and — this is the part worth knowing before you start — Rust's standard library does not have them. No
BigInt, noBigRational, nothing. You reach fornum-bigintandnum-rational, which are excellent and are also a dependency, a compile-time cost, and a heap allocation per value. The language that made the companion lesson's fast path free charges you for the slow path that Python gives away, because Python'sintwas arbitrary-precision the whole time and itsFractioninherited that for nothing. - Fixed-point with a stated rounding rule. Pick a scale, write down which way you round, and the count can no longer overflow or fail. It also can no longer claim to be exact — but if the specification fixes the scale, then the rounded answer is the correct answer by definition rather than an approximation of one. This is not a dodge; it is what published rules for money and quotas actually do, and it is the kata.
- Detect and escalate. Run the cheap fixed-width count, and on
Nonefall back to the expensive exact one. You get the common case fast and the hard case right, at the cost of maintaining two counts that must agree — and of a test suite that has to actually exercise the second one, which is the part that quietly does not happen.
What Rust contributes is not a way out of that trilemma. It is that the trilemma is visible: the type of the count is Outcome, so every caller has to say what it does when the arithmetic gives out, and there is no path where the program silently picks answer 4 and wraps.
If you are coming from another language¶
- Python — you would never find this bug, because
fractions.Fractionsits on arbitrary-precisionintand simply grows. That is a real advantage and it is why the reference implementations of these rules are written in Python. The cost is the one the companion lesson measured: unbounded correctness is also unbounded work, silently, with no signal when a run starts doing thousand-bit arithmetic. Rust inverts the default — you get told, and then you have to decide. Neither default is right; knowing which one you are standing in is. - ABAP — packed decimal is fixed-point with the rounding rule built into the type, so answer 2 above is the one you already reach for, and
TYPE p DECIMALS nis that decision written into the data declaration. The thing that transfers less well is the ceiling: apfield tops out at 16 bytes, and a computation that outgrows it raises at runtime rather than being caught in review. So the failure mode is the same shape as this page's — an arithmetic requirement that depends on the data, discovered while running — and the fix is the same too: decide the precision deliberately and write it down, rather than discovering it from a short dump.
Practice¶
Build the run that always finishes. The exact run on this page can give up partway through a real dataset, and no integer width fixes that in general. So build the fixed-point alternative: weights as integer counts of 1/scale, one stated rounding rule applied everywhere, no division outside it.
Then answer the question that decides whether you would ship it — how much precision does it actually need? Run it at scales from 10^18 down to 10^2 against the exact run as ground truth, on every dataset where the exact run survives to be ground truth. Find the coarsest scale that still reproduces the exact picks.
Then write down, in one sentence, what your answer establishes and what it does not.
Solution
compounding_weights_kata.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.
//! Kata solution — the count that always finishes, and what that costs.
//!
//! The lesson's exact count can run out of `i128` partway through a real
//! dataset, and there is no width that fixes it in general. So the shippable
//! answer is a fixed-point count: pick a scale, state a rounding rule, and never
//! divide outside it. It cannot overflow and it always produces a committee.
//!
//! The question this program answers is how much precision that actually needs,
//! and the answer is uncomfortable in a useful way.
use std::cmp::Ordering;
const K: i128 = 5;
fn gcd(mut a: i128, mut b: i128) -> i128 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a.abs()
}
// ------------------------------------------------------------ exact (baseline)
#[derive(Clone, Copy, PartialEq, Eq)]
struct Ratio {
num: i128,
den: i128,
}
impl Ratio {
fn int(n: i128) -> Ratio {
Ratio { num: n, den: 1 }
}
fn new(num: i128, den: i128) -> Option<Ratio> {
if den == 0 {
return None;
}
let g = gcd(num, den);
let g = if g == 0 { 1 } else { g };
let (mut num, mut den) = (num / g, den / g);
if den < 0 {
num = -num;
den = -den;
}
Some(Ratio { num, den })
}
/// The lcm form throughout — the lesson showed the schoolbook one dies sooner.
fn add(self, o: Ratio) -> Option<Ratio> {
let l = (self.den / gcd(self.den, o.den)).checked_mul(o.den)?;
Ratio::new(
self.num
.checked_mul(l / self.den)?
.checked_add(o.num.checked_mul(l / o.den)?)?,
l,
)
}
fn sub(self, o: Ratio) -> Option<Ratio> {
self.add(Ratio { num: -o.num, den: o.den })
}
fn mul(self, o: Ratio) -> Option<Ratio> {
Ratio::new(self.num.checked_mul(o.num)?, self.den.checked_mul(o.den)?)
}
fn div(self, o: Ratio) -> Option<Ratio> {
if o.num == 0 {
return None;
}
Ratio::new(self.num.checked_mul(o.den)?, self.den.checked_mul(o.num)?)
}
fn cmp_checked(self, o: Ratio) -> Option<Ordering> {
let g = gcd(self.den, o.den);
Some(
self.num
.checked_mul(o.den / g)?
.cmp(&o.num.checked_mul(self.den / g)?),
)
}
fn is_zero(self) -> bool {
self.num == 0
}
}
/// `None` when the exact answer stopped fitting in `i128`.
fn exact(rows: &[Vec<i128>], rounds: usize) -> Option<Vec<usize>> {
let (nb, nc) = (rows.len(), rows[0].len());
let mut w = vec![Ratio::int(1); nb];
let mut alive: Vec<usize> = (0..nc).collect();
let mut picked = Vec::new();
let quota_size = Ratio::new(nb as i128, rounds as i128)?;
for round in 1..=rounds {
let mut best: Option<(Ratio, usize)> = None;
for &c in &alive {
let mut total = Ratio::int(0);
for i in 0..nb {
if rows[i][c] != 0 && !w[i].is_zero() {
total = total.add(w[i].mul(Ratio::int(rows[i][c]))?)?;
}
}
let better = match best {
None => true,
Some((b, _)) => total.cmp_checked(b)? == Ordering::Greater,
};
if better {
best = Some((total, c));
}
}
let win = best?.1;
picked.push(win);
alive.retain(|&c| c != win);
if round == rounds {
break;
}
let mut quota = quota_size;
let mut sup: Vec<usize> = (0..nb)
.filter(|&i| rows[i][win] != 0 && !w[i].is_zero())
.collect();
while !sup.is_empty() {
let mut top = Ratio::int(0);
for &i in &sup {
let s = w[i].mul(Ratio::int(rows[i][win]))?;
if s.cmp_checked(top)? == Ordering::Greater {
top = s;
}
}
let mut grp = Vec::new();
for &i in &sup {
if w[i].mul(Ratio::int(rows[i][win]))? == top {
grp.push(i);
}
}
let mut allocated = Ratio::int(0);
for &i in &grp {
allocated = allocated.add(w[i])?;
}
if allocated.cmp_checked(quota)? != Ordering::Greater {
for &i in &grp {
w[i] = Ratio::int(0);
}
sup.retain(|i| !grp.contains(i));
quota = quota.sub(allocated)?;
if quota.is_zero() {
break;
}
continue;
}
let keep = Ratio::int(1).sub(quota.div(allocated)?)?;
for &i in &grp {
w[i] = w[i].mul(keep)?;
}
break;
}
}
Some(picked)
}
// --------------------------------------------------------------- fixed point
//
// THE RULE, stated once and applied everywhere:
//
// A weight is an integer count of 1/`scale` units. A full row is `scale`.
// Every division truncates toward zero — so a reweighted row is never
// credited with more weight than it is owed, and the count can only ever
// under-spend a quota, never over-spend it.
//
// Nothing here can overflow for any scale where `scale * scale` fits, and
// nothing here can fail to produce a committee.
fn fixed(rows: &[Vec<i128>], rounds: usize, scale: i128) -> Vec<usize> {
let (nb, nc) = (rows.len(), rows[0].len());
let mut w = vec![scale; nb];
let mut alive: Vec<usize> = (0..nc).collect();
let mut picked = Vec::new();
let quota_size = (nb as i128) * scale / (rounds as i128);
for round in 1..=rounds {
let mut best = (i128::MIN, 0usize);
for &c in &alive {
let mut t: i128 = 0;
for i in 0..nb {
if rows[i][c] != 0 && w[i] != 0 {
t += w[i] * rows[i][c];
}
}
if t > best.0 {
best = (t, c);
}
}
let win = best.1;
picked.push(win);
alive.retain(|&c| c != win);
if round == rounds {
break;
}
let mut quota = quota_size;
let mut sup: Vec<usize> = (0..nb)
.filter(|&i| rows[i][win] != 0 && w[i] != 0)
.collect();
while !sup.is_empty() {
let top = sup.iter().map(|&i| w[i] * rows[i][win]).max().unwrap();
let grp: Vec<usize> = sup
.iter()
.copied()
.filter(|&i| w[i] * rows[i][win] == top)
.collect();
let allocated: i128 = grp.iter().map(|&i| w[i]).sum();
if allocated <= quota {
for &i in &grp {
w[i] = 0;
}
sup.retain(|i| !grp.contains(i));
quota -= allocated;
if quota == 0 {
break;
}
continue;
}
let keep = scale - (quota * scale / allocated); // truncates
for &i in &grp {
w[i] = w[i] * keep / scale; // truncates
}
break;
}
}
picked
}
// ------------------------------------------------------------------ rows
struct Rng(u64);
impl Rng {
fn next(&mut self, m: u64) -> u64 {
self.0 = self
.0
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(self.0 >> 33) % m
}
fn dataset(seed: u64, raters: usize, projects: usize) -> Vec<Vec<i128>> {
let mut g = Rng(seed);
(0..raters)
.map(|_| (0..projects).map(|_| g.next(K as u64 + 1) as i128).collect())
.collect()
}
}
// --------------------------------------------------------------------- main
fn main() {
const SCALES: [(&str, i128); 6] = [
("10^18", 1_000_000_000_000_000_000),
("10^12", 1_000_000_000_000),
("10^9", 1_000_000_000),
("10^6", 1_000_000),
("10^4", 10_000),
("10^2", 100),
];
const RUNS: u64 = 6;
for &(nb, nc, rounds) in &[(700usize, 16usize, 10usize), (2000, 30, 20)] {
println!("{nb} rows, {nc} projects, {rounds} rounds — {RUNS} datasets\n");
// Ground truth, where there is any.
let datasets: Vec<Vec<Vec<i128>>> =
(1..=RUNS).map(|s| Rng::dataset(s, nb, nc)).collect();
let truth: Vec<Option<Vec<usize>>> =
datasets.iter().map(|e| exact(e, rounds)).collect();
let checkable = truth.iter().filter(|t| t.is_some()).count();
let overflowed = RUNS as usize - checkable;
println!(" exact count finished on {checkable} of {RUNS}, ran out of i128 on {overflowed}");
if overflowed > 0 {
println!(" (the fixed-point count returned a committee on all {RUNS})");
}
println!();
println!(" scale reproduces the exact pick list");
for &(name, sc) in &SCALES {
let agree = datasets
.iter()
.zip(&truth)
.filter(|(_, t)| t.is_some())
.filter(|(e, t)| fixed(e, rounds, sc) == *t.as_ref().unwrap())
.count();
let note = if agree == checkable { "" } else { " <-- diverges" };
println!(" {name:<7} {agree} of {checkable}{note}");
}
println!();
}
println!("Four decimal places reproduce every exact answer anyone could check.");
println!("Two do not. The exact count that ran out of i128 was working to 68-odd");
println!("bits of denominator to reach a result that 10^4 also reaches.");
println!();
println!("What that establishes: on these datasets, at these sizes, the");
println!("approximation and the exact answer agree. What it does not establish:");
println!("anything at all about an dataset with a tied round, which is exactly");
println!("where a truncated weight and an exact one part company, and exactly the");
println!("case the companion lesson opened with.");
}
Verified output of compounding_weights_kata.rs — regenerated by tools/run_examples.py, never hand-typed.
700 rows, 16 projects, 10 rounds — 6 datasets
exact count finished on 6 of 6, ran out of i128 on 0
scale reproduces the exact pick list
10^18 6 of 6
10^12 6 of 6
10^9 6 of 6
10^6 6 of 6
10^4 6 of 6
10^2 4 of 6 <-- diverges
2000 rows, 30 projects, 20 rounds — 6 datasets
exact count finished on 5 of 6, ran out of i128 on 1
(the fixed-point count returned a committee on all 6)
scale reproduces the exact pick list
10^18 5 of 5
10^12 5 of 5
10^9 5 of 5
10^6 5 of 5
10^4 5 of 5
10^2 1 of 5 <-- diverges
Four decimal places reproduce every exact answer anyone could check.
Two do not. The exact count that ran out of i128 was working to 68-odd
bits of denominator to reach a result that 10^4 also reaches.
What that establishes: on these datasets, at these sizes, the
approximation and the exact answer agree. What it does not establish:
anything at all about an dataset with a tied round, which is exactly
where a truncated weight and an exact one part company, and exactly the
case the companion lesson opened with.
Four decimal places is enough, and two is not. The exact run was carrying 68-bit denominators — and running out of i128 on one dataset in six — to reach a set of picks that 10^4 reaches as well, every time anyone could check.
That is a genuinely awkward result, and the awkwardness is the lesson. The case for exact arithmetic in the companion page was airtight: a tied round is a tied round, and f64 broke one. But "exact" turned out to be reachable only on datasets small enough not to overflow, while the approximation finished every time — so on the datasets where the two disagree about whether an answer exists at all, the exact run is the one with nothing to say.
Note precisely what the table establishes: on these datasets, at these sizes, the two agree. It establishes nothing about a dataset with a tied round, which is exactly where a truncated weight and an exact one part company, and exactly the case the companion lesson opened with. An empirical agreement is not an error bound, and no number of agreeing datasets becomes one.
Which is why the real answer is the one the third option in the list above only half describes: stop treating the rounding as an approximation and make it the rule. Real STV and proportional legislation specifies the number of decimal places for surplus transfers, precisely because exactness is not achievable and a published, reproducible rounding rule is. Once the statute says four decimal places, a count to four decimal places is not an approximation of the right answer — it is the right answer, and it is one that any two implementations can agree on exactly.
Po polsku¶
Cała różnica mieści się w jednej linijce. W regule przeliczanej ze stanu waga wiersza po n-tej rundzie jest funkcją liczby całkowitej — więc każdy mianownik, jaki może się pojawić, da się wypisać z góry, wziąć z nich NWW i policzyć wszystko w i128. W regule kumulującej waga tej rundy jest funkcją wag z rundy poprzedniej: mianownik powstaje z sumy wag tych wierszy, które akurat wylądowały na szczycie skali. Tego zbioru nie da się wyliczyć wcześniej, bo on nie istnieje, dopóki nie ma danych. Strona nie kończy się jednak na „ta sztuczka tu nie działa” — najciekawsze jest to, jak to zawodzi.
Zawodzi tak, że potrzebna szerokość liczby jest własnością danych, a nie rozmiaru zadania. Osiem zbiorów identycznych parametrami (900 wierszy, 18 projektów, 12 rund), różniących się wyłącznie zawartością, potrzebuje mianowników od 27 do 39 bitów — jeden z nich wymaga około czterech tysięcy razy większego zakresu niż drugi. Nie da się więc dobrać typu całkowitego z góry, bo parametry zadania nie są tym, od czego to zależy; nie da się też zmierzyć raz i zapisać stałej. Dlatego przebieg zwraca wyliczenie Outcome (Exact albo Overflowed z numerem rundy), a każda operacja na ułamku zwraca Option — jedyny uczciwy projekt to taki, który wykrywa, zamiast zakładać.
Tu wchodzi rzecz, którą polska szkoła podaje na tacy, a większość implementacji ignoruje: przepełnia się rachunek pośredni, nie wynik. Dodawanie „na krzyż”, a/b + c/d = (ad+cb)/bd, pada na 16. rundzie z dwudziestu. Sprowadzenie obu ułamków do NWW mianowników — czyli dokładnie to, czego uczy się na ułamkach zwykłych w podstawówce — dowozi wszystkie dwadzieścia, a najszerszy mianownik, który trzeba było zapisać, ma 68 bitów, czyli połowę pojemności i128. Temu pierwszemu rachunkowi wcale nie zabrakło miejsca na odpowiedzi; zabrakło mu miejsca na iloczyn, który za chwilę i tak miał się skrócić. Stąd praktyczny wniosek: None z checked_mul mówi, że nie weszła operacja, a nie że zadanie jest za duże — najpierw patrz na drogę, potem na typ. To samo dotyczy porównania, bo a/b < c/d też mnoży na krzyż, a wcześniejsze skrócenie wspólnego czynnika przesunęło moment awarii o kilka rund.
Gdy jednak i to się skończy, uczciwe wyjścia są trzy i każde czymś płaci:
- Ułamki o dowolnej precyzji. Poprawne bezwarunkowo — i tu niespodzianka dla kogoś, kto przychodzi z Pythona: biblioteka standardowa Rusta ich nie ma. Żadnego
BigInt, żadnegoBigRational; sięgasz po crate'ynum-bigintinum-rational, czyli po zależność, czas kompilacji i alokację na stercie przy każdej wartości. Pythonowyintbył nieograniczony od zawsze, aFractionodziedziczył to za darmo. - Stałoprzecinkowo, z zapisaną regułą zaokrąglania. Nie może się przepełnić i zawsze zwróci skład. Nie może też twierdzić, że jest dokładne.
- Wykrywaj i eskaluj. Tani rachunek na stałej szerokości, a przy
None— ten drogi. Kosztem są dwa liczenia, które muszą się zgadzać, i testy, które naprawdę uruchamiają to drugie (a to jest ta część, która po cichu nie powstaje).
Wynik ćwiczenia jest niewygodny i o to chodzi: cztery miejsca po przecinku odtwarzają każdą dokładną odpowiedź, jaką w ogóle dało się sprawdzić, a dwa już nie. Rachunek dokładny dźwigał 68-bitowe mianowniki i na jednych wyborach z sześciu nie dojechał do końca — żeby dostać ten sam skład, który skala 10^4 wylicza za każdym razem. Uwaga na to, czego to nie dowodzi: zgodność na tych elektoratach nie jest oszacowaniem błędu i nigdy się nim nie stanie, a o rundzie remisowej — czyli o jedynym miejscu, gdzie waga ucięta i waga dokładna się rozchodzą — nie mówi zupełnie nic. Dlatego prawdziwa odpowiedź brzmi: przestań traktować zaokrąglenie jak przybliżenie i zrób z niego regułę. Tak działają realne ordynacje wyborcze, które zapisują liczbę miejsc po przecinku przy transferze nadwyżek: gdy przepis mówi „cztery miejsca”, wynik policzony do czterech miejsc nie jest przybliżeniem poprawnego wyniku — on jest poprawnym wynikiem, i dwie niezależne implementacje mogą się na niego zgodzić co do ostatniej cyfry.
Szukaj po polsku: przepełnienie arytmetyczne · ułamki zwykłe, NWW i NWD · liczby o dowolnej precyzji · rust num-bigint num-rational · rust checked_mul overflow · allocated score reweighted range voting