14
points
1. Introduction
In java we can implement custom random number generator by using LCG (Linear congruential generator) algorithm. LCG is one of the oldest and best-known pseudorandom number generator algorithm. We can adjust this implementation to work on int or long.
Linear congruential generator is defined by recurrence relation:
Where:
- Xn+1 - new seed
- a - MULTIPLIER_A
- Xn - current seed field
- c - INCREMENT_C
- m - MODULUS
In our below implementation above variables were used.
2. Implementation in java
Note:
Every time
randomInt()method is called, we assign new value to seed.
public class RandomUtil {
private final static int MULTIPLIER_A = 1103515245;
private final static int INCREMENT_C = 12345;
private final static int MODULUS = 2147483647; // max int
private static int seed = 3819201;
public static int randomInt() {
seed = (seed * MULTIPLIER_A + INCREMENT_C) % MODULUS;
return seed;
}
public static int randomPositiveInt() {
int tmp = randomInt();
if (tmp < 0) {
seed = tmp * -1;
}
return seed;
}
public static void main(String[] args) {
System.out.println(randomPositiveInt()); // 1801118106
System.out.println(randomPositiveInt()); // 41211189
System.out.println(randomPositiveInt()); // 11738570
for (int i = 0; i < 7; i++) {
System.out.println(randomPositiveInt());
}
}
}Output:
1801118106
41211189
11738570
865299259
887958952
992620351
1793753076
477297891
1620379360
1194566247Explanation
Below 2 fields:
int MULTIPLIER_A = 1103515245;
int INCREMENT_C = 12345;are used by runtime libraries of various compilers:
- glibc (used by GCC)
- ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++
- C90, C99, C11: Suggestion in the ISO/IEC 9899, C18
3. Probability distribution test
import java.util.Arrays;
public class RandomUtilProbabilityTest {
public static void main(String[] args) {
int[] probabilityDistribution = new int[10];
for (int i = 0; i < 30_000; i++) {
int next = RandomUtil.randomPositiveInt() % 10;
probabilityDistribution[next]++;
}
// [2976, 3019, 2973, 3132, 3000, 3006, 3021, 2959, 3030, 2884]
System.out.println(Arrays.toString(probabilityDistribution));
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < probabilityDistribution.length; i++) {
int next = probabilityDistribution[i];
min = Math.min(min, next);
max = Math.max(max, next);
}
System.out.println(" min: " + min); // min: 2884
System.out.println(" max: " + max); // max: 3132
System.out.println("diff: " + (max - min)); // diff: 248
}
}Output:
[2976, 3019, 2973, 3132, 3000, 3006, 3021, 2959, 3030, 2884]
min: 2884
max: 3132
diff: 2484. JDK Random class - probability distribution test
import java.util.Arrays;
import java.util.Random;
public class JdkRandomProbabilityTest {
private static final Random random = new Random(3819201);
public static int nextInt(int min, int max) {
return random.nextInt((max - min) + 1) + min;
}
public static void main(String[] args) {
int[] probabilityDistribution = new int[10];
for (int i = 0; i < 30_000; i++) {
int next = nextInt(0, Integer.MAX_VALUE - 1) % 10;
probabilityDistribution[next]++;
}
// [2963, 2885, 3049, 3041, 3002, 3089, 2967, 3020, 3019, 2965]
System.out.println(Arrays.toString(probabilityDistribution));
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < probabilityDistribution.length; i++) {
int next = probabilityDistribution[i];
min = Math.min(min, next);
max = Math.max(max, next);
}
System.out.println(" min: " + min); // min: 2903
System.out.println(" max: " + max); // max: 3093
System.out.println("diff: " + (max - min)); // diff: 190
}
}Output:
[2976, 2984, 3091, 3093, 3037, 2969, 3030, 2903, 2905, 3012]
min: 2903
max: 3093
diff: 190References
