Linear congruential generator problem

Printable View

January 18th 2009, 12:42 PM
Pontius

Linear congruential generator problem

Hi. Not sure if I am posting in the right place.

I need to make a random numbers generator and have some problems with setting some initial values. Hope someone can help me out.

I am thinking I can use the following generator which I found at: Linear congruential generator - Wikipedia, the free encyclopedia

---------- Copied from wikipedia:

http://upload.wikimedia.org/math/5/6...89fc17a049.png where Xn is the sequence of pseudorandom values, and

http://upload.wikimedia.org/math/d/6...756a4869df.png the "modulus"

http://upload.wikimedia.org/math/0/6...cf32d4e193.png the "multiplier"

http://upload.wikimedia.org/math/9/8...ecd37d4f6b.png the "increment" (the special case of c = 0 corresponds to Park–Miller RNG)

http://upload.wikimedia.org/math/3/5...9f4e1e01e6.png the "seed" or "start value" are integer constants that specify the generator.

The period of a general LCG is at most m, and for some choices of a much less than that. The LCG will have a full period if and only if:

1. http://upload.wikimedia.org/math/8/d...213956f8d3.png and http://upload.wikimedia.org/math/c/4...c0d351fe41.png are relatively prime,

2. http://upload.wikimedia.org/math/b/e...f9ef3d78f0.png is divisible by all prime factors of http://upload.wikimedia.org/math/c/4...c0d351fe41.png,

3. http://upload.wikimedia.org/math/b/e...f9ef3d78f0.png is a multiple of 4 if http://upload.wikimedia.org/math/c/4...c0d351fe41.png is a multiple of 4.

------------ Copy end

In my generator the m is set to 999999999 (it can also be a lower number but preferable as close to 999999999 as possible)

X0 and n will be given and be different each time the generator runs.

So what I need help with is to set m, a and c according to the rules above. Remember m should not be altered or if it must be altered then as little as possible downwards.

Hope someone can help me (Bow)
January 18th 2009, 10:23 PM
Constatine11

Quote:

Originally Posted by Pontius

Hi. Not sure if I am posting in the right place.

I need to make a random numbers generator and have some problems with setting some initial values. Hope someone can help me out.

I am thinking I can use the following generator which I found at: Linear congruential generator - Wikipedia, the free encyclopedia

---------- Copied from wikipedia:

http://upload.wikimedia.org/math/5/6...89fc17a049.png where Xn is the sequence of pseudorandom values, and

http://upload.wikimedia.org/math/d/6...756a4869df.png the "modulus"

http://upload.wikimedia.org/math/0/6...cf32d4e193.png the "multiplier"

http://upload.wikimedia.org/math/9/8...ecd37d4f6b.png the "increment" (the special case of c = 0 corresponds to Park–Miller RNG)

http://upload.wikimedia.org/math/3/5...9f4e1e01e6.png the "seed" or "start value" are integer constants that specify the generator.

The period of a general LCG is at most m, and for some choices of a much less than that. The LCG will have a full period if and only if:

1. http://upload.wikimedia.org/math/8/d...213956f8d3.png and http://upload.wikimedia.org/math/c/4...c0d351fe41.png are relatively prime,

2. http://upload.wikimedia.org/math/b/e...f9ef3d78f0.png is divisible by all prime factors of http://upload.wikimedia.org/math/c/4...c0d351fe41.png,

3. http://upload.wikimedia.org/math/b/e...f9ef3d78f0.png is a multiple of 4 if http://upload.wikimedia.org/math/c/4...c0d351fe41.png is a multiple of 4.

------------ Copy end

In my generator the m is set to 999999999 (it can also be a lower number but preferable as close to 999999999 as possible)

X0 and n will be given and be different each time the generator runs.

So what I need help with is to set m, a and c according to the rules above. Remember m should not be altered or if it must be altered then as little as possible downwards.

Hope someone can help me (Bow)

Why can't you just look up suitable values? I beleive suitable values can be found in Abramowitz and Stegun and in Knuth.

Also I hope this is an excercise and not for use in a simulation, if the latter is the case there are far better PRNG out there available as source code in whatever programming language you require.

.

.
January 19th 2009, 04:45 AM
Pontius

Quote:

Originally Posted by Constatine11

Why can't you just look up suitable values? I beleive suitable values can be found in Abramowitz and Stegun and in Knuth.

Also I hope this is an excercise and not for use in a simulation, if the latter is the case there are far better PRNG out there available as source code in whatever programming language you require.

.

.

Please Constatine... We are in advanced math in the university and know what you told. Our teacher gave us this problem to see if anyone came up with same m, a and c as her. I am sure since you post in this forum that you will be able to help me with my request. (Nod)
January 19th 2009, 06:13 AM
Constatine11

Quote:

Originally Posted by Pontius

Please Constatine... We are in advanced math in the university and know what you told. Our teacher gave us this problem to see if anyone came up with same m, a and c as her. I am sure since you post in this forum that you will be able to help me with my request. (Nod)

Well the probability of finding the same paparmeters as your teacher are negligable unless you know rather more about her approach than you indicate.

But a simple set of values that meet conditions 1, 2 and 3 are:

$m$ the square of a prime $p$ , $a=p+1$ , $c$ a prime $<p^2$

and:

$m=31607^2 = 999 002 449$

could be used.

.