Random numers generator (srand(), rand()) VERY BAD distribution

[madredcake]

Hi everyone.
I am writing a program that needs random numbers, but when I was using srand(); rand() from standard stdlib.h library I got weird results.
I've written a tiny code to find error, but still don't see any.

That's the code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int maxx = 40000000                ;
const int size =       21                ;

int main(){
  int x                                  ;
  int counter[ size ] = {0}              ;

  srand ( time(0) )                      ;

  for(x=0; x<maxx; x++)
    counter[ rand() & (size) ]++         ;

  for(x=0; x<size; x++)
    printf("%2d - %8d\n", x, counter[x]) ;
  
  return(0)                              ;
}

And here are the sample results

 0 - 10000194
 1 -        0
 2 -        0
 3 -        0
 4 -  9999954
 7 -        0
 8 -        0
 9 -        0
10 -        0
11 -        0
12 -        0
13 -        0
14 -        0
15 -        0
16 -  9999937
17 -        0
18 -        0
19 -        0
20 -  9999915

What is wrong and, more importantly, how to repair that?

[hanst99]

counter[ rand() % (size) ]++

& is the binary AND operator in this case, you need modulo.

[Duthomhas]

The standard RNG is crap, everyone knows it. The way you are using it kind of multiplies the error though...

If you need something better, then you might want to google around a nice Mersenne Twister. Like this one:
http://www.bedaux.net/mtrand/

Good luck!

[filipe]

Using bitwise and as a faster modulo operation is a trick that only works with powers of 2. If instead of rand() you had a guaranteed power of 2 there, it would work.

[hanst99]

The standard RNG may be not very good (I wouldn't say crap), but it's ok for small scale applications, and when uneven RN distribution isn't really a problem for you.

[madredcake]

hanst99 thanks
It's obvious, but I really saw % there.
I have to change font.

[hanst99]

Using bitwise and as a faster modulo operation is a trick that only works with powers of 2. If instead of rand() you had a guaranteed power of 2 there, it would work.

Huh?
16&5 = 0
16%5 = 1
16&16 = 16
16%16=0

[filipe]

I didn't think it needed to be mentioned because the OP was already doing it. You need to decrement the rhs by one.

EDIT: since then, the OP has unfortunately changed the original post. Line 15 was:

counter[ rand() & (size - 1) ]++;

[hanst99]

Doesn't change anything if you do that.
16&4 - still 0
16&15 now 0, but that's thanks to the trivial fact that 16 & (16-(anything greater/equal 0 and lesser/equal 16)) = 0.

I still don't understand what you're getting at.

[filipe]

Oops. Forget what I said. What I meant to say was the original rhs must be a power of two:

16 % 4 == 16 & 3;

[lordmat]

How about a function such as

inline int random(int count){
	return 1 + static_cast<int>(count*static_cast<double>(rand())/(RAND_MAX+1.0));
}

Tends to generate better random numbers than %


Line 14 shouldn't be x<maxx instead it should be x<size

[Disch]

Tends to generate better random numbers than %

How do you figure?

[hanst99]

lord, yours isn't really any different from the normal one. You gotta switch out the rng, not the method by which you extract a number from it.