Newsgroups: comp.sys.apple2.programmer
Path: news.uiowa.edu!news.physics.uiowa.edu!math.ohio-state.edu!howland.reston.ans.net!swrinde!newsfeed.internetmci.com!news.dacom.co.kr!news.uoregon.edu!waikato!comp.vuw.ac.nz!actrix.gen.nz!dempson
From: dempson@atlantis.actrix.gen.nz (David Empson)
Subject: Re: random numbers
Message-ID:
Sender: news@actrix.gen.nz (News Administrator)
Organization: Actrix - Internet Services
Date: Thu, 4 Jan 1996 06:39:19 GMT
References: <3m6rro$sg3@tuba.cit.cornell.edu> <8B8044B.005A0001FF.uuout@pcwash.com>
X-Nntp-Posting-Host: atlantis.actrix.gen.nz
Lines: 68
In article <8B8044B.005A0001FF.uuout@pcwash.com>,
TOM LARSON wrote:
> Hello,
>
> I'm looking for a new random number methodology :).
>
> This isn't mission-critical code but I'd like it to be a bit more evenly
> distributed than I've gotten. Currently this is how I do it:
>
> The random number (unsigned 16 bit int) is generated by a counter that it
> incremented while the system is waiting for input.
Ick. Bad move, especially if the random numbers tend to be needed at
regular intervals, or short times governed by the response time of a user.
You probably want a simple pseudo-random number generator. Most of
these are based on the principle of taking a large seed value (usually
32 bits), and generating a sequence of 16-bit numbers by multiplying
the seed by a large integer, adding another large integer, then taking
the high order word of the result.
Another solution is much simpler to implement on the 6502. There was
an article in "The Sourceror's Apprentice", which was an Apple II
assembly language programming magazine that eventually merged into
"8/16", was taken over by Resource Central to become "8/16-Central",
and was then discontinued.
As far as I know, there is no way to get back issues of The Sourceror's
Apprentice.
In short, the method proposed by this article involved a 32-bit seed
which was updated using a shift/XOR method, with some of the high-order
bits being XORed together to produce the next LSB of the seed. It
produes a new 8-bit random number after each update. You can then use
this number divided down to the required range (assuming you need less
than 256 values).
To get it to work reasonably randomly, you need to seed it with a
large random number. In the IIgs, the vertical and horizontal scan
counters are good for this, possibly governed by a user-related pause.
In the IIe, you could use the 16-bit "random number" at $4E and $4F
which is updated by KEYIN while waiting for a keypress.
You could also seed it with some kind of pseudo-random number, and
then keep generating new random numbers while waiting for a keypress,
to get the seed to a random starting point.
To produce a random number from 0 to (N-1) with N < 256, the easiest
method is to do an 8-bit by 8-bit multiplication, producing a 16-bit
result, then use the high byte of the result.
For example, a random number from 0 to 99, you would take the random
number produced by the routine, multiply it by 100, then use the high
byte (which will be anything from 0 to 100 * 255 / 256 = 99.6, with the
fraction not available anyway). This produces reasonable distribution
of values, compared to the "modulus" method (dividing by 100 and taking
the remainder), which tends to clump the values towards the lower end
of the range.
I don't have the original 6502 version of the random number generator
handy right now (the article is buried at home somewhere), but I can
dig it out if you E-Mail me.
--
David Empson
dempson@actrix.gen.nz
Snail mail: P.O. Box 27-103, Wellington, New Zealand