Random number generation on the Apple II with AppleSoft BASIC

15 posts / 0 new
Last post
LoadError's picture
Offline
Last seen: 1 day 2 hours ago
Joined: May 11 2021 - 04:34
Posts: 24
Random number generation on the Apple II with AppleSoft BASIC

Howdy.

I've studied this article which details a well known limitation with AppleSoft BASIC when it comes to generating a pseudo-random number sequence:

https://link.springer.com/content/pdf/10.3758/BF03202585.pdf

I've done some experiments, and there is one thing I still cannot figure out.

Try to do this: set the AppleWin emulator to Apple II+ mode, paste this program, RUN it and then save the emulator state (f11):

---

10 home:get k$:x=rnd(-1*(peek(78)+256*peek(79))):print x

---

What this code does is wait for a keypress and then seed the random number generator with a value taken from the memory locations used by the keyboard scanning routine. Since the exact moment when a key is pressed can be considered pseudo random, this results in a different seed (x) being generated every time.

To test this, after saving the emulator state press a key, take note of the value of x, then load the emulator state you saved previously, and press a key again. The value of x will be different.

 

OK and as expected so far. Now try this code (and again, RUN the program and save the emulator state):

---

10 home:wait 49152,128:x=rnd(-1*(peek(78)+256*peek(79))):print x

---

This code is very similar, but instead of the GET statement we are using a WAIT statement that has the effect of waiting for a keypress while hiding the cursor. We can follow this with a GET to grab the keypress, but that does not change the issue I am about to explain.

Again, press a key and take note of the value of x, then load the emulator state you saved and press a key again. The value of x will be the same!

And the issue is not the RND statement, because PEEKing the values of 78 and 79 before generating the seed reveals the two values don't change. Try this:

---

10 home:wait 49152,128:print peek(78),peek(79):x=rnd(-1*(peek(78)+256*peek(79))):print x

---

Note that if you save the emulator state when the program is NOT running, so that to run it you will have to load the emulator state and then type RUN, this issue does NOT happen. It only happens when loading a RUNNING emulator state. In theory, loading an emulator state should be equivalent of "resuming reality" and not the equivalent of cold booting the machine straight to the program; and besides, even if that was the case, seeding the random number generator AFTER a keypress should guarantee that a new series of pseudo random numbers is generated every time.

OK, enough with the blah blah. Why does this happen? Why does the WAIT statement above cause the 78 and 79 memory locations to NOT get a pseudo random value from the keyboard scanning routine? Is this a problem with the emulator or can this be traced back to the actual machine?

 

 

 

 

Offline
Last seen: 2 hours 30 min ago
Joined: Jun 18 2010 - 13:54
Posts: 405
The values at 78 and 79 are

The values at 78 and 79 are only updated by the keyin routine while it's waiting for keyboard input. Just checking the keyboard flag at $C000 with the WAIT command bypasses this.

 

To accomplish what you want, just put the WAIT command in a loop that also increments a variable. Then, when the key is pressed use that value to seed RND().

LoadError's picture
Offline
Last seen: 1 day 2 hours ago
Joined: May 11 2021 - 04:34
Posts: 24
How can I put the WAIT

How can I put the WAIT statement in a loop? The "WAIT 49152,128" statement waits until any key is pressed, then resumes the program so if no key is pressed, no loop can occur.

Offline
Last seen: 2 hours 30 min ago
Joined: Jun 18 2010 - 13:54
Posts: 405
LoadError wrote:How can I put
LoadError wrote:

How can I put the WAIT statement in a loop? The "WAIT 49152,128" statement waits until any key is pressed, then resumes the program so if no key is pressed, no loop can occur.

 Sorry, do a PEEK(49152) and check for >128.

LoadError's picture
Offline
Last seen: 1 day 2 hours ago
Joined: May 11 2021 - 04:34
Posts: 24
Yes, that would work (>=128).

Yes, that would work (>=128). So basically, an INPUT or GET statement will update the keyboard scanning routine memory addresses, so that they can be used to seed the pseudo-random number generator, where a PEEK or a WAIT will not, so one has to manually seed the generator with a loop-and-variable workaround.

Honestly though this issue would only become apparent, if I'm not mistaken, in the half-unreal situation of an emulator loading a saved state (in which case there would be no keyboard input before the WAIT or PEEK statement), because if the program is loaded from a medium and then executed with RUN, this keyboard input will update the keyboard scanning routine memory locations, allowing to extract a new pseudo-random sequence from them (or directly with a RND([positive ]]) statement in integer BASIC).

All correct?

 

Offline
Last seen: 2 hours 30 min ago
Joined: Jun 18 2010 - 13:54
Posts: 405
Yes you are correct. Of

Yes you are correct. Of course no matter how you seed the RND() function, the sequence of values it returns (for that seed) will always be the same. So it was often thought that creating a new seed this way using the human randomness of a keypress would help. And indeed changing the seed before every call to the function could remove most of the "pseudo" from the sequence.

mmphosis's picture
Offline
Last seen: 1 week 4 days ago
Joined: Aug 18 2005 - 16:26
Posts: 372
RND

Here is code that uses a "wait for keypress" machine language routine that increments the RND locations while waiting:

 

10 HOME:FORI=768TO782:READB:POKEI,B:NEXTI:CALL768:PRINT PEEK(78),PEEK(79):X=RND(-1*(PEEK(78)+256*PEEK(79))):PRINT X:DATA230,78,208,2,230,79,44,0,192,16,245,44,16,192,96

 

 

I found the article Random Numbers for Applesoft  by Bob Sander-Cederlof informative, and it has some "better" RND functions:

http://www.txbobsc.com/aal/1984/aal8405.html#a1

LoadError's picture
Offline
Last seen: 1 day 2 hours ago
Joined: May 11 2021 - 04:34
Posts: 24
Interesting, thanks!While we

Interesting, thanks!

While we are on the subject: all the above implies using AppleSoft BASIC. But what about Integer BASIC? From what I've gathered so far, in this version of BASIC we don't have the ability to seed a new sequence with RND([negative integer]), so RND([positive integer]) generates a new random number from a sequence that is invariably seeded by the keyboard scanning routine memory locations; in this case the workaround of using a loop and a variable to seed a new sequence cannot be applied. Correct?

 

Offline
Last seen: 2 hours 30 min ago
Joined: Jun 18 2010 - 13:54
Posts: 405
I suppose you could add a

I suppose you could add a call to RND inside your key loop. Then you'd keep the last number generated by RND() after the key was pressed.

LoadError's picture
Offline
Last seen: 1 day 2 hours ago
Joined: May 11 2021 - 04:34
Posts: 24
Yes, that may be a workaround

Yes, that may be a workaround. Since the seed would not change, I would still get a random number from the same sequence, but at least the next number in the sequence would be semi-randomized.

mmphosis's picture
Offline
Last seen: 1 week 4 days ago
Joined: Aug 18 2005 - 16:26
Posts: 372
RND "wait for keypress" code golf

Here is a weirder and more fragile version of the code that uses a "wait for keypress" machine language routine that increments the RND locations while waiting:

 

# python3 savestate2fp.py | mondump -r | fp2txt # press F11 in AppleWin, and output the current Applesoft program ...

 

 10  HOME : GOSUB 62910: PRINT  PEEK (78), PEEK (79):X =  RND ( - 1 * ( PEEK (78) + 256 *  PEEK (79))): PRINT X

 62900  END

 62910 :

 62920  CALL  PEEK (121) +  PEEK (122) * 256 + 37: RETURN : VTAB P CLEAR  TAB(  NEW L HCOLOR=  INT  ONERR L IF LL IF LL IF LL VTAB @ CLEAR  TAB(  NEW 0 ASC  ASC N =  MID$  ASC O8 GOSUB  VAL  

LoadError's picture
Offline
Last seen: 1 day 2 hours ago
Joined: May 11 2021 - 04:34
Posts: 24
I cannot even begin to

I cannot even begin to understand what the last line of the subroutine does, expecially after the RETURN statement...

Offline
Last seen: 3 hours 52 min ago
Joined: Jul 5 2018 - 09:44
Posts: 539
That is a sneaky way of

That is a sneaky way of adding binary data to the end of an Applesoft program.  To figure that out, look at the tokenized values of those statements.  If you are curious about Applesoft tokenizing and detokenizing, I've written some code that may be of interest.

 

https://github.com/softwarejanitor/applesoft_tokenizer

https://github.com/softwarejanitor/applesoft_detokenizer

 

mmphosis's picture
Offline
Last seen: 1 week 4 days ago
Joined: Aug 18 2005 - 16:26
Posts: 372
The stuff after the RETURN

The stuff after the RETURN statement is 6502 machine code appearing as printable characters, and enterable Applesoft. It is a weirder version of the "wait for keypress" machine language routine that increments the RND locations while waiting:

]CALL-151

*860L

 

0860-   A2 50       LDX   #$50

0862-   BD C0 BF    LDA   $BFC0,X

0865-   4C 92 D3    JMP   $D392

0868-   A5 4C       LDA   $4C

086A-   AD 4C 4C    LDA   $4C4C

086D-   AD 4C 4C    LDA   $4C4C

0870-   AD 4C 4C    LDA   $4C4C

0873-   A2 40       LDX   #$40

0875-   BD C0 BF    LDA   $BFC0,X

0878-   30 E6       BMI   $0860

087A-   E6 4E       INC   $4E

087C-   D0 EA       BNE   $0868

087E-   E6 4F       INC   $4F

0880-   38          SEC  

0881-   B0 E5       BCS   $0868

 

The opcodes and bytes are carefully chosen and redundant code is added so that the binary can be entered as an Applesoft statement even though the statement doesn't make any sense when LISTed in Applesoft.

 

$ hexdump -vC keywait-shorter_bas

00000000  a2 50 bd c0 bf 4c 92 d3  a5 4c ad 4c 4c ad 4c 4c  |.P...L...L.LL.LL|

00000010  ad 4c 4c a2 40 bd c0 bf  30 e6 e6 4e d0 ea e6 4f  |.LL.@...0..N...O|

00000020  38 b0 e5                                          |8..|

00000023

$ echo -en "\x00">nul;  cat nul nul nul nul keywait-shorter_bas nul | fp2txt|cut -b 4-

VTAB P CLEAR  TAB(  NEW L HCOLOR=  INT  ONERR L IF LL IF LL IF LL VTAB @ CLEAR  TAB(  NEW 0 ASC  ASC N =  MID$  ASC O8 GOSUB  VAL

 

 

Offline
Last seen: 3 hours 52 min ago
Joined: Jul 5 2018 - 09:44
Posts: 539
mmphosis wrote:The stuff
mmphosis wrote:

The stuff after the RETURN statement is 6502 machine code appearing as printable characters, and enterable Applesoft. It is a weirder version of the "wait for keypress" machine language routine that increments the RND locations while waiting:

]CALL-151

*860L

 

0860-   A2 50       LDX  

 

This part is clever too.  It uses the zero page pointers to the end of the Applesoft program to make the call not be completely dependent on the code remaining the same size.

 

CALL  PEEK (121) +  PEEK (122) * 256 + 37

 

I could probably write a bit of code to generate Applesoft token data like that for a given set of binary code.  I already wrote an Applesoft tokenizer and detokenizer and a 65C02 assembler and disassembler.  It wouldn't take a lot more to do this.

 

 

 

Log in or register to post comments