BFP
BFP is a library for large floating point numbers in incremental games.
Features
- 0 memory allocation
- Fast with decent accuracy
- Identical behaviour on any platform (assuming floating point +, -, *, / and @abs are consistent)
BFP is not IEEE-754 compliant and does not always round correctly, however.
Background
I've been wanting to make a Hololive-themed incremental game with some really big numbers, bigger than what 128-bit floating point can handle (which Zig natively supports).
Some existing libraries did not exactly fit my needs:
- Multiple precision libraries like GMP offered arbritary precision, but I only wanted large magnitude so the extra precision would waste CPU and memory (I don't care about correct rounding either, we're not doing science).
- Googology-sized number libraries like OmegaNum.js can handle incomprehensibly large numbers without the exact precision of GMP, but they were designed for numbers much larger than what I was planning.
break_infinity.js was a sweet spot in range and speed (and is also what's used in Antimatter Dimentions), but the idea of writing the game in JS (or C#) did not appeal to me. I figured I could make something faster anyway.
Waiting for offline progress to be calculated in the later stages of Antimatter Dimensions always annoyed me. Sure, I could speed up the tick rate, but I always felt like I was losing efficiency at high speed ups, not to mention that my automator scripts tended to break past 8x speed. This was also in stark contrast to other simpler incremental games I played in the past where offline progress was calculated instantly, like as if Cabe Johnson was still running my 9000 lemonade stands in the background. But I digress.
Benchmarks
Below are some benchmarks comparing the performance of break_infinity.js and BFP, based on the benchmarks in break_infinity.js's README.
All projects except the first have all parsing done outside of the benchmark. The exact code for the JS benchmarks can be found here.
| Project | break_infinity.js | BFP | Speedup |
|---|---|---|---|
| new Decimal("1.23456789e987654321") | 1.6e7 | 0.132e7 | 0.083x |
| Decimal.add("1e999", "9e998") | 2.7e7 | 28.5e7 | 10.6x |
| Decimal.mul("1e999", "9e998") | 9.3e7 | 34.6e7 | 3.72x |
| Decimal.pow(987.789, 123.321) | 2.2e7 | 4.08e7 | 1.85x |
| Decimal.pow(2, 1e10) | 1.8e7 | 45.8e7 | 25.4x |
| Decimal.log("987.654e789", 2) | 410e7(?) | 21.2e7 | 0.052x |
With the exception of parsing, BFP is multiple times faster than break_infinity.js. As it is expected for parsing and formatting to only occur rarely, the focus for those operations in BFP was to reduce code size rather than maximise speed.
The log benchmark for break_infinity.js is a little sus as it reports 4.1GFLOPS on a 5.4GHz processor, but the code runs Math.log10 on a regular floating point number. The interpreter is probably optimizing the result away and I couldn't find a way to black box it.
Testing
In case anyone decides to speedrun my game, I wanted the code to be fully deterministic and reproducible across platforms. Apart from regular tests, I also have 5000 random samples for each operation tested on 21 different CPUs (emulated through QEMU and Wasmtime) to ensure that they all produce the same result.
For decimal formatting, I ran an exhaustive test of all IEEE-754 single-precision floats and matched the output to that generated by Zig's standard library. I had extended Schubfach to work with arbitrary bit width floats, but was unable to prove the amount of precision needed to always find the shortest correctly rounded representation. So the actual precision to use was derived empirically and I can only guarantee that it works for values in the range of f32 (I haven't found a failure yet though and it does work for really large values).
I also plan on using Zig's integrated fuzz tester when it becomes more stable and stops crashing.