Can rand() really be this bad?

Question

lol

Above is an example image generated by using rand() to get random coordinates and add a constant to the pixel value at those coordinates. This is how it looks from a few thousand iterations. I'm using the rand() from stdlib.h in Mac OS X Lion, giving it time(NULL) as the seed.

You can clearly see the vertical lines, as if the ones with an odd x-coordinate have higher values than those with even x-coordinates.

How would I implement a better algorithm, or where can I find one that doesn't have many dependencies? (I would prefer a header-only file).

Here's the code (sorry it took me so long):

void generate(int iterations = 1) {
 for (unsigned int x = 0;x < (area * 4);++x) {
  map[rand() % area] += 1;
 }
 number a = min();
 number b = max();
 for (int i = 0;i < area;++i) {
  map[i] -= a;
  map[i] /= b;
 }
}

Map contains double-floats and is later turned into RGB values.

Are you 100% certain we can't exclude a bug in your use of `rand()`? — Mat, May 21 '12 at 20:49
How are you constraining the rand() value to your valid range? Are you mod'ing (%'ing) it with the range or doing something else? — syplex, May 21 '12 at 20:50
Yes, `rand()` is pretty horrible. In most implementations it's just a simple LCG and unsuitable for anything beyond rolling a die maybe (and even then most programmers do stupid things, e.g. `rand() % 6 + 1`). — Joey, May 21 '12 at 20:52
The behavior looks like some precision is being lost (round off with % perhaps) — Chris, May 21 '12 at 20:54
Lets see the code. For all we know you could using it incorrectly. 1) Do you call srand() more than once. When calling rand() how do you truncate to X/Y coordinates. — Martin York, May 21 '12 at 21:18
Instead of `map[rand() % area] += 1;`, use `map[rand() / (((unsigned) RAND_MAX + 1) / area)] += 1;`. This is an improvement because the higher bits from `rand()` have a better distribution than the lower bits, assuming it's an LGC. — Dietrich Epp, May 21 '12 at 23:22
@DietrichEpp thanks, but there isn't much of a difference. I tried arc4random and it works better but you still see those vertical lines. I'll have a look at the C++11 stuff soon. — slartibartfast, May 21 '12 at 23:27
For posterity, adding a link to this answer that pretty much explains it - http://stackoverflow.com/a/20267526/2016408 — Leeor, Jan 04 '14 at 21:15

score 4 · Answer 1 · edited May 21 '12 at 21:00

4

C++11 provides pretty useful random number functionality in random. See here and here for more details.

edited May 21 '12 at 21:00

genpfault

51,148
11
85
139

answered May 21 '12 at 20:51

juanchopanza

223,364
34
402
480

score 3 · Accepted Answer · answered May 21 '12 at 20:49

3

Have you tried arc4random()? It provides much stronger and more uniform random values than rand().

You could also try SecRandomCopyBytes(), which is part of Security.framework. This basically just reads from /dev/random.

answered May 21 '12 at 20:49

Lily Ballard

182,031
33
381
347

score 3 · Answer 3 · answered May 21 '12 at 20:59

I think it would be most important to see how you use rand() to extract the coordinates. What is really surprising is, that you only see a pattern in the x coordinates, but not in the y ones. If there really was a deficiency in rand() it should appear in both.

That said, I could attempt a guess where these patterns come from: rand() is well known to produce more randomness in the high bits than in the low ones. Hence one should never use modulo to extract a smaller range, because this way one will only get the low bit parts with less randomness.

From this knowledge I would guess that you were extracting the low bits to produce the x values and the high bits to extract the y values. This would give you a much more random pattern along the y axis than along the x axis.

If this is now what you are doing, there still must be some artifact in your code, which causes larger randomness across the y axis than along the x axis. So without seeing your code it is hard to tell if this implementation is flawed.

score 1 · Answer 4 · edited Jun 20 '20 at 09:12

On the mac you can just use random instead of rand. The man page for random notes the following:

BUGS

About 2/3 the speed of rand(3).

The historical implementation used to have a very weak seeding; the random sequence did not vary much with the seed. The current implementation employs a better pseudo-random number generator for the initial state calculation.

Applications requiring cryptographic quality randomness should use arc4random(3).

Can rand() really be this bad?

4 Answers4

Linked