kr@asacsg.mh.nl (Koos Remigius) (06/28/90)
Hi there,
I have a question about random numbes generators.
I have found a random number that gives me a random integer.
This function gives me a random integer ( between 0 and range ).
=================================================================
function Randomize(range:Integer):Integer;
var
rawResult:LongInt; { "Raw" random number received from toolbox }
begin { Randomize }
rawResult:=(ABS(Random); { Get random number between 0 and 32767 }
Randomize:=(rawResult * range) div 32768; { Scale to specified range }
end; { Randomize }
=================================================================
What I need is a random number generator that gives me a random LongInt back.
The random number I want must lis between 0 and 2097151.
I any of you out there has an idee how to do this, and willing to
share your idee, than you can make me verry happy.
I' am using Think Pascal for the Macintosh.
Greetings from Holland,
Koos Remigius.
--
Koos Remigius kr@mh.nl via internet backbones
Asac Nederland B.V uucp: ..!{uunet,hp4nl}!mh.nl!kr
Coencoop 7, 2741 PG Waddinxveen, The Netherlands
-------------------- "Still crazy after all this years" ---------------------russotto@eng.umd.edu (Matthew T. Russotto) (06/29/90)
In article <152@asacsg.mh.nl> kr@asacsg.mh.nl (Koos Remigius) writes: >What I need is a random number generator that gives me a random LongInt back. >The random number I want must lis between 0 and 2097151. >I any of you out there has an idee how to do this, and willing to >share your idee, than you can make me verry happy. >I' am using Think Pascal for the Macintosh. >Greetings from Holland, >Koos Remigius. This may be naive, but why not rndnum,tmp:Longint; rndnum := Random; {get 16 bit random number from toolbox} rndnum := BitShift(rndnum, 16); tmp := Random; {get second 16 bit random number from toolbox} tmp := BitAnd(tmp,65535); {clear sign-extension} rndnum := abs(BitOr(tmp,rndnum)); {put the pieces together} rndnum := rndnum mod 2097152; -- Matthew T. Russotto russotto@eng.umd.edu russotto@wam.umd.edu ][, ][+, ///, ///+, //e, //c, IIGS, //c+ --- Any questions?
kaufman@Neon.Stanford.EDU (Marc T. Kaufman) (06/29/90)
In article <152@asacsg.mh.nl> kr@asacsg.mh.nl (Koos Remigius) writes: >What I need is a random number generator that gives me a random LongInt back. If you have a Mac II, the following might help.: Marc Kaufman (kaufman@Neon.stanford.edu) *** SEG 'Main' ******************************************************************* * ROUTINE Random.a * FUNCTION Provide Minimal-Standard random number generator * CALLING C-compatible calling sequences * * This generator is taken from CACM, October 1988, p.1192 * * It was designed by Stephen K. Park and Keith W. Miller * * For future reference: Possible better multipliers are 48271 and 69621 ******************************************************************* CASE ON MACHINE MC68020 PROC ENTRY MSRandomSeed Start DC.W ' ) Copyright Kaufman Research, 1988 ' MSRandomSeed DC.L 1 ; Place to store seed value ENDPROC ******************************************************************* * ROUTINE MSGetSeed * FUNCTION Return the current seed value * INPUT none * OUTPUT D0 = the seed ******************************************************************* MSGetSeed FUNC EXPORT move.l MSRandomSeed,D0 rts ENDFUNC ******************************************************************* * ROUTINE MSRandom * FUNCTION Return the next random number * INPUT none * OUTPUT D0 = the number ******************************************************************* MSRandom FUNC EXPORT lea MSRandomSeed,A0 move.l (A0),D1 mulu.l #16807,D0:D1 ; long multiply divu.l #$7fffffff,D0:D1 ; modulo 2^31 -1 move.l D0,(A0) rts ENDFUNC ******************************************************************* * ROUTINE MSRanSet * FUNCTION Set the random number seed * INPUT The seed value * OUTPUT The seed value ******************************************************************* MSRanSet FUNC EXPORT move.l 4(A7),D0 ; the value the user wants to use and.l #$7fffffff,D0 beq.s MSGetSeed ; zero is not a valid value cmp.l #$7fffffff,D0 beq.s MSGetSeed ; neither is 2^31-1 lea MSRandomSeed,A0 move.l D0,(A0) rts ENDFUNC END
davidd@ttidca.TTI.COM (David Dantowitz) (06/30/90)
Be quite careful how you splice together random numbers to form larger random numbers. Linear-conguential random number generators (of the form: seed = seed*a mod m + b) have more "random" high order bits than low order bits. Appending two 16 bit numbers may skew your application in a way that's difficult to measure. If you want a 32 bit random number then check out Knuth for some multipliers (a) and modulos (m) that will give you "good" random numbers. Sorry I don't have it handy. -- David Dantowitz Singing Barbershop when not computing
kaufman@Neon.Stanford.EDU (Marc T. Kaufman) (07/01/90)
In article <1990Jun29.020739.9146@Neon.Stanford.EDU> kaufman@Neon.Stanford.EDU (Marc T. Kaufman) writes: >In article <152@asacsg.mh.nl> kr@asacsg.mh.nl (Koos Remigius) writes: ->What I need is a random number generator that gives me a random LongInt back. and I write back: >If you have a Mac II, the following might help.: [some assembly code for the Mac deleted] I recently received the following mail: "You may like to know that the Random function in the Mac ROM *is* the same as the "minimal std" function published in the CACM paper. It's just that it truncates the computed result to 16-bits. However, you can get at the 32-bit result by accessing the QD global "RandSeed". This works because Random uses the linear congruential method which is iterative, and saves the next computed random no in the sequence in RandSeed. Ie do something like (in C) (void) Random(); /* ignore 16 bit result */ theValue = qd.randSeed; /* use 32-bit result */ In Pascal, just assign the unwanted 16-bit result to a dummy. I compared 10000 rn's from a C version of the CACM rn generator with that generated by the ROM's Random() function, and they were identical. Best regards Sak Wathanasin Network Analysis Limited uucp: ...!ukc!nan!sw other: sw@network-analysis-ltd.co.uk phone: (+44) 203 419996 telex: 9312130355 (SW G) snail: 178 Wainbody Ave South, Coventry CV3 6BX, UK I thank Sak for this info. I am not sure just which Macs this applies to -- probably the ci and fx, certainly not the SE. Can someone from Apple tell us when the algorithm changed, and is it part of a system patch so all Macs can benefit from it? Marc Kaufman (kaufman@Neon.stanford.edu)
nolan@tssi.UUCP (Michael Nolan) (07/04/90)
It's fairly easy to write a random number generator, and there are several
in Knuth's "Art of Computer Programming", I *think* in volume 2, at any rate
the subject matter of the correct volume is algorithms.
One I've used many times involves three relatively prime numbers n1, n2, and n3.
(Relatively prime means these numbers have no common factors above 1.)
Please pardon my pseudocode:
This_Random_Number = (Previous_Random_Number * n1 + n2) mod n3.
Of course, you need to provide an initial Previous_Random_Number as a seed.
This will generate a random number sequence of period n3. I assume this will
work in longints.
------------------------------------------------------------------------------
Mike Nolan "I don't know what apathy is,
Tailored Software Services, Inc. and I don't want to find out!"
Lincoln, Nebraska (402) 423-1490
UUCP: tssi!nolan should work,
if not try something like uunet!frith!upba!tssi!nolan alexr@ucscb.ucsc.edu (Alexander M. Rosenberg) (07/06/90)
In article <1990Jun30.170949.1426@Neon.Stanford.EDU> kaufman@Neon.Stanford.EDU (Marc T. Kaufman) writes: > I thank Sak for this info. I am not sure just which Macs this applies to -- > probably the ci and fx, certainly not the SE. Can someone from Apple tell us > when the algorithm changed, and is it part of a system patch so all Macs can > benefit from it? > > Marc Kaufman (kaufman@Neon.stanford.edu) Sak is incorrect. While he may note that the algorithm is the same (I'm not sure), it is definately not probable for him to have matched up 10000 numbers. Apple's random number generator uses the tick count as a seed upon each InitGraf (I may be wrong here, but I'm sure that it is time derived.) I do know that the mouse driver has always kept track of the time at which a click occurs, and takes the difference in time between that click and the previous one, and adds this number to the current randSeed. This is where an additional level of randomness is provided. (Humans tend to be more "random" than computers do, eh?) This is why you may have seen results that didn't follow a pattern. (It is possible that in 32-bit QuickDraw they changed the algorithm, but I seriously doubt it.) (ignore any paths found here, they are incorrect. I can be reached at Alex_Rosenberg.INTEGRATION@gateway.qm.apple.com) --------------------------------------------------------------------------- - Alexander M. Rosenberg - INTERNET: alexr@ucscb.ucsc.edu - Yoyodyne - - 330 1/2 Waverley St. - UUCP:ucbvax!ucscc!ucscb!alexr - Propulsion - - Palo Alto, CA 94301 - BITNET:alexr%ucscb@ucscc.BITNET- Systems - - (415) 329-8463 - Nobody is my employer so - :-) - - - so nobody cares what I say. - -
alexr@ucscb.ucsc.edu (Alexander M. Rosenberg) (07/06/90)
In article <8999@goofy.Apple.COM> alexr@ucscb.ucsc.edu (Alexander M. Rosenberg) writes: > Apple's random number generator uses the tick count as a seed upon each > InitGraf (I may be wrong here, but I'm sure that it is time derived.) I do > know that the mouse driver has always kept track of the time at which a > click occurs, and takes the difference in time between that click and the > previous one, and adds this number to the current randSeed. This is where > an additional level of randomness is provided. (Humans tend to be more > "random" than computers do, eh?) <SNIVELING WIMP MODE ON> Just to protect my sanity, I checked. The standard ADB mouse driver does the aforementioned random seed changes, to a low memory global, RndSeed ($156). InitGraf does use 1 as a seed. (a silly seed). Under Random, they suggest using RndSeed (the low-memory global) as a seed. I suspect that something in the system must use this as a seed. I was working from memory. Oops. Alex P.S. I'm sure that pre-ADB mouse driver code does the same thing. --------------------------------------------------------------------------- - Alexander M. Rosenberg - INTERNET: alexr@ucscb.ucsc.edu - Yoyodyne - - 330 1/2 Waverley St. - UUCP:ucbvax!ucscc!ucscb!alexr - Propulsion - - Palo Alto, CA 94301 - BITNET:alexr%ucscb@ucscc.BITNET- Systems - - (415) 329-8463 - Nobody is my employer so - :-) - - - so nobody cares what I say. - -
shahn@hstbme.mit.edu (Samuel Hahn) (07/07/90)
This may be a bit obvious but why don't you just generate a long number one character at a time? For instance to go between 0 and 999999999999 just pick each digit from random() mod 9? This won't be very fast but it should work if you are willing to accept the limitations of the built in random number generator... It also gets a bit trickier if you want numbers between 0 and say 945832427, but it could still be done with a bunch of conditional statements. Sam Hahn
vladimir@prosper (Vladimir G. Ivanovic) (07/07/90)
The June 1988 (v31 #6) issue of the Communications of the ACM has an article
by Pierre L'Ecuyer called, "Efficient and Portable Combined Random Number
Generators". The following October (v31 #10), Stephen Park and Keith Miller
published "Random Number Generators: Good Ones are Hard to Find."
Both articles are ESSENTIAL reading for anyone interested in random number
generation, and this includes naive users. The conclusion of both articles is
that horrible random (sic) number generators are used by people who don't know
better, while very good ones take less than 20 lines of Pascal! Amoung the
horrid generators are some that come with certain systems or are presented in
textbooks!
Here are the two proposed random number generators. Even though I have proof
read them twice, I made no guarantees whatsoever about the correctness or the
usablilty of the code below.
Here is the Minimal Standard proposed by Park and Miller:
function Random : real;
{ Initialize seed with 1..2147483646 }
{ maxint must be greater than 2**31 -1 }
const
a = 16807;
m = 2147483647;
q = 12773; { m div a }
r = 2836; { m mod a }
var
lo, hi, test : integer;
begin
hi := seed div q;
lo := seed mod q;
test := a * lo - r * hi;
if test > 0 then
seed := test
else
seed := test + m;
Random := seed / m
end;
Here is the Portable Combined Generator of Ecuyer for 32-bit computers. It
has a period of roughly 8.12544 x 10**12.
Function Uniform : real;
{ Initialize s1 to 1..2147483562; s2 to 1..2147483398 }
var
Z, k : integer;
begin
k := s1 div 53668;
s1 := 40014 * (s1 - k * 53668) - k * 12211;
if s1 < 0 then s1 := s1 + 2147483563;
k := s2 div 52774;
s2 := 40692 * (s2 - k * 52774) - k * 3791;
if s2 < 0 then s2 := s2 + 2147483399;
Z := s1 - s2;
if Z < 1 then Z := Z + 2147483562;
Uniform := Z * 4.656613e-10;
end;
All are urged to read both articles for a much better presentation. And you
don't have to be a mathematician to understand them: very little of either
article is not accessible to a competent programmer.
Enjoy!
-- Vladimir