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
 {
  private:
  
   T count, seed;

  public:

  T operator()()
    {
     seed^=count++;
     seed=ror(seed,1);
     seed+=count;
     return seed;
    }

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

  ~cheap_prng()=default;
 };

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

ret

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: