Randomness in SGDK... ?

[Xynxyn]

I was looking for random integers generator in SGDK, but for surprise I didn't find it. Here it is:
http://xynxyn.cba.pl/gendev/sgdkpp/
Download the "RND++".

srand(u16 seed) - sets the seed
rand()/RND/RAND/RANDOM - returns random u16

Enjoy! ;D

[neologix]

How random are you looking for? I highly recommend a Mersenne twister implementation if it's small enough for ROM use

[Xynxyn]

I use the linear congruential generator.
Constants are created by me, very similar to that used in Windows. (but Windows random number generator generates integers in range 0-32768, this creates integers in range 0-65535)

[r57shell]

Congruential generator. $0.. $FFFFFFFF range.

Code: Select all

static u32 iran;
iran=1664525L*iran+1013904223L;

Constants from research of D. Knuth and H.W. Lewis.

More info: http://en.wikipedia.org/wiki/Linear_con ... _generator

[Stef]

I was looking for random integers generator in SGDK, but for surprise I didn't find it. Here it is:
http://xynxyn.cba.pl/gendev/sgdkpp/
Download the "RND++".

srand(u16 seed) - sets the seed
rand()/RND/RAND/RANDOM - returns random u16

Enjoy! ;D

Actually you have this in SGDK (declared in maths.h) :

Code: Select all

/**
 *  \brief
 *      Return a random u16 integer.
 */
u16 random();

Pretty simple but do the job, the only thing i need to improve is the seed initialization (should take the HV counter at init)

[TmEE co.(TM)]

I used sequence of XORs and rotations to get a nice pseudo-garbage generator. With H counter in the mix it became pretty good but I never put any serious thought into it.

[Xynxyn]

@r57shell Yes, it's true. But many versions of this algorithm divide result to change range, as I did and Microsoft, and many other companies and operating systems.

I'm using the subtick as seed.

[r57shell]

If you don't want to do division, there is good property of random values from math. You can exclude any range.
Let random() - function that gives random values within some range.

Code: Select all

do { x = random(); }
while( !in_range(x) );

function in_range returns true if x good for you.
For example, I have 12 characters, I want to get random character.

Code: Select all

do { x = random(); }
while ( x >= 12 );

x = character id from 0 to 11.
BUT, if random has a large range, then it may take a lot of iterations.
So, assuming that range is power of 2, we can improve:

Code: Select all

do { x = random()&(16-1);}
while ( x >= 12 );

No division.
Notice: for this case, common method: x = random()%12. Bad method! It will be not uniform.

About properties.

First, if you repeat random generation when value does not satisfy your requirements, then distribution does "not changed" in some terms. In this case, "not changed" means that ratio between two different probabilities, does not changed. For example, you have random value in set {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} with uniform distribution. If you repeat random generation when value is in set {2,7,8,10,12}, then you will achieve uniform distribution in set {0,1,3,4,5,6,9,11,13,14,15}. It's easy to prove.

Second, if range is power of 2, and distribution is uniform, then you can remap range into smaller range just taking any of bits.