Need a good random number generator

[bpi...@gmail.com]

I've implemented a couple different methods so far, but both seem to be pseudo-random meaning that once I reboot the computer, the same exact series of numbers are repeated as the last time. Keep in mind I'm writing this program in assembly.

Below are the methods attempted so far:

Method 1:

lda num
asl a
bcc done
eor #$87
done sta num

Method 2:

Use the key-in page zero locations ($4e and $4f)

Thanks for your helps guys.

[Marco Verpelli]

You need a so called "seed" to initialize your random sequence.

An easy answer to your question: read Knut!!!

A little more easy: use AppleSoft ROM routine

The easiest answer: http://6502.org/source/

Marco

[qkumba]

But none of these suggestions provide a source for a seed, and the problem with using KEYIN is that it waits for a key.

[Marco Verpelli]

That's right.

But, can you find a suitable entropy source in the Apple// hardware?
Joystick/paddle/mouse?

Marco

[D Finnigan]

That's a good idea. Make the loading screen say "waddle your paddle" and
then get some seed from that.

[Michael J. Mahon]

All algorithms for generating "random numbers" by mathematical means can
only generate "pseudorandom" numbers. Given identical initial conditions,
they will generate precisely the same sequence.

The only way to obtain an unpredictable number to "seed" a sequence on an
Apple II is to request some user input. For example, when keyboard input is
requested, the ROM input routine increments a 16-bit value at high speed
while waiting for the user. This counter cycles rapidly enough that its
value is unpredictable after the input is received.

Input must be received again if another random number is needed, so many
games ask the user their name (or something) at the start, then use the
4E.4F value to "seed" a fast generator that produces subsequent
pseudorandom values.

RND accepts seed values, and it's "good enough" for some purposes. (But it
cycles after a few thousand calls.)

BTW, your first method produces a very low-quality sequence, and may not
satisfy your needs for unpredictability.
--
-michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

[Michael J. Mahon]

I second your suggestion--Knuth has an excellent treatment, and will
greatly increase your appreciation of the issues in constructing a
pseudorandom sequence generator.

The ROM version of RND gets into a short cycle after a few thousand calls,
so if you need high quality random numbers, use another generator.

[Michael J. Mahon]

Easier to "Hit a key".

[twalkowski]

Perhaps a random seed could be generated by a loop counter waiting for VBL'? Number of ticks till VBL' reached or something.

Just thinking out loud.

Tim

[Marco Verpelli]

Good thinking. Realtime clock (or more "soft" timer) can be used.

In my first answer I stressed the need of a better pseudorandom generator, a simply "shift-register + OR" don't produce a very long sequence also if you have a radioactive decay seed!

Marco

[John B. Matthews]

In article <b4dd9f3d-063e-415e...@googlegroups.com>,

bpi...@gmail.com wrote:

> I've implemented a couple different methods so far, but both seem to
> be pseudo-random meaning that once I reboot the computer, the same
> exact series of numbers are repeated as the last time. Keep in mind
> I'm writing this program in assembly.

Here's a transliteration of the Integer Basic random number generator
incorporated into Kyan Pascal & assembly. The MLI routine is rather
coarse, changing only once a minute. You could add RNDL/H at $4E/F,
which is updated by KEYIN at $FD1B.

procedure RndInit;
begin
#a
jsr _mli
db $82 ;get time
dw 0
lda $BF92
sta rnd
lda $BF93
and #$7F
sta rnd+1
#
end;
#a
rnd dw 0
#

function RndNext: integer;
begin
RndNext := 0;
#a
ldy #17 ;Wozniak lcg
rnd1 lda rnd+1
asl
clc
adc #$40
asl
rol rnd
rol rnd+1
dey
bne rnd1
ldy #5 ;return new value
lda rnd
sta (_sp),y
iny
lda rnd+1
sta (_sp),y
#
end;

function RndVal(min, max: integer): integer;
begin
Rndval := (abs(RndNext) mod (max - min + 1)) + min;
end;

--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

[Michael J. Mahon]

Been there, tried that.

At least on the //e and later machines, RESET resets the video generator as
well as the processor, so code runs the same way each time.

It's a deterministic machine.

[Michael J. Mahon]

Feedback shift register generators work well as long as they are long
enough (at least 32 bits) and the exclusive or bits are well chosen (see
Knuth or other references).

A real-time clock can provide a seed if it has enough low-order (sub
second) bits--hard to get for Apple clocks: non-standard and
low-resolution.

Again, if you plan to have *any* user interaction, the keyboard random
number counter is fine for seeding, and every Apple II has a keyboard! ;-)

[Egan Ford]

On 11/5/13 11:59 AM, Michael J. Mahon wrote:
> The only way to obtain an unpredictable number to "seed" a sequence on an
> Apple II is to request some user input. For example, when keyboard input is
> requested, the ROM input routine increments a 16-bit value at high speed
> while waiting for the user. This counter cycles rapidly enough that its
> value is unpredictable after the input is received.

I 2nd this. I did this for an Apple 1 game I wrote.

A combination timer and 32-bit random number seed generator:

.if CODESEG = 1
.segment "CODE1"
.endif

.export _getkey
.export _count
.export _key

KBDCR = $D011 ; Apple I got key?
KBDDATA = $D010 ; The key pressed

_count: .byte 0,0,0,0
_key: .byte 0

_getkey:
LDA KBDCR ; cycles 4 got key?
BMI DONE ; cycles 2 if neg, got key jmp DONE
CLC ; cycles 2 clear carry
LDA #1 ; cycles 2 A = 1
ADC _count+0 ; cycles 4 LSB += A
STA _count+0 ; cycles 4
LDA #0 ; cycles 2 A = 0
ROL A ; cycles 2 A = carry, carry = 0
ADC _count+1 ; cycles 4
STA _count+1 ; cycles 4
LDA #0 ; cycles 2 A = 0
ROL A ; cycles 2 A = carry, carry = 0
ADC _count+2 ; cycles 4
STA _count+2 ; cycles 4
LDA #0 ; cycles 2 A = 0
ROL A ; cycles 2 A = carry, carry = 0
ADC _count+3 ; cycles 4
STA _count+3 ; cycles 4
CLC ; cycles 2 clear carry
BCC _getkey ; cycles 2 + 1 back to checking for key
; total = 59
DONE: LDA KBDDATA ; get key value
AND #$7F ; 7th bit to 0
STA _key ; store in _key
RTS

[mmphosis]

http://6502.org/source/integers/random/random.html

[Michael J. Mahon]

mmphosis <mmph...@macgui.com> wrote:
> http://6502.org/source/integers/random/random.html

Since the fast version of this linear congruent oak generator allocates
1024 bytes to "multiply tables", it's worth pointing out that 1024 bytes
will support 32 parallel 256-bit shift registers for an excellent (and very
fast) feedback shift register generator.

In fact, allocating just 512 bytes for a 128-bit, 32-bit wide FSR is also
an excellent generator in the same number of cycles.

If space is an issue, as few as 32 32-bit array elements can be allocated,
requiring just 128 bytes (plus a little code to exclusive-or two "taps"
together and store them back into the array.

If you really only need 8-bit PRNs, then only 32 bytes of shift register
storage are needed. (And, of course, the exclusive-or only needs to work on
data 1-byte wide.)

In these parallel generators, no actual shifting is done--indexes into the
array locate the 0th bits and the two feedback bits.

[gid...@sasktel.net]

Random Numbers for Applesoft

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.
First, the flaws: 1) the initialization code fails to preset all five bytes of the
seed value (only the first four of five are loaded); 2) the RND code uses a
poor algorithm, and depends on "tweaks" to make the numbers more
random; 3) the RND code does not properly implement the algorithm it
appears to be aiming at.
BAD INITIALIZATION. The initialization code is at $F150 in the
Applesoft ROMs. This loop moves the CHRGET subroutine down to
$B1-C8, and is also supposed to copy the random number seed into $C9-
CD. The last byte does not get copied, due to a bug. Changing $F151
from $1C to $1D would fix it. Most of us don't really care about this bug,
because we are trying to get random numbers for games and the like, and
the more random the better: not copying the last byte could make the
numbers generated a little more random from one run to the next.
However, some applications in simulation programs require
REPEATABLE sequences of random numbers, so the effect of model
changes can be seen independent of the random number generator.
POOR ALGORITHM. Most generators use an algorithm which makes
the next random number by multiplying the previous one by a constant,
and adding another constant. The result is reduced by dividing by a third
constant and saving the remainder as the next random number. More on
this later. The proper choice of the three constants is critical. I am not sure
whether the Applesoft authors just made poor choices, or whether the bugs
mentioned below drove them to tweaking. Tweaking the generated value is
often thought to produce even more random results. In fact, according to
authorities like Donald Knuth, they almost always ruin the generator.
Applesoft tweaks the generated value by reversing the middle two bytes of
the 32-bit value. Guess what: it ruins the generator, assuming it was good
to start with.
BUGGY ALGORITHM. The congruency algorithm described in words
above will only work properly when integer arithmetic is used. Applesoft
uses floating point arithmetic. Further, Applesoft arithmetic routines expect
five-byte operands. For some reason the constants used in RND are only
four bytes long each. It appears that the exponents may have been omitted,
in the expectation that integer arithmetic was going to be used. You can
see the code for RND at $EFAE.
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.
Mathematicians have developed many sophisticated tests for random
number generators, but Applesoft fails even these simple ones! Depending
on the starting value, you can get the Applesoft generator in a loop. You
never get anywhere near the theoretically possible 4 billion different
values.
The Call APPLE article proposes a new algorithm. It comes with
impressive claims and credentials, but I have not found it to be better than
a properly implemented congruential algorithm. The algorithm multiplies
the previous seed by 8192, and takes the remainder after dividing by
67099547. This is a congruency algorithm:
X(n+1) = ( a * X(n) + c ) mod m

with a=8192, c=0, m=67099547
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. I also dug into some other references and came up
with another algorithm, from Knuth. It is also a congruency, but with
a=314159269, c=907633386, and m=2^32. This turns out to be easier to
compute, and according to Knuth it should be "better". "Better" is in
quotes because it is really hard to pin down what are the most important
properties. Anyway this one should have very good characteristics.
The RND function does three different things, depending on the argument.
You write something like R=RND(X). If X=0, you get the same number as
the previous use of RND produced. If X<0, the absolute value of X
becomes the new seed value. This allows you to control the sequence
when you wish, and also to randomize it somewhat by using a "random"
seed. If X>0, you get the next random number. The value will always be a
positive number less than 1. If you want to generate a number in a range,
you multiply by the width of the range and add the starting value. For
example, to generate a random integer between 1 and 10:
R = INT( RND(1)*10 ) + 1
The programs I have written build a little on the options available with
RND. They all begin with a little routine which hooks in the USR vector.
After executing this, you can write R=USR(X), in other words substitute
USR(X) anywhere you would have used RND(X). But I have added,
following the Call APPLE article, the option to automatically generate
integers in a range based at 0. If 0<X<2, you will get the next random
fraction. If X is 2 or greater than 2, you will get a random integer between
0 and X-1. Thus you can make a random integer between 1 and 10 like
this:
R = USR(10) + 1
as well as with:
R = INT (USR(1)*10) + 1
I wrote a third program which makes a 16-bit random value. This one uses
the seed at $4E and $4F which the Apple increments continuously
whenever the standard monitor input loop is waiting for an input
keystroke. Integer BASIC uses this seed, and as a result is quite valuable
in writing games. My new program gives you all the options stated above,
and is significantly quicker than any of the others. It uses a=19125,
c=13843, and m=2^16 in a standard congruency algorithm.
If you are seriously interested in random numbers, you need to read and
study Donald Knuth. Volume 2 of his series "The Art of Computer
Programming" is called "Seminumerical Algorithms". Chapter 3, pages 1-
160, is all about random numbers. (There is only one other chapter in this
volume, all about arithmetic in nearly 300 pages!) Knuth started the series
back in the 60's, with the goal of seven volumes covering most of what
programmers do. He finished the first three by 1972, went back and
revised the first one, and then evidently got sidetracked into typesetting
(several books around a typesetting language he calls "Tex").
Speaking of being sidetracked...!
Knuth ends his chapter with a list of four rules for selecting a, c, and m for
congruency algorithms. Let me summarize those rules here:
1. The number m is conveniently taken as the word size. In Applesoft, the
floating point mantissa is 32 bits; hence, I chose m=2^32.
2. If m is a power of 2 (and mine is), pick "a" so that "a mod 8 = 5". This,
together with the rules on choosing c below, ensure that all m values will
produced before the series repeats.
3. Pick "a" between m/100 and m-sqrt(m). The binary digits should NOT
have a simple, regular pattern. Knuth recommends taking some haphazard
constant, such as a=3131492621.
4. "c" should be odd, and preferably near "m*.2113248654".
Now for the program listings.
The first listing is for my rendition of Call APPLE's algorithm. Lines
1220-1280 link in the USR vector. Lines 1370-1450 branch according to
the value of the argument of the USR function. If the argument is negative,
lines 1550-1620 set up its absolute value as the new seed. If the argument
is zero, the old seed is used without change, lines 1420-1450. If positive
non-zero, lines 1470-1490 set up the argument as the RANGE.
Lines 1640-1690 calculate the new seed, which will be 8192 times the old
seed, modulo 67099547. 8192 is 2^13, so we can multiply be 13 left shifts.
After each shift, if the result is bigger than 67099547, we subtract that
value and keep the remainder. The final result will be some number smaller
than 67099547.
Lines 1700-1770 save the new seed, and then divide it by 67099547 to get
a fraction for the USR function result. Lines 1780-1860 check the initial
argument to see if you wanted a fraction between 0 and 1, or an integer
between 0 and arg-1. If the latter, the fraction is multiplied by the range
and reduced to an integer.
The subroutine named MODULO subtracts 67099547 from the seed value
if it would leave a positive remainder, and then renormalizes the result into
floating point.
Line 2270 defines the initial seed after loading the program to be 1.0. If
you want some other seed, change this line or be sure to seed it with
R=USR(-seed) in your Applesoft program.
1000 *--------------------------------
1010 *SAVE S.USRND S-C
1020 *--------------------------------
1030 * FROM CALL APPLE, JAN 1983, PAGE 29-34
1040 *--------------------------------
1050 .OR $300
1060 .TF B.USRND
1070 *--------------------------------
1080 NORMALIZE.FAC .EQ $E82E
1090 FMUL.FAC.BY.YA .EQ $E97F
1100 LOAD.ARG.FROM.YA .EQ $E9E3
1110 FDIV.ARG.BY.YA .EQ $EA5C
1120 LOAD.FAC.FROM.YA .EQ $EAF9
1130 STORE.FAC.AT.YX.ROUNDED .EQ $EB2B
1140 COPY.FAC.TO.ARG .EQ $EB66
1150 AS.INT .EQ $EC23
1160 *--------------------------------
1170 USER.VECTOR .EQ $0A THRU $0C
1180 FAC .EQ $9D THRU $A2
1190 FAC.SIGN .EQ $A2
1200 CNTR .EQ $A5
1210 *--------------------------------
1220 LINK LDA #$4C "JMP" OPCODE
1230 STA USER.VECTOR
1240 LDA #RANDOM
1250 STA USER.VECTOR+1
1260 LDA /RANDOM
1270 STA USER.VECTOR+2
1280 RTS
1290 *--------------------------------
1300 * R = USR (X)
1310 * IF X < 0 THEN RESEED WITH ABS(X)
1320 * IF X = 0 THEN R = REPEAT OF PREVIOUS
VALUE
1330 * IF 0 < X < 2 THEN GENERATE NEXT SEED
AND RETURN
1340 * 0 <= R < 1
1350 * IF X >= 2 THEN R = INT(RND*X)
1360 *--------------------------------
1370 RANDOM
1380 LDA FAC.SIGN CHECK FOR RESEEDING
1390 BMI .2 ...YES
1400 LDA FAC CHECK FOR X=0
1410 BNE .1 ...NO, X=RANGE
1420 LDA #SEED
1430 LDY /SEED
1440 JSR LOAD.ARG.FROM.YA
1450 JMP .5
1460 *---X --> RANGE------------------
1470 .1 LDX #RANGE
1480 LDY /RANGE
1490 JSR STORE.FAC.AT.YX.ROUNDED $EB2B
1500 *---SEED --> FAC-----------------
1510 LDA #SEED
1520 LDY /SEED
1530 JSR LOAD.FAC.FROM.YA $EAF9
1540 *---PREPARE SEED-----------------
1550 .2 LDA #0 MAKE SEED POSITIVE
1560 STA FAC.SIGN
1570 LDA FAC LIMIT SEED TO 67099547
1580 CMP #$9A
1590 BCC .3
1600 LDA #$9A
1610 STA FAC
1620 JSR MODULO
1630 *---(8192*SEED) MOD 67099547-----
1640 .3 LDA #13
1650 STA CNTR
1660 .4 INC FAC
1670 JSR MODULO
1680 DEC CNTR
1690 BNE .4
1700 *---SEED/67099547----------------
1710 LDX #SEED
1720 LDY /SEED
1730 JSR STORE.FAC.AT.YX.ROUNDED
1740 JSR COPY.FAC.TO.ARG $EB66
1750 .5 LDA #FLT67
1760 LDY /FLT67
1770 JSR FDIV.ARG.BY.YA $EA5C
1780 *---SCALE TEST-------------------
1790 LDA RANGE
1800 CMP #$82 IS RANGE BETWEEN ZERO AND
ONE?
1810 BCC .6 ...YES
1820 *---SCALE------------------------
1830 LDA #RANGE
1840 LDY /RANGE
1850 JSR FMUL.FAC.BY.YA $E97F
1860 JSR AS.INT $EC23
1870 *---RETURN-----------------------
1880 .6 RTS
1890 *--------------------------------
1900 MODULO
1910 LDY #0
1920 LDA FAC
1930 CMP #$9A
1940 BCC .3 < 67099547
1950 BEQ .1 67099547...
1960 LDY #4
1970 .1 SEC
1980 LDA FAC+4 LSB
1990 SBC MAN67+3,Y
2000 PHA
2010 LDA FAC+3
2020 SBC MAN67+2,Y
2030 PHA
2040 LDA FAC+2
2050 SBC MAN67+1,Y
2060 PHA
2070 LDA FAC+1
2080 SBC MAN67+0,Y
2090 PHA
2100 BCC .2 <67099547
2110 PLA
2120 STA FAC+1
2130 PLA
2140 STA FAC+2
2150 PLA
2160 STA FAC+3
2170 PLA
2180 STA FAC+4
2190 JMP NORMALIZE.FAC $E82E
2200 .2 PLA
2210 PLA
2220 PLA
2230 PLA
2240 .3 RTS
2250 *--------------------------------
2260 RANGE .HS 81.00000000
2270 SEED .HS 81.00000000
2280 FLT67 .HS 9A.7FF6E6C0 = 67,099,547
2290 MAN67 .HS FFF6E6C0
2300 .HS 7FFB7360
2310 *--------------------------------

The second listing is for my 32-bit algorithm based on Knuth's rules.
Again, lines 1210-1270 set up the USR linkage. Lines 1360-1400 decide
what kind of argument has been used. If negative, lines 1470-1590 prepare
a new seed value. If zero, the previous value is re-used. If positive, the
argument is the range.
In this version the seed is maintained as a 32-bit integer. Lines 1470-1590
convert from the floating point form of the argument in FAC to the integer
form in SEED. If the argument happens to be bigger than 2^32, I simply
force the exponent to 2^32.
Lines 1600-1690 form the next seed by multiplying by 314159269 and
adding 907633386. The calculation is done in a somewhat tricky way.
Essentially it involves loading 907633386 into the product register, and
then adding the partial products of 314159269*seed to that register. The
tricks allow me to do all that with a minimum of program and variable
space, and I hope with plenty of speed. I understood it all this morning, but
it is starting to get hazy now. If you really need a detailed explanation, call
me some day. The modulo 2^32 part is automatic, because bits beyond 32
are thrown away.
Lines 1700-1780 load the seed value into FAC and convert it to a floating
point fraction.
Lines 1790-1870 check the range requested. If less than 2, the fraction is
returned as the USR result. If 2 or more, the fraction is multiplied by the
range and integerized.
1000 *--------------------------------
1010 *SAVE S.RANDOM KNUTH
1020 *--------------------------------
1030 * FROM KNUTH'S "THE ART OF COMPUTER
PROGRAMMING"
1040 * VOLUME 2, PAGES 155-157.
1050 *--------------------------------
1060 .OR $300
1070 .TF B.RANDOM KNUTH
1080 *--------------------------------
1090 NORMALIZE.FAC .EQ $E82E
1100 FMUL.FAC.BY.YA .EQ $E97F
1110 STORE.FAC.AT.YX.ROUNDED .EQ $EB2B
1120 AS.QINT .EQ $EBF2
1130 AS.INT .EQ $EC23
1140 *--------------------------------
1150 USER.VECTOR .EQ $0A THRU $0C
1160 FAC .EQ $9D THRU $A2
1170 FAC.SIGN .EQ $A2
1180 FAC.EXTENSION .EQ $AC
1190 AS.SEED .EQ $CA THRU $CD
1200 *--------------------------------
1210 LINK LDA #$4C "JMP" OPCODE
1220 STA USER.VECTOR
1230 LDA #RANDOM
1240 STA USER.VECTOR+1
1250 LDA /RANDOM
1260 STA USER.VECTOR+2
1270 RTS
1280 *--------------------------------
1290 * R = USR (X)
1300 * IF X < 0 THEN RESEED WITH ABS(X)
1310 * IF X = 0 THEN R = REPEAT OF PREVIOUS
VALUE
1320 * IF 0 < X < 2 THEN GENERATE NEXT SEED
AND RETURN
1330 * 0 <= R < 1
1340 * IF X >= 2 THEN R = INT(RND*X)
1350 *--------------------------------
1360 RANDOM
1370 LDA FAC.SIGN CHECK FOR RESEEDING
1380 BMI .1 ...YES
1390 LDA FAC CHECK FOR X=0
1400 BEQ .6 ...YES, REUSE LAST NUMBER
1410 *---X --> RANGE------------------
1420 LDX #RANGE
1430 LDY /RANGE
1440 JSR STORE.FAC.AT.YX.ROUNDED $EB2B
1450 JMP .4
1460 *---PREPARE SEED-----------------
1470 .1 LDA #0 MAKE SEED POSITIVE
1480 STA FAC.SIGN
1490 LDA FAC LIMIT SEED TO 2^32-1
1500 CMP #$A0
1510 BCC .2
1520 LDA #$A0
1530 STA FAC
1540 .2 JSR AS.QINT $EBF2
1550 LDX #3 COPY FAC INTO SEED
1560 .3 LDA FAC+1,X
1570 STA SEED,X
1580 DEX
1590 BPL .3
1600 *---SEED*314159269+907633386-----
1610 .4 LDX #0
1620 .5 LDA SEED,X
1630 STA MULTIPLIER
1640 LDA C,X
1650 STA SEED,X
1660 JSR MULTIPLY
1670 INX
1680 CPX #4
1690 BCC .5
1700 *---LOAD SEED INTO FAC-----------
1710 .6 LDX #5
1720 .7 LDA FLT.SEED,X
1730 STA FAC,X
1740 DEX
1750 BPL .7
1760 LDA #0
1770 STA FAC.EXTENSION
1780 JSR NORMALIZE.FAC
1790 *---SCALE TEST-------------------
1800 LDA RANGE
1810 CMP #$82 IS RANGE BETWEEN ZERO AND
ONE?
1820 BCC .8 ...YES
1830 *---SCALE------------------------
1840 LDA #RANGE
1850 LDY /RANGE
1860 JSR FMUL.FAC.BY.YA $E97F
1870 JSR AS.INT $EC23
1880 *---RETURN-----------------------
1890 .8 RTS
1900 *--------------------------------
1910 MULTIPLY
1920 STX BYTE.CNT
1930 LDY #3
1940 .1 LDA A,Y
1950 STA MULTIPLICAND,X
1960 DEY
1970 DEX
1980 BPL .1
1990 LDY #8
2000 BNE .2 ...ALWAYS
2010 *--------------------------------
2020 .5 CLC DOUBLE THE MULTIPLICAND
2030 .6 ROL MULTIPLICAND,X
2040 DEX
2050 BPL .6
2060 .2 LSR MULTIPLIER
2070 BCC .4
2080 LDX BYTE.CNT
2090 CLC
2100 .3 LDA MULTIPLICAND,X
2110 ADC SEED,X
2120 STA SEED,X
2130 DEX
2140 BPL .3
2150 .4 LDX BYTE.CNT
2160 DEY
2170 BNE .5
2180 RTS
2190 *--------------------------------
2200 RANGE .HS 81.00000000
2210 FLT.SEED .HS 80
2220 SEED .HS 00.00.00.00
2230 .HS 00 SIGN
2240 A .HS 12.B9.B0.A5 314159269
2250 C .HS 36.19.62.EB 907633386
2260 MULTIPLIER .BS 1
2270 MULTIPLICAND .BS 4
2280 BYTE.CNT .BS 1
2290 *--------------------------------

The third listing is cut down from the second one, to produce a 16-bit
random number. The code is very similar to the program above, so I will
not describe it line-by-line. If you want an optimized version of this, the
multiply especially could be shortened.
1000 *--------------------------------
1010 *SAVE S.RANDOM KEYIN
1020 *--------------------------------
1030 * ALLOWS ACCESS TO THE KEYIN RANDOM VALUE
1040 *--------------------------------
1050 .OR $300
1060 .TF B.RANDOM KEYIN
1070 *--------------------------------
1080 NORMALIZE.FAC .EQ $E82E
1090 FMUL.FAC.BY.YA .EQ $E97F
1100 STORE.FAC.AT.YX.ROUNDED .EQ $EB2B
1110 AS.QINT .EQ $EBF2
1120 AS.INT .EQ $EC23
1130 *--------------------------------
1140 USER.VECTOR .EQ $0A THRU $0C
1150 FAC .EQ $9D THRU $A2
1160 FAC.SIGN .EQ $A2
1170 FAC.EXTENSION .EQ $AC
1180 KEY.SEED .EQ $4E,4F
1190 *--------------------------------
1200 LINK LDA #$4C "JMP" OPCODE
1210 STA USER.VECTOR
1220 LDA #RANDOM
1230 STA USER.VECTOR+1
1240 LDA /RANDOM
1250 STA USER.VECTOR+2
1260 RTS
1270 *--------------------------------
1280 * R = USR (X)
1290 * IF X < 0 THEN RESEED WITH ABS(X)
1300 * IF X = 0 THEN R = REPEAT OF PREVIOUS
VALUE
1310 * IF 0 < X < 2 THEN GENERATE NEXT SEED
AND RETURN
1320 * 0 <= R < 1
1330 * IF X >= 2 THEN R = INT(RND*X)
1340 *--------------------------------
1350 RANDOM
1360 LDA FAC.SIGN CHECK FOR RESEEDING
1370 BMI .1 ...YES
1380 LDA FAC CHECK FOR X=0
1390 BEQ .6 ...YES, REUSE LAST NUMBER
1400 *---X --> RANGE------------------
1410 LDX #RANGE
1420 LDY /RANGE
1430 JSR STORE.FAC.AT.YX.ROUNDED $EB2B
1440 JMP .4
1450 *---PREPARE SEED-----------------
1460 .1 LDA #0 MAKE SEED POSITIVE
1470 STA FAC.SIGN
1480 LDA FAC LIMIT SEED TO 2^16-1
1490 CMP #$90
1500 BCC .2
1510 LDA #$90
1520 STA FAC
1530 .2 JSR AS.QINT $EBF2
1540 LDA FAC+3
1550 STA KEY.SEED
1560 LDA FAC+4
1570 STA KEY.SEED+1
1580 *---SEED*19125+13843-------------
1590 .4 LDX #0
1600 .5 LDA KEY.SEED,X
1610 STA MULTIPLIER
1620 LDA C,X
1630 STA KEY.SEED,X
1640 JSR MULTIPLY
1650 INX
1660 CPX #2
1670 BCC .5
1680 *---LOAD SEED INTO FAC-----------
1690 .6 LDA #0
1700 STA FAC+3
1710 STA FAC+4
1720 STA FAC.SIGN
1730 STA FAC.EXTENSION
1740 LDA #$80
1750 STA FAC
1760 LDA KEY.SEED
1770 STA FAC+1
1780 LDA KEY.SEED+1
1790 STA FAC+2
1800 JSR NORMALIZE.FAC
1810 *---SCALE TEST-------------------
1820 LDA RANGE
1830 CMP #$82 IS RANGE BETWEEN ZERO AND
ONE?
1840 BCC .8 ...YES
1850 *---SCALE------------------------
1860 LDA #RANGE
1870 LDY /RANGE
1880 JSR FMUL.FAC.BY.YA $E97F
1890 JSR AS.INT $EC23
1900 *---RETURN-----------------------
1910 .8 RTS
1920 *--------------------------------
1930 MULTIPLY
1940 STX BYTE.CNT
1950 LDY #1
1960 .1 LDA A,Y
1970 STA MULTIPLICAND,X
1980 DEY
1990 DEX
2000 BPL .1
2010 LDY #8
2020 BNE .2 ...ALWAYS
2030 *--------------------------------
2040 .5 CLC DOUBLE THE MULTIPLICAND
2050 .6 ROL MULTIPLICAND,X
2060 DEX
2070 BPL .6
2080 .2 LSR MULTIPLIER
2090 BCC .4
2100 LDX BYTE.CNT
2110 CLC
2120 .3 LDA MULTIPLICAND,X
2130 ADC KEY.SEED,X
2140 STA KEY.SEED,X
2150 DEX
2160 BPL .3
2170 .4 LDX BYTE.CNT
2180 DEY
2190 BNE .5
2200 RTS
2210 *--------------------------------
2220 RANGE .HS 81.00000000
2230 A .DA /19125,#19125
2240 C .DA /13843,#13843
2250 MULTIPLIER .BS 1
2260 MULTIPLICAND .BS 2
2270 BYTE.CNT .BS 1
2280 *--------------------------------

What do you do if you want even more randomness than you can get from
one generator? You can use two together. The best way (for greatest
randomness) is to use one to select values from a table produced by the
other. First generate, say 50 or 100, random values with one generator. The
generate a random value with the second generator and use it to pick one
of the 50 or 100 values. That picked value is the first number to use. Then
replace the picked value with a new value from the first generator. Pick
another value randomly using the second generator, and so on. This is
analogous to two people working together. The first person picks a bowlful
at random from the universe. The second person picks items one at a time
from the bowl. The first person keeps randomly picking from the universe
to replace the items removed from the bowl by the second person.
You could use the 16-bit generator to pick values from a "bowl" kept full
by my 32-bit generator.
Now back to those tests mentioned at the beginning. I am happy to report
that all three of the algorithms listed above completely fill the hi-res screen,
no holes left, eventually.
By the way, the August 1981 AAL contained an article about the Integer
BASIC RND function, and how to use it from assembly language.

[Michael J. Mahon]

Beautiful!

Thanks for the thorough explanation and the algorithms!

[gid...@sasktel.net]

> Beautiful!

hanks for the thorough explanation and the algorithms!

> -michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

My apologies. This article is not mine. I didn't realize it used the word "I" in it quite a bit. It is just part of my collection. I believe it was written by Bob Sander-Cederlof.

[gid...@sasktel.net]

> Beautiful!

hanks for the thorough explanation and the algorithms!

> -michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

[mmphosis]

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

[Michael J. Mahon]

In that case, thanks for pointing it out! ;-)
--