hairston@henry.ece.cmu.edu (David Hairston) (12/03/90)
how random is the Toolbox routine Random()? IM-I says it returns an integer in the range -32767 (not -32768) to 32,767 before cycling. does this mean it will hit every number in that range once before repeating? and why the seemingly strange range -dave- hairston@henry.ece.cmu.edu
ldo@waikato.ac.nz (Lawrence D'Oliveiro, Waikato University) (12/04/90)
The QuickDraw Random function uses a reasonably good algorithm.
It's basically the same as the "minimal standard" one described
in the article "Random Number Generators: Good Ones are Hard to Find",
by Stephen K Park and Keith W Miller, in Communications of the ACM,
volume 31, number 10, October 1988.
However, to obey this algorithm *exactly*, you have to ignore the
function result from Random, and look at the value of the RandSeed
QuickDraw global instead. This takes on uniformly-distributed values
from 1 up to 2147483647 (2 ** 31 - 1) inclusive.
Here's an example routine which returns a uniformly distributed
real number from 0 up to (but not including) 1:
Procedure GetRandomReal
(
var Result : Real
);
Var
Ignore : Integer;
Begin
Ignore := Random; { cause a change to RandSeed }
Result := (RandSeed - 1) / 2147483647.0
End {GetRandomReal};
As for the result of the Random function itself, I don't know what
its properties (e g autocorrelation and other signs of non-randomness)
are. But if you read the article I mentioned above, you'd be less
likely to trust any old random number algorithm (or variation thereof)
until you've seen the results of some very careful testing.
Lawrence D'Oliveiro fone: +64-71-562-889
Computer Services Dept fax: +64-71-384-066
University of Waikato electric mail: ldo@waikato.ac.nz
Hamilton, New Zealand 37^ 47' 26" S, 175^ 19' 7" E, GMT+13:00
"...so she tried to break into the father bear's computer, but it was
too hard. Then she tried to break into the mother bear's computer, but
that was too easy..."Chris.Gehlker@p12.f56.n114.z1.fidonet.org (Chris Gehlker) (12/04/90)
> how random is the Toolbox routine Random()? IM-I says it returns > an integer in the range -32767 (not -32768) to 32,767 before > cycling. does this mean it will hit every number in that range > once before repeating? and why the seemingly strange range It definately won't hit every number once before repeating. The strange range makes it easy to scale because you can use Random() * MaxInt / ScaleFactor or abs(Random) * MaxInt / Scalefactor. Other formulations to get unifrom extendeds, longs or shorts over any give range will suggest themselves. They all rely on the distribution of Random() being symetric about 0. If Random() returned values from -32768 to 32767 it would be a real bitch to scale it and still have a uniform distribution. Yeah that was real rambling but it's late. -- Uucp: ...{gatech,ames,rutgers}!ncar!asuvax!stjhmc!56.12!Chris.Gehlker Internet: Chris.Gehlker@p12.f56.n114.z1.fidonet.org
lins@Apple.COM (Chuck Lins) (12/05/90)
In article <31359.275BAB9A@stjhmc.fidonet.org> Chris.Gehlker@p12.f56.n114.z1.fidonet.org (Chris Gehlker) writes: >> how random is the Toolbox routine Random()? IM-I says it returns >> an integer in the range -32767 (not -32768) to 32,767 before >> cycling. does this mean it will hit every number in that range >> once before repeating? and why the seemingly strange range > >It definately won't hit every number once before repeating. And if it did hit every number in the range before repeating it wouldn't be random. -- Chuck Lins | "Is this the kind of work you'd like to do?" Apple Computer, Inc. | -- Front 242 20525 Mariani Avenue | Internet: lins@apple.com Mail Stop 37-BD | AppleLink: LINS@applelink.apple.com Cupertino, CA 95014 | "Self-proclaimed Object Oberon Evangelist" The intersection of Apple's ideas and my ideas yields the empty set.
hairston@henry.ece.cmu.edu (David Hairston) (12/05/90)
[hairston@henry.ece.cmu.edu writes:] [] how random is the Toolbox routine Random()? IM-I says it returns [] an integer in the range -32767 (not -32768) to 32,767 before [] cycling. does this mean it will hit every number in that range [] once before repeating? and why the seemingly strange range [Chris.Gehlker@p12.f56.n114.z1.fidonet.org (Chris Gehlker) writes:] [] It definately won't hit every number once before repeating. [lins@Apple.COM (Chuck Lins) writes:] [] And if it did hit every number in the range before repeating it wouldn't be [] random. hmmm, we're getting picky here. "pseudo-random" is okay. i'd like a generator that uniformly and pseudo-randomly hits every number in its range once before repeating and it would be better of i could specify the range as a parameter or seed. it seems random number generators can have properties that are optimized to different tastes. i've read UMPG and i'll have to read it again 'cause it seemed a little uncertain on this point altho it did suggest a formula and a couple of references. thanx to all who responded! -dave- hairston@henry.ece.cmu.edu
kaufman@Neon.Stanford.EDU (Marc T. Kaufman) (12/05/90)
In article <47094@apple.Apple.COM> lins@Apple.COM (Chuck Lins) writes: >In article <31359.275BAB9A@stjhmc.fidonet.org> Chris.Gehlker@p12.f56.n114.z1.fidonet.org (Chris Gehlker) writes: ->> how random is the Toolbox routine Random()? IM-I says it returns ->> an integer in the range -32767 (not -32768) to 32,767 before ->> cycling. does this mean it will hit every number in that range ->> once before repeating? and why the seemingly strange range ->It definately won't hit every number once before repeating. >And if it did hit every number in the range before repeating it wouldn't be >random. It isn't random. Its pseudo-random. A previous poster suggested looking at the seed value, which is 32 bits. In 32-bit space, Random() hits 2^31 -2 values before repeating. The lower 16 bits do not cycle through all values before repeating. In fact, I don't really know what the statistical properties of the lower 16-bits of Random() are. Has anyone looked at it? It should be OK for uniform distribution, at least. Marc Kaufman (kaufman@Neon.stanford.edu)
Chris.Gehlker@p12.f56.n114.z1.fidonet.org (Chris Gehlker) (12/08/90)
> hmmm, we're getting picky here. "pseudo-random" is okay. i'd like a > generator that uniformly and pseudo-randomly hits every number in its > range once before repeating and it would be better of i could specify > the range as a parameter or seed. it seems random number generators > can have properties that are optimized to different tastes. If the range is fairly limited, why not fill an array with each value of the range and then shuffle the array by using random to generate array indices and swapping elements. It seems to be pretty generally accepted that if you generate arraySize * 3 suffles you can then just pull elements out of the array and get a uniformly distributed w/o replacement sample set. This is pretty much what the card game and lottery simulators do. -- Uucp: ...{gatech,ames,rutgers}!ncar!asuvax!stjhmc!56.12!Chris.Gehlker Internet: Chris.Gehlker@p12.f56.n114.z1.fidonet.org