Apple II Random Number Generator

by David Empson



There was a series of articles published many years ago, which described
a cyclic shift/XOR-based random number generator.  It was published in
The Sourceror's Apprentice, Volume 1 Number 4 (April 1989).  The article
was called "Random Bytes", and was written by Robert C Moore of the Applied
Physics Laboratory at the John Hopkins University in Laurel, Maryland.

The method generates 8-bit random numbers from a 32-bit seed variable, and
has a repeat period of 2^32-1 (4194962795).  The seed can be any value 
except zero, and could be derived from memory locations $4E and $4F, which
are incremented continuously while the system is waiting for a keypress
(with the standard monitor routines, as used by GET and INPUT from BASIC).

I've used this algorithm on various other processors, and it seems to
work well, as long as it is seeded correctly.


The article covers two designs for shift and exclusive OR random number
generators.  I'll used the simpler one here, which has a shorter period
of 2^25-1 (33554431).

To use this routine you need a four bytes to hold a the random number
seed.  I'll use memory locations $3C1 through $3C4 for the random number
working variable.  The variable is stored in little-endian order (low
order byte first).  After each call to the RANDOM routine, the new
random 8-bit number can be taken from the first byte of the variable (at
$03CC).  If you need a random number larger than 8 bits, it is necessary
to call the RANDOM routine once for each 8-bit result.  Don't try to use
the values stored in the second, third or fourth byte of the variable.

Before this routine can be used, the random number variable must be
seeded from an appropriate source, with a 25-bit to 32-bit value which
can be anything except zero.  (You will always get the same sequence of
results if you use the same seed value each time.)

If you can only provide a shorter seed value (e.g. 16 bits), then it is
a good idea to "kick start" the random number generator by generating
several random numbers before you start to use the result (otherwise you
are likely to get several zero bytes for the first few "random"
numbers).


Here is my Apple II random number routine in source form:


R1       EQU $03CC
R2       EQU $03CD
R3       EQU $03CE
R4       EQU $03CF

RANDOM   ROR R4           ; Bit 25 to carry
         LDA R3           ; Shift left 8 bits
         STA R4
         LDA R2
         STA R3
         LDA R1
         STA R2
         LDA R4           ; Get original bits 17-24
         ROR              ; Now bits 18-25 in ACC
         ROL R1           ; R1 holds bits 1-7
         EOR R1           ; Seven bits at once
         ROR R4           ; Shift right by one bit
         ROR R3
         ROR R2
         ROR
         STA R1
         RTS

Here is a routine to seed the random number generator with a reasonable
initial value:

INITRAND LDA $4E          ; Seed the random number generator
         STA R1           ; based on delay between keypresses
         STA R3
         LDA $4F
         STA R2
         STA R4
         LDX #$20         ; Generate a few random numbers
INITLOOP JSR RANDOM       ; to kick things off
         DEX
         BNE INITLOOP
         RTS

Now to wrap this in a "fill the hi-res graphics screen" routine:

NOISEGEN JSR INITRAND     ; Seed the random number generator
         LDA #$00
         STA $3C          ; Borrow monitor variables for a pointer
         LDA #$20
         STA $3D
         LDY #$00         ; Initialize the offset
         LDX #$20         ; and the page count
FILLLOOP JSR RANDOM
         STA ($3C),Y
         INY
         BNE FILLLOOP
         INC $3D
         DEX
         BNE FILLLOOP
         RTS

Converting this to machine code, I'll put the NOISEGEN routine at $0300,
the INITRAND routine at $0320, and the RANDOM routine at $0340.  Here
are the monitor commands necessary to enter this program into memory:

0300:20 20 03 A9 00 85 3C A9 20 85 3D A0 00 A2 20 20
0310:40 03 91 3C C8 D0 F8 E6 3D CA D0 F3 60 EA EA EA

0320:A5 4E 8D C1 03 8D C3 03 A5 4F 8D C2 03 8D C4 03
0330:A2 20 20 40 03 CA D0 FA 60 EA EA EA EA EA EA EA

0340:6E C4 03 AD C3 03 8D C4 03 AD C2 03 8D C3 03 AD
0350:C1 03 8D C2 03 AD C4 03 6A 2E C1 03 4D C1 03 6E
0360:C4 03 6E C3 03 6E C2 03 6A 8D C1 03 60


If you want to save the whole thing, use:

BSAVE NOISEGEN,A$300,L$6D


Note: This routine doesn't have any connection to the Applesoft
      BASIC RND() function.


I've tried it out on my IIgs, and it seems to work fine.  With the
system set to Normal speed (1 MHz), it takes about 1 second to fill the
screen, which is somewhat slower than the clear screen routine, but not
enough to worry about.  It looks pretty random to me.

Note that if you want to do this again (getting a different pattern),
you should avoid calling INITRAND more than once.

You can use CALL 800 to call the INITRAND routine directly, then use
CALL 771 for each random fill.

If you only need to use it once, just CALL 768.