Groups > comp.sys.apple2.programmer > #944 > unrolled thread

Need a good random number generator

Started by	bpicchi@gmail.com
First post	2013-11-05 08:25 -0800
Last post	2014-02-03 12:00 -0800
Articles	20 on this page of 22 — 10 participants

Back to article view | Back to comp.sys.apple2.programmer

  Need a good random number generator bpicchi@gmail.com - 2013-11-05 08:25 -0800
    Re: Need a good random number generator Marco Verpelli <mverpelli@libero.it> - 2013-11-05 09:28 -0800
      Re: Need a good random number generator qkumba <peter.ferrie@gmail.com> - 2013-11-05 10:26 -0800
        Re: Need a good random number generator Marco Verpelli <mverpelli@libero.it> - 2013-11-05 10:45 -0800
          Re: Need a good random number generator D Finnigan <dog_cow@macgui.com> - 2013-11-05 18:55 +0000
            Re: Need a good random number generator Michael J. Mahon <mjmahon@aol.com> - 2013-11-05 13:02 -0600
      Re: Need a good random number generator Michael J. Mahon <mjmahon@aol.com> - 2013-11-05 12:59 -0600
    Re: Need a good random number generator Michael J. Mahon <mjmahon@aol.com> - 2013-11-05 12:59 -0600
      Re: Need a good random number generator twalkowski <twalkowski32@att.net> - 2013-11-05 11:18 -0800
        Re: Need a good random number generator Marco Verpelli <mverpelli@libero.it> - 2013-11-05 12:43 -0800
          Re: Need a good random number generator Michael J. Mahon <mjmahon@aol.com> - 2013-11-05 23:34 -0600
        Re: Need a good random number generator Michael J. Mahon <mjmahon@aol.com> - 2013-11-05 23:34 -0600
      Re: Need a good random number generator Egan Ford <datajerk@gmail.com> - 2013-11-06 20:45 -0700
    Re: Need a good random number generator "John B. Matthews" <nospam@nospam.invalid> - 2013-11-05 23:26 -0500
    Re: Need a good random number generator  mmphosis <mmphosis@macgui.com> - 2013-11-09 00:38 +0000
      Re: Need a good random number generator Michael J. Mahon <mjmahon@aol.com> - 2013-11-08 20:19 -0600
    Re: Need a good random number generator gids.rs@sasktel.net - 2014-02-03 08:53 -0800
      Re: Need a good random number generator Michael J. Mahon <mjmahon@aol.com> - 2014-02-03 12:21 -0600
        Re: Need a good random number generator gids.rs@sasktel.net - 2014-02-03 12:00 -0800
          Re: Need a good random number generator  mmphosis <mmphosis@macgui.com> - 2014-02-03 22:26 +0000
          Re: Need a good random number generator Michael J. Mahon <mjmahon@aol.com> - 2014-02-03 20:51 -0600
        Re: Need a good random number generator gids.rs@sasktel.net - 2014-02-03 12:00 -0800

Page 1 of 2 [1] 2 Next page →

#944 — Need a good random number generator

From	bpicchi@gmail.com
Date	2013-11-05 08:25 -0800
Subject	Need a good random number generator
Message-ID	<b4dd9f3d-063e-415e-80d8-23af11a06118@googlegroups.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.

[toc] | [next] | [standalone]

#945

From	Marco Verpelli <mverpelli@libero.it>
Date	2013-11-05 09:28 -0800
Message-ID	<8be81ea3-4556-4b1e-9d6e-fd454f793222@googlegroups.com>
In reply to	#944

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

[toc] | [prev] | [next] | [standalone]

#946

From	qkumba <peter.ferrie@gmail.com>
Date	2013-11-05 10:26 -0800
Message-ID	<9aa8d498-e9c2-49c7-8c75-5d0a48dfcaae@googlegroups.com>
In reply to	#945

> 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/

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

[toc] | [prev] | [next] | [standalone]

#947

From	Marco Verpelli <mverpelli@libero.it>
Date	2013-11-05 10:45 -0800
Message-ID	<5acc7bac-e622-45e3-a5ff-c79fc6a97847@googlegroups.com>
In reply to	#946

That's right.

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

Marco

[toc] | [prev] | [next] | [standalone]

#948

From	D Finnigan <dog_cow@macgui.com>
Date	2013-11-05 18:55 +0000
Message-ID	<dog_cow-1383677722@macgui.com>
In reply to	#947

Marco Verpelli wrote:
> That's right.
> 
> But, can you find a suitable entropy source in the Apple// hardware?
> Joystick/paddle/mouse?

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

[toc] | [prev] | [next] | [standalone]

#951

From	Michael J. Mahon <mjmahon@aol.com>
Date	2013-11-05 13:02 -0600
Message-ID	<436341429405370940.563715mjmahon-aol.com@news.giganews.com>
In reply to	#948

D Finnigan <dog_cow@macgui.com> wrote:
> Marco Verpelli wrote:
>> That's right.
>> 
>> But, can you find a suitable entropy source in the Apple// hardware?
>> Joystick/paddle/mouse?
> 
> That's a good idea. Make the loading screen say "waddle your paddle" and
> then get some seed from that.

Easier to "Hit a key". 
-- 
-michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

[toc] | [prev] | [next] | [standalone]

#950

From	Michael J. Mahon <mjmahon@aol.com>
Date	2013-11-05 12:59 -0600
Message-ID	<895934490405369623.547422mjmahon-aol.com@news.giganews.com>
In reply to	#945

Marco Verpelli <mverpelli@libero.it> wrote:
> 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

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 - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

[toc] | [prev] | [next] | [standalone]

#949

From	Michael J. Mahon <mjmahon@aol.com>
Date	2013-11-05 12:59 -0600
Message-ID	<1386909187405369875.245751mjmahon-aol.com@news.giganews.com>
In reply to	#944

<bpicchi@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. 
> 
> 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.

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

[toc] | [prev] | [next] | [standalone]

#952

From	twalkowski <twalkowski32@att.net>
Date	2013-11-05 11:18 -0800
Message-ID	<d33c034c-bedc-4a6b-9fa8-6ab2ad0672cf@googlegroups.com>
In reply to	#949

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

[toc] | [prev] | [next] | [standalone]

#953

From	Marco Verpelli <mverpelli@libero.it>
Date	2013-11-05 12:43 -0800
Message-ID	<0f83052b-5927-4d0a-b29e-b474b8adc95e@googlegroups.com>
In reply to	#952

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

[toc] | [prev] | [next] | [standalone]

#956

From	Michael J. Mahon <mjmahon@aol.com>
Date	2013-11-05 23:34 -0600
Message-ID	<772532650405408286.138775mjmahon-aol.com@news.giganews.com>
In reply to	#953

Marco Verpelli <mverpelli@libero.it> wrote:
> 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

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!  ;-)
-- 
-michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

[toc] | [prev] | [next] | [standalone]

#955

From	Michael J. Mahon <mjmahon@aol.com>
Date	2013-11-05 23:34 -0600
Message-ID	<716716327405408110.004893mjmahon-aol.com@news.giganews.com>
In reply to	#952

twalkowski <twalkowski32@att.net> wrote:
> 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

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 - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

[toc] | [prev] | [next] | [standalone]

#957

From	Egan Ford <datajerk@gmail.com>
Date	2013-11-06 20:45 -0700
Message-ID	<l5f2cn$si5$1@news.xmission.com>
In reply to	#949

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

[toc] | [prev] | [next] | [standalone]

#954

From	"John B. Matthews" <nospam@nospam.invalid>
Date	2013-11-05 23:26 -0500
Message-ID	<nospam-4E4D38.23264805112013@news.aioe.org>
In reply to	#944

In article <b4dd9f3d-063e-415e-80d8-23af11a06118@googlegroups.com>,
 bpicchi@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>

[toc] | [prev] | [next] | [standalone]

#959

From	mmphosis <mmphosis@macgui.com>
Date	2013-11-09 00:38 +0000
Message-ID	<mmphosis-1383957509@macgui.com>
In reply to	#944

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

[toc] | [prev] | [next] | [standalone]

#960

From	Michael J. Mahon <mjmahon@aol.com>
Date	2013-11-08 20:19 -0600
Message-ID	<1030242042405655615.208521mjmahon-aol.com@news.giganews.com>
In reply to	#959

mmphosis <mmphosis@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. 
-- 
-michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

[toc] | [prev] | [next] | [standalone]

#1141

From	gids.rs@sasktel.net
Date	2014-02-03 08:53 -0800
Message-ID	<a6165382-e075-485a-a1c2-bde7d83e8a0c@googlegroups.com>
In reply to	#944

On Tuesday, November 5, 2013 10:25:12 AM UTC-6, 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. 

> 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.



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.

[toc] | [prev] | [next] | [standalone]

#1142

From	Michael J. Mahon <mjmahon@aol.com>
Date	2014-02-03 12:21 -0600
Message-ID	<874540624413143984.132529mjmahon-aol.com@news.giganews.com>
In reply to	#1141

<gids.rs@sasktel.net> wrote:
> On Tuesday, November 5, 2013 10:25:12 AM UTC-6, 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. 
> 
>> 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.
> 
> 
> 
> 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.

Beautiful!

Thanks for the thorough explanation and the algorithms!
-- 
-michael - NadaNet 3.1 and AppleCrate II: http://home.comcast.net/~mjmahon

[toc] | [prev] | [next] | [standalone]

#1143

From	gids.rs@sasktel.net
Date	2014-02-03 12:00 -0800
Message-ID	<08018438-f4d9-4c2e-840f-2eabb0a0ff00@googlegroups.com>
In reply to	#1142

> 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.

[toc] | [prev] | [next] | [standalone]

#1146

From	mmphosis <mmphosis@macgui.com>
Date	2014-02-03 22:26 +0000
Message-ID	<mmphosis-1391466364@macgui.com>
In reply to	#1143

gids.rs wrote:
>> 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.
>

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2 [1] 2 Next page →

csiph-web

Need a good random number generator

Contents

#944 — Need a good random number generator

#945

#946

#947

#948

#951

#950

#949

#952

#953

#956

#955

#957

#954

#959

#960

#1141

#1142

#1143

#1146