Random Numbers

[troyc71]

Hello all,

I'm new to the group & happy to find it. I've got a crude game or two I'll link to soon. I'm pretty novice as you'll see from my question:

Is there a way to generate a "truly" random number in a program? I have a couple games that rely on random numbers, but of course whenever the games load up in VICE, the outcome is the same every time since the sequence of "random" numbers is the same every time. Is this just an emulator issue or will I get the same result on my real VIC (currently in storage)?

Thanks,
Troy

[Zeela]

Just a quick tip...

To get another sequence of random numbers use RANDOMIZE.

// Zee

[vic user]

i picked up this little tip from a book, but i can't remember the title right now:

950 T = VAL(RIGHT$(TI$,2))

951 FOR I = 1 TO T: R = RND(0): NEXT I

952 RETURN

i gosub this routine just before i get the computer to generate a 'proper' random number that i will use in my program.

chris

[carlsson]

Even if you randomize (by calling RND with a negative number), the key is to get a seed that will not be the same every time.

When you turn on the VIC-20 - no matter if it is the real thing or an emulator - the TOD clock starts running, and the random number generator is seeded. If you make a call Z=RND(-TI), you will seed the generator again, so within one session you can get new sequences of random numbers.

But! If you auto-load and run a program (normally only possible in emulation, or if you load an autostarting program or insert a cartridge), it will always take the same amount of time to start the program, which means the random number generator will be seeded with the same value. You could solve this by requiring the user to press a key to start the game, and not re-seed the random number generator until that has happened.

[troyc71]

Thanks to everyone for the tips. I was tired of knowing the outcome of every game I used a random number in!

[saundby]

I always reseeded the generator in BASIC with a modulo of TI after an INPUT statement. I'd add an INPUT requesting the player's name even if I didn't use it (except perhaps when printing game results or high scores.) Another thing I'd do is wait on the first press of the fire button (Press Fire to Start) and take a modulo of TI then.

-Mark G.

[carlsson]

Yes, the "press a key to start" is a good way to hopefully make some time pass before the game is started and one can get a unique random seed for everytime the game loads from scratch. Apart from in emulation and cartridges, I think only the 1540 has the option to autoboot something; not the same thing as autostarting after a manual LOAD command.

[Jeff-20]

As a kid I assumed some kernal routine was called for a random number. Now, looking at my books, I find no explaination for RND(. We all know the clock is involved, but can anyone elaborate on how the numbers are generated by RND?

[tlr]

As a kid I assumed some kernal routine was called for a random number. Now, looking at my books, I find no explaination for RND(. We all know the clock is involved, but can anyone elaborate on how the numbers are generated by RND?

No clock involved.
I haven't looked at the code, but I'm fairly sure it is implemented as a Linear Congruential Generator.

[Jeff-20]

hmmm... interesting. Where is the vic going to (what routine is called) to get this number.

Also, can anyone propose an algorithm for shuffling numbers? In a particular program, I would like to shuffle 1-10 assuring I would not go 20 cycles without any number recurring (not as difficult as a card deck simulation).

The only way I could think of achieving bijection is with an array, but there must be a better way. A more simple way -- how do CD players do it?

[Mike]

RND() is indeed some form of linear congruential generator. However, CBM tried to "improve" upon that, and made additional byteswaps onto the intermediate result. See here. This more or less breaks the generator. Since the number stored internally is 32 bits, we could hope, that the RND() only repeats after ~4*10^9 calls. But it's worse:

(Best checked in VICE, at max. speed)

Code: Select all

1 X=RND(-TI):CLR : REM take random seed
2 FORT=1TO100000:X=RND(1):NEXT : REM warm up generator and keep last generated number
3 S=S+1:IFRND(1)<>XTHEN3 : REM check for period
4 PRINTS

In 10 tries I got printed the number 58078. If you enter 'GOTO 3' some times, you'll see that RND() now repeats every 58078 calls.

The book 'Numerical Recipes in C' has a chapter about good random number generators. The simplest of these can be expressed in CBM BASIC as follows:

Code: Select all

1 S=7612351:REM some random seed, integer number, must not be 0
2 :
3 REM return new random number in S
4 Q=INT(S/127773):R=S-127773*Q:S=16807*R-2836*Q:IFS<0THENS=S+2147483647
5 :
6 PRINT (S-1)/2147483646 : REM print random number 0..1 - 0 inclusive, 1 exclusive
7 GOTO 4

It has a period of 2^31-2. S ranges from 1 to 2147483646.

@Jeff: With a linear congruential generator like this, you indeed produce all numbers in an interval - seemingly random - and only once. But they need to be carefully designed. For your task, using an array for card shuffling seems to be the best option.

Greetings,

Michael

P.S. If you are interested, I can produce a ML version of the generator in line 4. This should then be of comparable speed to RND().

[carlsson]

The RND routine starts at E094, by checking the argument. For RND(1), you call E0BB:

Code: Select all

JSR $E0BB ; RND(1)
JSR $DC0C ; FAC to AFAC
LDY #7
JSR $D3A2 ; Load FAC with .Y
JSR $DA30 ; Multiply FAC with AFAC
JSR $D1AA ; Convert FAC to integer in A/Y
INY ; Add one to get range 1..7

.A would contain the upper byte and .Y the lower byte, in case the multiplication results in a number larger than 255. If you're satisfied with just getting a floating point number 0<=x<1, just the first call to $E0BB is required.

The MFLPT constands for RND evaluation start at $E08A, if you need to know.

[nippur72]

thank you for the ML routine, it's very useful to me because my program had to switch back and forth from ML to basic just because of an RND. Now it's all in ML. BTW, how do you do RND(-TI) in ML?

[carlsson]

It is a bit more difficult... Here is a way to convert TI to FAC:

Code: Select all

lda #$01
ldy #$00
jsr $d391 ; load the numeric constant 256 into FAC
jsr $dc0c ; and store into AFAC
lda $a0
ldy $a1
jsr $d391 ; load upper two bytes of TI into FAC
jsr $da30 ; multiply by AFAC
jsr $dc0c ; and store into AFAC
ldy $a2
jsr $d3a2 ; load last byte of TI into FAC
jsr $d86a ; add AFAC to FAC

Then we want to call RND with negative argument (follows directly):

Code: Select all

jsr $df84 ; negate FAC
jsr $e0d0 ; call RND with negative argument

Then you make the other calls to RND with positive argument as before. I'm not 100% this works as intended, and perhaps there is a more elegant way to convert TI to FAC.

Basically, if you need fast integer pseudo-random numbers only once in a while, you might just as well just read the low byte of TI ($A2) or the raster line ($9004). Rarily the user will notice any difference, and in the case of an autostarting image loaded into an emulator, no matter which method you choose, you will always get the same sequence given the same seed (i.e. the same delay between program is loaded and started). One way to solve that is to have a "Press a key to start" as mentioned above.

[nippur72]

The above code sometimes gives me an "?overflow error", I think it's because of the $d391 that accepts only integers in the range 0-32767. So I've added an "and 127". I was also considering that for most purposes only the least significant bytes of TI are necessary, so the "randomize" routine would becomes something like that:

Code: Select all

        lda $a1
        and #127
        tay
        lda $a2
        jsr $d391 ; load lsb bytes of TI into FAC
        jsr $df84 ; negate FAC
        jsr $e0d0 ; call RND with negative argument

I've also tried the quick way, that is

Code: Select all

        
        lda $a0
        ldy $a1
        ldx $a2    ; takes jiffy clock and puts into random seed locations
        sta $8b
        stx $8c
        sty $8d

but it gives me a strange return value on the first RND(1) call (probably due to random seed not correctly initialized). Leaving $8B untouched seems to work but I'm not going to use this solution because it's not reliable.