Applesoft (pseudo) Random Numbers - alternatives?

Question

What are the alternatives (with examples on how to implement) to Applesoft RND(1) command? I have read of people using a completely different algorithm by poking machine code stored in a DATA statement. Yet zero working examples. A simple dice probability example would be awesome.

I did however read that Applesoft’s RND starting point on a pseudo-list of numbers can be changed based on keyboard input timings. Eg.

X=RND(-1*(PEEK(78)+256*PEEK(79)))

This definitely helps RND(1) become more random, yet RND(1) seems to fall apart nonetheless after heavy use.

Answer 1

I found an example that plotted on the hi-res screen to evaluate a replacement RNG. The code is based on a Call-A.P.P.L.E. article from 1989, available here. It appears to be a linear congruential algorithm, but the youtube video shows it's pretty effective.

The author tied it to the Applesoft USR function, which makes it very convenient to use. (It actually requests a buffer from ProDOS and relocates itself using a relocation dictionary, which is sort of interesting. You could probably strip a lot of that out if you want it to live in a fixed location.)

FWIW, using PEEK 78/79 only helps if you occasionally use the ROM character input routine, which increments those locations while it waits. Starship Commander tries to seed the RNG that way, but since it uses its own input routines, it ends up configuring the seed to the same value if you boot directly into the game at power-on.

Answer 2

RND in most 8-bit BASICs is a Linear Congruential PRNG, which has rather spectacularly poor quality output but is exceedingly simple to implement. Generally it will produce a fixed, repeating sequence in which the low-order bits often have an easily recognisable pattern. You cannot merely "fix" a Linear Congruential PRNG to improve the quality of its output, but must replace it with a better algorithm.

One such algorithm might be RC4, which is also very simple. Rather than keeping a single integer of state, as Linear Congruential does, RC4 keeps a 256-byte buffer of state plus two indexes into that buffer, for a total of 258 bytes of state. The maximum possible quality of a PRNG is closely related to the state it keeps.

Applesoft BASIC is a very limited language compared to what I'm used to. Here's how I'd do it in BBC BASIC - converting it to some other dialect is left as an exercise for the reader:

DIM RandBuf% 256

DEF PROCrandSeed
LOCAL seed$,x%,t%
RandI% = 0
RandJ% = 0
FOR x% = 0 TO 255 : RandBuf%?x% = x% : NEXT
INPUT "Enter a seed string for the PRNG: ";seed$
FOR x% = 0 TO 256*LEN(seed$)-1
RandJ% = (RandJ% + RandBuf%?RandI% + ASC(MID$(seed$,1+(x% MOD LEN(seed$)),1))) MOD 256
t% = RandBuf%?RandI% : RandBuf%?RandI% = RandBuf%?RandJ% : RandBuf%?RandJ% = t%
RandI% = (RandI% + 1) MOD 256
NEXT
ENDPROC

DEF FNrand%()
LOCAL t%,u%
RandI% = (RandI% + 1) MOD 256
RandJ% = (RandJ% + RandBuf%?RandI%) MOD 256
t% = RandBuf%?RandI% : u% = RandBuf%?RandJ%
RandBuf%?RandJ% = t% : RandBuf%?RandI% = u%
=RandBuf%?((u% + t%) MOD 256)

DEF FNdice%()
LOCAL r%
REPEAT : r% = FNrand%() : UNTIL r% >= (256 MOD 6)
=(r% MOD 6) + 1

Answer 3

This 1984 paper reviewing various machines' RND functions states that:

In a study of the statistical and temporal characteristics of random number generators for microcomputers, several peculiarities related to seeding random number generators were noted. Some vendor-supplied generators, including those on the Apple II+, Apple IIe, Osborne Executive, and IBM-PC, were so seriously flawed that they should not be used for simulation studies.

The same authors wrote an article for BYTE magazine in 1987 - volume 12, number 1, page 175 - where they mention one of the RND cycles having a period of only 202 values. The problem can be easily seen in this handy YouTube video where the RND characteristics are not sufficient to plot every pixel on a hires screen.

In Apple Assembly Line Volume 4 Issue 8 Bob Sander-Cederlof documented the RND problems and presented his own smaller version of the original Call APPLE algorithm as a USR function.

The RND function in Applesoft is faulty, and many periodicals have loudly proclaimed its faults. "Call APPLE", Jan 83, pages 29-34, tells them in "RND is Fatally Flawed", and presents an alternative routine which can be called with the USR function.

If you want to see some non-random features using RND, type in and RUN the following program:

   10 HGR:HCOLOR=3
   20 X=RND(1)*280:Y=RND(1)*160
   30 HPLOT X,Y
   40 GO TO 20

You will see the Hi-Res screen being sprinkled with dots. After about seven minutes, but long before the screen is full, new dots stop appearing. RND has looped, and is replotting the same sequence of numbers. Another test disclosed that the repetition starts at the 37,758th "random" number.

I re-implemented the Call APPLE algorithm, and my listing follows. The Call APPLE version would not quite fit in page 3, but mine does with a little room to spare.

The listing is in S-C Assembler format. The assembler is available and I had a quick look, but I don't know how to use it. At some point I'll get around to converting this and post the hex here.

Answer 4

You can implement an LCG in BASIC, though it might not be very fast. Here's a small AppleSoft BASIC program that implements an LCG and shows it tested across 10000 simulated dice throws:

10 REM LCG FOR APPLESOFT - SCRUSS, 2021-05
20 REM THIS IS "RANDOM0" - SEE WIKIPEDIA
30  DEF FNS0(S) = 8121 * S + 28411
40  DEF FNS(S) = FNS0(S) -  INT (FNS0(S) / 134456) * 134456
50  DEF FNR(S) = S / 134456
60  DEF FNTHROW(S) =  INT (FNR(S) * 6) + 1
70  LET SEED = 1:REM THIS WILL ALWAYS GIVE THE SAME SEQUENCE
80  DIM T(6)
90  LET THROWS = 10000 - 100
100  LET N = 0
110  TEXT : HOME 
120  FOR X = 1 TO 100
130  LET N = N + 1
140  LET SEED = FNS(SEED)
150  LET DICE = FNTHROW(SEED)
160 REM LET DICE=INT(RND(1)*6)+1: REM UNCOMMENT FOR STD RND()
170  LET T(DICE) = T(DICE) + 1
180  NEXT X
190  PRINT "AFTER ";N;" THROWS:": PRINT 
200  FOR X = 1 TO 6
210  PRINT X;": ";T(X), INT (1000 * T(X) / N) / 10;"%"
220  NEXT X
230  PRINT 
240  IF N <  = THROWS THEN  GOTO 120
250  END 

This isn't a particularly great set of parameters for an LCG, but it has a much longer period (> 134000) than AppleSoft's. After setting the seed (which it looks like you've got a handle on already) the way you can use this code is:

LET SEED=FNS(SEED)
LET RANDVAL=FNR(SEED)

or if you want to use it for dice throws:

LET SEED=FNS(SEED)
LET DICEVAL=FNTHROW(SEED)

The seeds are integer values, but the random output is between 0 .. 1. Because AppleSoft BASIC doesn't have a MOD function/operator, I split the function in two: FNS0 does the transformation, while FNS does the modulus.

AppleSoft BASIC's RND(1) implementation isn't great, but it's better than some.