Example of random number generator

Page 2/3
1 | | 3

By flyguille

Prophet (3029)

flyguille's picture

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

mmmm...

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

By marison

Expert (104)

marison's picture

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?

By ARTRAG

Enlighted (6407)

ARTRAG's picture

15-06-2005, 16:16

no
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.

By ricbit@work

Supporter (3)

ricbit@work's picture

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

By ARTRAG

Enlighted (6407)

ARTRAG's picture

18-03-2008, 15:57

A faster uniform generator for 7 bit numbers should be :

rand:
                ld   a,r
                ld   b,a
                ld   a,(old_rnd)
                xor  b
                ld   (old_rnd),a
                ret

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

Question

By NYYRIKKI

Enlighted (5559)

NYYRIKKI's picture

18-03-2008, 16:18

web.archive.org/web/20011027002011/http://dilbert.com/comics/dilbert/archive/images/dilbert2001182781025.gif

By pitpan

Prophet (3131)

pitpan's picture

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

By ARTRAG

Enlighted (6407)

ARTRAG's picture

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 ?

By MOA

Champion (293)

MOA's picture

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

rand16:
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
.end
ld (SEED),HL ; self modifying code (seed is hardcoded in opcode)
ret

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

By poke-1,170

Paragon (1762)

poke-1,170's picture

20-03-2008, 03:10

Smile

Page 2/3
1 | | 3