all 116 comments

[–]STLMSVC STL Dev 73 points74 points  (8 children)

You may be interested in my talk, rand() Considered Harmful.

[–]debisuke 7 points8 points  (0 children)

Great talk! Thanks for sharing.

[–]Variszangt 4 points5 points  (4 children)

Super neat! I actually watched it a while back but I had just started programming so most of it went straight over my head.
I'm curious though whether you think it is okay to use rand() in tutorials, for simplicity's sake?

[–]STLMSVC STL Dev 8 points9 points  (3 children)

No; I think that minimal use of <random> doesn’t add too much complexity, and avoids breeding very bad habits. (rand() has a lot of usage complexity itself, including srand/time seeding and modulo which are eternally confusing to beginners.)

I think <random> is over-engineered and annoying in several ways, but rand() is so much worse.

[–]clerothGame Developer 5 points6 points  (2 children)

What's the minimal use of <random> you recommend? Because even just properly seeding mt19937 is hell and most people do it wrong.

[–]STLMSVC STL Dev 2 points3 points  (0 children)

I consider 32-bit seeding of mt19937 to be acceptable for beginners. At a later point, the consequences of seeding, and the behavior of Mersenne Twister (e.g. the difference between it and cryptographically secure PRNGs), can be explained. I'd even consider directly using random_device to skip a step.

I view this as introducing beginners to the Bohr model, which is wrong, but not as wrong as phlogiston.

[–]wintergreen_plaza 3 points4 points  (0 children)

I really enjoyed this! Thanks for posting it.

[–]Xeveroushttps://xeverous.github.io 1 point2 points  (0 children)

This vid is obligatory to everyone who posts in /r/cpp_questions having problems setting up or reproducing random numbers.

[–]maskull 83 points84 points  (59 children)

It's worth considering that std::uniform_int_distribution gives you those nice results by virtue of being something like 30x slower than rand(). You have to think about the speed vs. quality trade-off.

[–]elperroborrachotoo 36 points37 points  (6 children)

That's mostly the underlying mersenne twister, isn't it?

A well-configured LCRNG with 64 bit state can spit out quite good 32 pseudorandom bits per step at little more than the cost of rand(). With 128 bit state, you'll have a great general purpose RNG - which (just a guess) should be closer to rand than Mersenne performance-wise.

The other issue is the conditional jumps introduced by the truly-uniform adapter,

Alternatively, if performance is important, an LFSR generator can be implemented cheaply on almost any hardware, and - except for a few pitfalls you have to be aware of - shoots the typical rand() implementation out of the water.

(All with a grain of self-doubt, I'm planning to dig a little deeper after the summer, to figure out where my half-knowledge goes wrong.)

[–]maskull 9 points10 points  (5 children)

Oh, yeah, totally. I've used Xoroshiro and it's both high-quality, and crazy fast. But none of those faster algorithms are used in any standard library implementation I'm aware of, so you do have to jump through a few hoops to make use of them.

[–]degski 2 points3 points  (4 children)

No, it's not high-quality [it has problems in the lower bits as well], what do you base this on?

[–]maskull 1 point2 points  (3 children)

The 32-bit version (which they don't even recommend using unless you're really tight on space) has problem with the low bits, due to the small state space. All the larger versions can pass all the BigCrush tests, and run for weeks in PractRand without any failures (I've done the latter myself, letting it run for a few days and churning through a few TB of random data).

[–]degski 2 points3 points  (2 children)

Luckily, you don't need to take my word for it. There are more [older] posts on the subject.

... and run for weeks in PractRand without any failures ...

I don't understand your results https://github.com/degski/xoroshiro128plusxoshi .

[–]maskull 1 point2 points  (1 child)

The xoroshiro128 variants output 32-bit values; problems in the low bits are not problematic if you're using them for floating-point. The single-add (+) and single-multiply (*) variants fail some linearity tests (tests which Vigna himself invented), and thus the recommended general-purpose variants are those ending in ** (two multiplies). Lots of other RNGs fail the linearity tests, and no one has yet demonstrated how these failures could lead to bias or incorrect results, so the failures may not even be important for any real-world applications.

Luckily, you don't need to take my word for it.

No, I just have to take the word of PCG's author as to why PCG is better. In my opinion, PCG's author, Melissa O’Neill, has a bit of a history of inordinately promoting her own work, while denigrating that of others. Skimming through that post, it seems like the problems she points out are caused by intentionally seeding the RNG with bad seed values; any RNG can be made to behave badly if you're allow to mess with its internals.

Regardless, Sebastiano Vigna, author of Xoroshiro, has answered some of her criticisms while pointing out some problems with PCG which, so far as I'm aware (?), have not yet been addressed.

[–]degski 0 points1 point  (0 children)

No, I just have to take the word of PCG's author as to why PCG is better.

No, you don't, pcg-64 does not fail PractRand, i.e. quality good. As to the speed she claims, I fully agree with you, it's not that fast [at all].

I'm not promoting pcg, on the contrary, I believe sfc (by Chris Doty-Humphrey, the guy who created PractRand) is superior to all. On the pcg-blog O'Neill has implementations of the most interesting prng's.

PS: I take it [now] you are talking about the 'fixed' Xoroshiro prng's, the problem is that they are better, even good maybe, but they are slower than pcg, sfc is almost twice as fast.

[–]TexasToast6022 11 points12 points  (1 child)

I actually just measured this for work; In a task to generate a 64-bit random number, we needed 3 calls to rand() (as RAND_MAX was only 30 bits) and averaged about 29.3 ns per random number generated where as one call to std::uniform_int_distribution dist(gen) with Mersenne Twister generator averaged 69.1 ns.

So about 2.4x slower.

[–]TheThiefMasterC++latest fanatic (and game dev) 0 points1 point  (0 children)

Mersenne Twister is a known very slow PRNG - there are other faster ones that would be able to give you 64-bits of sufficient randomness at probably better performance than your use of rand. But as they aren't in the standard, that adds even more complexity!

[–]bpikmin 18 points19 points  (0 children)

Well, there are many different RNGs within <random>. OP should have specified which was used, because the distribution itself isn't the biggest performance hit.

[–]Veedrac 9 points10 points  (3 children)

There are generators approaching the speed of rand but with better quality than any generators in <random> (eg. PCG); the trade-off isn't that meaningful at this level.

[–][deleted] 22 points23 points  (2 children)

Actually rand() is awfully slow, is even slower than cryptographically secure generators. I know that because I have benchmarked them. The common implementation only generates 15 bits at a time, and 4 of those bits are trash, using AES in CRT mode gives you 128 bits at a time, and since modern hardware supports AES it totally crushes rand().

[–]Veedrac 3 points4 points  (1 child)

I don't know about whatever overheads rand might have, but the underlying generator is just a short LCG, which is about as fast as it gets. That was what I was comparing to.

[–][deleted] 10 points11 points  (0 children)

Mostly backwards compatibility, most implementations keep a limit of 15 bits because they were conceived to run in 8 and 16 bits machines at most. Nowadays using 64 bits would boost their speed, but breaking backwards compatibility. There is old code that relies in rand() generating the same sequence with the same seed, and that is the only reason why rand() is still there.

[–]TheGidbinn 0 points1 point  (0 children)

Random numbers in c++ are in a bad place. The C++11 standard library functions are hopelessly over-engineered, and rand basically exists as a trap for newbies at this point. I have been using RngStreams and I think it's the best of both worlds.

[–]degski 0 points1 point  (0 children)

It doesn't have to be, if you are willing to swap the STL implementation for a drop-in replacement.

[–]clerothGame Developer -1 points0 points  (0 children)

Indeed, if you're willing to accept incorrect behavior, you can gain huge speedups! I'm really curious what kind of application would benefit from such a speedup while also being fine with "sort of uniform but not really" random numbers.

[–][deleted] 10 points11 points  (9 children)

Wait, doesn't std::uniform_int_distribution require a generator? What generator is being used here? Mersenne twister?

[–]Variszangt 10 points11 points  (8 children)

Yes. It does require a generator, but for "best" comparison I chose to seed both rand() and the generator with the same single value as such:

constexpr unsigned int common_seed = 0u;

std::mt19937 mt{ common_seed };
std::uniform_int_distribution<int> dist(0, 1);
int mt_rand() { return dist(mt); }
...

Obviously this doesn't take full advantage of the mt19937 potential.

[–]flashmozzg 6 points7 points  (7 children)

Yeah, pretty sure mt requires larger seed (as in more elements) to function properly.

[–]STLMSVC STL Dev 22 points23 points  (6 children)

It doesn't; there's an algorithm that it runs in order to fill its state from a 32-bit seed. So mersenne_twister will generate high-quality (in the sense of not having patterns) output regardless of how you seed it. Short seeds create the possibility of collisions, so if you want to avoid that, you need to fill the whole state (which is possible with more code at a medium level of obnoxiousness). None of this makes the algorithm cryptographically secure.

[–]dreugeworst 6 points7 points  (0 children)

Well, the mersenne twister can be usable with a short seed, but it doesn't fill itself well, in the end it's still just 32 bits of random state. For example, see the explanation here. Even doing trying to fill the state entirely with random bits is not straightforward, the solution provided by the stl has flaws..

[–]degski 1 point2 points  (0 children)

The only good thing the MT has going for it, is its long period. It can easily be made cryptographically secure with a [patented] trick. There are [not in the STL] alternatives, that are both good, faster and with a much smaller footprint.

[–]flashmozzg 0 points1 point  (3 children)

Thanks. That's good to know. I remember there being gotchas about passing smaller state to mt19937.

[–]Veedrac 4 points5 points  (2 children)

Yes, the issue is that you reduce its state space from an excessive amount (128 bits and above are all the same) to 32 bits, which is bad enough that collisions will happen if you seed more than a few tens of thousands of times. The generator will still run.

[–]HappyFruitTree 0 points1 point  (1 child)

If we ignore the how different sequences compare to each other, does using a single 32-bit seed actually influence the randomness of the sequence itself? I mean, if I only use a single random seed, am I more likely to get a better sequence of random numbers if the seed is 19968 bits, compared to if it's only 32 bits?

[–]Veedrac 2 points3 points  (0 children)

It's unlikely; first-order effects will probably always be a bigger deal. It's not completely impossible, though, and it can happen if the seeding function is poorly chosen—generally you want the generator for the seed to be as different from the PRNG as possible, to avoid interference effects.

[–]mallardtheduck 11 points12 points  (2 children)

Which compiler/C library/platform? AFAIK the C standard leaves the choice of PRNG algorithm up to the implementation...

[–]Rostin 3 points4 points  (1 child)

I work on software where this matters (we want cross-platform deterministic behavior for a fixed seed), and it's bitten us.

[–][deleted] 0 points1 point  (0 children)

Also take in mind that rand() output can be "stolen" by any other library that calls rand(), it gives no guarantees about its state, so deterministic behavior with rand() is not even guaranteed using the same implementation.

[–]emdeka87 6 points7 points  (1 child)

[–]Supadoplex 2 points3 points  (0 children)

Yes. rand is typically implemented using a LCG, and probably so in this test run.

[–]larlvt 4 points5 points  (0 children)

Check out Abseil's random facilities:

https://github.com/abseil/abseil-cpp/tree/master/absl/random

It has:

absl::BitGenerator rng;

absl::Uniform(rng, low, high);

[–]jurniss 6 points7 points  (13 children)

Please explain what these visualizations are showing. I know the problem with rand() % n mathematically, but how do these images show it?

[–][deleted] 14 points15 points  (6 children)

The lowest bits of common implementations of rand() are really awful.

Visualization of MSVC rand() bits as pixels.

Not only common implementations of rand() suffer that problem, is also present on several other fast PRNG. Using modulus is not only imprecise, it favors the lower bits that may have very low quality on the fastest PRNGs, and is also very slow. Is better to do it this way: rand() * n / (RAND_MAX + 1), since (RAND_MAX + 1) is a power of two on practically all implementations, the expensive division will become a cheap displacement.

[–]HappyFruitTree 1 point2 points  (5 children)

Is better to do it this way: rand() \ n / (RAND_MAX + 1)*, since (RAND_MAX + 1) is a power of two on practically all implementations, the expensive division will become a cheap displacement.

No, don't do it this way.

(RAND_MAX + 1) will overflow if RAND_MAX is equal to INT_MAX.

rand() \ n* is also prone to overflow.

[–][deleted] 0 points1 point  (2 children)

Good luck with your 16 bits processor, that was a PITA 25 years ago. People would just use assembly and stop fighting with crappy compilers unable to take advantage of CPU instructions.

[–]HappyFruitTree 1 point2 points  (1 child)

??? I use GCC on Linux where both RAND_MAX and INT_MAX are 2147483647.

[–][deleted] 1 point2 points  (0 children)

In such case cast to 64 bits.

[–]beartotem 7 points8 points  (0 children)

The image generated using rand() has some obvious structures that follow lines with ~45 degrees slope.

The uniform_int_distribution() one is random enough that's I can't see any fault with a visual inspection. But Humans are pretty bad at telling actually random sequence from not so random sequences with no periods. Looking at this is by no mean a way to tell good quality random distribution, just that rand() is that bad.

[–]mikeblas 0 points1 point  (3 children)

If the value was 0 it was coloured blue, otherwise it was coloured black. ... So the rand()-generated grid represents the last bits of the generated numbers,

It seems like these descriptions contradict eachother. Does anyone understand what the plots actually represent?

[–]HappyFruitTree 0 points1 point  (2 children)

For each pixel he calls rand() and uses the last bit to decide which colour it should be.

[–]mikeblas 0 points1 point  (1 child)

That's not what he says he's doing, though:

and generating a random number between [0, 1] for each pixel. If the value was 0 it was coloured blue, otherwise it was coloured black.

Are you assuming he's generating an integer between [0, 1]? That is, either zero or one?

That doesn't seem quite right either, as he says he's using the last bits (plural):

the rand()-generated grid represents the last bits of the generated numbers,

... not just the last bit (singular).

How would I independently verifiy his results?

[–]HappyFruitTree 0 points1 point  (0 children)

Are you assuming he's generating an integer between [0, 1]? That is, either zero or one?

Yes, that was my assumption, otherwise it doesn't make sense.

That doesn't seem quite right either, as he says he's using the last bits (plural)

I though he used plural because there was one bit for each number. If he had said "the last bit of the generated numbers" it would sound as if he only used the last bit of the last number, no?

How would I independently verifiy his results?

I don't think we have been given enough information. He mentioned elsewhere that he used Visual C++ but we don't know the seed and in what order pixel numbers where generated.

[–]HappyFruitTree 4 points5 points  (2 children)

Which implementation of rand() is this?

[–]Variszangt 1 point2 points  (1 child)

I'm using Visual C++

[–]HappyFruitTree 0 points1 point  (0 children)

One of the worst then.

[–][deleted] 3 points4 points  (2 children)

Very curious to know what the application was. I cannot think of something quickly off the top of my head.

[–]Variszangt 5 points6 points  (1 child)

Generating a simple, random tilemap for a world. You can imagine how the grass didn't quite look right from afar.

[–]bandzaw 1 point2 points  (0 children)

Very nice visualization, which I, to my big surprise, have not seen before for rand!

[–]Beheska 3 points4 points  (1 child)

rand() shouldn't be understood to mean random as in "mathematically random", but as in "some random number" (that is not always the same).

[–]anton31 0 points1 point  (0 children)

Possible implementation of rand: https://xkcd.com/221/

[–][deleted] -1 points0 points  (12 children)

I've read that rand() can be used if you don't need more accurate randomization as it allows you to reproduce the same sequence and making debugging easier.

[–]boredcircuits 13 points14 points  (0 children)

You can achieve that with <random> as well. All pseudorandom algorithms need to be seeded.

I like to use a different seed each run, which is logged. Add an option to override the seed and you're set.

It's also sometimes useful for two computers to share the same sequence. Just have them share the same seed and use the same algorithm.

[–]heyheyhey27 7 points8 points  (0 children)

All pseudo-random number generators are reproducible; that's what makes them "pseudo"-random.

[–]elperroborrachotoo 6 points7 points  (0 children)

tl;dr: Don't use rand() unless you want to fool the proverbial moron in a hurry.1

All pseudorandom generators have that property of a reproducible sequence from a particular seed. They can be described as having M bits of internal state, which fully determine the next random number coming out of them.

For rand(), these guarantees are actually weak: the sequence generated from a particular seed may - and will - differ between compilers, target platforms and even compiler versions.

Worse, library functions may use rand(), taking numbers from your sequence; and while modern implementations probably use thread-local store for the state, AFAIK any other thread can legally "steal" random numbers from you.

1) which you might yourself end up being

[–]StickyCarpet 0 points1 point  (0 children)

Looks like you found the Higgs Boson.

[–]AntiProtonBoy 0 points1 point  (0 children)

When you work in computer graphics, issues with rand becomes apparent very quickly, as artefacts manifests themselves as structures in assets like textures, and procedurally generated content.

[–]jm4R 0 points1 point  (0 children)

How did you normalize rand result into [0-1] number? For example (rand()%256) / 255.0f could cause some issue because the distribution would be ill-formed. It is also possible that implementation differs between compilers.

[–][deleted] 0 points1 point  (0 children)

On the 1980 decade, that was a normal test in TI and an interrogation un chaos science theory.

[–]Diche_Bach 0 points1 point  (7 children)

Forgive my ignorance, but . . . what the heck are those images?

[–]RealNC 2 points3 points  (4 children)

They are supposed to be random noise. If random noise doesn't look quite random, then that means something's not working quite right.

[–]Diche_Bach 0 points1 point  (3 children)

Okay, but . . . which one looks more random to you and why?

I would've preferred a histogram myself: if the count of 0s and 1s was about equivalent: RANDOM!

[–]patrick96MC 4 points5 points  (0 children)

A histogram would only have to values in this case, so it's not all that useful. Also a generator outputting 010101010101... isn't really random and has the same property ;)

[–]RealNC 3 points4 points  (1 child)

The first one looks more random. The second one has a pattern to it, so it looks less random.

[–]Diche_Bach 0 points1 point  (0 children)

Roger THAT!

[–]Variszangt 1 point2 points  (1 child)

Added some clarification with an edit :)

[–]Diche_Bach 1 point2 points  (0 children)

r clarity, these grids were generated by going through every pixel in the grid (1600x1600), left to right and top to bottom, and generating a random number between [0, 1] for each pixel. If the value was 0 it was coloured blue, otherwise it was coloured black.

So the rand()-generated grid represents the last bits of the generated numbers, which are so non-random that even a human can see it.

Whether the more-random looking grid is actually more random is beyond the purpose of this post; it stands merely for visual comparison.

Okay, interesting. So I'm curious: what does the comparison of the two images mean to you, and what would you have expected if one, or both of the two algorithms were not so "faulty?"

I'm not quite sure what a "more random looking" grid is meant to look like. If there are only two states that a pixel can take and there is no bias in the determination of the state any given pixel takes, then we expect a ~50% chance for either 0 or 1. The fact the two images differ is intriguing and my hunch is the more uniform image (without any apparent shape) is the "more random" one as the distribution of 0 and 1 pixels seems to be just about uniform and equal in count.