In an Old Notebook (Generating Random Sequences VI)

Looking for something else in old notebooks, I found a diagram with no other indication, but clearly a low-cost random generator.

So, why not test it?

A quick implementation of the thing would be something like

template <typename T>
T ror(const T & a, size_t n)
  return (a>>n) | (a<<(std::numeric_limits<T>::digits-n));

template <typename T>
class cheap_prng
   T count, seed;


  T operator()()
     return seed;

  cheap_prng(const T & s)
   : count(0),seed(s)


The supposedly interesting part is that the random-generating function is especially inexpensive. The assembly for the function itself, assuming a 32 bits type, excluding loads and write-backs, boils down to:

;mov eax,<seed>
;mov edx,<count>

xor eax,edx
inc edx
ror eax,1
add eax,edx

;mov <count>,edx
;mov <seed>,eax


How does it fare? Using T=unsigned short and 10000 times 65536 draws, we get:

Which is kind of uniform. It would probably pass the Chi Square test. Even if you draw it, say, modulo 7, it looks good enough. For T=unsigned char, modulo 7 yields:

0	370108
1	368697
2	369940
3	370286
4	360392
5	361169
6	359408

* *

It’s clearly not that strong, however, but to generate (noisy) textures, for example, it seems to be good enough:

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: