idflyfish Posted November 15, 2011 Share Posted November 15, 2011 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 ; Quote Link to comment Share on other sites More sharing options...
idflyfish Posted November 15, 2011 Author Share Posted November 15, 2011 Sorry if my OP was vague....does anyone wanna take a stab at explaining it? Quote Link to comment Share on other sites More sharing options...
moulinaie Posted November 15, 2011 Share Posted November 15, 2011 $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 ? Quote Link to comment Share on other sites More sharing options...
+Lee Stewart Posted November 15, 2011 Share Posted November 15, 2011 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 Quote Link to comment Share on other sites More sharing options...
moulinaie Posted November 15, 2011 Share Posted November 15, 2011 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. Quote Link to comment Share on other sites More sharing options...
+RXB Posted November 15, 2011 Share Posted November 15, 2011 (edited) 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 Quote Link to comment Share on other sites More sharing options...
Willsy Posted November 15, 2011 Share Posted November 15, 2011 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! Quote Link to comment Share on other sites More sharing options...
Willsy Posted November 15, 2011 Share Posted November 15, 2011 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! Quote Link to comment Share on other sites More sharing options...
+RXB Posted November 15, 2011 Share Posted November 15, 2011 (edited) 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 Quote Link to comment Share on other sites More sharing options...
idflyfish Posted November 16, 2011 Author Share Posted November 16, 2011 $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? Quote Link to comment Share on other sites More sharing options...
Willsy Posted November 16, 2011 Share Posted November 16, 2011 Nothing significant in either of those addresses as far as I know. I think the code is copied from Leo Brodie IIRC... Quote Link to comment Share on other sites More sharing options...
moulinaie Posted November 16, 2011 Share Posted November 16, 2011 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. 1 Quote Link to comment Share on other sites More sharing options...
idflyfish Posted November 16, 2011 Author Share Posted November 16, 2011 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 Quote Link to comment Share on other sites More sharing options...
+Lee Stewart Posted November 16, 2011 Share Posted November 16, 2011 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 1 Quote Link to comment Share on other sites More sharing options...
moulinaie Posted November 16, 2011 Share Posted November 16, 2011 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. Quote Link to comment Share on other sites More sharing options...
idflyfish Posted November 16, 2011 Author Share Posted November 16, 2011 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. Quote Link to comment Share on other sites More sharing options...
+Lee Stewart Posted November 16, 2011 Share Posted November 16, 2011 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 Quote Link to comment Share on other sites More sharing options...
+RXB Posted November 16, 2011 Share Posted November 16, 2011 (edited) 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 Quote Link to comment Share on other sites More sharing options...
Willsy Posted November 17, 2011 Share Posted November 17, 2011 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 1 Quote Link to comment Share on other sites More sharing options...
Willsy Posted November 17, 2011 Share Posted November 17, 2011 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.... Quote Link to comment Share on other sites More sharing options...
idflyfish Posted November 18, 2011 Author Share Posted November 18, 2011 (edited) 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 Quote Link to comment Share on other sites More sharing options...
Willsy Posted November 18, 2011 Share Posted November 18, 2011 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. Quote Link to comment Share on other sites More sharing options...
idflyfish Posted November 18, 2011 Author Share Posted November 18, 2011 ya that works great. Nice speed on the 1.1 RND btw. Quote Link to comment Share on other sites More sharing options...
Willsy Posted November 18, 2011 Share Posted November 18, 2011 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! 1 Quote Link to comment Share on other sites More sharing options...
Willsy Posted November 18, 2011 Share Posted November 18, 2011 garbage post deleted Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.