4 ms·
Go 1's math/rand would more accurately be called an additive lagged Fibonacci generator. The first publication of it is due to Green, Smith, and Klem [1]. [1]
by pbsd 2y ago
Go 1's math/rand would more accurately be called an additive lagged Fibonacci generator. The first publication of it is due to Green, Smith, and Klem [1].
[1] https://doi.org/10.1145/320998.321006 https://doi.org/10.1145/320998.321006
- rsc 2y agoThat publication doesn't seem to mention the "lagged" part, or maybe I missed it. I am aware of https://www.leviathansecurity.com/blog/attacking-gos-lagged-fibonacci-generator https://www.leviathansecurity.com/blog/attacking-gos-lagged-... which also refers to it as a lagged Fibonacci generator. Rob Pike and I exchanged mail with Don Mitchell (who wrote the original C version of the Go 1 generator) a few months back to see how he would describe the algorithm, and he said "As I recall Jim and I implemented Marsaglia's LFSR-like generator." I think both descriptions (lagged Fibonacci and LFSR-like) are accurate in different ways, so either would be fine, but for the post I decided to use the original author's description.
- pbsd 2y agoThe name itself might be due to Knuth; they were initially known as additive generators in other early literature.
- pbsd 2y agoActually it wasn't Knuth; only the 1997 3rd edition contains the lagged Fibonacci name. The first instance of the name I can find is Marsaglia-Tsay in 1985 [1] (and possibly Marsaglia's 1984 "A current view of random number generators", which is impossible to find online). [1] https://doi.org/10.1016/0024-3795(85)90192-2 https://doi.org/10.1016/0024-3795(85)90192-2