       linear congruential generator

• To: mathgroup at smc.vnet.net
• Subject: [mg4770] linear congruential generator
• From: cabana at flinet.com (David Cabana)
• Date: Fri, 13 Sep 1996 13:54:52 -0400
• Organization: Florida Internet Corp
• Sender: owner-wri-mathgroup at wolfram.com

```This is in response to a recent posting regarding (among other things), a
linear congrential generator.  Here is what I got when I ran the proposed
code:

In:=
x = 1;
x[n+1] := Mod[(7^7*x[n]), 2^31 -1]//N
u[n] := x[n]/(2^31-1)
Table[x[n], {n,1,10}]

Out=
{x, x, x, x, x, x, x, x, x, x}

Here is roughly the same code, with some changes to make it work.

x = 1;
x[n_] := Mod[(7^7 * x[n-1]), 2^31 - 1]
u[n_] := x[n]/(2^31-1) //N
Table[x[n], {n,1,10}]

Notice the changes in the definitions of x and u. The underscores are
critical. I also expressed the recursion a bit differently.  The generator
must use exact integer arithmetic to be correct, so I moved the //N to the
definition of u.

There is another problem. As written, this program is very slow. The
reason is that to compute  x it must compute x, x, ..., x.
Then to compute x, it must compute x, x, x, ... x. It
computes the same thing over and over again.  There are various fixes to
this. One is to use memoization, say by writing
x[n_] := x[n] = Mod[(7^7 * x[n-1]), 2^31 - 1]
x[n_] := Mod[(7^7 * x[n-1]), 2^31 - 1]

Another is to take an entirely different approach:

generator[n_]:= Mod[7^7 * n, 2^31 - 1]
uniformVariates[n_, seed_] :=
NestList[generator, seed, n] / (2^31 - 1) //N

I did not run timing tests, but I suspect the 2nd approach is quicker.

--
David Cabana   cabana at flinet.com

==== [MESSAGE SEPARATOR] ====

```

• Prev by Date: Graphic for Conic Sections
• Next by Date: functional code
• Previous by thread: Graphic for Conic Sections
• Next by thread: functional code