Scale the denominator away¶
Level: 301 · deep dive
One line: A total that has to be exact does not have to use fractions — if every denominator it will ever meet comes from a set you can enumerate before reading a single input, you can multiply through by their least common multiple once and spend the rest of the sum in plain integer arithmetic, which is both exactly right and about thirty times faster than the rationals it replaces.
This page is about a specific shape of problem, and the shape is more common than the example: exact arithmetic over a bounded set of denominators. Proportional voting is where I met it. Money, tax tables, interest accrual, resource quotas and anything that divides a fixed pool into shares all have the same shape, and the same three-way choice between a float that is fast and wrong, a rational that is right and slow, and a scaled integer that is both.
Why not just use floats¶
Because the failure is not "the last digit is off." The failure is that a tie stops being a tie.
Here is one round of a proportional allocation. A fixed pool is shared out over several rounds, and after each round a reviewer's weight drops to C / (C + S), where C is the per-round cap and S is what that reviewer has already been allocated. Round 1 funded Wren, so the six reviewers now weigh 5/10, 5/9, 5/8, 5/7, 5/6 and 5/5, and two projects are left for round 2.
Verified output of scaled_integers.rs — regenerated by tools/run_examples.py, never hand-typed.
Round 2 of a 5-round proportional allocation, 0-5 ratings.
Round 1 funded Wren, so each reviewer now weighs 5/(5+their rating for Wren).
reviewer gave Wren weight Alpha Bravo
1 5 5/10 0 0
2 4 5/9 0 3
3 3 5/8 1 1
4 2 5/7 1 1
5 1 5/6 1 5
6 0 5/5 5 0
1. f64
Alpha 7.17261904761904745
Bravo 7.17261904761904834
difference 8.881784197001252e-16
-> makes Bravo the larger share in round 2
2. exact rationals
Alpha 1205/168
Bravo 1205/168
-> a TIE — exactly equal shares
gcd calls: 36 — 3 per reviewer-and-project, to build the
weight, scale it by the rating, and add it in
3. scaled integers, everything over l = 2329089562800
Alpha 16705672161750
Bravo 16705672161750
-> TIE — same answer as the rationals
gcd calls while totalling: 0 (setup, once, before any rating: 26)
same value? true
What the scale costs in headroom. The worst a single reviewer can
contribute is 5 x 5 x (l/5), so the reviewer capacity is that into the type:
rounds denoms scale l max reviewers i64 in i128
1 5..10 2520 732013653718633 1.4e34
2 5..15 360360 5118976599431 9.4e31
3 5..20 232792560 7924112383 1.5e29
4 5..25 26771144400 68905325 1.3e27
5 5..30 2329089562800 792015 1.5e25
6 5..35 144403552893600 12774 2.4e23
7 5..40 5342931457063200 345 6.4e21
8 5..45 9419588158802421600 0 3.6e18
One million reviewers over 5 rounds, worst case, in i64:
checked_mul -> None (the honest answer)
wrapping_mul -> -6801296259709551616 (what a release build does if you just write `*`)
the same product in i128 -> 11645447814000000000
Read the first two totals against each other. Alpha and Bravo are exactly tied — both 1205/168 — and a tied round is not a rare pathology in a small allocation, it is the case the rules have a whole tie-breaking procedure for. f64 puts Bravo ahead by 8.9e-16 and that procedure never runs. Nobody sees an error, no test fails, and the round goes to whoever the rounding favoured.
That is the argument for exactness, and it is worth being precise about what it is not. It is not that floats are inaccurate — 8.9e-16 is an outstandingly accurate answer to the question "how much is 1205/168". It is that the caller does not want a good approximation of the total, it wants to know whether two totals are equal, and equality is the one question floating point cannot answer for you.
What exactness costs¶
So the implementations use rationals. Python's fractions.Fraction, Rust's num_rational::Ratio, and the forty-line Ratio in this page's example are all the same idea: carry a numerator and a denominator, and reduce after every operation so the pair does not grow without bound. Reducing means gcd, and the run above called gcd 36 times for 6 reviewers and 2 projects — three per reviewer-and-project, to build the weight, scale it by the rating, and add it into the running total.
That is the shape of the cost, and it scales with the problem: rows × columns × rounds, each with a gcd over numbers that get longer as the denominators accumulate. A Python program doing this kind of reweighted arithmetic spends most of its time in Fraction, and real ones notice: starvote ↗, which runs exactly this reweighting, carries a helper called _fraction_or_int whose entire job is to hand back a plain int whenever a Fraction happens to have denominator 1, because a Fraction is expensive enough to be worth escaping from when you can.
The trick¶
Look at where the denominators come from. A reviewer's weight is C / (C + S), C is 5, and S is the integer total allocated so far — so S runs from 0 to rounds × C, and the denominator runs over the finite, known set 5, 6, 7, … 30. Not "some fractions." Twenty-six specific integers, all of them known before the first rating is read.
So compute l = lcm(5..=30) once, and carry every total as a multiple of 1/l. A reviewer's contribution becomes
and l / den is an exact integer precisely because l is a multiple of every denominator in play. No fraction is ever constructed, no gcd runs during the count, and the totals are integers you compare with ==. Look at the third count in the output above: same tie, same answer as the rationals, and gcd ran zero times after the twenty-six calls that built the scale.
The assert! in count_scaled is not decoration:
let den = C + SPENT_IN_ROUND_1[i];
assert!(l % den == 0, "denominator {den} does not divide the scale");
total += score * C * (l / den);
l / den is integer division. If a denominator ever turns up that l does not cover, that line does not fail — it truncates, and the count carries on producing numbers that are slightly not the exact answer. The precondition is the entire basis of the technique, so it belongs in the code as a check rather than in your head as a fact. That is the kata.
When this works, and when it does not¶
The precondition is sharper than "the denominators are bounded." It is that the weight is recomputed from integer state each round, rather than multiplied into the previous weight. The difference decides whether the technique applies at all, and both cases live in the same file of the same engine:
| how the weight is updated | denominators | |
|---|---|---|
| Recomputed from state | weight = C / (C + S), from the accumulated integer S |
drawn from a fixed set — scaling works |
| Allocated Score | weight = weight × (1 − quota/allocated) |
multiplied round on round — scaling does not |
In the first, the weight in round 4 depends only on an integer, so every denominator that can ever appear is enumerable in advance. In the second, each round multiplies a new fraction into the old weight, so the denominators compound, the set is no longer fixed, and no single l covers it. There you keep the rationals — and the win available to you is the ordinary one of a compiled language, not two orders of magnitude.
The second case gets its own page — when the denominators compound — because "the trick doesn't apply here" turns out to be the least interesting thing true about it. Being able to tell the two apart at a glance is most of the value of this one. The question to ask of any weighted count is: is this round's weight a function of an integer, or of last round's weight?
Why i128, specifically¶
Multiplying everything by 2.3 trillion has a bill, and the bill is headroom. The worst a single reviewer can contribute is 5 × 5 × (l/5), so the number of reviewers that fit is that value into the integer type — and the last block of the output above is that arithmetic:
| rounds | scale l |
reviewers that fit i64 |
in i128 |
|---|---|---|---|
| 5 | 2,329,089,562,800 | 792,015 | 1.5e25 |
| 7 | 5,342,931,457,063,200 | 345 | 6.4e21 |
| 8 | 9,419,588,158,802,421,600 | 0 | 3.6e18 |
i64 is not enough. Not "not enough for a hypothetical" — a five-round allocation overflows it somewhere under 800,000 reviewers, and by eight rounds the scale alone exceeds what i64 can hold for a single reviewer. i128 absorbs all of it with room to spare, and it is an ordinary primitive: no crate, no allocation, no bignum, just two registers and a handful of extra instructions.
That is the concrete reason the phrase is "the whole count becomes i128 integer arithmetic" and not i64. Rust having a 128-bit integer in the language is what makes the technique comfortable rather than delicate.
Overflow is a decision, and Rust makes you make it¶
Which brings up the thing that actually bites. In Rust, a * b on integers has two different behaviours: a debug build panics on overflow, and a release build wraps. That is deliberate and documented, and it means the same expression can pass every test you run and then silently produce a negative total in production.
So for arithmetic whose range you have not proved, write the decision down. The last block of the output is one multiplication asked three ways:
checked_mul -> None (the honest answer)
wrapping_mul -> -6801296259709551616 (what a release build does if you just write `*`)
the same product in i128 -> 11645447814000000000
checked_mul returns Option — multiplication is a partial function once the type is finite, and this is the same idea as every other Option in this library: the case that has no answer gets a value instead of a lie. saturating_mul clamps, wrapping_mul wraps on purpose, and overflowing_mul hands back both the wrapped value and a flag. All four are explicit; only bare * is ambiguous about which you meant.
The negative number is the one to sit with. A project's total went below zero, and in a release build nothing in the language would have mentioned it.
What the two changes are actually worth¶
Here is the measurement, and it is the reason this page exists in the shape it does. The same 200,000-term accumulation, four ways — one machine, Python 3.14.2, rustc 1.97.1 -O, best of five runs:
| exact rationals | scaled integers | |
|---|---|---|
| Python | 571 ms | 37 ms |
| Rust | 86 ms | 2.7 ms |
Read the rows and columns separately, because they say different things:
- Porting the rationals to Rust as-is bought 6.6×. That is a good return and it is not two orders of magnitude. A hand-rolled
Ratio<i128>still callsgcdon every operation, and Python'sFractionis not naive — it reduces throughmath.gcd, which is C. Compiled-language speedups on code that is dominated by one library call are usually modest, and this is one of those. - Changing the representation bought 32× in Rust — and 15× in Python, without changing language at all. This is the larger of the two effects, and it was available the whole time. If the count has to stay in Python, this is the change to make.
- "100× faster in Rust" is true only if you do both, and the honest attribution is that most of it was the algorithm.
That distinction generalizes past this page. The instinct to reach for a faster language is often really an instinct to escape a data representation that the slower language made convenient — Fraction is right there in Python's standard library, and struct Ratio { num: i128, den: i128 } is something you have to decide to write. Rewriting in Rust does deliver, but if you rewrite the arithmetic faithfully you will bank the smaller half of the win and conclude that the language was the ceiling.
(One benchmarking note, learned the hard way while writing this: the first version of the scaled loop measured 0.0 ms, because LLVM could see the whole sum was a constant and deleted it. Anything you time in Rust needs std::hint::black_box ↗ around the inputs and the result, or you will measure the optimizer's opinion of your benchmark rather than your code. The example on this page prints no timings at all — a duration is exactly the kind of input the answer keys cannot hold.)
If you are coming from another language¶
- Python —
fractions.Fractionis the same design and it is a genuinely good one; the cost is that every value is a heap object with two arbitrary-precision integers inside it, so each operation is an allocation plus amath.gcdplus interpreter overhead, andintdivision is not the escape because it is not exact. What transfers is the whole technique: the 15× in the table above is Python-to-Python. What changes in Rust is the ceiling underneath it — aFractioncannot become two machine registers no matter how you write it, andintsilently growing to arbitrary precision means Python can never tell you that your scale has outgrown your type. - ABAP — you already have this.
TYPE p DECIMALS 2is fixed-point scaling built into the language: the value is stored as an integer and the decimal point is metadata, which is exactly "pick a denominator up front and stop dividing." So the idea needs no selling; what changes is that ABAP picks the scale for you as a power of ten, and here you pick it as an lcm because your denominators are 7 and 9 and 11, which no power of ten covers. And the overflow reporting inverts: packed arithmetic raisesCX_SY_ARITHMETIC_OVERFLOWat runtime and you catch it, whereas Rust wants the range argued before the run —i128because you did the multiplication on the whiteboard, withchecked_mulwhere you could not.
Both bridges end in the same place. The technique is old and neither language invented it; what Rust adds is a 128-bit integer that makes the scale fit, and a compiler that will not let you leave the overflow question unanswered — though, as the release-build wrap above shows, it will let you answer it badly.
Practice¶
The scale that stopped covering the problem. Deriving l costs an lcm over a couple of dozen integers on every run, so the obvious tidy-up is to compute it once and paste it in as a const. Do that — hard-code 2_329_089_562_800 — and then grow the allocation from five rounds to seven, so that reviewers can carry denominators of 31 and 32.
Make the mistake first and look hard at the result before fixing it, because the interesting part is what the failure does not do. Then fix it twice: derive the scale from the round count, and add the check that would have caught the stale one. Finally, work out what your correct scale did to the reviewer capacity, and decide whether the type you chose still fits the problem.
Solution
scaled_integers_kata.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.
//! Kata solution — the scale that stopped covering the allocation.
//!
//! The lesson's scale was derived from `ROUNDS`. Deriving it costs an lcm over a
//! couple of dozen integers on every run, which looks like exactly the sort of
//! thing to compute once and paste in as a constant. Then the allocation grows a
//! round, the constant does not, and the run keeps running.
//!
//! What makes this worth a kata is how it fails. It does not panic, it does not
//! produce an absurd number, and it does not change who won. It just quietly
//! stops being exact — which was the only reason to leave `f64` in the first
//! place.
const C: i128 = 5;
/// The allocation is seven rounds now. It was five when the constant below was
/// computed.
const ROUNDS: i128 = 7;
/// Late in the run: six reviewers, and the totals they have already spent on the
/// six projects elected so far. Denominators are `C + S`.
const SPENT: [i128; 6] = [26, 27, 30, 12, 0, 5];
const ALMA: [i128; 6] = [4, 0, 3, 5, 2, 1];
const BRUNO: [i128; 6] = [1, 5, 2, 0, 4, 3];
/// The stale constant: `lcm(5..=30)`, correct for a five-round allocation.
const STALE_SCALE: i128 = 2_329_089_562_800;
fn gcd(mut a: i128, mut b: i128) -> i128 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a.abs()
}
/// Derive the scale from the allocation, which is the fix.
fn scale_for(rounds: i128) -> i128 {
let mut l: i128 = 1;
for den in C..=(C + rounds * C) {
l = l / gcd(l, den) * den;
}
l
}
/// The count with no precondition check — what the lesson's `assert!` was for.
fn count_unchecked(scores: &[i128; 6], l: i128) -> i128 {
let mut total = 0;
for (i, &score) in scores.iter().enumerate() {
total += score * C * (l / (C + SPENT[i]));
}
total
}
/// The same count, refusing to run on a scale that cannot represent the answer.
fn count_checked(scores: &[i128; 6], l: i128) -> Result<i128, String> {
let mut total = 0;
for (i, &score) in scores.iter().enumerate() {
let den = C + SPENT[i];
if l % den != 0 {
return Err(format!(
"reviewer {} has denominator {den}, which does not divide the scale {l}",
i + 1
));
}
total += score * C * (l / den);
}
Ok(total)
}
/// Exact totals, as a reduced fraction, to compare both counts against.
fn count_exact(scores: &[i128; 6]) -> (i128, i128) {
let (mut num, mut den) = (0i128, 1i128);
for (i, &score) in scores.iter().enumerate() {
let (n, d) = (score * C, C + SPENT[i]);
let (nn, dd) = (num * d + n * den, den * d);
let g = gcd(nn, dd);
num = nn / g;
den = dd / g;
}
(num, den)
}
fn main() {
println!("A {ROUNDS}-round count, still scaled by a constant computed for 5 rounds.\n");
// 1. The precondition, stated out loud.
println!("1. Which denominators the stale scale can still represent");
println!(" stale scale = {STALE_SCALE} (= lcm 5..=30)");
for (i, &s) in SPENT.iter().enumerate() {
let den = C + s;
println!(
" reviewer {} denominator {:>2} {}",
i + 1,
den,
if STALE_SCALE % den == 0 { "exact" } else { "TRUNCATES" },
);
}
println!(" 31 is a prime above 30, and 32 needs a fifth factor of two.");
println!(" Neither is in lcm(5..=30), so neither divides it.");
// 2. The failure, and how invisible it is.
let good = scale_for(ROUNDS);
let (stale_a, stale_b) = (
count_unchecked(&ALMA, STALE_SCALE),
count_unchecked(&BRUNO, STALE_SCALE),
);
let (good_a, good_b) = (
count_unchecked(&ALMA, good),
count_unchecked(&BRUNO, good),
);
let (ea, eb) = (count_exact(&ALMA), count_exact(&BRUNO));
println!("\n2. What the stale scale actually does to the run");
println!(" exact Alma {}/{} Bruno {}/{}", ea.0, ea.1, eb.0, eb.1);
println!(
" stale scale Alma {stale_a} Bruno {stale_b} -> {} wins",
if stale_a > stale_b { "Alma" } else { "Bruno" }
);
println!(
" derived Alma {good_a} Bruno {good_b} -> {} wins",
if good_a > good_b { "Alma" } else { "Bruno" }
);
println!(
" stale total equals the exact value? Alma {} Bruno {}",
stale_a * ea.1 == ea.0 * STALE_SCALE,
stale_b * eb.1 == eb.0 * STALE_SCALE,
);
println!(
" derived total equals the exact value? Alma {} Bruno {}",
good_a * ea.1 == ea.0 * good,
good_b * eb.1 == eb.0 * good,
);
println!(" -> the larger share is the same either way. No test on the larger share");
println!(" would ever have caught this.");
// 3. The check that does catch it.
println!("\n3. The same count, checking its precondition first");
match count_checked(&ALMA, STALE_SCALE) {
Ok(v) => println!(" stale scale -> Ok({v})"),
Err(e) => println!(" stale scale -> Err: {e}"),
}
match count_checked(&ALMA, good) {
Ok(v) => println!(" derived scale -> Ok({v})"),
Err(e) => println!(" derived scale -> Err: {e}"),
}
// 4. And the bill for fixing it.
println!("\n4. What the correct scale costs");
for rounds in [5i128, 7] {
let l = scale_for(rounds);
let per_reviewer = C * C * (l / C);
println!(
" {rounds} rounds: scale {l:>22} reviewers that fit i64: {:>7}",
i64::MAX as i128 / per_reviewer,
);
}
println!(" Fixing the exactness bug cut the i64 reviewer capacity from 792,015");
println!(" to 345. In i128 the same allocation still has room for 6.4e21 reviewers.");
}
Verified output of scaled_integers_kata.rs — regenerated by tools/run_examples.py, never hand-typed.
A 7-round count, still scaled by a constant computed for 5 rounds.
1. Which denominators the stale scale can still represent
stale scale = 2329089562800 (= lcm 5..=30)
reviewer 1 denominator 31 TRUNCATES
reviewer 2 denominator 32 TRUNCATES
reviewer 3 denominator 35 exact
reviewer 4 denominator 17 exact
reviewer 5 denominator 5 exact
reviewer 6 denominator 10 exact
31 is a prime above 30, and 32 needs a fifth factor of two.
Neither is in lcm(5..=30), so neither divides it.
2. What the stale scale actually does to the run
exact Alma 37217/7378 Bruno 46721/6944
stale scale Alma 11748675285800 Bruno 15670707584025 -> Bruno wins
derived Alma 26951461105654800 Bruno 35948603197789425 -> Bruno wins
stale total equals the exact value? Alma false Bruno false
derived total equals the exact value? Alma true Bruno true
-> the larger share is the same either way. No test on the larger share
would ever have caught this.
3. The same count, checking its precondition first
stale scale -> Err: reviewer 1 has denominator 31, which does not divide the scale 2329089562800
derived scale -> Ok(26951461105654800)
4. What the correct scale costs
5 rounds: scale 2329089562800 reviewers that fit i64: 792015
7 rounds: scale 5342931457063200 reviewers that fit i64: 345
Fixing the exactness bug cut the i64 reviewer capacity from 792,015
to 345. In i128 the same allocation still has room for 6.4e21 reviewers.
Three things worth taking from that run.
31 and 32 are not arbitrary. 31 is a prime larger than 30, so it appears in no product of the numbers below it; 32 needs a fifth factor of two and lcm(5..=30) has only four. The failure is number-theoretic and completely predictable — which is what makes it checkable, and why the check is a one-liner rather than a test suite.
The answer did not change. Both runs put Bravo ahead. The truncation moves each total by less than one part in a trillion, so no assertion about the result — not the leader, not the round order, not a golden-file test of the printed report — would ever have failed. The only thing that changed is that the answer stopped being exact, and exactness was the entire reason for leaving f64. A wrong answer too small to see is still the bug you took on all this machinery to avoid; if a part-in-a-trillion error were acceptable you should have kept the float and its speed.
The fix has a bill. Deriving the scale correctly for seven rounds grows l to 5,342,931,457,063,200, and the number of reviewers that fit in i64 falls from 792,015 to 345. Fixing an exactness bug uncovered an overflow bug, which is the usual way these two travel; in i128 the same problem still has room for 6.4e21 reviewers, and that is the whole argument for the wider type in one number.
Po polsku¶
Polski czytelnik zna już połowę tej sztuczki, tylko pod inną nazwą: kwoty trzyma się w groszach. Zasada „nigdy nie licz pieniędzy na float” jest w polskich materiałach księgowych i bazodanowych tak stara, że nikt jej już nie uzasadnia — a uzasadnienie jest dokładnie takie, jak na tej stronie. Różnica jest jedna i to ona jest tematem lekcji: przy groszach skalą jest potęga dziesiątki, bo mianownik zawsze wynosi sto. Tutaj mianowniki to 5, 6, 7 … 30 — dwadzieścia sześć konkretnych liczb, znanych zanim padnie pierwsza ocena — więc skalą jest ich NWW (najmniejsza wspólna wielokrotność, lcm). Po przemnożeniu wszystkiego przez l dzielenie l / den jest dzieleniem bez reszty, żaden ułamek nie powstaje, a NWD (gcd) nie odzywa się w trakcie liczenia ani razu.
Warto też nazwać po polsku to, na czym f64 przegrywa, bo to nie jest „niedokładność”. 8,9e-16 to znakomicie dokładna odpowiedź na pytanie, ile wynosi 1205/168. Tyle że to liczenie nie pyta o wartość sumy, tylko o to, czy dwie sumy są równe — a równość to jedyne pytanie, na które liczby zmiennoprzecinkowe nie potrafią odpowiedzieć. Skutek jest gorszy niż zły wynik: remis przestaje być remisem, procedura rozstrzygania remisów w ogóle nie rusza, żaden test nie pęka i nikt się nie dowiaduje. Stąd trzy reprezentacje i jedna decyzja:
f64— szybka i po cichu nieprawdziwa;- ułamki (
Ratio, w Pythoniefractions.Fraction) — dokładne, ale każda operacja togcdi obiekt na stercie; - liczby całkowite po przeskalowaniu — dokładne i szybkie, pod jednym warunkiem.
Ten warunek jest ostrzejszy, niż się wydaje: nie wystarczy, że mianowniki są ograniczone — waga musi być przeliczana z całkowitego stanu w każdej rundzie, a nie mnożona przez wagę z rundy poprzedniej. Gdy waga to C / (C + S), a S jest liczbą całkowitą, zbiór mianowników da się wypisać z góry; gdy każda runda dokłada nowy czynnik, mianowniki się mnożą i żadne pojedyncze l ich nie pokryje. Dlatego assert!(l % den == 0) nie jest ozdobą: l / den to dzielenie całkowite, więc gdy warunek przestanie obowiązywać, program nie padnie — po cichu obetnie wynik i policzy do końca. Kata na dole strony pokazuje najgorszy wariant tej awarii: wynik się nie zmienia, więc żaden test na wynik nigdy by tego nie złapał.
Dwie rzeczy są specyficznie Rustowe. Po pierwsze i128 jest zwykłym typem prostym — nie BigInteger, nie klasa, nie alokacja — i to on sprawia, że skala rzędu 2,3 biliona mieści się razem z milionem wierszy, podczas gdy w i64 pięciorundowy przydział przepełnia się już poniżej 800 tysięcy wierszy. Po drugie przepełnienie (overflow) jest w Ruscie decyzją, i to taką, którą łatwo przeoczyć: to samo a * b panikuje w kompilacji debug, a w release się zawija, więc kod przechodzi wszystkie testy i dopiero na produkcji daje ujemną sumę. checked_mul zwraca Option, saturating_mul przycina, wrapping_mul zawija świadomie — tylko samo * nie mówi, o co ci chodziło.
Na koniec liczba warta zapamiętania przy każdej dyskusji „przepiszmy to na Rusta”: przepisanie ułamków jeden do jednego dało 6,6×, a zmiana reprezentacji — 32× w Ruscie i 15× w samym Pythonie, bez zmiany języka. Większa część wygranej leżała w algorytmie i była dostępna przez cały czas.
Szukaj po polsku: arytmetyka stałoprzecinkowa · kwoty w groszach · najmniejsza wspólna wielokrotność · przepełnienie zmiennej · rust checked_mul overflow release build · rust i128 exact fixed point arithmetic