Stop Floats Leaking in Sums, Comparisons, IDs, Variance and Percentages

Goal

You will look at the actual value of 0.1, measure how the sum of the same sequence changes with the order of addition, and decide what to compare with instead of ==. You will count the pairs where 64-bit IDs collide in a JavaScript double and build a function that sends them as strings, pin down a rounding policy with Decimal, compute variance on a large offset with Welford, make percentages that sum to 100, and then gather it all into a single dashboard response.

Why it matters

A float is a promise to write numbers close using 53 bits, while a service's rules usually demand "exactly equal" and "the sum adds up." The places where the two collide raise no exception, so they are found late, as a total that differs by a few won on every rerun, an ID that is wrong only in the browser, or a negative variance. If you separate what is a limit of representation from what is a contract (where to round, comparison tolerance, transmission format), you can see where to fix. So the grader does not look only at the numbers you wrote; it runs your functions again on inputs that are not the materials and compares them with the reference implementation.

Materials

They are under /opt/fixtures/svccs/float/. Only read them. A .txt with one value per line is read with float(줄) or int(줄) (with the line as the argument).

series.txt   금액 흐름 3,010줄(float). 상쇄되는 큰 이체가 끼어 있다
pairs.csv    a,b — 계산한 값과 기대한 값의 쌍(float 표기)
ids.txt      64비트 주문 ID(정수)
lines.csv    line_id,amount — 소수 셋째 자리까지 있는 청구 금액(문자열 그대로 쓸 것)
samples.txt  에포크 밀리초로 찍힌 응답 시각(float)
shares.csv   category,count — 결제 수단별 건수
records.csv  id,amount,latency_ms,category — 대시보드 원본
params.json  exact_values — 1단계에서 볼 소수 표기 목록

Steps

1. In /root/svccs/float/exact.json, write values (a list, in the order of exact_values in params.json, of {"text": 표기, "exact": str(Decimal(float(표기))), "hex": float(표기).hex(), "is_exact": Decimal(float(표기)) == Decimal(표기)}, where text is the decimal notation string), sum_0_1_0_2 (the float value of 0.1 + 0.2), and equals_0_3 (the result of 0.1 + 0.2 == 0.3).
2. In /root/svccs/float/floatkit.py, create sums(xs): it returns {"forward": 앞에서부터, "reverse": 뒤에서부터, "ascending": 값이 작은 것부터(sorted), "fsum": math.fsum} (forward is from the front, reverse is from the back, ascending is from the smallest value (sorted), and fsum is math.fsum), and the first three are added by a for loop using += (not the built-in sum()). With series.txt, in /root/svccs/float/sums.json write those four values, plus n (the number of lines), distinct (the number of distinct values among the four), and builtin_sum (the built-in sum(xs)).
3. In the same file, create close(a, b) = math.isclose(a, b, rel_tol=1e-9, abs_tol=1e-9). With pairs.csv, in /root/svccs/float/close.json write pairs, equal_exact (the number of pairs where a == b), equal_close (the number of pairs where close is true), and equal_rel_only (the number of pairs that are true with math.isclose(a, b, rel_tol=1e-9), without abs_tol).
4. With ids.txt, in /root/svccs/float/ids.json write ids (the count), unsafe_ids (the numbers whose absolute value is greater than 2^53 − 1), float_collision_pairs (the number of pairs for which float(id) becomes equal; n·(n−1)/2 for every n equal values), ids_in_collisions (the number of IDs in such groups), and largest_group (the size of the largest group). In the same file, create to_wire(ids) so that it returns the text of a JSON array holding all the IDs as decimal strings, and write that result to /root/svccs/float/ids_wire.json.
5. In the same file, create half_up(text, places): the string obtained by rounding the decimal string text to places decimal places with ROUND_HALF_UP (ties go away from 0) (Decimal(text).quantize(...), never going through a float). With lines.csv, in /root/svccs/float/rounding.json write, as strings, lines, sum_of_rounded_lines (the sum of half_up(…, 2) of each line), rounded_total (half_up(…, 2) after adding all the amounts as Decimals), and difference (the former − the latter), and as an integer lines_builtin_round_differs (the number of lines where round(float(amount), 2) and float(half_up(amount, 2)) differ).
6. In the same file, create welford(xs): it returns {"n", "mean", "var"} (population variance, divided by n) and computes it with Welford's one-pass update. With samples.txt, in /root/svccs/float/variance.json write n, mean (the true mean), var_naive (Σx²/n − (Σx/n)² added up in a loop), var_welford, and var_exact (the population variance computed with fractions.Fraction, as a float).
7. In the same file, create largest_remainder(counts, total): give the integer part of each share c·total/Σc, and add 1 to the leftover shares in descending order of fractional part (earlier items first on a tie), as a list of integers (all 0 if Σc is 0). With shares.csv, in /root/svccs/float/percent.json write categories, naive (each round(c·100/Σc)), naive_sum, largest_remainder (total=100), and largest_remainder_sum.
8. In the same file, create summarize(records) and, with records.csv, write /root/svccs/float/dashboard.json. Each record is one line of records.csv = {"id", "amount", "latency_ms", "category"} (the values may be strings or numbers). What to return: ids (the decimal string of each id, in input order), total_amount (the string of the sum of half_up(amount, 2) of each line), latency_mean·latency_var (welford), categories (the sorted list of distinct categories), and share_pct (largest_remainder(…, 100) applied to the counts in categories order).

Notes

• The grader imports floatkit.py. Put code that reads files and produces results in a separate script or in python3 - <<'PY'.
• JSON writes floats in a notation that gives the same value when read back (repr). The grader compares the sums and the pair counts exactly.
• If you want to see how JavaScript reads it, you can check it like node -e 'console.log(JSON.parse("[1873000000000000001]")[0])'. The grader imitates the same thing with json.loads(text, parse_int=float).
• Common mistakes: comparing with ==, writing the built-in sum() as "the sum added from the front," reading IDs as int and reporting 0 collisions, substituting round() or Decimal(float(x)) for the rounding policy, using the textbook variance formula as it is, and emitting percentages that sum to 99 as they are.
• The outputs disappear when the session ends. Keep them elsewhere if you need them.

Look at the actual value of 0.1

For each of the exact_values in params.json, write the actual stored value, the hexadecimal notation, and whether it is exact to values in /root/svccs/float/exact.json, and also write sum_0_1_0_2 and equals_0_3.

If you convert a float to a Decimal, as in Decimal(0.1), the binary value is carried over to decimal without loss. If you check whether it equals Decimal("0.1") made from a string, you can tell whether that notation is exact as a float. Only decimals whose denominator is a power of 2 are exact.

The order of addition changes the sum

Create sums(xs) in /root/svccs/float/floatkit.py, and with series.txt write forward, reverse, ascending, fsum, n, distinct, and builtin_sum to /root/svccs/float/sums.json. The grader calls sums with variant sequences.

Add the first three sums with += in a for loop. The built-in sum() in Python 3.12 uses a more accurate algorithm for float sums and its value can differ from the loop. The cause of the difference is that next to a large value of ±10^15, the low digits of a small amount are cut off.

What to compare with instead of ==

Create close(a, b) in floatkit.py, and with pairs.csv write pairs, equal_exact, equal_close, and equal_rel_only to /root/svccs/float/close.json. The grader calls close with variant pairs that include pairs near 0.

The default abs_tol of math.isclose is 0.0, so when compared with 0, any nonzero value is always false. If it is a check that a balance must be 0, give abs_tol as well. equal_rel_only is counted with abs_tol deliberately left out.

64-bit IDs overlap in the browser

With ids.txt write ids, unsafe_ids, float_collision_pairs, ids_in_collisions, and largest_group to /root/svccs/float/ids.json, and create to_wire(ids) in floatkit.py and write its result to /root/svccs/float/ids_wire.json. The grader reads the result of to_wire as doubles, the way JavaScript does.

Python reads integers as int, so everything seems fine. You can see the collisions only if you convert with float(id) as the receiver does and group equal values. Near 2^60 the gap between neighboring doubles is 256. Transmit as strings, not JSON numbers.

Pin the rounding policy down with Decimal

Create half_up(text, places) in floatkit.py, and with lines.csv write lines, sum_of_rounded_lines, rounded_total, difference, and lines_builtin_round_differs to /root/svccs/float/rounding.json. The grader calls half_up with variant amounts and several numbers of decimal places.

Decimal("2.675") is exactly 2.675, but Decimal(2.675) is 2.67499… Create it directly from a string and quantize. round() sends ties to the even side, and a value that cannot be written as a float may not even be a tie. Half-up for negative numbers goes away from 0.

Variance on a large offset

Create welford(xs) in floatkit.py, and with samples.txt write n, mean, var_naive, var_welford, and var_exact to /root/svccs/float/variance.json. The grader calls welford with variant samples at other offsets.

Σx²/n and (Σx/n)² are two large numbers near the square of 1.79e12, so nearly all significant digits disappear in the subtraction. Welford shifts the mean little by little and accumulates only deviations, so it avoids this cancellation. var_exact is computed by converting each float to a Fraction.

Percentages that sum to 100

Create largest_remainder(counts, total) in floatkit.py, and with shares.csv write categories, naive, naive_sum, largest_remainder, and largest_remainder_sum to /root/svccs/float/percent.json. The grader calls largest_remainder with variant counts that include ties.

If you compute the shares as floats, the same remainder becomes slightly different and the tie judgment wobbles. If you build the shares with fractions.Fraction, it is exact. On a tie, the earlier item goes first.

Gather it into one dashboard response

Create summarize(records) in floatkit.py, and write /root/svccs/float/dashboard.json with records.csv. The grader calls summarize with variant records, and reads the result as doubles, the way JavaScript does, to see whether the IDs survive.

Use half_up, welford, and largest_remainder from the earlier steps as they are. IDs are strings, and the amount total is the string of a Decimal. If you compute latency with the textbook formula, you can get a negative number.