nimiq / core-rs-albatross

Rust implementation of the Albatross protocol
https://nimiq.com
Other
128 stars 43 forks source link

Use only primitive IEEE 754 features in supply curve calculations #2720

Open hrxi opened 5 days ago

hrxi commented 5 days ago

Additionally use a relatively simple square-and-multiply exponentiation.

The key realization is that x ** (y * z) is equal to (x ** y) ** z. We can use that to only require calculating integer powers of floating point numbers, but that can be done with the square-and-multiply algorithm.

We find that exp(-1.1e-9) ≈ 0.9999999989 and 2 ** -5.7327557121556496e-12 ≈ 0.9999999999960264, both as exact as f64 (confirmed with WolframAlpha).

The results of the supply curve differ only by less than 0.001%

https://en.wikipedia.org/w/index.php?title=Exponentiation_by_squaring&oldid=1229001691#With_constant_auxiliary_memory