LLX > Neil Parker > Apple II > New RND

MSWSRAND: A Modern Random Number Generator for Applesoft

The inadequacies of Applesoft's random number generator, RND, have long been noted. Several replacements with better properties have been published—these are mostly linear congruential generators, which, though they have well-known flaws, are at least a lot better than RND, and at the time (the mid 1980's) few reasonable alternatives were available.

The state of the art in random number generators has advanced a great deal since then, and there are now a number of high-quality random number generators known which pass even the strongest statistical tests. But alas, most of these are designed to run efficiently on modern 32- and 64-bit processors, and implementing them on an 8-bit CPU often requires an uncomfortably large amount of code.

While browsing Wikipedia's list of random number generators, my eye was caught by Bernard Widynski's Middle-Square Weyl Sequence random number generator, which gets good-quality random numbers out an attractively simple fragment of C code:

 uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
 inline static uint32_t msws32() {
    x *= x; x += (w += s); return x = (x>>32) | (x<<32);
 }

On a 64-bit x86 CPU, this can be compiled to just four assembly-language instructions. On the 6502, of course, it takes quite a bit more code than that, but the resulting routine isn't a whole lot bigger than the linear congruential RND-replacements from the 1980's.

So just for the fun of it, I implemented it as an Applesoft USR function. While I doubt that anybody today is still doing serious Monte Carlo simulations on an Apple II, nevertheless, with the software downloadable from this page, modern high-quality random numbers are available to Applesoft. The price for this (beyond the memory consumed by its code) is speed—it's a bit slower than RND.

Despite what the author claims in the paper, this generator is not suitable for cryptographic use.

MSWSRAND and its source code are freeware, and may be redistributed in accordance with the terms in the included LICENSE file (a 3-clause BSD license).

Usage

BRUN MSWSRAND

This command installs the random number generator. It consumes 512 bytes above the file buffers under ProDOS, or 465 bytes above HIMEM under DOS 3.3. BRUNning it again consumes more memory, so provisions have been made for determining whether or not MSWSRAND has already been installed.

MSWSRAND initially loads at memory location 8192 ($2000), and then moves itself to high memory. It has been designed to coexist peacefully with other high-memory modules, and unlike some such modules, it need not be the first one loaded.

& "MSWSRAND"

 & "MSWSRAND"

This command does nothing. Its purpose is to help your program figure out whether MSWSRAND is already installed. It's intended primarily for ProDOS (though it's available in DOS 3.3 too), where it might be used like this:

10  ON  PEEK (116) > 148 OR  PEEK (1015) = 190 GOTO 40: ONERR  GOTO 30
20  & "MSWSRAND": POKE 216,0: GOTO 50
30  CALL 62248: POKE 216,0
40  PRINT  CHR$ (4);"BRUN MSWSRAND"
50  REM The rest of your program starts here

Line 10 tests whether HIMEM is too high to accommodate MSWSRAND, or whether the & hook hasn't been used yet. Line 20 uses & "MSWSRAND" to test whether MSWSRAND is already installed.

MSWSRAND's above-HIMEM hiding place under DOS 3.3 isn't safe from FP, INT, or MAXFILES, so it's probably best for a DOS 3.3 progam to just throw away any previously-loaded copy and load it anew. For example,

10  POKE 1013,76: POKE 1014,88: POKE 1015,255: REM Reset & vector
20  PRINT  CHR$ (4);"MAXFILES 3": REM Throw away above-HIMEM buffer
30  PRINT  CHR$ (4);"BRUN MSWSRAND"
40  REM The rest of your program starts here

But that causes the generator to start over again using its initial seed. If you need the random number sequence the second time you run your program to continue from where the first run left off, then you need avoid reloading MSWSRAND, similar to the ProDOS code:

10  ON  PEEK (1015) = 255 GOTO 40: ONERR  GOTO 30
20  & "MSWSRAND": POKE 216,0: GOTO 50
30  CALL 62248: POKE 216,0
40  PRINT  CHR$ (4);"BRUN MSWSRAND"
50  REM The rest of your program starts here

Beware, though—if FP or MAXFILES has been used between the two runs, that could end up calling into memory that will soon be overwritten, or may already have been overwritten, by string variables.

Because BRUN MSWSRAND moves HIMEM, a DOS 3.3 program should avoid using any string variables until after MSWSRAND is installed.

USR

 USR (numeric-expression)

Return a new random number. The numeric-expression is similar to Applesoft's RND, but not quite the same. Let X be the numeric-expression—then:

• If X is 1 (or any other number greater than 0 but less than 2), a random number greater or equal to zero and less than 1 is returned.
• If X is 2 or more, USR (X) is the same as INT ( USR (1) * X), returning a number between 0 and X-1 inclusive.
• USR (0) returns the previous random number again, as a number greater than or equal to 0 and less than 1.
• If X is negative, a new random number is returned, but as an integer between 0 and 2³²-1 inclusive. (Beware—many of these numbers are too big for Applesoft to print in integer form.)

Like all software random number generators, USR has a finite period, after which it starts returning the same numbers in the same order that it already returned before. USR's period is not known, but is guaranteed to be at least 2⁶⁴ ≈ 1.8 × 10¹⁹.

The numbers returned from USR (1) and USR (-1) are uniformly distributed and equally spaced. But numbers returned from USR (X) when X >= 2 are not quite uniformely distributed unless X is a power of 2—some numbers are returned slightly more often than others. The effect is probably negligible for most uses, but some uses cannot tolerate even that slight non-uniformity—if you need perfect uniformity, pass a power of 2 larger than your X, and repeat until you get a number in the right range. For example, here's a one-liner that rolls a 6-sided die with perfect uniformity:

 FOR ZZ = 0 TO 1:R =  USR (8):ZZ = R < 6: NEXT

Or a larger power of 2 can be used to reduce the number of repeats:

 FOR ZZ = 0 TO 1:R =  USR (32768):ZZ = R < 32766: NEXT :R = R -  INT (R / 6) * 6

Or if you really want to minimize the number of repeats, use a negative argument, like this:

 FOR ZZ = 0 TO 1:R =  USR ( - 1) - 4:ZZ = R >  =  0: NEXT :R = R -  INT (R / 6) * 6

which works because 2³² MOD 6 = 4.

Unlike RND, this generator cannot be reseeded by passing a negative number to USR. Reseeding the generator requires more bits that can be passed in USR's argument, so a separate command has been provided for reseeding.

& RND

 &  RND numeric-expression[,numeric-expression]

This statement reseeds the random number generator. The two numeric-expressions should be numbers between 0 and 2³²-1 inclusive. They are truncated to 32-bit integers, and concatenated to give a 64-bit number which becomes the new seed for the generator. If the second expression is omitted, it's treated as if it were the same as the first expression.

In terms of the C routine shown at the top of the page, & RND A,B sets both the x and w variables to A + 232 * B. The constant s is unchanged, not because it shouldn't be changed, but because choosing good values for it isn't quite trivial—it must be an odd number, and should have equal or nearly-equal numbers of 0 and 1 bits, well-scattered through the number. See below under Internal Variables to learn how to find s in memory if you want to POKE a new value into it.

If you want a truly random seed, finding 64 truly random bits for it will be a challenge. Asking the user to type something at the keyboard, and then looking at the keyboard input counter, can get you 16 random bits...if you need more than that, and can contrive an excuse to ask the user for input more than once, you can do something like this:

100  INPUT "What is your name? ";N$:A =  PEEK (78) + 256 *  PEEK (79)
110  INPUT "What is your quest? ";Q$:B =  PEEK (78) + 256 *  PEEK (79)
120  &  RND A,B

A point about reseeding to be aware of: Here are the first five values produced after & RND 0, and the first five values produced after & RND 1:

Note the resemblence in the first couple of rows. This can be expected to happen whenever two seeds differ by only a few bits—it takes a few iterations of USR to thoroughly mix the difference between the seeds. If this might be a problem for your program, try throwing away the first few values from USR after reseeding, for example,

 &  RND A,B: FOR ZZ = 1 to 5:R =  USR (1): NEXT

& RND 0,0 (or just & RND 0) will cause USR to duplicate the output of the C routine. When MSWSRAND is first installed, it behaves as if it were seeded by & RND 0,0.

& USR

 &  USR

This command points the USR vector at MSWSRAND's USR function handler. This is normally done by BRUN MSWSRAND, but since the USR vector can be used by only one handler at a time, this provides a way to reconnect MSWSRAND's USR handler after something else has usurped it.

& &

If other & handlers were installed before MSWSRAND, they remain available, and can be invoked as if MSWSRAND were not present, unless the prior command happens to have the same name as a MSWSRAND command. In that case, putting a second & in front of the command passes control to the prior handler.

The same convenience isn't available for USR, because it's not clear how to determine whether a USR call should be passed to another handler. At least with the & USR command, it's possible to reconnect MSWSRAND's handler if something else replaces it.

Internal Variables

For users who want to PEEK and POKE MSWSRAND's internal variables, a pointer to them is available. After using USR or any of the & statements (except & &), memory locations 6 and 7 point to the start of the buffer where MSWSRAND keeps the internal state of the generator. After saying (for example), X = USR (0):P = PEEK (6) + 256 * PEEK (7):