FW: bad rand generator: distribution/prevalences/periodicity

[HaWe]

pls don't ever bug me with Java...^^

[HaWe]

I meanwhile found the original code in the original reference:
http://computer.howstuffworks.com/c14.htm

[spillerrec]

So, as I have passed the exam, I checked how rand(), Random() and Random(x) is implemented.
First of all, according to the specification (version 2.0) the number generator returns an signed 16-bit number. It reseeds for every 20 calls to this function.

For Random(16) the compiled NBC code is:

Code: Select all

set __D0main, 16
syscall 24, __RandomArgs
mov __RandomTmp, __RandomArgs.Result
add __RandomTmp, __RandomArgs.Result, __constVal32768
mul __RandomTmp, __RandomTmp, __D0main
div __RandomTmp, __RandomTmp, __constVal65536
mov __D0main, __RandomTmp

It stores the range, then it calls the internal random function and moves the result into __RandomTmp which is a unsigned long. (Notice that this actually doesn't matter, as it is overwritten just after that...)
It adds 2^15 which insures that it becomes a positive value.
Now the range is multiplied into the result. Then it is divided with 2^16 which truncates all the lower unnecessary bits.

In short, it uses the most significant bits instead of the less significant bits which modulus would do.

Random() is simply:

Code: Select all

syscall 24, __RandomArgs
mov __D0main, __RandomArgs.Result

This is why it is signed when a range is not specified.

rand() is:

Code: Select all

mov __D0main, __constVal32768
syscall 24, __RandomArgs
mov __RandomTmp, __RandomArgs.Result
add __RandomTmp, __RandomArgs.Result, __constVal32768
mul __RandomTmp, __RandomTmp, __D0main
div __RandomTmp, __RandomTmp, __constVal65536
mov __D0main, __RandomTmp

Which is exactly the same as Random( RAND_MAX ).

IIRC casting should work fine in NBC so I don't know why it doesn't make use of that instead.

[HaWe]

So, as I have passed the exam

Congratulations!

About the rand function processing I'm not sure if we should use this any more, the equal distribution of the basic series is simply too bad.
I think I will always use my custom function in future (provided the results of further statistical tests will still be ok)

[spillerrec]

I don't see why this isn't good enough for NXT purposes:

Run with Random(16)

Random16.jpg (23.5 KiB) Viewed 7702 times

What do you need to do which require it to be better than this?

[HaWe]

what exactly have you done?
edit:
ok, I suppose you used Random(16) instead of rand()%16

well, the distribution is ok, but
1) Random is no C cmd and I don't like non-C-cmds
2) the underlying rand() function is still not equally distributed (if it was, rand()%16 would be also equally distributed)
3) so the random series produced bei Random() is faked or manipulated in some way
4) It's still not possible to plant a random seed using NXC rand() or Random() with srand(x)
5) my own function rand_() works like ANSI C rand() and I can plant a random seed using srand(x) :)

[muntoo]

1) Random is no C cmd and I don't like non-C-cmds

The C version of rand() isn't perfect, either... if your function really is the real implementation of C-rand().

2) the underlying rand() function is still not equally distributed (if it was, rand()%16 would be also equally distributed)

And don't forget the patterns...

Here's the firmware code:

Code: Select all

//
//cCmdWrapRandomNumber
//ArgV[0]: (return) Random number, SWORD
//
NXT_STATUS cCmdWrapRandomNumber(UBYTE * ArgV[])
{
  static UBYTE count = 0;
  SWORD random;

  if (count == 0)
    srand(dTimerRead());

  if (count > 20)
    count = 0;
  else
    count++;

  //!!! IAR's implementation of the rand() library function returns signed values, and we want it that way.
  //Some stdlib implementations may return only positive numbers, so be wary if this code is ported.
  random = rand();

  *((SWORD *)ArgV[0]) = random;

  return NO_ERR;
}

As you can see, we keep reseeding every 20 calls. I don't like this. *suspicious* This indicates the presence of some sort of pattern, assuming rand() is like the function @doc-helmut posted earlier.

Maybe John could make the reseeding happen over a larger period of time/calls. I suggest a minimum of 256 calls.

[mightor]

Maybe make the seeding interval random too?

- Xander

[muntoo]

Maybe make the seeding interval random too?

I thought of that, but only if it's something like 1/1024 probability of reseed.

Once again, I don't like the rand() implementation... but I guess it's OK speedwise.

[HaWe]

1) First, I don't claim that the code I took is "the" rand implementaion of C rand, it's just one that I found somewhere. There might be trillions of different random generators written by or for C - the main thing is: the pseudo random series they are producing are (stochstically) "good enough" so that they can be taken as a substitute to "real random numbers". I assume so far that the code I'm using is actually good enough - anyway, it seems to be a good deal better than Lego/NXC-rand().

2) from view of stochastics, there is not such a thing like "important" or "unimportant" bits. Each random number is as valid as any other, independ from it's size.
so e.g. the following series or randomly drawn numbers (1...1000000)are completely coequal and no bit of any number is more important than any other :
1, 89562, 2, 9
11, 895256, 778, 73562


3) next point:
there is no need of re-seeding ever.

if we once have 2 different seeds which lead to 2 different stochastical independend series of random numbers - what else do we want?
e.g. we may show (by sufficiently large samples) that 2 systematically or randomly taken seeds of consecutive numbers ((1,2), (56,57), (19,20), (82,83)) in every single case of those doublets lead to different random series (different sequence and not shifted against each other).
It that once has been shown, then e.g. 2 numbers taken from a rising system-time-counter (like time(0)) will also lead to stachastically different random series.
Also a seed like SystemTime since switched-on (CurrentTick() ) multiplied by a (provided) non-reproducable variable (like Batterylevel) will do the same.

If we have the reasonable presumption that a random generator is able to do this, there will be no need of re-seeding. If we want 2 independend random series we will only have to seed it by 2 different seeds.

On the other hand, if the same seed will lead to identical series we may reproduce each pseudo-random series as often as we want. Repeatedly re-seeding will make this probably impossible.