11

For the purposes of a programming class I'm trying to illustrate the weaknesses of the random number generators that usually come with the standard C library, specifically the "bad random generator" rand() that comes with OSX (quoth the manpage).

I wrote a simple program to test my understanding of the spectral test:

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

int main() {
  int i;
  int prev = rand();
  int new;

  for (i=0; i<100000; i++) {
    new = rand();
    printf("%d %d\n", prev, new);
    prev = new;
  }
  return 0;
}

But when I plot the resulting scatterplot, here is what I get:

Spectral test of OSX's rand()

I would have expected something showing more structure, like what one finds on Wikipedia. Am I doing something wrong here? Should I plot in more dimensions?

UPDATE

Following pjs's suggestion I zoomed in on the part of the plot where the numbers are smaller than 1e7, and here is what I found:

Spectral test of OSX's rand() limited to numbers smaller than 1e7

I find exactly the same lines showed by pjs. They seem to be vertical, but this is impossible as it would imply that some values were "missed" by rand(). When I sort -n the data this is (a sample of) what I see:

571 9596797
572 9613604
575 9664025
578 9714446
580 9748060
581 9764867
584 9815288
586 9848902
587 9865709
590 9916130
592 9949744
127774 13971
127775 30778
127780 114813
127781 131620
127782 148427
127783 165234
127785 198848
127787 232462
127788 249269

In other words, the points lie in lines that are almost, but not quite, vertical.

7
  • If each input is random, then I would expect to see noise like what you received. If you want structured output, like displayed in the linked page, random data is probably not what you want.
    – SevenBits
    Apr 29, 2013 at 20:03
  • Yes, but the point is that this is an attempt to demonstrate that the random data isn't quite random. The image displayed in the link page purports to be a plot of a hundred thousand random numbers. (I'm curious, though. Does "Each point represents 3 consecutive pseudorandom values" mean that each three numbers are used as the x,y,z coordinates of a point? Apr 29, 2013 at 20:07
  • I think you should try 3D. Apr 29, 2013 at 20:07
  • 1
    To get such structure you need to variate width of your image. Also don't generate coordinates: use rand() like intensity of point!
    – Eddy_Em
    Apr 29, 2013 at 20:08
  • 2
    Surely the graph would show structure only if the range of rand() were a problem? What you're trying to show is that knowing the last n results gives you grounds to make some prediction about the next. On the wikipedia page I think the point being made is that any two outputs from that particular generator allows you to make a pretty good guess about the third. So in this case I think what your graph shows is that knowing one doesn't give you enough information to make a good guess at the next. So as Daniel says, probably you need to try plotting in higher dimensions.
    – Tommy
    Apr 29, 2013 at 20:13

2 Answers 2

12

Linear congruential generators all suffer from a problem identified by George Marsaglia. "Marsaglia's Theorem" says that k-tuples (vectors of length k) will fall on a bounded number of hyperplanes. The bound is m**(1/k), where k is the size of the tuple and m is the number used for the modulus of the generator. Thus, if the modulus is (2**31 - 1) and you're looking at sets of 3, a 3-d plot will show the points falling on no more than the cube root of (2**31 - 1), or about 1290 planes, when viewed from the right orientation.

All LCG's are subject to Marsaglia's Theorem. A "good" one performs at or close to the upper bound, a bad one falls well short of the upper bound. That's what the spectral test is effectively measuring, and that's what you were seeing in your Wikipedia link - RANDU, the LCG from hell, produces triplets that fall in a mere 15 planes.

Apple's carbon library generator uses 16807 as its multiplier and (2**31 - 1) as its modulus. As LCG's go, it's not really all that bad. Hence your plot didn't show the same extremes RANDU has. However, if you want decent quality random numbers don't use an LCG.

Addendum

I've gone ahead and cranked a billion numbers from the Apple rand() function, but only printed the ones where both values of the pair were less than 2 million, i.e., the bottom left corner of your plot. Sure enough, they fall on lines. You just need to really zoom in to see it because of the density of lines.

Old George was a clever fella!

Marsaglia at work

2
  • Thanks! I had a hard time understanding how the lines could be vertical, but then I sort -n'ed the data and found that the lines are in fact not perfectly vertical but slightly tilted.
    – lindelof
    Apr 30, 2013 at 19:32
  • You're welcome! Good call using sort -n. Yeah, the lines look vertical until you realize that the spacing between "adjacent" lines is over 100K, so horizontal shifting by 100's or even 1000's is barely going to be noticeable.
    – pjs
    Apr 30, 2013 at 20:47
3

Assuming the bad rand is a linear congruential generator, i.e. it's of the form:

next = a * prev + b (mod RAND_MAX+1)

you can just take a few terms and solve the equations for a and b. After that, you should be able to generate a function of the output such that the structure becomes readily apparent.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.