Example of random number generator

Page 1/3
| 2 | 3

By marison

Expert (104)

marison's picture

12-06-2005, 00:56

;In: nothing
;Out: A with a random number
;Author: Ricardo Bittencourt aka RicBit (BrMSX, Tetrinet and several other projects)
; choose a random number in the set [0,255] with uniform distribution
RAND:
PUSH HL
LD HL,(SEED)
ADD HL,HL
SBC A,A
AND 83h
XOR L
LD L,A
LD (SEED),HL
POP HL
RET

The random number generated will be any number from 0 to FFh.

Despite be a random number generator routine, your results will pass in several statistical tests.

Before the first call, the SEED value must be initiated with a value different of 0.

For a deterministic behavior (the sequence of values will be the same if the program was initiated), use a fixed SEED value.

For a somewhat more random sequence, use:

LD A,(JIFFY);MSX BIOS time variable
OR 80H ;A value different of zero is granted
LD A,(SEED)

The values obtained from this method is much more *random* that what you get from LD A,R.

Login or register to post comments

By BiFi

Enlighted (4348)

BiFi's picture

12-06-2005, 08:59

The JIFFY one only works if you're using the complete standard interrupt handler and have interrupts enabled all the time.

Always the best random generator is using the human interface with a LD A,R or any other (described above) method. Reading the joystick status directly from the PSG ports or some other user-influenceable input is very hard to plan and therefore one of the best methods to implement.

By pitpan

Prophet (3131)

pitpan's picture

12-06-2005, 13:16

Fully agree with that. And the best solution is using LD A,R and then this A value as an index for a lookup random number table. Please note that only the 7 less significant bits change in R register.

By marison

Expert (104)

marison's picture

14-06-2005, 22:35

The JIFFY one only works if you're using the complete standard interrupt handler and have interrupts enabled all the time.

The JIFFY value could be read in the game start routine once, before the interrupt handler be installed. After all, you only need to set SEED once too.

You could create a time variable in your interrupt handle, and use that variable to initiate the seed value.

Always the best random generator is using the human interface with a LD A,R or any other (described above) method. Reading the joystick status directly from the PSG ports or some other user-influenceable input is very hard to plan and therefore one of the best methods to implement.

A good idea to think about. LD A,R will generate numbers almost in sequence if used almost sequentially. This behavior is not useful to use this value without any other treatment. Do you agree?

By flyguille

Prophet (3029)

flyguille's picture

14-06-2005, 22:51


PUSH HL
LD HL,(SEED)
ADD HL,HL
SBC A,A
AND 83h
XOR L
LD L,A
LD (SEED),HL
POP HL
RET

mmm letme see, if i see correctly, it does:
if SEED => 32768 then
SEED = SEED * 2
SEED low byte = SEED low byte XOR 83h
OUT = SEED low byte
else
SEED = SEED * 2
OUT = SEED low byte
end if

mmmmm... it isn't too simply?

in resume: it just multiplies to SEED * 2 and if it overflows the new SEED has its low byte with the bits 0,1 and 7 switched, the rest goes as it is... i am not an expert in this matter.... it is enought?

anyone can test it and to calculate it in a graphic for see the dispersion of the obtained results?

By ARTRAG

Enlighted (6248)

ARTRAG's picture

15-06-2005, 00:43

SEED = 1

20000 trials: here you have the histogram (in txt :-) )

  • 0 85
    1 74
    2 75
    3 87
    4 62
    5 82
    6 73
    7 84
    8 74
    9 73
    10 83
    11 83
    12 71
    13 78
    14 79
    15 82
    16 81
    17 91
    18 81
    19 81
    20 74
    21 72
    22 77
    23 77
    24 76
    25 77
    26 92
    27 85
    28 80
    29 78
    30 80
    31 83
    32 77
    33 79
    34 91
    35 65
    36 79
    37 86
    38 78
    39 72
    40 76
    41 77
    42 72
    43 78
    44 85
    45 81
    46 83
    47 74
    48 80
    49 75
    50 76
    51 84
    52 85
    53 79
    54 76
    55 72
    56 78
    57 76
    58 80
    59 87
    60 78
    61 80
    62 84
    63 74
    64 83
    65 71
    66 85
    67 79
    68 89
    69 78
    70 71
    71 75
    72 76
    73 85
    74 80
    75 81
    76 86
    77 76
    78 79
    79 78
    80 73
    81 85
    82 73
    83 88
    84 73
    85 77
    86 82
    87 84
    88 82
    89 71
    90 73
    91 74
    92 81
    93 68
    94 75
    95 76
    96 78
    97 76
    98 77
    99 76
    100 71
    101 75
    102 75
    103 72
    104 85
    105 83
    106 77
    107 69
    108 78
    109 75
    110 80
    111 78
    112 75
    113 74
    114 75
    115 81
    116 72
    117 87
    118 78
    119 78
    120 78
    121 70
    122 78
    123 81
    124 83
    125 72
    126 77
    127 77
    128 75
    129 77
    130 71
    131 75
    132 80
    133 89
    134 74
    135 84
    136 83
    137 88
    138 70
    139 68
    140 69
    141 89
    142 83
    143 76
    144 67
    145 80
    146 79
    147 76
    148 82
    149 74
    150 85
    151 79
    152 84
    153 75
    154 73
    155 64
    156 74
    157 78
    158 74
    159 82
    160 83
    161 80
    162 84
    163 71
    164 74
    165 79
    166 82
    167 81
    168 77
    169 74
    170 76
    171 80
    172 77
    173 73
    174 78
    175 77
    176 80
    177 76
    178 77
    179 80
    180 77
    181 73
    182 75
    183 80
    184 77
    185 76
    186 68
    187 76
    188 84
    189 81
    190 76
    191 76
    192 79
    193 74
    194 79
    195 77
    196 77
    197 65
    198 80
    199 86
    200 72
    201 85
    202 79
    203 77
    204 83
    205 74
    206 78
    207 74
    208 75
    209 78
    210 73
    211 80
    212 82
    213 76
    214 69
    215 75
    216 82
    217 81
    218 76
    219 80
    220 83
    221 76
    222 83
    223 80
    224 80
    225 74
    226 75
    227 82
    228 82
    229 89
    230 86
    231 82
    232 78
    233 75
    234 89
    235 77
    236 78
    237 72
    238 79
    239 73
    240 81
    241 77
    242 79
    243 80
    244 75
    245 85
    246 78
    247 76
    248 84
    249 83
    250 75
    251 84
    252 82
    253 73
    254 82
    255 77

and the matlab code:

SEED = 1;

T=[];

for n=1:20000

if SEED >= 32768

SEED = bitand(SEED * 2, 2^16-1);

SEED = bitxor(SEED,131);

OUT = bitand(SEED , 255);

else

SEED = SEED * 2;

OUT = bitand(SEED , 255);

end

T = [T; OUT];

end

The data seems more o less uniform

By flyguille

Prophet (3029)

flyguille's picture

15-06-2005, 15:06

that is really not ramdon! that has a pattern

By marison

Expert (104)

marison's picture

15-06-2005, 15:24

SBC A,A will turn all A bits equal Carry Flag. This will be used to calculate SEED LSB.

;Carry Flag=0 => A=0, Carry Flag=1 => A=FFh
SBC A,A
;A and 83h
AND 83h
;A xor SEED LSB
XOR L

Carry Flag come from the overflow of ADD HL,HL.

Am I correct?

By flyguille

Prophet (3029)

flyguille's picture

15-06-2005, 15:41

Yes, you are correct, by that reason i see that is too simply, because here alone is a transportation of the bit 15 of SEED (in each LOOP) to the bit 7, 1 and 0, plus that no data enters in the bit 0, so, bit 0 alone is the overflowed bit 15. So really, you got bit 7 and 1 switched according the the bit 15.

By flyguille

Prophet (3029)

flyguille's picture

15-06-2005, 15:54

a very real ramdon number is too hard to obtain. Indeed there is books that only are dedicated to this matter.
You can make complex or less complex calculations but with the time and certain ammount of loops it will always back to a previously given pattern.

The secret is how to do a pattern that returns all the values of the range, each value in an equal proportion..

So, to test a ramdon generator you needs to do it

like in 10.000 executions.... how much times it returns 0, how much times it returns 1.... how much times it returns 2....... how much times it returns 255....

then make a graphic, with X axis the VALUE returned.... and Y axis the ammount of time that the value was returned....
if that graphic has a LINE, and not mountains or peaks-up or peaks-down.... you got it!. The perfect one!

By ARTRAG

Enlighted (6248)

ARTRAG's picture

15-06-2005, 15:58

I cannot see any pattern!!

Each bin in the histogram I have posted is very close to 78.1250 wich is the expected value (20000/256).
In my opinion this is a nice random number generator, at least excellent for game programming.

Actually this is a variation of a method known as linear congruence generator.
The pattern really is periodic, but the period can be very large and the goodness
of the seguence dependes on the initial paramenters

Page 1/3
| 2 | 3