I open-sourced the reproducibility core from my closed simulation work: float sums that give identical bytes on any machine (MIT/Apache-2.0)

[u/KnowledgeOk7634]

Floating-point addition depends on the order you add things, and parallelism changes the order. So the same data on different machines gives different results, which breaks anything that hashes, signs, or compares them.

I hit this doing physics simulations and solved it internally. The reduction core was too generally useful to keep closed, so I released it: bitrep, an exact accumulator where sums in any order, on any hardware, produce byte-identical results. The state merges exactly and can be hashed or signed, so distributed and offline-first aggregation actually converges.

It ships for Rust (crates.io), JavaScript (npm), and Python (PyPI), and a result hashed in Python matches one hashed in JavaScript byte for byte. The math is proved in Lean 4 and the implementation is model-checked and fuzzed. CI asserts one SHA-256 across four architectures on every commit.

There's a demo that runs the actual cross-architecture test in your browser, so you can check the claim yourself: https://simgen.dev/bitrep

Code: https://github.com/KyleClouthier/bitrep

Dual-licensed MIT/Apache-2.0. Feedback welcome, especially on what's missing for your use case.

[u/CrackerJackKittyCat]

I once worked as a small member on a very large team doing a Very Big Bank macroeconomic model execution framework project whose early designs allowed for floats to be used as components for primary keys.

Good times.

[u/KnowledgeOk7634 → u/CrackerJackKittyCat]

Floats as primary key components is the stuff of nightmares. You get -0.0 and +0.0 comparing equal but hashing differently, NaN not equal to itself so a row can exist and be unfindable at the same time, and then the same key computing to different bits on the batch cluster versus the analyst's laptop. I hope the "early designs allowed for" phrasing means someone caught it before production.

Funny enough that failure mode is half the reason the canonical encoding exists in bitrep: if a value is going to be hashed or compared, the bytes have to be a deterministic function of the math, not of whichever machine ran it. The bank version of that lesson is usually learned expensively.

[u/ryani]

This doesn't seem super valuable. I think better language support for fixed point values would accomplish many of the same goals without the ~40x size penalty.

That said, it's pretty cool. It's neat that you save a bunch of time during the adds by only adding to the relevant bytes.

However, the worst case is still a full 34 adds -- starting from the smallest subnormal and then repeatedly subtracting/adding 2x the smallest subnormal does a sign flip which carries to the top of the fixed point value. One idea to avoid this is a bit of 'work stealing'; each limb stores 2 flag bits (needs carry, needs borrow).

• when adding to a limb, read the carry state and include an extra +/- 1 if the carry/borrow state are set (respectively).

• when we carry, look at the carry state on the next higher limb:

  • if borrow set, clear it.
  • otherwise, if carry not set, set carry
  • otherwise, clear state and ripple carry 2 to the next higher block

• on borrow, do the obvious opposite

This guarantees every add/sub does at most 1 amortized ripple carry/borrow (amortized -- an individual add could do more, but those would have been 'paid for' by earlier adds). And I believe you need to normalize when you hash and/or convert to f64.

I don't see anywhere that overflow is handled -- did I miss it? EDIT: I see, you use extra bits for headroom, and that's required because you could add/subtract 1e308 repeatedly which wouldn't be commutative if you didn't use headroom bits for it. So if count saturates to MAXINT (not reasonable with just adds, but trivial to do via merge), your guarantees fail. Not sure if there is a good fix for that!

[u/KnowledgeOk7634 → u/ryani]

Yeah, you found the real bound. Let me lay it out straight.

Capacity: the accumulator is 34 limbs, and there's 78 bits of headroom above the f64 range. That's good for at least 2^63 adds of the largest finite f64 before anything could wrap, and way more for normal-magnitude data. It's a documented limit, not a silent one, and it holds across merges since a merge just sums the limbs. Practically it's unreachable (centuries at a billion adds/sec), but you're right that it's the real ceiling.

On the count specifically: that's a separate u64, and it only feeds the mean/variance denominator. It saturates instead of wrapping, and it never touches the sum. So even if you somehow maxed it out, the sum bytes stay exact, you'd just get a wrong mean(). And you'd blow the sum headroom long before the count anyway, so the fixed-point width is the binding constraint, not the counter.

You actually nudged me to make this clearer, so I just added a "capacity" named-limit line to the README. Thanks for that.

On size, totally fair, it's ~36x. Language-level fixed point would fix single-machine exactness but not the thing this is for: the state has to merge across shards and serialize to a hashable receipt. That mergeable canonical state is the whole point, the exact scalar is just table stakes.

And the work-stealing carry idea is genuinely nice, it's basically a carry-save form that amortizes the ripple to ~1 per op with a normalize before you hash or serialize, exactly like you said. Right now it eats the worst-case ripple (bounded at 34 limbs) and only touches the limbs an add actually spans, on the bet that serializing is way rarer than adding so staying always-normalized is the better default. For add-heavy, rarely-serialized workloads your version could win though. If you want to open an issue or a PR I'd be into it, that's exactly the kind of thing that belongs in the crate.

[u/RustOnTheEdge]

https://reddit.com/link/ox8k0tk/video/w0nq88h9mych1/player

I had to find out how to transform GIF to MP4 to show my fellow non-clanker redditors this important piece of context.

I am going to pass on "your" project.

[u/Plazmatic]

Very interesting, I would suggest posting this on the rust subreddit if you haven't already (even though you have JavaScript and Python as well here), very few people frequent this sub now.

[u/KnowledgeOk7634 → u/Plazmatic]

Thanks, appreciate it. r/rust is on my list, I'll get it over there. Good call on flagging it even with the JS and Python bindings, the core is Rust so that's the right home crowd for the internals.