Principle Pseudo Random and Optimization of Java Random Number
- 2021-06-28 09:18:20
- OfStack
This article describes random numbers in Java and why they are pseudo-random.
Catalog:
Math.random() Random Class Pseudo-random How to Optimize Random Encapsulated Random Processing Tool Class
1. Math.random()
1.1 Introduction
Random numbers can be obtained from Math.random(), which returns an double value between [0.0, 1.0].
private static void testMathRandom() {
double random = Math.random();
System.out.println("random = " + random);
}
Execute output: random = 0.8543235849742018
double accounts for 8 bytes on 32-bit and 64-bit machines in Java, with up to 17 significant digits in the positive and decimal parts of double.
If you want to get an integer of type int, you only need to convert the result above to type int.For example, get the int integer between [0, 100].The methods are as follows:
double d = Math.random();
int i = (int) (d*100);
1.2 Implementation Principles
private static final class RandomNumberGeneratorHolder {
static final Random randomNumberGenerator = new Random();
}
public static double random() {
return RandomNumberGeneratorHolder.randomNumberGenerator.nextDouble();
}
Get an Random object first, in Math is the singleton mode, only 1.
Calling the nextDouble method of the Random object returns a random double value.
You can see that the Math.random() method is also ultimately a call to a method in the Random class.
2. Random class
2.1 Introduction
The Random class provides two constructors:
public Random() {
}
public Random(long seed) {
}
One is the default constructor, and one is capable of passing in a random seed.
Random numbers are then obtained from the Random object, such as:
int r = random.nextInt(100);
2.2 API
boolean nextBoolean() // Return 1 individual boolean Type Random Number
void nextBytes(byte[] buf) // Generate random bytes and place them in a byte array buf in
double nextDouble() // Return 1 individual [0.0, 1.0) Between double Random number of type
float nextFloat() // Return 1 individual [0.0, 1.0) Between float Random number of type
int nextInt() // Return 1 individual int Type Random Number
int nextInt(int n) // Return 1 individual [0, n) Between int Random number of type
long nextLong() // Return 1 individual long Type Random Number
synchronized double nextGaussian() // Return 1 individual double Type of random number, which is Gauss (normally) distributed double Value, the average of which is 0.0 , the standard deviation is 1.0 .
synchronized void setSeed(long seed) // Use a single long Seed Sets the seed for this random number generator
2.3 cases
private static void testRandom(Random random) {
// Get Random boolean value
boolean b = random.nextBoolean();
System.out.println("b = " + b);
// Get a random array buf[]
byte[] buf = new byte[5];
random.nextBytes(buf);
System.out.println("buf = " + Arrays.toString(buf));
// Get Random Double Value, range [0.0, 1.0)
double d = random.nextDouble();
System.out.println("d = " + d);
// Get Random float Value, range [0.0, 1.0)
float f = random.nextFloat();
System.out.println("f = " + f);
// Get Random int value
int i0 = random.nextInt();
System.out.println("i without bound = " + i0);
// Get Random [0,100) Between int value
int i1 = random.nextInt(100);
System.out.println("i with bound 100 = " + i1);
// Getting the random Gaussian distribution double value
double gaussian = random.nextGaussian();
System.out.println("gaussian = " + gaussian);
// Get Random long value
long l = random.nextLong();
System.out.println("l = " + l);
}
public static void main(String[] args) {
testRandom(new Random());
System.out.println("\n\n");
testRandom(new Random(1000));
testRandom(new Random(1000));
}
Execute output:
b = true
buf = [-55, 55, -7, -59, 86]
d = 0.6492428743107401
f = 0.8178623
i without bound = -1462220056
i with bound 100 = 66
gaussian = 0.3794413450456145
l = -5390332732391127434b = true
buf = [47, -38, 53, 63, -72]
d = 0.46028809169559504
f = 0.015927613
i without bound = 169247282
i with bound 100 = 45
gaussian = -0.719106498075259
l = -7363680848376404625b = true
buf = [47, -38, 53, 63, -72]
d = 0.46028809169559504
f = 0.015927613
i without bound = 169247282
i with bound 100 = 45
gaussian = -0.719106498075259
l = -7363680848376404625
You can see that during a run, if the seeds are the same, the random values are the same.
Summary 1:
1. With the same seed, N random numbers are generated. When you set the seed, what N random numbers are is determined.The random numbers generated the same number of times are identical.*
2. If two Random instances are created with the same seed, the same method call sequence is applied to each instance, and they will generate and return the same number sequence.
2.4 Implementation Principles
Let's start with the Random class constructor and properties:
private final AtomicLong seed;
private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53)
private static final AtomicLong seedUniquifier
= new AtomicLong(8682522807148012L);
public Random() {
this(seedUniquifier() ^ System.nanoTime());
}
private static long seedUniquifier() {
for (;;) {
long current = seedUniquifier.get();
long next = current * 181783497276652981L;
if (seedUniquifier.compareAndSet(current, next))
return next;
}
}
public Random(long seed) {
if (getClass() == Random.class)
this.seed = new AtomicLong(initialScramble(seed));
else {
this.seed = new AtomicLong();
setSeed(seed);
}
}
synchronized public void setSeed(long seed) {
this.seed.set(initialScramble(seed));
haveNextNextGaussian = false;
}
There are two constructors, one parameterless and one transmissible to the seed.
What is the function of seeds?
The seed is the first used value to generate a random number. The mechanism is to convert the value of the seed into a point in the random number space through a function, and the resulting random number is evenly dispersed in the space, and the subsequent random number is related to the first random number.
A seed is generated by seedUniquifier () ^ System.nanoTime () without parameters, which is achieved by using the CAS spin lock.Using the System.nanoTime() method, a nanosecond time amount was obtained, which participated in the formation of 48-bit seeds, and then a very abnormal operation was performed: multiply by 1817834972766981L continuously until the same result before and after a multiplication to increase randomness in one step, where nanotime can be considered a true random number, but it is necessary to mention that,nanoTime, unlike our commonly used currenttime method, returns a random number instead of the time from January 1, 1970 to the present. It is only used to compare and calculate a period of time, such as the run time of a line of code, the time of database import, etc. It is not used to calculate the day today.
Do not set random seeds at will. You may get the same random number if you run more times. The seeds generated by Random can already meet your usual needs.
Take nextInt() as an example to continue the analysis:
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
Or through CAS, and then back to the displacement, this block of algorithm is more complex, not in-depth study.
3. Pseudo-random
3.1 What is pseudo-random?
(1) Pseudo-random numbers are periodic sequences that appear to be random but are fixed in nature, i.e. regular random.
(2) As long as this random number is generated by a deterministic algorithm, that is, pseudo-random, you can only make your random number closer to random through continuous algorithm optimization. (Random is a property that contradicts the algorithm itself)
(3) True random numbers are those obtained from real random events.
3.2 Java Random Number Generation Principle
The random number generation of Java is generated by a linear congruence formula, that is, by a complex algorithm.
Insecurity of 3.3 Pseudo-Random Numbers
The random number function that comes with Java is very easy to crack because a hacker can deduce your seed by getting a random number sequence of a certain length, and then he can predict the next random number.For example, eos's dapp guess game stole a lot of tokens because the hacker cracked the random rules.
4. How to Optimize Random
The main consideration is that the generated random number cannot be repeated, and if it is repeated, one will be regenerated.You can use the array or Set storage to determine whether duplicate random numbers are included, and regenerate a new random number recursively.
5. An encapsulated random processing tool class
https://github.com/kuangzhongwen/android-common-libs/blob/master/src/main/java/waterhole/commonlibs/utils/RandomUtils.java