Java random number algorithm principle and implementation method example explanation

This article describes the java random number algorithm. Share with you for your reference, as follows:

The algorithms implemented by software are pseudo-random algorithms, and the random seed is generally the system time

In number theory, linear congruence equation is the most basic congruence equation. "Linear" means that the number of unknowns of the equation is once, that is, the form is as follows:

Ax ≡ B (MOD n). The equation has a solution if and only if B can be divided by the greatest common divisor of a and n (recorded as GCD (a, n) | b). At this time, if x0 is a solution of the equation, all solutions can be expressed as:

{x0+kn/d|(k∈z)}

Where D is the greatest common divisor of a and n. In the complete residue system {0,1,..., n-1} of module n, there are exactly D solutions.

Example editing

*In equation 3x ≡ 2 (MOD 6), d = GCD (3,6) = 3, 3 does not divide 2, so the equation has no solution.

*In equation 5x ≡ 2 (MOD 6), d = GCD (5,6) = 1, 1 divides by 2, so the equation has exactly one solution in {0,2,3,4,5}: x = 4.

*In equation 4x ≡ 2 (MOD 6), d = GCD (4,6) = 2, 2 is divided by 2, so the equation has exactly two solutions in {0,5}: x = 2 and x = 5.

Pure linear congruence random number generator

Introduction to linear congruence random number generator:

The ancient LCG (linear coherent generator) represents the best and simplest pseudo-random number generator algorithm. The main reason is that it is easy to understand, easy to implement and fast.

The LCG algorithm is mathematically based on the formula:

@H_ 301_ 47@X (0)=seed; X(n+1) = (A * X(n) + C) % M;

Where, the coefficients are:

X (0) indicates seed

Module m, M > 0

Coefficient a, 0 < a < m

Increment C, 0 < = C < m

Original value (seed) 0 < = x (0) < m

The parameters c, m and a are sensitive, or directly affect the quality of pseudo-random number generation.

Generally speaking, we use @ H_ 301_ 47@M =(2 ^ 31) - 1 = 2147483647. This is a 31 bit prime number, a = 48271. This a can make m obtain a complete period, where C is an odd number. At the same time, if the data selection is not good, it is likely to obtain a random number with a very short period. For example, if we go to seed = 179424105, the period of the random number is 1, which will lose the meaning of randomness.

@H_ 301_ 47 @ (48271 * 179424105 + 1) mod (31st power of 2 - 1) = 179424105

Write a simple example yourself, 100000 times at random, with a random range of 0 to 9, to see if it is uniform

Relatively speaking, it is quite uniform

PS: here are two online tools with similar functions for your reference:

Online random number / string generation tool: http://tools.jb51.net/aideddesign/suijishu

Online random character / random password generation tool: http://tools.jb51.net/aideddesign/rnd_password

High strength password generator: http://tools.jb51.net/password/CreateStrongPassword

For more information about Java algorithms, readers who are interested can see the topics on this site: Java data structure and algorithm tutorial, summary of Java character and string operation skills, summary of Java DOM node operation skills, summary of java file and directory operation skills, and summary of Java cache operation skills