和・比較・ID・分散・百分率で float が漏れる場所を塞ぐ

目標

0.1の実際の値を見て、同じ数列の合計が足す順序によって変わることを測り、==の代わりに何で比較するかを決めます。64ビットのIDがJavaScriptのdoubleで衝突するペアを数えて、文字列で送る関数を作り、丸めポリシーをDecimalで固定し、大きなオフセット上の分散をWelfordで求め、合計が100になるパーセンテージを作ったあと、すべてをダッシュボードのレスポンス1つにまとめます。

なぜ重要なのか

floatは、53ビットで近い値を書くという約束であり、サービスのルールは、たいてい「正確に同じ」と「合計が合う」ことを要求します。その2つがぶつかる場所は、例外を出さないため、再実行のたびに数ウォンずつ違う合計、ブラウザーでだけ間違うID、負の分散のように、発見が遅れます。何が表現の限界で、何が契約(丸めの位置・比較の許容誤差・送信形式)なのかを切り分ければ、直すべき場所が見えてきます。そのため採点ツールは、書いた数字だけを見るのではなく、あなたの関数を、用意された素材ではない入力で再実行して、基準の実装と突き合わせます。

用意するもの

/opt/fixtures/svccs/float/の下にあります。読み取り専用で使ってください。1行に1つの値を持つ.txtは、float(줄)またはint(줄)で読みます(コード内の韓国語は「行」を意味する語です)。

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단계에서 볼 소수 표기 목록

このコードブロックの韓国語の説明は、順に、series.txtは金額の流れ3,010行(float)で打ち消し合う大きな振替が混ざっていること、pairs.csvは計算した値と期待した値のペアであること、ids.txtは64ビットの注文ID(整数)、lines.csvは小数第3位まである請求金額で文字列のまま使うこと、samples.txtはエポックミリ秒で記録された応答時刻(float)、shares.csvは決済手段ごとの件数、records.csvはダッシュボードの元データ、params.jsonはexact_valuesとしてステップ1で見る小数表記のリストを持つこと、を述べています。

ステップ

/root/svccs/float/exact.jsonに、values(params.jsonのexact_valuesの順に、{"text": 표기, "exact": str(Decimal(float(표기))), "hex": float(표기).hex(), "is_exact": Decimal(float(표기)) == Decimal(표기)}のリスト。韓国語で「表記」を意味する語です)・sum_0_1_0_2(0.1 + 0.2のfloat値)・equals_0_3(0.1 + 0.2 == 0.3の結果)を書きます。
/root/svccs/float/floatkit.pyにsums(xs)を作成します。{"forward": 앞에서부터, "reverse": 뒤에서부터, "ascending": 값이 작은 것부터(sorted), "fsum": math.fsum}を返し(コード内の韓国語は、順に「先頭から」「後ろから」「値の小さいものから」を意味する語です)、最初の3つは、forループの+=で足します(組み込みのsum()ではありません)。series.txtを使って、/root/svccs/float/sums.jsonに、その4つの値と、n(行数)・distinct(4つの値のうち異なるものの個数)・builtin_sum(組み込みのsum(xs))を書きます。
同じファイルにclose(a, b) = math.isclose(a, b, rel_tol=1e-9, abs_tol=1e-9)を作成します。pairs.csvを使って、/root/svccs/float/close.jsonに、pairs・equal_exact(a == bであるペアの数)・equal_close(closeが真であるペアの数)・equal_rel_only(math.isclose(a, b, rel_tol=1e-9)で、abs_tolなしで真になるペアの数)を書きます。
ids.txtを使って、/root/svccs/float/ids.jsonに、ids(個数)・unsafe_ids(絶対値が2^53 − 1より大きい数)・float_collision_pairs(float(id)が同じになるペアの数。同じ値n個ごとにn·(n−1)/2)・ids_in_collisions(そのようなグループに含まれるIDの数)・largest_group(最大のグループのサイズ)を書きます。同じファイルにto_wire(ids)を作成し、IDをすべて10進文字列として入れたJSON配列のテキストを返すようにして、その結果を/root/svccs/float/ids_wire.jsonに書きます。
同じファイルにhalf_up(text, places)を作成します。10進文字列textを、小数places桁にROUND_HALF_UP(同点は0から遠いほう)で丸めた文字列です(Decimal(text).quantize(...)で、floatを経由しません)。lines.csvを使って、/root/svccs/float/rounding.jsonに、lines・sum_of_rounded_lines(行ごとにhalf_up(…, 2)した値の合計)・rounded_total(amountをDecimalですべて足したあとにhalf_up(…, 2))・difference(前者 − 後者)を文字列で、lines_builtin_round_differs(round(float(amount), 2)とfloat(half_up(amount, 2))が異なる行数)を整数で書きます。
同じファイルにwelford(xs)を作成します。{"n", "mean", "var"}(母分散、nで割る)を返し、Welfordの1パスの更新で計算します。samples.txtを使って、/root/svccs/float/variance.jsonに、n・mean(真の平均)・var_naive(ループで足したΣx²/n − (Σx/n)²)・var_welford・var_exact(fractions.Fractionで計算した母分散をfloatにしたもの)を書きます。
同じファイルにlargest_remainder(counts, total)を作成します。各割合c·total/Σcの整数部分を与え、余りの枠を、小数部分が大きい順(同じなら先にある項目が先)に1ずつ加えた整数のリストです(Σcが0ならすべて0)。shares.csvを使って、/root/svccs/float/percent.jsonに、categories・naive(それぞれround(c·100/Σc))・naive_sum・largest_remainder(total=100)・largest_remainder_sumを書きます。
同じファイルにsummarize(records)を作成し、records.csvを使って/root/svccs/float/dashboard.jsonを書きます。recordsは、records.csvの1行が{"id", "amount", "latency_ms", "category"}です(値は文字列でも数値でもかまいません)。返すもの: ids(各idの10進文字列、入力順)、total_amount(行ごとにhalf_up(amount, 2)した合計の文字列)、latency_mean・latency_var(welford)、categories(異なるcategoryをソートしたリスト)、share_pct(categoriesの順序の件数に対するlargest_remainder(…, 100))。

参考

採点ツールはfloatkit.pyを読み込みます。ファイルを読んで結果を作るコードは、別のスクリプトかpython3 - <<'PY'に置いてください。
JSONは、floatを読み戻すと同じ値になる表記(repr)で書きます。採点ツールは、合計とペアの数を正確に突き合わせます。
JavaScriptがどう読むかを直接見たいなら、node -e 'console.log(JSON.parse("[1873000000000000001]")[0])'のように確認できます。採点ツールは、json.loads(text, parse_int=float)で同じことを真似ます。
よくある間違い: ==で比較すること、組み込みのsum()を「先頭から足した合計」として書くこと、IDをintとして読んで衝突0と報告すること、round()やDecimal(float(x))で丸めポリシーの代わりにすること、教科書の分散の式をそのまま使うこと、合計が99のパーセンテージをそのまま出力すること。
出力物はセッションが終わると消えます。必要なら別に保管してください。

0.1の実際の値を見る

params.jsonのexact_valuesごとに、実際の保存値・16進表記・正確かどうかを、/root/svccs/float/exact.jsonのvaluesに書き、sum_0_1_0_2とequals_0_3も一緒に書いてください。

Decimal(0.1)のようにfloatをDecimalに変えると、二進の値が損失なく十進に移されます。文字列から作ったDecimal("0.1")と同じかどうかを見れば、その表記がfloatで正確かどうかがわかります。分母が2のべき乗になる小数だけが正確です。

足す順序が合計を変える

/root/svccs/float/floatkit.pyにsums(xs)を作成し、series.txtを使って、/root/svccs/float/sums.jsonにforward・reverse・ascending・fsum・n・distinct・builtin_sumを書いてください。採点ツールは、変形した数列でsumsを呼び出します。

最初の3つの合計は、forループの+=で足します。Python 3.12の組み込みsum()は、floatの合計により正確なアルゴリズムを使うので、ループと値が異なることがあります。大きな値±10^15の隣で、小さな金額の下位の桁が切り捨てられることが、違いの原因です。

==の代わりに何で比較するか

floatkit.pyにclose(a, b)を作成し、pairs.csvを使って、/root/svccs/float/close.jsonにpairs・equal_exact・equal_close・equal_rel_onlyを書いてください。採点ツールは、0付近のペアが混ざった変形したペアでcloseを呼び出します。

math.iscloseのデフォルトのabs_tolは0.0なので、0と比較すると、0でない値は常に偽になります。残高が0であるべき検査なら、abs_tolも一緒に指定します。equal_rel_onlyは、わざとabs_tolを除いて数えます。

64ビットのIDがブラウザーで重なる

ids.txtを使って、/root/svccs/float/ids.jsonにids・unsafe_ids・float_collision_pairs・ids_in_collisions・largest_groupを書き、floatkit.pyにto_wire(ids)を作成して、その結果を/root/svccs/float/ids_wire.jsonに書いてください。採点ツールは、to_wireの結果を、JavaScriptのようにdoubleとして読んでみます。

Pythonは整数をintとして読むので、何も問題がないように見えます。受け取る側のようにfloat(id)に変換して、同じ値どうしをグループにしないと、衝突が見えません。2^60付近で、隣り合うdoubleの間隔は256です。送信は、JSONの数値ではなく、文字列で行います。

丸めポリシーをDecimalで固定する

floatkit.pyにhalf_up(text, places)を作成し、lines.csvを使って、/root/svccs/float/rounding.jsonにlines・sum_of_rounded_lines・rounded_total・difference・lines_builtin_round_differsを書いてください。採点ツールは、変形した金額と複数の桁数でhalf_upを呼び出します。

Decimal("2.675")は正確に2.675ですが、Decimal(2.675)は2.67499…です。文字列から直接作ってquantizeしてください。round()は同点を偶数の側に丸め、floatで書けない値は、同点ですらないことがあります。負の数のhalf-upは、0から遠いほうです。

大きなオフセット上の分散

floatkit.pyにwelford(xs)を作成し、samples.txtを使って、/root/svccs/float/variance.jsonにn・mean・var_naive・var_welford・var_exactを書いてください。採点ツールは、別のオフセットの変形したサンプルでwelfordを呼び出します。

Σx²/nと(Σx/n)²は、1.79e12の二乗付近にある2つの大きな数なので、引き算で有効数字がほとんど消えます。Welfordは、平均を少しずつ移しながら偏差だけを累積するので、この桁落ちを避けます。var_exactは、各floatをFractionに変換して計算します。

合計が100になるパーセンテージ

floatkit.pyにlargest_remainder(counts, total)を作成し、shares.csvを使って、/root/svccs/float/percent.jsonにcategories・naive・naive_sum・largest_remainder・largest_remainder_sumを書いてください。採点ツールは、同点が混ざった変形した件数でlargest_remainderを呼び出します。

割合をfloatで計算すると、同じはずの余りがわずかに異なり、同点の判定が揺らぎます。fractions.Fractionで割合を作れば正確です。同点は、先にある項目が先です。

ダッシュボードのレスポンス1つにまとめる

floatkit.pyにsummarize(records)を作成し、records.csvを使って、/root/svccs/float/dashboard.jsonを書いてください。採点ツールは、変形したレコードでsummarizeを呼び出し、結果をJavaScriptのようにdoubleとして読んで、IDが生き残るかどうかを確認します。

前のステップのhalf_up・welford・largest_remainderをそのまま使います。IDは文字列、金額の合計はDecimalの文字列です。latencyを教科書の式で求めると、負の数が出ることがあります。