EN
Java - own random number generator (custom implementation)
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
randomNumber()
method is called, we assign new value to seed.
/**
* Based on long as int can overflow.
*/
public class RandomUtil {
private final static long MULTIPLIER_A = 1103515245L;
private final static long INCREMENT_C = 12345L;
private final static long MODULUS = 2147483647L; // max int
private static long seed = 3819201L;
public static long randomNumber() {
// we use long instead of int, as int can overflow
// when seed * MULTIPLIER_A + INCREMENT_C
seed = (seed * MULTIPLIER_A + INCREMENT_C) % MODULUS;
return seed;
}
public static long randomPositiveNumber() {
long tmp = randomNumber();
if (tmp < 0) {
seed = tmp * -1;
}
return seed;
}
public static void main(String[] args) {
System.out.println(randomPositiveNumber()); // 1801118106
System.out.println(randomPositiveNumber()); // 41211189
System.out.println(randomPositiveNumber()); // 11738570
for (int i = 0; i < 7; i++) {
System.out.println(randomPositiveNumber());
}
}
}
Output:
1801118106
41211189
11738570
865299259
887958952
992620351
1793753076
477297891
1620379360
1194566247
Explanation
Below 2 fields:
long MULTIPLIER_A = 1103515245L;
long INCREMENT_C = 12345L;
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++) {
long next = RandomUtil.randomPositiveNumber() % 10L;
probabilityDistribution[(int) next]++;
}
// [2979, 3049, 3000, 2971, 2975, 2954, 3016, 3072, 3027, 2957]
System.out.println(Arrays.toString(probabilityDistribution));
// 30000
System.out.println(Arrays.stream(probabilityDistribution).sum());
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: 2954
System.out.println(" max: " + max); // max: 3072
System.out.println("diff: " + (max - min)); // diff: 118
}
}
Output:
[2979, 3049, 3000, 2971, 2975, 2954, 3016, 3072, 3027, 2957]
30000
min: 2954
max: 3072
diff: 118
4. 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: 190