Linear Congruential Random Number GeneratorThe Linear Congruential Random Number Generator is a popular method of creating random numbers. It is linear congruential as the values are related to each other in a linear way, modulo m. It uses the sequence generator of: \(X_i\ = (a \times X_{i-1} + c) \mod m\) and where X0 is the initial seed value of the series. Enter some values and the program should generate 200 random values. Normally the value of \(m\) is a prime number. The results are then:
|
Try an example
- a=21, seed=35, c=31, and m=100. Gen. This should give 66 17 88 79 90 ...
- a=22, seed=35, c=31, and m=100. Gen. Ths should give 1 53 97 65 61 ...
- a=2,175,143, seed=3553, c=10,653, and m=1,000,000. Gen. This should give 293,732 114,329 934,700 172,753 ...
- a=954,365,343, seed=436,241, c=55,119,927, and m=1,000,000. Gen. This should give 715,590 917,297 157,798 514,641 606,790 ...
Example
For example a=21, seed=35, c=31, and m=100 will generate the random values of (where the value of m will define the range of numbers):
66 17 88 79 90 21 72 43 34 45 76 27 98 89 0 31 82 53 44 55 86 37 8 99 10 41 92 63 54 65 96 47 18 9 20 51 2 73 64 75 6 57 28 19 30 61 12 83 74 85 16 67 38 29 40 71 22 93 84 95 26 77 48 39 50 81 32 3 94 5 36 87 58 49 60 91 42 13 4 15 46 97 68 59 70 1 52 23 14 25 56 7 78 69 80 11 62 33 24 35
To provide this we can take the first three values:
(21x35+31) mod 100 gives 66 (21x66+31) mod 100 gives 17 (21x17+31) mod 100 gives 88 and so on.
If we make one change of a=22 we get:
1 53 97 65 61 73 37 45 21 93 77 25 81 13 17 5 41 33 57 85 1 53 97 65 61 73 37 45 21 93 77 25 81 13 17 5 41 33 57 85 1 53 97 65 61 73 37 45 21 93 77 25 81 13 17 5 41 33 57 85 1 53 97 65 61 73 37 45 21 93 77 25 81 13 17 5 41 33 57 85 1 53 97 65 61 73 37 45 21 93 77 25 81 13 17 5 41 33 57 85
This is an unacceptable value, as the sequence repeats. The basic rule is that c shares no common factors with m
Our real examples will have large and safe values, for example a=2,175,143, seed=3553, c=10,653, and m=1,000,000:
293732 114329 934700 172753 489332 85129 759100 61953 644932 335929 623500 671153 760532 866729 527900 353 836132 677529 472300 49553 871732 768329 456700 818753 867332 139129 481100 307953 822932 789929 545500 517153 738532 720729 649900 446353 614132 931529 794300 95553 449732 422329 978700 464753 245332 193129 203100 553953 932 243929 467500 363153 716532 574729 771900 892353 392132 185529 116300 141553 27732 76329 500700 110753 623332 247129 925100 799953 178932 697929 389500 209153 694532 428729 893900 338353 170132 439529 438300 187553 605732 730329 22700 756753 1332 301129 647100 45953 356932 151929 311500 55153 672532 282729 15900 784353 948132 693529 760300 233553
Coding
The program just takes the values and determines 200 random values:
public static string gen_linear(long a, long seed, long c, long m) { long x=seed; string res=""; long val; for (int i = 0; i < 200; i++) { Math.DivRem(a * x + c, m, out val); res += Convert.ToString(val) + " "; x = val; } return (res); }
Python
The following is the Python equivalent (showing the first 200 values):
import math def gen_linear(a, seed,c, m): x=seed res="" for i in range(0,200): val = (a * x + c) % m res += str(val) + " " x = val; return (res) a=21 X0=35 c=31 m=100 res=gen_linear(a,X0,c,m) print res
Monte Carlo test for PI
A method we can use is to take the random numbers and use the Monte Carlo value for Pi test. For this we get with your first test we get:
Monte Carlo PI Test: 3.280 PI should be 3.142
which is a fairly good approximation to PI. With this method, we take our random numbers and scale them between 0.0 and 1.0, and take two at a time and calculate:
Sqrt(x*x+y+y)
If this value is less than one, we place in the circle, otherwise it is out of the circle. The estimation of PI is then 4 times the number of points in the circle divided by the total number of points. In the diagram below the blue points are outside the circle and the yellow ones are inside:
The code for the Monte Carlo test for PI is:
public static double pi_test(string values, long m) { int ntotal = 0; int inCircle = 0; double piApprox = 0; string[] vals = values.Split(' '); for (int i = 0; i < 200; i += 2) { double x1 = Convert.ToDouble(vals[i]); double y1 = Convert.ToDouble(vals[i + 1]); if ((Math.Sqrt((x1 / m) * (x1 / m) + (y1 / m) * (y1/m)) <= 1.0)) inCircle++; ntotal++; } piApprox = 4 * ((double)inCircle / (double)ntotal); return (piApprox); }
and for the Serial Coefficient test:
public static double KnuthSerialCoefficient(string vals) { string[] values= vals.Split(' '); int[] idata = new int[values.Length-1]; for (int x = 0; x < values.Length-1; x++) { idata[x] = Convert.ToInt32(values[x].ToString()); } double n = (double) idata.Length; double[] U = new double[(int) n]; double[] V = new double[(int) n]; double sU = 0; // sum(U[j]) double sV = 0; // sum(V[j]) double vU2 = 0; // sum(U[j]^2) double sV2 = 0; // sum(V[j]^2) double sUV = 0; // sum(U[j]*V[j]) for (int j = 0; j < (int) (n - 1); j++) { U[j] = (double) idata[j]; V[j] = idata[j + 1] % n; sU += U[j]; sV += V[j]; vU2 += U[j] * U[j]; sV2 += V[j] * V[j]; sUV += U[j] * V[j]; } double sUsU = sU * sU; double sVsV = sV * sV; double numerator = n * sUV - (sU * sV); double denominator = Math.Pow((n * vU2 - sUsU) * (n * sV2 - sVsV), 0.5); return numerator / denominator; }
Entropy
Entropy measures the amount of randomness in the data. It is measured in terms of the number of bits used.
public static double en(string str, long n) { string[] values = str.Split(' '); Listlist = new List (values); list.Sort(); int index = 0; while (index < list.Count - 1) { if (list[index] == list[index + 1]) list.RemoveAt(index); else index++; } long val = 256 * list.Count / n; return (Math.Log(val) / Math.Log(2)); }