tiny, fast PRNG

Go To Last Post
9 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
uint8_t rnd(void) {
static uint8_t s=0xaa,a=0;

        s^=s<<3;
        s^=s>>5;
        s^=a++>>2;
        return s;
}

Tiny and fast 8 bit pseudo random number generator. Period is generally 55552 bytes. You can seed by changing s and/or a, but about 16% of the seeds give much shorter periods and reduced randomness.

Randomness analysis with ent:

bernhard@b:/data/home/bernhard/src/prng$ ./xorshift 0xaa 0 3 5|head -c 1000000|ent
Entropy = 7.999790 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 290.74, and randomly
would exceed this value 10.00 percent of the times.

Arithmetic mean value of data bytes is 127.4850 (127.5 = random).
Monte Carlo value for Pi is 3.145164581 (error 0.11 percent).
Serial correlation coefficient is -0.001617 (totally uncorrelated = 0.0).

Last Edited: Sat. Nov 3, 2012 - 06:36 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Cool.

And if you tuned into this Thread you might also like to look at this month's Circuit Cellar, (Nov 2012), where Patrick Schaumont has a nice article on Pseudo Random Number Generators and True Random Number Generators, (PRNGs and TRNGs).

He then did a project using an Altera Cyclone IV FPGA.

Since I don't work with FPGAs I tend to like software approaches, like Darsie's, above.

JC

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This compiles on an express edition vc

Attachment(s): 

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Interesting.

Just coded the world's worst by putting a hundred digits on pi into program memory and reading them out one at a time. It's bad, but it served that specific purpose.

Um, I don't really know C very well, what does s^ mean?

 

"We trained hard... but it seemed that every time we were beginning to form up into a team, we would be reorganized. I was to learn later in life that we tend to meet any new situation by reorganizing. And a wonderful method it can be of creating the illusion of progress while producing confusion, inefficiency and demoralization." Petronius Arbiter, approx. 2000 years ago.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

xor

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Torby wrote:
Um, I don't really know C very well, what does s^ mean?

s=s+1; is the same as s+=1;
so s^=s<<3; means s=s^(s<<3);

And ^ is xor, as bob said.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I see. Probably would have seen that if I'd looked at my C reference card.

Wow, learned 2 useful things from this thread.

 

"We trained hard... but it seemed that every time we were beginning to form up into a team, we would be reorganized. I was to learn later in life that we tend to meet any new situation by reorganizing. And a wonderful method it can be of creating the illusion of progress while producing confusion, inefficiency and demoralization." Petronius Arbiter, approx. 2000 years ago.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

When you seed with with
s= one of 15 18 63 101 129 156 172 208 and
a=96..138
you'll get a period of 55552. These are contiguous ranges of 43 seeds with good period. So you could seed with something like a=96+x%43.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I had a look at this rng, and as the old saying goes "Random number generators, good ones are hard to find", is still true (well it isn't, there's a lot of good ones).

So what properties do we (I) want from a random number generator? Some basic properties are at least:

* a uniform distribution

We normally want this, that is, for a 8 bit generator, all numbers from 0 to 255 have the same probability to be drawn. This rng looks pretty good in this aspect. I draw up to 50000 numbers, and the distribution looks pretty uniform. (There is no point in analyzing more than one period of a periodic rng).

* a long period (if periodic)

This isn't really fulfilled for this rng. It's claimed to be like 55000 which isn't very long (depending of what you're going to use it for). But it's very good for a 8 bit generator. For a 8 bit LFSR generator the maximum period is 256, so this is good. It's actually 256 8 bit LFSR generators (one for every value of a).

* Some kind of independence

This one is a little harder. What is independence? How do we measure it? If we draw a sequence of random numbers, we want them to look as if they were drawn from a sequence of independent random variables. One way to measure this is by correlation. If two random variables are independent, then the correlation between them is zero. So for a given sequence of random numbers we expect the correlation coefficient, for example between adjacent numbers to be close too zero. And it is with this rng (actually almost too close to zero).

But. Independent random variables infer zero covariance, but it's not necessarily the other way around. Dependent random variables can have correlation zero (by some kind of symmetry). So correlation is actually a very weak measurement of independence (and it is independence we want).

We need to look in at least two dimensions to investigate independence. If we, for example, look at one number as a function of the previous or next, we expect a two dimensional uniform distribution, that is, every 256x256 point in a grid from 0 to 255 in each direction have the same probability to show up. So let's take the 50000 numbers and plot them in that way. Se attachment. That is not the outcomes from a uniform two dimensional distribution (based of two independent, one dimensional uniform distributions). We see that a large number of points (most of them) can't appear at all. And, for example, if we get a random number 5, then the next one is (have to be) between 0 and 63. That's not independence. So this is an example of dependent random variables with zero correlation (as my avatar is too). But it's probably ok to flash a LED in a random(ish) fashion.

Attachment(s):