Jump to content
Sign in to follow this  
idflyfish

TurboForth Random Number Generator

Recommended Posts

Anyone know why there are two copies in CPU RAM space of the VDP status byte? There's the VDPSTA equate of 8802h (discussed somewhere above) and the one in the CPU RAM PAD of 837Bh. What's interesting in Classic99 is that, in the debugger window, you can see that VDPST is changing rapidly between what appears to be 1Fh and 9Fh, i.e., the VDP interrupt bit is rapidly toggling; but, 837Bh appears to be locked at 9Fh and 8802h at 0. Actually, if I programmatically sample those two spots 32767 (7FFFh) times in a loop, I get only 9Fh at 837Bh, but only 1Fh at 8802h! A side issue is why the debugger window never shows anything but 0 at 8802h, but sampling it clearly shows 1Fh.

 

...lee

Share this post


Link to post
Share on other sites

...same thing happens in MESS (well, no debugger window); but, CPU RAM locations 837Bh and 8802h behave the same as Classic99. ...lee

Edited by Lee Stewart

Share this post


Link to post
Share on other sites

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:

 

post-24932-0-58963600-1321610420_thumb.png

 

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!

 

:)

 

It sure does. The only anamoly I have seen is in my code when using

24 RND 32 RND 254 RND 1 VCHAR

Share this post


Link to post
Share on other sites

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.

 

:?

 

Damn! I just spent a bit of time today figuring out how to code something that was faster than HCHAR because I knew that HCHAR was performing two operations to reach one point in the screen table and that if I performed only one TF RND operation for that point instead of two, maybe the periodicity of Idflyfish's code would disappear, when you (Willsy), of course, had just posted it! Oh, well---it was still an instructive exercise. I guess I sometimes just need to be slapped in the face with the explanation to get it---kind of like needing to have an obvious joke explained!

 

...lee

Share this post


Link to post
Share on other sites

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.

 

:?

 

 

If you look at the last 6 digits of the multiples of 24 below 65536, they all finish with these 8 patterns:

111000, 011000, 101000, 001000, 110000, 010000, 100000, 000000

 

With "24 RND", when the variable "seed" is a multiple of 24, "RND" returns 0 (remainder of division).

 

Then, on the next call of "RND" with "32 RND", the variable "seed" is shifted one bit right and xor'ed with >B400, so the last 5 digits of "seed" after this operation have only 8 different values when "24 RND" return 0.

 

Since the last five digits are the remainder of the division by 32, "32 RND" returns only 8 different values when "24 RND" returns 0. That's why there are only 8 positions filled on the first row.

 

When "24 RND" returns 1, the patterns are the same, except that the last bit is 1, but it's shifted out during the next "RND" call, so the second row has the same 8 positions filled.

 

 

It's easy to understand with 24 and 32, but I tried some other couples of values like 9 and 27 that are not filling the screen either, probably because they have a "Greatest common divisor" greater than 1.

Share this post


Link to post
Share on other sites

That's disappointing. I guess I should have tested it more thoroughly. I suppose we'll just have to live with it as I'm not planning another TF release. :(

 

Still, if anyone comes up with a decent routine, I'd be happy to produce a CODE version which will run in TF at full assembly speed.

 

Mark

Share this post


Link to post
Share on other sites

I appreciate that this does not deal with RND in TF but in

a way it is related. Run the following program in XB

(including RXB) and notice the certain amount of

predictability that you get. The first two decimal numbers

keep increasing by .21 and the following 8 digits are the

same. You will not get the same result in TI Basic and the

numbers are more random. Remove line 115 and you get the

starting base numbers.

 

100 RANDOMIZE 0

110 FOR X=1 TO 5

115 RANDOMIZE X

120 PRINT RND,RND

130 NEXT X

 

You can write an XB program that will produce exactly the

same series of numbers without using RANDOMIZE and RND but

you must store the base amounts of 13248654 and 36753429

and other bases. You can expand the loop in line 110 and

also add more RND statements and the appearance of

predictabilty holds true.

 

I think that all this exercise proves is that XB RND

differs from RND produced by TI BASIC.

Share this post


Link to post
Share on other sites

Jacques...

 

I am not sure I understand all your points; but, RND is supposed to generate exactly the same sequence of pseudo-random numbers every time the same seed is used to initiate the sequence. If you want a number generated by RND to be unpredictable from the point of view of the user, you should use RANDOMIZE with no expression. All RANDOMIZE does is to store a new seed for the next execution of RND, which thus begins a new, and predictable, sequence.

 

Statement 100 is superfluous because that seed (0) never gets used by RND. "RANDOMIZE 1" gets executed before the first call to RND.

 

If you replace your program with the following, you will get unpredictable sequences in that multiple runs of the program will produce different numbers. If you knew what seed RANDOMIZE had picked each time when no expression was passed to it, you could, in fact, reproduce the sequence with "RANDOMIZE X":

 

110 FOR X=1 TO 5
115 RANDOMIZE
120 PRINT RND,RND
130 NEXT X

 

...lee

Share this post


Link to post
Share on other sites

Lee, thank you for the comments.

 

I think that I placed myself so close to this and could not see the forest for the trees.

 

I guess all that my little exercise has shown is that using RANDOMIZE with a seed will produce a sort of predictable sequence which starts from the result when RANDOMIZE 0 is used. The number of times RND is used after RANDOMIZE with a seed also plays into the sequence. I agree that line 100 is not necessary.

 

The remaining mystery is why the same program run in XB and also in TI BASIC gives different results?

Share this post


Link to post
Share on other sites

The remaining mystery is why the same program run in XB and also in TI BASIC gives different results?

 

More than likely they are using different algorithms.

 

...lee

Share this post


Link to post
Share on other sites

That's disappointing. I guess I should have tested it more thoroughly. I suppose we'll just have to live with it as I'm not planning another TF release. :(

 

Still, if anyone comes up with a decent routine, I'd be happy to produce a CODE version which will run in TF at full assembly speed.

 

Mark

 

Michael & Mark...

 

Following is TurboForth Assembler coding of TI Forth's RNDW (somewhere far above) folded into RND ( limit --- n ) format so everyone can look over my shoulder for errors or enhancements:

ASM: RND	( limit --- n )
 $83C0 @() R1 MOV,	\ copy seed to R1
 R0 $6FE5 LI,		 \ load multiplier
 R0 R1 MPY,		   \ multiply R1 by R0
 R2 $7AB9 AI,		 \ add 7AB9h to R2
 R2 5 SRC,			\ rotate R2 5 bits right
 R2 $83C0 @() MOV,	\ copy R2 to seed
 R1 CLR,			  \ clear R1, msw of dividend
 *SP R1 DIV,		  \ divide R1 by # on stack
 R2 *SP MOV,		  \ copy remainder, R2, to stack
;ASM

 

...and, here it is in CODE form:

CODE: RND
C060 83C0 0200 6FE5 3840 0222
7AB9 0B52 C802 83C0 04C1 3C54
C502 ;CODE

 

...lee

Share this post


Link to post
Share on other sites

Wow! Awesome - thanks Lee :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup:

 

Did you try it with idflyfish's litte routine... I'll try it later this afternoon!

 

Thanks for this - much appreciated!

Share this post


Link to post
Share on other sites

Wow! Awesome - thanks Lee :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup:

 

Did you try it with idflyfish's litte routine... I'll try it later this afternoon!

 

Thanks for this - much appreciated!

 

Yes---and, it seems to work quite well. It should be even faster with your V! line. It also seems to cover all the cells, though I did not rigorously test it.

 

...lee

Share this post


Link to post
Share on other sites

Did you take a look at this thread?

 

http://www.atariage.com/forums/topic/163646-not-prime/

 

Particularly post #14 which has the results of the RNG routine testing I did, and also explains what the "funny numbers" are that TI used. For a good fast routine, I recommend the code Tursi posted in that thread. If you need to limit the range of numbers, be *very* careful simply trying to use bit masks since that can produce unexpected results. This is one case where the DIV instruction really comes to the rescue.

 

As for 8802h, that is the address where the 9918A's read-status port is wired up in the 99/4A's memory map, and any time you read it, the status registers in the 9918A is cleared. It is not a "memory address" in the 99/4A in the same sense that 837Bh is. If you are polling 8802h to track the 9918A's interrupt signal yourself, I strongly suggest you have interrupts disabled with LIMI 0, or you are going to get in to all kinds of conflicts with the system's ISR, which is the code that ultimately updates 837Bh with the status byte.

 

In Forth, I think Willsy said he does enable/disable interrupts once in a loop somewhere, i.e. LIMI 2/LIMI 0, so that means the system ISR is being allowed to run, which means you need to not poll the 9918A's status directly. Even if all the "interrupt facilities" are disabled using the ISR's control byte (can't remember the address right off hand), the ISR still has to figure out what caused the interrupt, and that is rather involved due to the way interrupts are crippled in the 99/4A. You can read all about it in detail on Thierry's site if you are curious. But basically, if you are allowing the system ISR to run, you have to be very careful with how you use the scratch pad RAM, and you should not poll the 9918A's status directly.

 

It is also worth mentioning that the 9918A's interrupt can be enabled/disabled via R1 bit 2 (using TI's numbering.)

Share this post


Link to post
Share on other sites

Matthew...

 

Thanks for all your information. I should note that it was TI programmers who wrote the code to poll 8802h in TI Forth's RANDOMIZE routine listed far above but shown again here:

HEX
: RANDOMIZE 8802 [email protected] DROP 0 BEGIN 1+ 8802 [email protected] 80 AND UNTIL SEED ;

 

I would have thought they, more than anyone, would know what they were doing in this regard. And, on the real iron, it works rather well. As I mentioned earlier, it does not work at all on the three emulators I tested it on (Classic99, MESS, TI994W) because 8802h never changes.

 

...lee

Share this post


Link to post
Share on other sites
I would have thought they, more than anyone, would know what they were doing in this regard. And, on the real iron, it works rather well. As I mentioned earlier, it does not work at all on the three emulators I tested it on (Classic99, MESS, TI994W) because 8802h never changes.

 

That's a bit of a strange thing. Reading from >8802 reads the VDP status register. What changes are you seeing in hardware that the emulators do not do?

 

The only bits in the status register are as follows:

 

>80 - Interrupt active (set at end of frame)

>40 - 5 or more sprites on a line

>20 - Sprite collision

>1F - number of the fifth sprite on a line, if >40 is set

 

If you aren't using sprites, then all 7 of the least significant bits should all be zero (in practice I've seen the 'fifth sprite' indicator be some random value, but not a changing one). Also, >80 would only read as set if you managed to see it before the TF processor allowed interrupts with LIMI 2 - at that point it would be cleared by the interrupt routine reading it (as well as the sprite status bits).

 

: RANDOMIZE 8802 [email protected] DROP 0 BEGIN 1+ 8802 [email protected] 80 AND UNTIL SEED ;

 

In looking at this code, all it is doing is incrementing a counter until the vertical blank interrupt bit is set. If TF enables interrupts with LIMI 2, you can not expect this to work reliably under TF, since the console interrupt routine will likely respond to the interrupt bit being set before you can. It gives you a "random" number in that you probably don't know exactly how long it will be until the end of frame, although in code with very predictable timing, the returned number will be predictable as well.

 

That bit certainly used to work in Classic99, though, and I'm very sure it also works in MESS. I use it in my Zombie MOTIF game, so it'd be surprising if it's really failing.

Share this post


Link to post
Share on other sites

Oddly TI GPL mananual says:

* True random number generation[/sub]
RGEN RAND 99[/sub]
		 SCAN[/sub]
		 CZ @>837C[/sub]
		 BR RGEN[/sub]
* Continue on with new random number determined by key press never the same twice.[/sub]

 

And I never see this in but like 8 GPL GAMES? WTH?

(I do not get it 87% of the world uses Internet Explorer and the dang thing does not work correctly with this web site)

Edited by RXB

Share this post


Link to post
Share on other sites
I would have thought they, more than anyone, would know what they were doing in this regard. And, on the real iron, it works rather well. As I mentioned earlier, it does not work at all on the three emulators I tested it on (Classic99, MESS, TI994W) because 8802h never changes.

 

That's a bit of a strange thing. Reading from >8802 reads the VDP status register. What changes are you seeing in hardware that the emulators do not do?

 

The only bits in the status register are as follows:

 

>80 - Interrupt active (set at end of frame)

>40 - 5 or more sprites on a line

>20 - Sprite collision

>1F - number of the fifth sprite on a line, if >40 is set

 

If you aren't using sprites, then all 7 of the least significant bits should all be zero (in practice I've seen the 'fifth sprite' indicator be some random value, but not a changing one). Also, >80 would only read as set if you managed to see it before the TF processor allowed interrupts with LIMI 2 - at that point it would be cleared by the interrupt routine reading it (as well as the sprite status bits).

 

: RANDOMIZE 8802 [email protected] DROP 0 BEGIN 1+ 8802 [email protected] 80 AND UNTIL SEED ;

 

In looking at this code, all it is doing is incrementing a counter until the vertical blank interrupt bit is set. If TF enables interrupts with LIMI 2, you can not expect this to work reliably under TF, since the console interrupt routine will likely respond to the interrupt bit being set before you can. It gives you a "random" number in that you probably don't know exactly how long it will be until the end of frame, although in code with very predictable timing, the returned number will be predictable as well.

 

That bit certainly used to work in Classic99, though, and I'm very sure it also works in MESS. I use it in my Zombie MOTIF game, so it'd be surprising if it's really failing.

 

Tursi...

 

Somewhere far above I discuss what is happening (or not happening). As you point out, 80h is used to sample the VDP interrupt (vertical blanking bit). The TI Forth code does not, in fact, return a predictable number for the counter, probably because the code cannot catch the interrupt before the ISR always at the same time; but, as I said, on the iron, it does catch it in pretty short order. To my understanding, the purpose of RANDOMIZE is not to generate a random number, but, rather, an unpredictable seed---perhaps my making the distinction is pedantic.

 

Concerning what is happening in the emulators, RANDOMIZE never returns. It is stuck in an infinite loop. I have never had this happen on the TI99/4A. It always returns after a mere hesitation. If I put sampling 8802h in a very long loop, I catch the interrupt quite a lot on the TI, but never on the emulators, i.e., the interrupt bit is always cleared. In the debugger, I would expect to see that 8802h is changing, but it is always 0 with not the least flicker.

 

...lee

Share this post


Link to post
Share on other sites

I do not get it? The GPL XB source code I posted shows that the RANDOM numbers:

 

* RANDOMIZE given a seed value

* (99,000,000,000,001 possible starting positions)

* (Place-value is ignored in the input number)

 

 

So how could you create a RANDOM seed to beat that 14 digit number?

That is the max number the TI could even use?

Edited by RXB

Share this post


Link to post
Share on other sites
Tursi...

 

Somewhere far above I discuss what is happening (or not happening). As you point out, 80h is used to sample the VDP interrupt (vertical blanking bit). The TI Forth code does not, in fact, return a predictable number for the counter, probably because the code cannot catch the interrupt before the ISR always at the same time; but, as I said, on the iron, it does catch it in pretty short order. To my understanding, the purpose of RANDOMIZE is not to generate a random number, but, rather, an unpredictable seed---perhaps my making the distinction is pedantic.

 

Concerning what is happening in the emulators, RANDOMIZE never returns. It is stuck in an infinite loop. I have never had this happen on the TI99/4A. It always returns after a mere hesitation. If I put sampling 8802h in a very long loop, I catch the interrupt quite a lot on the TI, but never on the emulators, i.e., the interrupt bit is always cleared. In the debugger, I would expect to see that 8802h is changing, but it is always 0 with not the least flicker.

 

...lee

 

I can only speak for Classic99, of course, and not for MESS, Win994A, or even TI Forth or TurboForth. There's no way in Classic99's debugger to observe the VDP status register as >8802 -- that's a CPU memory address, and in order for the debugger to parse it as a memory-mapped device, it must actually access the VDP, something that it is forbidden to do (because it will change the state of the debug). So, it will always return zero because there is no memory behind it. You have to watch the VDPST breakout or the VDPST register value, and you will see it changing continuously to reflect the VDP Interrupt (I have just verified this).

 

Your code will work straight up if interrupts are disabled in the CPU, VDP, or 9901 to prevent the console ISR from running. I don't actually have TI Forth, so I can't check that, but TurboForth allows interrupts. It's very possible and that this code will take longer to return in that case, although there's a little magic of timing that might allow it to occur occasionally. It's a race condition in this case, and not something that you should rely on (the race being - can you catch it before the console does?) I suppose there might be an argument made that a race makes for a better random number (seed, either one).

 

Interestingly.. when I attempt to run that loop in TurboForth, interrupts no longer happen, but neither does it appear to actually read the status register. I removed SEED and left the rest, since it didn't know SEED.

 

So I tried by hand... and, well, hehe. "8802" is a decimal number, not hex, at least in TF. Better still, it's address >2262, which /is/ RAM.

 

Unfortunately, the language reference at Turboforth.net is not working for me! So I had to poke around and experiment a bit. But this works in TurboForth 1.0 under Classic99, and returns a different number each time:

 

: RANDOMIZE $8802 [email protected] DROP 0 BEGIN 1+ $8802 [email protected] $80 AND UNTIL . ;

 

Note, of course, that I don't seed the generator (don't know how since SEED didn't work), I just use '.' to print the value on the stack. Each time you type RANDOMIZE, it generates a different number.

 

The only change needed was to use hexadecimal numbers -- could you be having a similar problem?

Edited by Tursi

Share this post


Link to post
Share on other sites

The TI Forth code does not, in fact, return a predictable number for the counter, probably because the code cannot catch the interrupt before the ISR always at the same time; but, as I said, on the iron, it does catch it in pretty short order.

 

The primary problem here, is, polling the 9918A's status directly, while also trying to use the ISR (or allow it to run), is going to create undesirable behavior or side effects. If the ISR is running, your code should not be racing to try and catch the interrupt before the ISR. If interrupts are enabled, and thus the console ISR, the status byte in scratch pad is what should be polled, not the 9918A.

 

Concerning what is happening in the emulators, RANDOMIZE never returns. It is stuck in an infinite loop. I have never had this happen on the TI99/4A. It always returns after a mere hesitation. If I put sampling 8802h in a very long loop, I catch the interrupt quite a lot on the TI, but never on the emulators, i.e., the interrupt bit is always cleared. In the debugger, I would expect to see that 8802h is changing, but it is always 0 with not the least flicker.

 

My theory as to what is going on here has to do with the way that emulators on preemptive OSes (i.e. windows, linux, mac) are written. Emulators try very hard to get the timing right, but asynchronous interrupt signals are some of the hardest to emulate. If MESS is modeled after MAME, then I can see how this situation could easily happen. As for Classic99, Tursi uses threads and I'm not sure how asynchronous signals between components are delivered, but it is possible that it happens in somewhat of a serialized fashion inside the emulator.

 

On the real hardware, you can obviously grab the 9918A status bit before the interrupt causes the CPU to transfer control to the ISR. But based on how an emulator's scheduling is written, it might never happen (and in this case it has been shown to never happen.) It has probably never caused a problem or come up before because it is not a good idea to poll the 9918A status with interrupts enabled, so I suspect most software does one or the other, but not both.

Share this post


Link to post
Share on other sites

Just for the record, interrupts in TF are enabled in only three cases:

 

1) Just before a write to VDP with VSBW

2) Just before a call to JOYST

3) When on the command line (i.e. the cursor is flashing)

 

In both cases it's a simple LIMI 2 LIMI 0 sequence. I would have liked to have had it such that interrupts were pretty much free running, but I couldn't get it to work.

 

Therefore in TF, if you poll the CPU ram version of the VDP status byte in a tight loop, then you'll never see the end of frame bit, because the console ISR never runs and it's the console ISR that updates the CPU memory version of the VDP status byte!

 

Thusly, you would have to poll the VDP status directly. TF is easily fast enough to catch this.

 

For the record, in TF, numbers with a $ preceding them are forced to be evaluated as hex. (numbers with a preceding % are binary). Otherwise the number will be evaluated according to the current setting of BASE (the default is 10 for decimal).

 

The words HEX and DECIMAL can be used to temporarily change BASE whilst compiling. They are immediate words (i.e. they don't get compiled, they just change a setting).

Share this post


Link to post
Share on other sites

...this works in TurboForth 1.0 under Classic99, and returns a different number each time:

 

: RANDOMIZE $8802 [email protected] DROP 0 BEGIN 1+ $8802 [email protected] $80 AND UNTIL . ;

 

Yep. That'll do it. If you don't want to use $ for hex numbers, then execute HEX first:

 

HEX
: RANDOMIZE 8802 [email protected] DROP 0 BEGIN 1+ 8802 [email protected] 80 AND UNTIL . ;
DECIMAL

 

I also checked with TF V1.1 on real iron (with an F18 fitted, no less ;) ) and it worked fine - a different number each time.

 

I would there propose to make the definition of RANDOMIZE (in TF) as follows:

 

: RANDOMIZE 8802 [email protected] DROP 0 BEGIN 1+ 8802 [email protected] 80 AND UNTIL $83C0 ! ;

 

Which should dove-tail neatly with Lee's RND routine published above.

 

Mark

Share this post


Link to post
Share on other sites

Just for the record, interrupts in TF are enabled in only three cases:

 

1) Just before a write to VDP with VSBW

2) Just before a call to JOYST

3) When on the command line (i.e. the cursor is flashing)

 

I'm wondering what TF uses the ISR for? I think you mentioned that you have all the "facilities" turned off via the control byte.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...