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