FW: bad rand generator: distribution/prevalences/periodicity

[muntoo]

I would say it was your code if that is what you used to generate a random number between 0 and 3. Seriously? You can't be serious.

This was a long, long time ago in a galaxy far, far away. Also, it was probably a bit more complicated than that, but the underlying problem might have been the same. (In my Maze Generation program, somewhere.)

[schodet]

Also note that ((RAND_MAX-1)/16+1) is optimized at compile-time to be 2048 since there are no spaces in the expression and all the values are constants.

You mean that spaces have a meaning in NXC?

[muntoo]

You mean that spaces have a meaning in NXC?

The NBC "optimizer" doesn't work with spaces.

[afanofosc]

Well, actually, it is optimized at compile time to 2048 even if there are spaces in the expression. I was thinking of the constant expression evaluator in NBC which only accepts expressions if they contain no whitespace.

At the NXC level as an expression is evaluated it is passed through a routine called OptimizeExpression. By this point the expression string no longer contains whitespace. It is passed into the same expression evaluator object that is used at the NBC level and if it can evaluate the expression then all of the lines of code that were generated for that expression are replaced with a single line of code that loads the constant value into the main register variable. Sorry for forgetting how that worked earlier.

John Hansen

[HaWe]

at which NXC (Bricxcc preferences/compiler) optimization level will that "white space thing" work or not?

[afanofosc]

The constant expression optimization that happens in NXC will occur with or without whitespace in the expression at optimization level 1+, iirc. It definitely is applied at level 2, which is the level I always use.

FYI, I have changed rand() to be defined like this:

Code: Select all

#define rand() (Random()+32768)

and RAND_MAX is now correctly defined like this:

Code: Select all

#define RAND_MAX 65535

I briefly flirted with changing rand to be something like the function Doc used in his code above along with a simplified form of srand but in the end I decided against that approach. With rand defined as above I get a million iterations through Doc's for loop (after removing the in-loop screen drawing) in 231089 milliseconds. This is from a modified form of his code:

Code: Select all

    // 231089
    j=rand()/(RAND_MAX / 16 + 1);
/*
	syscall 24, __RandomArgs
	add __signed_stack_001main, __RandomArgs.Result, __constVal32768
	div __main_7qG2_j_7qG2_000, __signed_stack_001main, __constVal4096
*/

With Random(16) I get this:

Code: Select all

    // 279698
    j=Random(16);
/*
	set __D0main, 16
	syscall 24, __RandomArgs
	add __RandomTmp, __RandomArgs.Result, __constVal32768
	mul __RandomTmp, __RandomTmp, __D0main
	div __RandomTmp, __RandomTmp, __constVal65536
	mov __main_7qG2_j_7qG2_000, __RandomTmp
*/

And with the rand_ function I get this:

Code: Select all

    // 285057
//    j=rand_()%16;       // customized randomization function
/*
	subcall rand_, __rand__return
// the body of rand_
	mul __signed_stack_001rand_, _RAND_SEED_, __constVal1103515245
	add _RAND_SEED_, __signed_stack_001rand_, __constVal12345
	mod __DU0rand_, _RAND_SEED_, __constVal32768
	subret __rand__return
// end of the body of rand_
	mod __main_7qG2_j_7qG2_000, __DU0rand_, __constVal16
*/

I also removed the extra mov from the underlying __Random macro in NXTDefs.h that spiller pointed out. As defined now, rand() still does not produce results that work with the poor %N algorithm originally used by Doc (and working fine with Doc's rand_ function). It does, however, produce great (and the fastest possible) results when you use the algorithm shown above, i.e., /(RAND_MAX / N + 1).

John Hansen

[HaWe]

John,
glad to see that the discussion was worth while
only having srand is left which I had appreciated very much
(srand(1) as the default, srand(x) for user defined reproducible series, something like srand(time(0)) as a randomized series)

[HaWe]

ps:
speed is not the point,
having a good RNG is the point (equally distributed, very long period length, no hyperplane behavior (no serial correlation between successive values / no affine ciphers),...
Re: Mersenne Twister https://sourceforge.net/apps/phpbb/mind ... 8513#p8513
how is the Lego rand() about that? What type of RNG is it?

[muntoo]

having a good RNG is the point (equally distributed, very long period length, no hyperplane behavior (no serial correlation between successive values / no affine ciphers),....

Of course, MT has some problems with taking a few MT_init() iterations to get off the ~0 values.

Marsaglia provided several examples of random number generators that are less complex yet which provide significantly larger periods. For example, a simple complementary multiply-with-carry generator can have a period 1033000 times as long, be significantly faster, and maintain better or equal randomness.[7][8]

Another issue is that Mersenne Twister is sensitive to poor initialization and can take a long time to recover from a zero-excess initial state. An alternative, WELL ("Well Equidistributed Long-period Linear"), has quicker recovery, same or better performance and equal randomness.[9]

[LINK]

Some WELL code, if you're feeling up to it.

[HaWe]

did you try MY MT implementation?
It has actually no zero-states at all...! (because of very smart initialization routines... ;) )

Marsaglia provided several examples of random number generators that are less complex yet which provide significantly larger periods. For example, a simple complementary multiply-with-carry generator can have a period 1033000 times as long, be significantly faster, and maintain better or equal randomness.[7][8]

write such a thing and show us if you wish (notice that NXC has got no double !