FW: bad rand generator: distribution/prevalences/periodicity

[HaWe]

m-goldberg,
since 1951 there has been some minor progress in algebra, informatics and computer sciences. If you want to learn about it, refer to already published references.
spillerec,
I published my test code. If you doubt my results, do the tests you wish by your own and publish them.
If you're still in doubt of the results, the best choice of all would be if you'll manage to run a spectral test on the 3 RNGs.
But to me the previous tests are sufficient, I don't have to convince myself or anyone.

[afanofosc]

Well, in spite of the fact that I think the existing standard firmware Random system call function produces random numbers that are "good enough" for just about anything that seems to be the kind of program you might run on an NXT I was persuaded by articles on the web (and Doc's persistent complaining) that it was worth adding an additional random number generator system call function to the enhanced NBC/NXC firmware.

So if you target the enhanced firmware and have a very recent version of 1.31 (yeah, I know) of the enhanced NBC/NXC firmware (not yet publicly available) then you can now call srand(seed) and rand() with a new random number generator. I am using Park-Miller aka Lehmer LCG (http://en.wikipedia.org/wiki/Lehmer_RNG) with n = 2^31-1 and g = 48271.

RAND_MAX, with this new version, is 2147483646.

John Hansen

[HaWe]

WOW!

praise, praise, praise!
(I know, mun2 is better in these things, but anyway!)

[spillerrec]

spillerec,
I published my test code. If you doubt my results, do the tests you wish by your own and publish them.
If you're still in doubt of the results, the best choice of all would be if you'll manage to run a spectral test on the 3 RNGs.
But to me the previous tests are sufficient, I don't have to convince myself or anyone.

Again, I do not question your tests. I just predict that the Lego rand() function will return its very first 20 numbers again in sequence using the range your are testing in. (In this case it is just important you use the very first 20 numbers, i.e. rand() must not have been called before from when the NXT was turned on.) Why is left as an exercise to the reader.

I'm still very curious to why you need something which is better than the standard Lego rand() function. Do you just want to be able to use modulus with rand()?

To John,
You say you added an "additional random number generator" which mean there are now two? So Random(x) calls the old and rand() calls the new?

[m-goldberg]

m-goldberg,since 1951 there has been some minor progress in algebra, informatics and computer sciences. If you want to learn about it, refer to already published references.

I am somewhat familiar with the work done on pseudo-random number generators in the last half of the 20th century. I spent a large part of my 47-year career in software development working on large-scale discrete event simulations. Pseudo-random number generators are critical to such work and some knowledge of them is necessary for those who work in the field.

What von Neumann said is as relevant today as it was in 1951. He was making both a joke and a serious point: all pseudo-random number generators are flawed in some way. That was already known in von Neuman's time and no work the in field since then has invalidated it. Those people whose work critically depends on really long sequences of pseudo-random numbers must be very careful in their choice of generators. This was the position taken in the 1950s and I know of nothing in the literature that permits any relaxation of this.

I posted the quotation because I thought those who following this thread would enjoy von Neumann's joke.

On the other hand, I fully agree with John Hansen. For all normal uses of the NXT (hobby, education, and play) I think the Random API call -- even before John modified it -- is quite good enough.

[HaWe]

my respect!

On the other hand, I fully agree with John Hansen. For all normal uses of the NXT (hobby, education, and play) I think the Random API call -- even before John modified it -- is quite good enough.

haha, never! (except you want to mimicri loaded cubes): <<<=== (no joke!)
not for normal, not nearly for Monte Carlo Filters. Did you ever read my evaluations?

Instead, please don't put on any empty assertions, but prove it by own test results.

I think this thread may be closed.

My (probably) last sentence to this issue:
"But everyone to his own beliefe..."

[spillerrec]

Wait! You need to prove the newly implemented RNG is better than the old!

(btw, I'm pretty sure all of us are using your tests results for our argumentation. ; ) )

[afanofosc]

I just predict that the Lego rand() function will return its very first 20 numbers again in sequence using the range your are testing in. (In this case it is just important you use the very first 20 numbers, i.e. rand() must not have been called before from when the NXT was turned on.) Why is left as an exercise to the reader.
[/quote

spillerrec is referring to how the standard firmware's Random system call function calls srand with dTimerRead() every 20 times you ask for a random number. So Doc's test doesn't compare apples to apples. It would do so only if he called sKrand or sMrand with new seed every twenty times that you ask for a random number.

You say you added an "additional random number generator" which mean there are now two? So Random(x) calls the old and rand() calls the new?

Rather than change the standard Random system call, I added a new one called RandomEx. The structure looks like this:

Code: Select all

struct RandomExType {
  long Seed;   /*!< The random number or the new seed value. */
  bool ReSeed; /*!< A flag indicating whether or not to seed the random number generator. */
};

The new NXC API functions are implemented like this:

Code: Select all

#define srand(_s) asm { __SeedRandomEx(_s, __RETVAL__) }
#define rand() asm { __RandomEx(__RETVAL__) }

#define SysRandomEx(_args) asm { \
  compchktype _args, RandomExType \
  syscall RandomEx, _args \
}

__RandomEx and __SeedRandomEx look like this (in NXTDefs.h):

Code: Select all

#define __SeedRandomEx(_seedin, _out) \
  acquire __RandomExMutex \
  set __RandomExArgs.ReSeed, TRUE \
  mov __RandomExArgs.Seed, _seedin \
  syscall RandomEx, __RandomExArgs \
  mov _out, __RandomExArgs.Seed \
  release __RandomExMutex

#define __RandomEx(_out) \
  acquire __RandomExMutex \
  set __RandomExArgs.ReSeed, FALSE \
  syscall RandomEx, __RandomExArgs \
  mov _out, __RandomExArgs.Seed \
  release __RandomExMutex

Since srand is a #define macro that emits an asm block it can only take a variable or a simple constant value. It returns the new seed value so if you pass in 0 or -1 you can store the seed being used, if you like. If you target the standard firmware then you can't call srand but you can still call rand() which is defined as I described earlier in this thread (Random()+32768) with RAND_MAX equal to 65535.

For the curious, you can see my firmware changes here:

http://mindboards.svn.sourceforge.net/v ... ortby=date

And you can view the changes to NBCCommon.h, NXTDefs.h, and NXCDefs.h in the BricxCC SVN repository.

John Hansen

[afanofosc]

Please try the new test release which now has support for the new RandomEx enhanced NBC/NXC firmware random number system call. This new system call is used when you target the enhanced firmware and you call the srand and rand functions.

http://bricxcc.sourceforge.net/test_releases/

Also in this release are a new JoystickMessageType structure and JoystickMessageRead API function that work with recently made enhancements to the BricxCC Joystick tool which allow you to change the tool from its default mode of directly controlling the motors to sending a message whenever motor direction and speed or joystick button states are changed. You can set the new Joystick tool options by double clicking on the tool window to bring up an options dialog.

Code: Select all

/*
struct JoystickMessageType {
  byte JoystickDir;
  byte LeftMotor;
  byte RightMotor;
  byte BothMotors;
  char LeftSpeed;
  char RightSpeed;
  unsigned long Buttons;
};
*/
task main()
{
  JoystickMessageType jmt;
  while (true)
  {
    char result = JoystickMessageRead(MAILBOX1, jmt);
    if (result == NO_ERR)
    {
      NumOut(0, LCD_LINE1, jmt.JoystickDir);
      NumOut(0, LCD_LINE2, jmt.LeftMotor);
      NumOut(0, LCD_LINE3, jmt.RightMotor);
      NumOut(0, LCD_LINE4, jmt.BothMotors);
      ClearLine(LCD_LINE5);
      NumOut(0, LCD_LINE5, jmt.LeftSpeed);
      ClearLine(LCD_LINE6);
      NumOut(0, LCD_LINE6, jmt.RightSpeed);
      ClearLine(LCD_LINE7);
      NumOut(0, LCD_LINE7, jmt.Buttons);
    }
    else
      NumOut(0, LCD_LINE8, result);
    Wait(MS_100);
  }
}

I have not updated the history.txt or bricxcc release notes or the help file yet. I will work on those this coming week.

John Hansen

[HaWe]

John, thx for your efforts, I'll try it asap.
some question remaining:
1) what exactly do
srandEx(0)
srandEx(1) (in that case ANSI C srand(1) re-seeds to the random start default)
srandEx(-1)

2) which values are specifically, explicitely forbidden to srandEx because of severe interferences with the LCG

the initial seed X0 must be coprime to the modulus n that is not required for LCGs in general. The choice of the modulus n and the multiplier g is also more restrictive for the Lehmer RNG. In contrast to LCG, the maximum period of the Lehmer RNG equals n−1 and it is such when n is prime and g is a primitive root modulo n. On the other hand, the discrete logarithms (to base g or any primitive root modulo n) of Xk in \mathbb{Z}_n represent linear congruential sequence modulo Euler totient φ(n).

3) what kind of algorithms do you recommend for randomizing within subsets {0...n} ⊂ {0...RAND_MAX} (except modulus)?

4) what will predictibly happen if you pass values > RAND_MAX to srandEx? (such as CurrentTick()*BatteryLevel(), e.g. 14,000,000*7900=1.1*1011?)
(This is to mimicri the ANSI C randomized seed srand(time(0)) )
Are there any restrictions?