Example of random number generator

Página 2/4
1 | | 3 | 4

Por flyguille

Prophet (3028)

Imagen del flyguille

15-06-2005, 16:08

the average needs to be 78
there is values with 64 times.... and others returned 89 times
that trace a line of 27! from min to max


well, as i said i am not an expert in this matter

Por marison

Expert (104)

Imagen del marison

15-06-2005, 16:10

The range is narrow, in your sample at least, because you used 1 for initiate SEED, no?

Do you have tested with other values?


Enlighted (6862)

Imagen del ARTRAG

15-06-2005, 16:16

but actually the seed should not be very relevant, becouse, if the
generator i sgood, SEED, while the loop is working, should pass
trough all the 2^16-1 values except zero.
In this case you have the maxlengh random pediod (wich is of course
2^16-1 )

The true parameters are 2 and 131 that decide IF SEED passes
trough all the admissible values, ie if you are generating a
maxlengh random sequence.

Por ricbit@work

Supporter (3)

Imagen del ricbit@work

15-06-2005, 16:32

Hi people

This routine is a very optimized Linear Feedback Shift Register (LFSR). Please read any book on random number generation to learn how it works. It's exactly the same method used in hardware, inside the PSG, to generate the random noise channel. It's also used inside CDMA cell phones, and anything else using spread spectrum techniques. Linear congruence generators, such as the one used inside MSX BASIC, are much slower than LFSR.

This particular implementation has indeed a maxlength sequence (65535), actually it's the smallest 16-bit LFSR known (this can be proven by brute force search in the number of taps). If you iterate the algorithm 65535 times, you will see that the distribution is quite uniform.

The generated sequence *has* a pattern, of course, it's a 65535-size pattern that repeats over and over. This can't be avoided with pseudo-random numbers. The only way to avoid this is increasing the range of the number, say, making all the calculations with 24 bits. This would be much slower, and not really useful for practical purposes as game programming.

The seed can be any value different from 0 (I use JIFFY OR 1, but actually any value is fine).

Of course, you don't need to believe me in that, just load the 65535-pattern in matlab and perform some statistical tests. Knuth's "Art of Computer Programming" has a lot of tests you could apply to the data.

Some considerations about LFSR can be found on the wikipedia: http://en.wikipedia.org/wiki/LFSR


Enlighted (6862)

Imagen del ARTRAG

18-03-2008, 15:57

A faster uniform generator for 7 bit numbers should be :

                ld   a,r
                ld   b,a
                ld   a,(old_rnd)
                xor  b
                ld   (old_rnd),a

IMHO seems even more uniform than the first one posted at the beginning of this tread...
Anyone willing confirm my impression?



Enlighted (5940)

Imagen del NYYRIKKI

18-03-2008, 16:18


Por pitpan

Prophet (3152)

Imagen del pitpan

18-03-2008, 16:45

Sooooooooooo good!

Anyway, ARTRAG, you should remember to init the R register with a 0 to have numbers between 0 and 127. Something like XOR A ; LD R,A


Enlighted (6862)

Imagen del ARTRAG

18-03-2008, 17:59

Well, it generates 7 bit random numbers even if bit 7 stays to 1.

Any idea on how good it is ?


Champion (293)

Imagen del MOA

20-03-2008, 01:10

Well, it generates 7 bit random numbers even if bit 7 stays to 1.

Any idea on how good it is ?

I just incorporated it in my z80 asm random maze generator with mixed results... the mazes look ok (although patterns are visible), but the loops that distribute treasure [making sure there's only 1 treasure per Y tile to avoid too many sprites per row] sometimes gets stuck in an endless (?) loop, waiting for a suitable random number.

Using the high byte (ld A,H) of this function gives very nice results:

SEED: equ rand16 + 1

ld BC,0
ld HL,253
xor A
sbc HL,BC
sbc A,B
sbc HL,BC
sbc A,B
ld C,A
sbc HL,BC
jr nc,.end
inc HL
ld (SEED),HL ; self modifying code (seed is hardcoded in opcode)

p/s: this function was ripped of the internet and slightly optimized by me.

Por poke-1,170

Paragon (1769)

Imagen del poke-1,170

20-03-2008, 03:10


Página 2/4
1 | | 3 | 4