gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Random Number Warning

#25278 - sgeos - Thu Aug 19, 2004 10:58 pm

In short, always seed your random number generators with odd numbers. Details below.

I was mucking about with a 16 bit linear congruential generator (LCG) and discovered something very interesting about seeding the generator and it's period.

This is the generator I used:

Code:
#define RNG_M 0x0DCD        /* == 3533 */

u16 g_seed;

u16 seed_rng(u16 p_seed)
{
        g_seed = p_seed;
        return g_seed;
}


u16 rngf(void)
{
        g_seed *= RNG_M;
        return g_seed;
}


Here are the seeds and generator periods I found:
Code:
Period  Seed    Hex

16384   1       0x0001
8192    2       0x0002
4096    4       0x0004
2048    8       0x0008
1024    16      0x0010
512     32      0x0020
256     64      0x0040
128     128     0x0080
64      256     0x0100
32      512     0x0200
16      1024    0x0400
8       2048    0x0800
4       4096    0x1000
2       8192    0x2000
1       16384   0x4000


Here are the periods for the seed 0 through 31:
Code:
Period  Seed    Hex

1       0       0x0000
16384   1       0x0001
8192    2       0x0002
16384   3       0x0003
4096    4       0x0004
16384   5       0x0005
8192    6       0x0006
16384   7       0x0007
2048    8       0x0008
16384   9       0x0009
8192    10      0x000A
16384   11      0x000B
4096    12      0x000C
16384   13      0x000D
8192    14      0x000E
16384   15      0x000F
1024    16      0x0010
16384   17      0x0011
8192    18      0x0012
16384   19      0x0013
4096    20      0x0014
16384   21      0x0015
8192    22      0x0016
16384   23      0x0017
2048    24      0x0018
16384   25      0x0019
8192    26      0x001A
16384   27      0x001B
4096    28      0x001C
16384   29      0x001D
8192    30      0x001E
16384   31      0x001F


Just in case anyone was wondering where 69069 came from, it is 0x10DCD in hex, or 65536 + 3533. I suspect that 0x100000DCD or 0x100010DCD would make a good multiplier for a 64 bit LCG, although I have not done any tests.

I'd be more than willing to send my testing code to any interested party.

-Brendan

#25283 - poslundc - Fri Aug 20, 2004 12:09 am

You might try the "alternate" version of the Super-Duper LCG, which has a value of b = 1 (add 1 to the seed). It's supposed to have a better spectrum.

I personally use BCPL (a = 2147001325, b = 715136305) and while I haven't done any tests on it, it's supposed to have one of the "better" spectrums as well.

Dan.

#25290 - sgeos - Fri Aug 20, 2004 4:30 am

poslundc wrote:
I personally use BCPL (a = 2147001325, b = 715136305) and while I haven't done any tests on it, it's supposed to have one of the "better" spectrums as well.

It uses the full spectrum. (a = 0x7FF8A3ED, b = 0x2AA01D31, a' = 0x1F6931E5)
The 16-bit version is easy to construct. (a = 0xA3ED, b = 0x1D31, a' = 0x31E5)

Thanks a lot for the numbers!

-Brendan

#25316 - f(DarkAngel) - Fri Aug 20, 2004 1:57 pm

If i recall correctly, prime numbers should produce the best result.
_________________
death scream...

#25323 - sgeos - Fri Aug 20, 2004 4:30 pm

f(DarkAngel) wrote:
If i recall correctly, prime numbers should produce the best result.

The numbers need only be relatively prime to one another.

-Brendan