eiverson@nmsu.edu (Eric Iverson) (11/21/90)
I need a random number generator for Modula-2. Any help would be appreciated. -- ------------------------------------------------------------------------ Eric Iverson Internet: eiverson@nmsu.edu Computing Research Lab Box 30001/3CRL Life is something to do when New Mexico State University you can't get to sleep. Las Cruces, NM 88003-0001 -Fran Lebowitz VOICE: (505) 646-5711 FAX: (505) 646-6218
adamr@pain (Adam Ravid) (11/23/90)
eiverson@nmsu.edu (Eric Iverson) writes: > > I need a random number generator for Modula-2. Any help would be > appreciated. a nice and simple randomlib stolen from "Data Structures & Prog Design in Modula-2," L.Nyhoff/S.Leestma (pp 35-37) DEF MOD RandomLib; PROC RandomCard (First,N:CARDINAL):CARDINAL; PROC RandomReal () :REAL; (* returns 0.0-1.0 *) END RandomLib. IMP MOD RandomLib; FROM InOut IMPORT WriteString, WriteLn, ReadCard; (*excluded on my lib*) CONST (*I would have put these const in the def!*) Mult =29; Modulus =2048; Addend =431; VAR Seed:CARDINAL; PROC RandomReal ():REAL; BEGIN Seed := Seed * Mult + Addend; Seed := Seed MOD Modulus; RETURN FLOAT(Seed) / FLOAT(Modulus) END RandomReal; PROC RandomCard (First,N:CARDINAL):CARDINAL; BEGIN RETURN First + TRUNC(FLOAT(N) * RandomReal()) END RandomCard; PROC GetSeed; (* I excluded this one in my lib *) BEGIN WriteLn; WriteString ("Enter a seed for the random number generator"); WriteLn; WriteString ("(preferable a prime number): "); ReadCard (Seed); Seed := Seed MOD Modulus END GetSeed; BEGIN (* library source, executed upon opening of calling program *) GetSeed END RandomLib; Adam ...a word juggler in disguise.... ---------------------------------------------------------------------------- pain!adamr cbcscaar@ma.secs.csun.edu
Jon.Guthrie@p15.f20.n226.z1.fidonet.org (Jon Guthrie) (11/25/90)
> I need a random number generator for Modula-2. Any help would be > appreciated. Which compiler? Which Machine? I've got a Pseudorandom number generator for FST Modula-2 (running under MS-DOS) but it uses some assembly language. -- uucp: uunet!m2xenix!puddle!226!20.15!Jon.Guthrie Internet: Jon.Guthrie@p15.f20.n226.z1.fidonet.org
v056ped5@ubvmsd.cc.buffalo.edu (Brian M McNamara) (11/27/90)
In article <1484.2750D9EC@puddle.fidonet.org>, Jon.Guthrie@p15.f20.n226.z1.fidonet.org (Jon Guthrie) writes... > > I need a random number generator for Modula-2. Any help would be > > appreciated. >Which compiler? Which Machine? I've got a Pseudorandom number generator for >FST Modula-2 (running under MS-DOS) but it uses some assembly language. Please post the source for the FST RND thang. I developed my own which seemed to be working great until recently when I realized that it had a period of about 50 generations. I took my numbers directly from a statistics textbook so I am sure it is a problem with my methodology. I think that users of the FTP compiler would appreciate it. If nothing else, "Hey, FST people... include a RND function in version 2.something +". Brian
eiverson@nmsu.edu (Eric Iverson) (11/27/90)
Just in case anyone cares, this is the random number generator Ted
Dunning hacked out today:
IMPLEMENTATION MODULE Rand;
(* 7^5 is a reasonable linear congruential generator for 32 bit
arithmetic, longs should be at least that long, see cacm october
or november 1988 *)
FROM Clock IMPORT (* Type *) SystemTime,
(* Procedure *) GetSystemTime;
FROM MathLib IMPORT Entier;
TYPE
LONGSEED = ARRAY[0..55] OF LONGINT;
VAR
Seed : LONGSEED;
Next : INTEGER;
PROCEDURE SetSeed ( );
VAR
I : INTEGER;
N : LONGINT;
S : SystemTime;
BEGIN (* SetSeed *)
GetSystemTime(S);
N := S.seconds + S.microSeconds;
FOR I := 0 TO 55 DO
Seed[I] := N;
N := 7*N;
N := 7*N;
N := 7*N;
N := 7*N;
N := 7*N;
IF ( N < 0 ) THEN
N := -N;
END (* IF *);
IF ( N < 0 ) THEN
N := 0;
END;
END (* FOR *);
Next := 0;
END SetSeed;
PROCEDURE Random ( ):REAL;
VAR
K: INTEGER;
BEGIN
K := Next-24;
IF ( K < 0 ) THEN
K := K+56;
END (* IF *);
Seed[Next] := Seed[Next] + Seed[K];
K := Next-55;
IF ( K < 0 ) THEN
K := K+56;
END (* IF *);
Seed[Next] := Seed[Next] + Seed[K];
K := Next;
Next := Next+1;
IF ( Next >= 56 ) THEN
Next := 0;
END (* IF *);
IF ( Seed[K] < 0 ) THEN
Seed[K] := -Seed[K];
END (* IF *);
IF ( Seed[K] < 0 ) THEN
Seed[K] := 0;
END;
RETURN FLOAT(Seed[K])/2147483647.0;
END Random;
BEGIN (* Rand *)
SetSeed;
END Rand.
--
------------------------------------------------------------------------
Eric Iverson Internet: eiverson@nmsu.edu
Computing Research Lab
Box 30001/3CRL Life is something to do when
New Mexico State University you can't get to sleep.
Las Cruces, NM 88003-0001 -Fran Lebowitz
VOICE: (505) 646-5711
FAX: (505) 646-6218Frank.Warren@f42.n161.z1.fidonet.org (Frank Warren) (12/03/90)
The best way to do it, unless you're into native code, is to use several prime numbers as multipliers, a prime as the modulus, and give up a few numbers. I've been playing with a 16-bitter that uses numbers like 7411 etc for multipliers, and 65521 for the modulus. With 5 of these multipliers, I get periods that are well beyond 10 million; I haven't had the patience to wait until the sequence repeats. It's slower than lesser generators, but I think you'll agree that such a period is remarkable for 16 bit arithmetic. The key is that you use LONGCARDs to hold the result and avoid getting cut off at the knees. This will work for you, but is not canned code I can pass alon since it is proprietary. The principle works with all numbers, though. What I suggest you also do is have counts to see to it you don't fall into a "hole". Some choices of multipliers for the linear congruential method deteriorate into subcycle generators (one of the reasons for using primes to begin with; they tend not to suffer from this). The reason for the longer period is that you get intermixed combinations from each of the LCG's you use. This method fares poorly on the spectral test, but it does produce good pseudo-random sequences. -- uucp: uunet!m2xenix!puddle!161!42!Frank.Warren Internet: Frank.Warren@f42.n161.z1.fidonet.org
smcgee%albion.utah.edu@cs.utah.edu (Scott Mcgee) (12/05/90)
I have a RND function around somewhere for the Macintosh if anyone needs it.
I don't have right handy here but can dig it out if anyone wants me to.
I am reading this group for the first time today so if someone else already
posted one please excuse this post.
Scott
All opinions are my own! | A cannon is a large machine that makes a lot
(Unless I have been bribed | of noise and indulges in negatively-intended
to use someone elses!) | mechanical interaction at a distance.
>>>>>>>>>>>>>>>> smcgee%albion@cs.utah.edu (Scott McGee) <<<<<<<<<<<<<<<<allen@sonia.math.ucla.edu (William C. Allen) (12/07/90)
Regarding all of the posted random number generators for modula-2, here
is one which works very well. I hope its ok with the readers if I don't
code it. This random number generator idea comes from Knuth's "ACP, volume 2",
and was invented in 1958 by G.J. Mitchell and D.P. Moore (unpublished).
Define initially some sequence of non-negative integers
X(1), X(2), ... , X(55)
which are not all even. For n > 55, define X(n) by
X(n) = ( X(n - 24 + 1) + X(n - 55 + 1) ) mod M
where M is large and even. That's it.
As you can easily see, one doesn't really need an infinite array, but merely
a cyclic array (queue) of 55 integers, in order to implement this algorithm.
The values 24 and 55 appearing above are not chosen arbitrarily, but are
instead special values that guarantee { X(n) } will have a period of length
at least 2^f * ( 2^55 - 1 ) for some f satisfying 0 <= f <= log M. The big
drawback of this method is that there is very little theory developed to
prove that it has desirable randomness properties. However, I've implemented
this thing in several languages, and it seems to work just fine. Knuth adds
that this method has consistently passed statisical tests of randomness with
flying colors, in extensive testing done since 1958. The biggest advantage
of this thing is that once you have your inital array of 55 elements, which
you can get by using some weak method of generating integers, the successive
elements can be gotten using only addition and subtraction:
current := X[ n - 24 + 1 ] + X[ n - 55 + 1 ];
if ( current >= M ) then
current := current - M;
X[n] := current;
(* normalized := ( X[n] * 1.0 ) / ( 1.0 * M ) *)
I'll leave the index arithmetic to you. Knuth actually implements this
algorithm using subtraction, so all comparisons can be made against 0,
shaving even a few more ticks off of the cpu time.
--Bill Allen
--UCLA Math