u/camel-cdrin r/C_Programming • Recommends
Generating random floats is harder than you'd think (YouTube link is timestamped)
0:00 / 0:00
How computers generate random numbers (A guide for programmers)
Together C and C++
410 subscribers • 1 video on Hallway
- Recommended by 1 person: 1 in engineering communities.
- Linked in the descriptioncamel-cdr/cauldron
Advanced. Deep dive for people who know the field.
1.9K views5 years ago1 recommendation
Computer scienceSystems programmingAlgorithmsMath for programmersC++
This deep dive covers pseudo-random number generators, cryptographically secure generators, and the challenges of generating random floating-point numbers.
Broadcasted live on Twitch -- Watch live at twitch.tv/tccpp Links / Sources: github.com/camel-cdr/cauldron/blob/main/cauldron/random.h "Multiply with carry", George Marsaglia (1994) "On the probability of overlap of random subsequences of pseudorandom number generators" Sebastiano Vigna (2020) pcg-random.org/posts/too-big-to-fail.html en.wikipedia.org/wiki/Linear_congruential_generator pcg-random.org "Predicting the PCG Pseudo-Random Number Generator In Practice." Charles Bouillaguet, Florette Martinez, Julia Sauvage (2020) romu-random.org "Middle Square Weyl Sequence RNG" Bernard Widynski (2017-2020) en.wikipedia.org/wiki/IEEE_754 "Generating Pseudo-random Floating-Point Values" Allen B. Downey (2007) "Generating Random Floating-Point Numbers by Dividing Integers: a Case Study" Frédéric Goualard (2020) "Generating Pseudo-random Floating-Point Values" AllenB. Downey (2007) "The ziggurat method for generating random variables." Marsaglia, G., and Wai Wan Tsang (2000) "A Convenient Method for Generating Normal Variables" Marsaglia, G.; Bray, T. A. (1964) "Computer Generation of Random Variables Using the Ratio of Uniform Deviates" A. J. Kindermann, J. F. Monahan (1976) "A Fast Normal Random Number Generator" Joseph L. Leva (1991) andrew-helmer.github.io/permute/ github.com/camel-cdr/cauldron/blob/main/tools/random/permute… - Introduction - Terminology - A PRNG to think about - Quantifying randomness - Quality and Speed comparison of PRNGs - Permuted congruential generator (PCG) family - Rotate-multiply (Romu) family + Instruction-Level Parallelism (ILP) - Middle Square Weyl Sequence (msws) generator - Random integer in a range - Random floats - Clarifying Seeding and problems with C++'s random library - Random normals - Fisher-Yates shuffle - Random Permutations - Questions and AnswersWhy it's here
1 person recommends thisWhat people say. Recommended as an incredibly thorough deep dive into the complexities of generating random floats and integers.
Moments people linked to
u/camel-cdrin r/compsci • Recommends
How computers generate random numbers (A guide for programmers)
u/camel-cdrin r/C_Programming • Mentions
On “Generating random floats is harder than you'd think (YouTube link is timestamped)”
This is a part of a presentation I held about what I learned while writing my C random number library and I though this might be interesting for this subreddit.
Use this timestamp, if you need a refresher on the IEEE floating-point format.
TLDW:
`rand32() / UINT32_MAX` is wrong, because it generates numbers in the range `0;1` and getting a `1` has an unproportionately low probability of `1/2**32`.
It's also suboptimal, because there isn't a one to one mapping of integers to floating point values and because it can't generate all possible floating point numbers.
`(rand32() >> 8) * (1.0f / (1ul << 24))` or spelled out `(rand32() >> (32 - FLT_MANT_DIG)) * (1.0f / (UINT32_C(1) << FLT_MA…
u/camel-cdrin r/C_Programming • Mentions
On “A C Standard Library”
…cs. It's always preferable to run a benchmark multiple times and output the average, deviation and other useful metrics, over just outputting the time of a single run. You should also consider adding compiler specific `DoNotOptimize` macros, that help the programmer from stopping the compiler the code that is supposed to be benchmarked. (check out link to this video
3. Think about implementing a custom PRNG for `randnum_gen`, since `rand()` is quite slow and has low quality randomness on many platforms, mostly for historical reasons. Resources to check out: rand considered harmful, https://pcg-random.org, https://prng.di.unimi.it/, https://romu-random.org, and for a bit of self promo…
u/camel-cdrin r/C_Programming • Mentions
On “SIMD-oriented Fast Mersenne Twister in C and non STD library discussion”
I wouldn't recommend using the Mersenne Twister if you aren't forced to.
It fails statistical tests, isn't as fast as other higher quality PRNGs, and has a needlessly huge state but still manages to fail statistical tests.
It really depends on your use case, but I've written a header only PRNG library that might be interesting to you. I've also held a presentation about it, if you are interested in the specifics: "How computers generate random numbers (A guide for programmers)"
Since you mentioned SIMD, it could be the case that you need to, for whatever reason, generate huge amounts of bulk random data, in that case I recommend checking out the SHISHUA PRNG, which was designed for that…
u/camel-cdrin r/C_Programming • Mentions
On “Bench marking Random Float Functions.”
…d()` is (on most systems) a very bad random number generator.
> but you could always sample /dev/urandom for a higher entropy seed before each time you call the random function, an example provided
Please, at that point, just use `/dev/urandom` directly.
Now, if you are interested in the topic, I can recommend you to take a look at this video: link to this video
and (a bit of self shilling) this video: link to this video
(Sorry for the weird format, I didn't have that much time to spend on writing this)…
u/jacksaccountonredditin r/C_Programming • Mentions
On “Best PRNG\CSPRNG do you recommend for Monte Carlo simulations in c?”
u/camel-cdr- has an interesting talk evaluating a range of PRNGs, as well as an accompanying library.
u/camel-cdrin r/compsci • Mentions
On “How computers generate random numbers (A guide for programmers)”
Since the has been a post about random number generation recently, I though that this sub might also be interested in my talk about how computers generate random numbers.
It's based on what I learned while writhing a random number library.
Some interesting timestamps, if you don't want to watch the entire video:
a high quality PRNG so simple that you can memorize it completely
generating random integers in a range
generating random floating points (It's harder than you'd think)
u/camel-cdrin r/C_Programming • Mentions
On “Bench marking Random Float Functions.”
`rand()` has very low quality, e.g. the output repeats quite early on windows.
It's fast, but there are faster PRNGs that have very high quality and pass all randomness tests. (E.g. https://romu-random.org)
You can also watch the first 20 minutes of this talk I held, which covers PRNG quality and performance.
Edit: Also check out this talk link to this video "Rand considered harmful", which doesn't cover the quality of randomness that much, but shows other problems.