TurboForth Random Number Generator

[idflyfish]

Hello all,

 

I am using the random number generator I saw in some of Willsy's code and it works great. However I would love to understand it better. Anyone want to take a stab?

$8379 C@ VALUE SEED
: RND SEED 31421 * 6927 @ +  $8379 C@ TO SEED ;

[idflyfish]

Sorry if my OP was vague....does anyone wanna take a stab at explaining it?

[moulinaie]

$8379 C@ VALUE SEED
: RND SEED 31421 * 6927 @ +  $8379 C@ TO SEED ;

 

Takes a value names SEED

times 31421

and adds the content of ram location 6927

this is the random number

 

then it takes the byte located at $8379 and stores it into SEED for the next call.

 

Guillaume.

 

PS: what is there in 6927? and in $8379 ?

[+Lee Stewart]

Hello all,

 

I am using the random number generator I saw in some of Willsy's code and it works great. However I would love to understand it better. Anyone want to take a stab?

$8379 C@ VALUE SEED
: RND SEED 31421 * 6927 @ +  $8379 C@ TO SEED ;

 

I can tell you some of what's going on. $8379 is the CPU RAM PAD address for the VDP interrupt timer. It ticks 60 times a second, so it is constantly changing from 0 to 255 in a circular manner and likely to be different from the last time it was sampled. There is probably some good reason for choosing 31421 (binary 0111101010111101) to multiply it. I don't know about 6927 except that it is somewhere in console ROM---and, it doesn't seem to change, at least, not in the few seconds I looked at it. Anyway, that is obviously added to the previous product and will be what is left on the stack after "$8379 C@ TO SEED" updates SEED from the VDP interrupt timer.

 

...lee

[moulinaie]

Lee Stewart,

 

If you're right and that content at address 6927 doesn't change, it looks like there are only 256 random numbers depending on the value taken from $8379.

Most of all if the RND call is regular (in a game for example) then it oulc be synchro with the 60 Hz clock and returning everytime the same value...

 

I have used a pseudo random number generator in MLC that only uses additions and looks good enough. If someone wants it, I can explain a bit.

 

Guillaume.

[RXB]

Well this is the XB RANDOMIZE GPL code:

<0453>			   ***********************************************************
<0454>			   * CONSTANTS FOR THE RANDOM NUMBER ROUTINE
<0455> A34F 43,01,2B RNDA2  BYTE >43,>01,>2B,>59,>52,>00,>00,>00 * = 1438982
   A352 59,52,00
   A355 00,00
<0456> A357 42,2A,08 RNDA1  BYTE >42,>2A,>08,>15,>00,>00,>00,>00 * = 0420821
   A35A 15,00,00
   A35D 00,00
<0457> A35F 43,02,0B RNDC2  BYTE >43,>02,>0B,>20,>30,>00,>00,>00 * = 2113248
   A362 20,30,00
   A365 00,00
<0458> A367 43,06,36 RNDC1  BYTE >43,>06,>36,>05,>13,>00,>00,>00 * = 6540519
   A36A 05,13,00
   A36D 00,00
<0459> A36F 43,0A,00 RNDEP  BYTE >43,>0A,>00,>00,>00,>00,>00,>00 * = 1E7
   A372 00,00,00
   A375 00,00
<0460> A377 3C,0A,00 RNDEM  BYTE >3C,>0A,>00,>00,>00,>00,>00,>00 * = 1/1E7
   A37A 00,00,00
<0461>			   ***********************************************************
<0462>			   *				   RANDOMIZE STATEMENT
<0463>			   ***********************************************************
<0464> A37F 06,6A,78 NRNDMZ CALL CHKEND			Seed provider?
<0465> A382 63,C0		   BS   RNDM1			 No
<0466>			   * RANDOMIZE given a seed value
<0467>			   * (99,000,000,000,001 possible starting positions)
<0468>			   * (Place-value is ignored in the input number)
<0469> A384 0F,74		   XML  PARSE			 Parse the seed
<0470> A386 83			  BYTE TREMZ		   * Up to end of statement
<0471> A387 06,A3,ED		CALL CKSTNM
<0472> A38A 8F,4A		   DCZ  @FAC			  Check FAC for zero
<0473> A38C 63,B6		   BS   GA3B6
<0474> A38E BE,4A,46		ST   >46,@FAC		  0 < FAC < 1E14
<0475> A391 0F,77		   XML  VPUSH			 Let FAC = X2*1E7+X1
<0476> A393 31,00,08		MOVE 8,G@RNDEM,@ARG		ARG = 1/1E7
   A396 5C,A3,77
<0477> A399 0F,08		   XML  FMUL				  FAC = X2+X1/1E7
<0478> A39B 06,00,22		CALL GRINT				 FAC = X2
<0479> A39E 35,00,05		MOVE 5,@FAC,V@RNDX2		FAC = X2
   A3A1 A3,A0,4A

99/4 GPL-ASSEMBLER (Pass 3) correct								   PAGE 0018
EQUATES EXEC-359
<0480> A3A4 31,00,08		MOVE 8,G@RNDEP,@ARG		ARG = 1E7
   A3A7 5C,A3,6F
<0481> A3AA 0F,08		   XML  FMUL				  FAC = X2*1E7
<0482> A3AC 0F,0C		   XML  SSUB				  FAC = X1
<0483> A3AE 35,00,05		MOVE 5,@FAC,V@RNDX1		FAC = X1
   A3B1 A3,A5,4A
<0484> A3B4 0F,75		   XML  CONT				  FAC = X1
<0485> A3B6 BD,A3,A0 GA3B6  DST  @FAC,V@RNDX2		  FAC = 0
   A3B9 4A
<0486> A3BA BD,A3,A5		DST  @FAC,V@RNDX1		  FAC = 0
   A3BD 4A
<0487> A3BE 0F,75		   XML  CONT
<0488>			   * RANDOMIZE given number seed value (use GPL RAND function)
<0489>			   * (16K possible starting positions)
<0490> A3C0 BF,4A,42 RNDM1  DST  >4201,@FAC			FAC = >4201
   A3C3 01
<0491> A3C4 86,4E		   CLR  @FAC4				 FAC4= >00
<0492> A3C6 06,A3,D2		CALL RNDMZ
<0493> A3C9 03,A5		   DATA RNDX1
<0494> A3CB 06,A3,D2		CALL RNDMZ			 Set up seed
<0495> A3CE 03,A0		   DATA RNDX2
<0496> A3D0 0F,75		   XML  CONT			  Continue on
<0497> A3D2 88,52	RNDMZ  FETCH @FAC8			Fetch address of seed (high b
<0498> A3D4 88,53		   FETCH @FAC9			Fetch address of seed (low by
<0499> A3D6 02,63		   RAND 99				GPL Randomize
<0500> A3D8 BC,4C,78		ST   @RANDOM,@FAC2	 >00<=FAC+2<=FF
<0501> A3DB E6,4C,02		SRL  2,@FAC2		   >00<=FAC+2<=3F
<0502> A3DE 02,63		   RAND 99				GPL Randomize
<0503> A3E0 BC,4D,78		ST   @RANDOM,@FAC3	 >00<=FAC+3<=FF
<0504> A3E3 E6,4D,02		SRL  2,@FAC3		   >00<=FAC+3<=3F
<0505> A3E6 35,00,05		MOVE 5,@FAC,V*FAC8	 Put in seed
   A3E9 B0,52,4A
<0506> A3EC 00			  RTN
<0507> A3ED D6,4C,65 CKSTNM CEQ  >65,@FAC2
<0508> A3F0 6D,28		   BS   ERRSNM
<0509> A3F2 00			  RTN
<0510> A3F3 40,01,00 FLT1   BYTE >40,>01,>00,>00,>00,>00,>00,>00
   A3F6 00,00,00
   A3F9 00,00

 

I think this provides you with some cool constants that were not discussed and how TI tackled the problem.

 

>03A0 and >03A5 are VDP Seed Storage for XB.

Edited November 15, 2011 by RXB

[Willsy]

TurboForth v1.1 has the word RND which performs much better (as far as I know - seems fine for things like screen locations etc) you give it a limit and it returns a number. I stole the code from someone here - might have been Afamantyr. There's a thread somewhere on this board on this exact subject!

[Willsy]

Here it is...

 

atariage.com/forums/topic/186520-assembly-rnd-routine/page__pid__2367705#entry2367705

 

I used the 'compact routine' - I think tursi may have developed it - can't remember now!

[RXB]

I think that 16K possible for the TI GPL version is valid but not as easy to adapt for pure Assembly so why short cuts had to be used.

 

But I do wonder how compact a version you could make in Assembly that uses the TI format.

 

Also the TI version from the documents seems to prefer different predictable starting numbers.

 

I suppose for match computations to be predictable.

 

Also if you just POKE the VDP interupt timer on a CALL KEY into the Randomize Seed you could do the same thing.

Edited November 15, 2011 by RXB

[idflyfish]

$8379 C@ VALUE SEED
: RND SEED 31421 * 6927 @ +  $8379 C@ TO SEED ;

 

Takes a value names SEED

times 31421

and adds the content of ram location 6927

this is the random number

 

then it takes the byte located at $8379 and stores it into SEED for the next call.

 

Guillaume.

 

PS: what is there in 6927? and in $8379 ?

 

Well ya...I get that. What I guess I am wondering is why multiply by 31421 and not some other number? What is the significance of 31421? Also, what is @ address 6927?

[Willsy]

Nothing significant in either of those addresses as far as I know. I think the code is copied from Leo Brodie IIRC...

[moulinaie]

 

Well ya...I get that. What I guess I am wondering is why multiply by 31421 and not some other number? What is the significance of 31421? Also, what is @ address 6927?

 

If I remember well, the RND generators in the form a*seed+b use two values a and b that have no common divisor, ie, GCD(a,b)=1. Else, you would limit the number of RND values, example:

24*SEED+18, you can note that 24 and 18 can be divided by 6, so it is equivalent to: 6*(4*SEED+3) and all the values generated will be divided by six, si limited to the serie 0, 6, 12, 18 etc...

 

If there was not @ in you program, I could understand that they use 31421 and 6927 because GCD(31421,6927)=1. But in FORTH, the "@" means recall value whose address is on the stack.

 

Guillaume.

[idflyfish]

Well ya...I get that. What I guess I am wondering is why multiply by 31421 and not some other number? What is the significance of 31421? Also, what is @ address 6927?

 

If I remember well, the RND generators in the form a*seed+b use two values a and b that have no common divisor, ie, GCD(a,b)=1. Else, you would limit the number of RND values, example:

24*SEED+18, you can note that 24 and 18 can be divided by 6, so it is equivalent to: 6*(4*SEED+3) and all the values generated will be divided by six, si limited to the serie 0, 6, 12, 18 etc...

 

If there was not @ in you program, I could understand that they use 31421 and 6927 because GCD(31421,6927)=1. But in FORTH, the "@" means recall value whose address is on the stack.

 

Guillaume.

 

Thanks for the awesome reply. I am going to look further into this see if I can better understand how it works

[+Lee Stewart]

The "@" is, in fact, an error. Brodie's example (p. 265, 1st Ed.) does not have it. BTW, his RND function is RANDOM and his SEED variable is RND---go figure!

 

That said, the definition of RND under discussion is atypical. Typically, you want a predictable sequence of numbers generated with RND from a given starting value of SEED to aid in testing a program that uses it. That is why you will see that TurboForth and TI Forth both jam the result of RND into SEED (or equivalent) for the next go-round before exiting. It is the RANDOMIZE function (where it exists) that is defined to give an unpredictable value to SEED. So, using Idflyfish's citation, I would do the following:

$8379 C@ VALUE SEED
: RND SEED 31421 * 6927 +  DUP TO SEED ;
: RANDOMIZE $8379 C@ TO SEED ;

 

 

Of course, it would be better to have more than 256 possible starting values generated from RANDOMIZE. Unfortunately, the VDP interrupt timer location (8379h) is only one byte wide. It is also very slow for use in a running program.

 

...lee

[moulinaie]

Lee,

So I was right with my idea of two numbers with a GCD = 1.

 

And why 31421 and 6927 I think that they are close enough to 32767, the max positive number into 16 bits. So using 31421*VALUE+6927 overpasses the limit and cycles back to zero into an unpredictable value (well, not easely predictable! enough for a RND function).

 

Guillaume.

[idflyfish]

The "@" is, in fact, an error. Brodie's example (p. 265, 1st Ed.) does not have it. BTW, his RND function is RANDOM and his SEED variable is RND---go figure!

 

That said, the definition of RND under discussion is atypical. Typically, you want a predictable sequence of numbers generated with RND from a given starting value of SEED to aid in testing a program that uses it. That is why you will see that TurboForth and TI Forth both jam the result of RND into SEED (or equivalent) for the next go-round before exiting. It is the RANDOMIZE function (where it exists) that is defined to give an unpredictable value to SEED. So, using Idflyfish's citation, I would do the following:

$8379 C@ VALUE SEED
: RND SEED 31421 * 6927 +  DUP TO SEED ;
: RANDOMIZE $8379 C@ TO SEED ;

 

 

Of course, it would be better to have more than 256 possible starting values generated from RANDOMIZE. Unfortunately, the VDP interrupt timer location (8379h) is only one byte wide. It is also very slow for use in a running program.

 

...lee

 

Well the error would explain the weird results I was getting last night.

[+Lee Stewart]

I am sure I will learn much more about the inner workings of the TI99/4A than I know now (largely as a result of participating in these fora); but, I just ran into a snag in every last emulator I have tried (Classic99, MESS and TI994W), The TI Forth word RANDOMIZE samples the VDP status register (8802h) while incrementing the eventual value of the seed for the random number generator (RNG), as it waits for a VDP interrupt to occur (bit 0 or most significant bit of 8802h). This happens very quickly on the TI99/4A console in text mode, but never seems to happen in any of the three emulators I mentioned. When the byte at 8802h is sampled, it is supposed to reset, i.e., clear the byte to all 0s. If I put sampling that byte into a loop on the TI, it changes often, but in the emulators, it stays the same!

 

TI Forth also uses 83C0h to hold the RNG seed value. This is R0 of the GPL interpreter's workspace. Page 406 of the E/A Manual gives its use as "random number seed". Following are the four TI Forth words for the RNG:

HEX
: RNDW 83C0 DUP @ 6FE5 * 7AB9 + 5 SRC DUP ROT ! ;   ( --- n )
: RND RNDW ABS SWAP MOD ;   ( n1 --- n2 )
: SEED 83C0 ! ;   ( n --- )
: RANDOMIZE 8802 C@ DROP 0 BEGIN 1+ 8802 C@ 80 AND UNTIL SEED ;   ( --- )

 

RNDW does a 5-bit circular right-shift in addition to the multiplication and addition. The resulting number n can be signed or unsigned. RND , on the other hand, leaves a positive number n2 such that 0≤n2<n1. SEED simply stores the number n on top of the stack into 83C0h.

 

And then there's RANDOMIZE ! The first part ( 8802 C@ DROP ) clears the VDP status register and discards the unwanted result before initializing the seed value to 0. You can figure out the rest. I guess I should parse Rich's GPL code above to see how XB is actually doing it. Anybody have more to say about the VDP status byte at 8802h and what's going on with it in the emulators? Set me straight, someone.

 

...lee

[RXB]

Lee the XB (RXB) GPL code all use two different version of RANDOMIZE as TI expected people to be lazy.

<0464> A37F 06,6A,78 NRNDMZ CALL CHKEND	 Seed provider?
<0465> A382 63,C0					  BS   RNDM1		 No

So RNDM1 is for those times that a seed number is provided. If no seed it just continues on.

 

GA3B6 executes if the seed number is zero, so the seed number stays zero.

 

RMDMZ is the one that actually takes a seed number and creates random numbers in two bytes.

Edited November 16, 2011 by RXB

[Willsy]

Very interesting stuff Lee! Looks like you found a snag in the emulators - I'm sure Tursi will be interested in that - I should also email Michael Zapf (MESS maintainer) about it too!

 

FWIW, TF initialises the seed at startup from the value in >83C0. If you watch >83C0 in Classic99 you will see it ticking like mad when the TI is on the master title screen or the cartridge selection screen. As soon as you launch TF, the value in >83C0 is frozen at its last value. This becomes the seed for the RND routine in TF. Each time a random number is generated, it is used as the seed for the next call.

 

Here's the code for anyone that is interested. Of course, this could all be done in Forth, but I included it in TF for speed and convenience, as I knew anyone writing a game of any sort will want access to simple random numbers:

 

;[ RND ( limit -- n)
; pushes a pseudo random number between 0 and limit-1 (rnd MOD limit)
; For the full range (0-65535) use a limit of 0
_rnd    clr r6			  ; upper part of 32 bit dividend
    mov @seed,r7	    ; seed to lower part of dividend
    srl r7,1		    ; shift r0 1 bit to the right
    jnc nocarr		  ; jump if no carry
    xor @mask,r7	    ; calculate new random number using mask
nocarr  mov r7,@seed	    ; store it as a seed for next time
    div *stack,r6	   ; divide number by divisor (from stack)
    mov r7,*stack	   ; push remainder of the DIV
    b @retb0		    ; jump to push and exit routine
mask    data >b400
;]

 

Here's a simple test program (TF V1.1 required)

 

: TEST 1000 0 DO 100 RND . LOOP ;

 

To see how much overhead the screen scrolling adds, try running TEST with the screen scrolling turned off:

 

FALSE SSCROLL !   TEST 

 

It's probably 10 times faster

[Willsy]

By the way, I tipped Michael Zapf (maintainer of the 4A emulation in MESS) off about the bug. I know he'd want to know

 

I guess Tursi will read this anytime soon. Very interesting that ALL the emulators do it. I wonder if the F18A exhibits the same problem? Hmmm....

[idflyfish]

I wrote a little demo which uses the TF 1.1 RND word quite a bit and I have found some interesting behavior. Hopefully someone can shed some light on why it is happening.

 

In this one it looks like RND is exhibiting a pattern.

: DEF-CHARS
254 0 DO
  DATA 4 $007E $7E7E $7E7E $7E00 I DCHAR
LOOP ;

: DEF-COLORS
31 0 DO
  I 31 RND 31 RND COLOR
LOOP ;
: SQUARES
1 GMODE
32 RND SCREEN
DEF-CHARS
DEF-COLORS
BEGIN
  24 RND 32 RND 254 RND 1 VCHAR
0 UNTIL ;

 

 

This one looks like what I expected.

: DEF-CHARS
254 0 DO
  DATA 4 $007E $7E7E $7E7E $7E00 I DCHAR
LOOP ;

: DEF-COLORS
31 0 DO
  I 31 RND 31 RND COLOR
LOOP ;
: SQUARES
1 GMODE
32 RND SCREEN
DEF-CHARS
DEF-COLORS
BEGIN
  23 RND 31 RND 254 RND 1 VCHAR
0 UNTIL ;

 

The first run is with

24 RND 32 RND 254 RND 1 VCHAR

and the second run is with

23 RND 31 RND 254 RND 1 VCHAR

Edited November 18, 2011 by idflyfish

[Willsy]

That's very interesting. It looks like some sort of flaw in the random number generating algorithm, rather than a bug in the code per-se.

 

I must admit, I don't really know why/what it's doing! The RND code, as posted earlier, looks for a carry and if there is a carry it does an XOR, otherwise it doesn't. That's it.

 

I replaced the HCHAR call with this:

 

254 RND 768 RND V!

 

Since the 'limit' in the call to RND is even, I expected it to exhibit the same results as your code. However, it worked just fine.

 

[idflyfish]

ya that works great. Nice speed on the 1.1 RND btw.

[Willsy]

A combination of boredom and interest led me to ponder on just how 'random' RND is... I.e. is it good enough for the things it would likely be used for (games)?

 

I wrote the following program to test RND:

 

FBUF: clipboard \ define a file buffer called clipboard
: TEST
 \ define clipboard as a DV80 sequential output file pointing
 \ to the classic99 device CLIP...
 S" CLIP DV80SO" clipboard FILE

 \ open the file referenced by clipboard (CLIP)...
 clipboard #OPEN

 \ abort if the call to #OPEN failed...
 ABORT" cant open windows clipboard"

 10000 0 DO
   \ generate a random number...
   1000 RND
    
   \ convert the number on stack to a string...
   N>S
    
   \ write the string out to the device...
   clipboard #PUT DROP ( drop fail/success flag)
 LOOP

 \ close the file referenced by clipboard
 clipboard #CLOSE
;

 

The above selects a number between 0 and 1000 and writes the value to the windows clipboard (so this will only work in Classic99)

 

It does this 10000 times. Once we have the data on the clipboard we can paste it into a spreadsheet and graph it:

 

 

As you can see, there is quite a uniform distribution - as we would expect/hope. There are a couple of holes, but one would expect that they would be filled in given enough iterations. Importantly, the mean line looks spot on - the mean value should be 500 (one would expect?) and it is. So, it looks like it's at least good enough for games, and maybe even your lottery numbers!

 

[Willsy]

garbage post deleted