How to randomly delete half of the files on the server? Writing the Linux command shuf (a command that makes the output Random) with very little data, I extended it with Java’s Random class.

The Random () function

Start from the source code, the process of encountering do not understand the extension out, solved and then back to the source code, until the core code to understand.

/** * An instance of this class is used to generate a stream of * pseudorandom numbers. The class uses a 48-bit seed, which is * modified using a linear congruential formula. (See Donald Knuth, * <i>The Art of Computer Programming, Volume 2</ I >, Section 3.2.1.) * <p> * If two instances of {@code Random} are created with the same
 * seed, and the same sequence of method calls is made for each, they
 * will generate and return identical sequences of numbers. In order to
 * guarantee this property, particular algorithms are specified for the
 * class {@code Random}. Java implementations must use all the algorithms
 * shown here for the class {@code Random}, for the sake of absolute
 * portability of Java code. However, subclasses of class {@code Random}
 * are permitted to use other algorithms, so long as they adhere to the
 * general contracts for all the methods.
 * <p>
 * The algorithms implemented by class {@code Random} use a
 * {@code protected} utility method that on each invocation can supply
 * up to 32 pseudorandomly generated bits.
 * <p>
 * Many applications will find the method {@link Math#random} simpler to use.
 *
 * <p>Instances of {@code java.util.Random} are threadsafe.
 * However, the concurrent use of the same {@codejava.util.Random} * instance across threads may encounter contention and consequent * poor performance. Consider instead  using * {@link java.util.concurrent.ThreadLocalRandom} in multithreaded
 * designs.
 *
 * <p>Instances of {@code java.util.Random} are not cryptographically
 * secure.  Consider instead using {@link java.security.SecureRandom} to
 * get a cryptographically secure pseudo-random number generator for use
 * by security-sensitive applications.
 *
 * @author  Frank Yellin
 * @since1.0 * /
Copy the code

Let’s flip it around

Key points:

This example is used to generate pseudo-random numbers, using a 48-bit seed, modified from a linear congruent equation.

Features:

  1. If the seeds are the same, the sequence of random numbers generated is the same.
  2. The Random class is thread-safe, but calling it in the same instance will result in poor performance due to contention. Consider using itjava.util.concurrent.ThreadLocalRandom 。
  3. The Random class is not encrypted,java.security.SecureRandomPseudorandom number generator that provides secure encryption.

Linear congruence algorithm

Pseudo-random number algorithm core. As for the deeper issues of using this algorithm for me, how to guarantee randomness, etc., I thought about it, but it’s too complicated… Figure out the algorithm first… The deeper issues, I probably gave up, after all, I’m a Java developer. (Manual dog head)

Linear congruence equation

A *x≡b (mod m)

A *x and b divided by m have the same remainder, read a*x congruent with b, mod c.

Random class linear congruences

X(n+1) = (a * X(n) + c) % m

Where X(0) is the seed, the value of X(0) is calculated to get X(1), the value of X(1) is calculated to get X(2)…

By analogy, once the seed (X(0)) is determined, the random number queue is determined and is the cause of characteristic 1.

Let’s see how Random implements X(0). There are two constructors, one to seed and one not to pass.

    // A constructor with no arguments
    public Random(a) {
        this(seedUniquifier() ^ System.nanoTime());
    }

    private static long seedUniquifier(a) {
        // L'Ecuyer, "Tables of Linear Congruential Generators of
        // Different Sizes and Good Lattice Structure", 1999
        for (;;) {
            long current = seedUniquifier.get();
            long next = current * 181783497276652981L;
            if (seedUniquifier.compareAndSet(current, next))
                returnnext; }}private static final AtomicLong seedUniquifier
        = new AtomicLong(8682522807148012L);
        
    // The constructor of the parameter
    public Random(long seed) {
        if (getClass() == Random.class)
            this.seed = new AtomicLong(initialScramble(seed));
        else {
            // subclass might have overriden setSeed
            this.seed = newAtomicLong(); setSeed(seed); }}Copy the code

The no-parameter constructor gets the seed by multiplying current(8682522807148012L) by 181783497276652981L.

The compareAndSet method is thread-safe and is multiplied again if it detects that the current value has been changed by another thread. For (;;) Equivalent to while(ture).

Then you use the result next XOR system.nanotime (), and the result is the seed.

System.nanotime (), like System.currentTimemillis (), is a random number related to time, but it can only be used to calculate time periods. For example, to calculate the execution time of a method, call system.nanotime () before and after the method, and then subtracted from it. But cannot be used to calculate the current date.

Linear congruence appears in the next method. This is the heart of the Random class, and all methods that compute Random numbers call a method.

    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));
    }
    
    private static final long multiplier = 0x5DEECE66DL;
    private static final long addend = 0xBL;
    private static final long mask = (1L << 48) - 1;
Copy the code

Nextseed = (oldseed * multiplier + addend) &mask is equivalent to X(n+1) = (a * X(n) + c) % m.

Multiplier, addend, and mask correspond to A, C, and m respectively, and % m becomes &mask.

The Internet explains it this way:

  1. All the bits higher than the 2 to the N bit, including the 2 to the N bit, are 0
  2. All the bits below 2 to the N are left as they are

So x & [(1L << 48) — 1] is equivalent to x (mod 2^48).

Why does Java use 48-bit seeds instead of the regular 32 or 64 bit ones?

why 48 bit seed in util Random class?



You need more bits of state than bits of output, because the nature of an LCG is such that the low-order bits of state are not very random at all. So if you want 32-bit outputs, you need more than 32 bits of state.



Why use 48 rather than 64? Because 48 is enough, and you’re designing this decades ago, so there are good reasons to want to avoid using any more resources than are strictly necessary.

Good good, please let go, Java bit operator I know it but I do not know why, and for the gross linear compatibility equation can be used to do random number algorithm I do not know, do not want to pretend to know pretend deep (manual laugh cry), hope to understand the big guys with me… (Manual dog head), lol.

Every time I grow up, I want to share with you.