181783497276652981 및 8682522807148012는 무작위로 무엇입니까 (Java 7)?

181783497276652981 및 8682522807148012는 무작위로 무엇입니까 (Java 7)?

---

왜 181783497276652981그리고에 8682522807148012선택 Random.java되었습니까?

다음은 Java SE JDK 1.7의 관련 소스 코드입니다.

/**
 * Creates a new random number generator. This constructor sets
 * the seed of the random number generator to a value very likely
 * to be distinct from any other invocation of this constructor.
 */
public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}

private static long seedUniquifier() {
    // 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))
            return next;
    }
}

private static final AtomicLong seedUniquifier
    = new AtomicLong(8682522807148012L);

따라서, new Random()seed 매개 변수없이 호출 하면 현재 "seed uniquifier"를 가져와이를 XOR합니다 System.nanoTime(). 그런 다음 다음에 181783497276652981저장 될 다른 시드 균등화기를 작성 하는 데 사용 됩니다 new Random().

리터럴가 181783497276652981L와 8682522807148012L상수에 배치되지 않습니다,하지만 그들은 다른 곳에서는 나타나지 않습니다.

처음에 그 의견은 나에게 쉬운 리드를 제공합니다. 해당 기사를 온라인으로 검색 하면 실제 기사가 생성 됩니다. 8682522807148012신문에 나타나지 않지만 181783497276652981나타나지 않습니다 - 다른 번호의 문자열로 1181783497276652981하고, 181783497276652981로모그래퍼 1앞에 추가.

이 논문 1181783497276652981은 선형 합동 발생기에 좋은 "장점"을 산출하는 숫자라고 주장한다 . 이 숫자가 단순히 Java로 잘못 복사 되었습니까? 않습니다 181783497276652981허용 장점을 가지고?

그리고 왜 8682522807148012선택 되었습니까?

두 번호를 온라인으로 검색하면 아무런 설명 만 얻을 수없는 페이지 도 떨어 통지 1의 앞을 181783497276652981.

이 두 숫자뿐만 아니라 다른 숫자를 선택할 수 있습니까? 그 이유는 무엇?

---

1. 이 숫자가 단순히 Java로 잘못 복사 되었습니까?

   예, 오타 인 것 같습니다.

2. 181783497276652981에 허용되는 장점이 있습니까?

   이것은 논문에 제시된 평가 알고리즘을 사용하여 결정할 수 있습니다. 그러나 "원래"숫자의 장점은 아마도 더 높을 것입니다.

3. 그리고 왜 8682522807148012가 선택 되었습니까?

   무작위로 보입니다. 코드 작성시 System.nanoTime ()의 결과 일 수 있습니다.

4. 이 두 숫자뿐만 아니라 다른 숫자를 선택할 수 있습니까?

   모든 숫자가 똑같이 "좋은"것은 아닙니다. 그래서 안돼.

시드 전략

JRE 구현과 버전 간 기본 시딩 스키마에는 차이가 있습니다.

public Random() { this(System.currentTimeMillis()); }

public Random() { this(++seedUniquifier + System.nanoTime()); }

public Random() { this(seedUniquifier() ^ System.nanoTime()); }

첫 번째는 여러 RNG를 연속으로 생성하는 경우 허용되지 않습니다. 생성 시간이 동일한 밀리 초 범위에 속하는 경우 완전히 동일한 시퀀스를 제공합니다. (같은 씨드 => 같은 순서)

두 번째는 스레드 안전하지 않습니다. 동시에 초기화 할 때 여러 스레드가 동일한 RNG를 얻을 수 있습니다. 또한, 후속 초기화의 시드는 상관되는 경향이 있습니다. 시스템의 실제 타이머 해상도에 따라 시드 시퀀스가 ​​선형으로 증가 할 수 있습니다 (n, n + 1, n + 2, ...). 무작위 씨앗 은 어떻게 다를 필요가 있습니까? 의사 난수 발생기의 초기화에서 참조 된 논문 공통 결함에서 , 상관 된 시드는 다수의 RNG의 실제 시퀀스 사이에 상관을 생성 할 수있다.

The third approach creates randomly distributed and thus uncorrelated seeds, even across threads and subsequent initializations. So the current java docs:

This constructor sets the seed of the random number generator to a value very likely to be distinct from any other invocation of this constructor.

could be extended by "across threads" and "uncorrelated"

Seed Sequence Quality

But the randomness of the seeding sequence is only as good as the underlying RNG. The RNG used for the seed sequence in this java implementation uses a multiplicative linear congruential generator (MLCG) with c=0 and m=2^64. (The modulus 2^64 is implicitly given by the overflow of 64bit long integers) Because of the zero c and the power-of-2-modulus, the "quality" (cycle length, bit-correlation, ...) is limited. As the paper says, besides the overall cycle length, every single bit has an own cycle length, which decreases exponentially for less significant bits. Thus, lower bits have a smaller repetition pattern. (The result of seedUniquifier() should be bit-reversed, before it is truncated to 48-bits in the actual RNG)

But it is fast! And to avoid unnecessary compare-and-set-loops, the loop body should be fast. This probably explains the usage of this specific MLCG, without addition, without xoring, just one multiplication.

And the mentioned paper presents a list of good "multipliers" for c=0 and m=2^64, as 1181783497276652981.

All in all: A for effort @ JRE-developers ;) But there is a typo. (But who knows, unless someone evaluates it, there is the possibility that the missing leading 1 actually improves the seeding RNG.)

But some multipliers are definitely worse: "1" leads to a constant sequence. "2" leads to a single-bit-moving sequence (somehow correlated) ...

The inter-sequence-correlation for RNGs is actually relevant for (Monte Carlo) Simulations, where multiple random sequences are instantiated and even parallelized. Thus a good seeding strategy is necessary to get "independent" simulation runs. Therefore the C++11 standard introduces the concept of a Seed Sequence for generating uncorrelated seeds.

---

If you consider that the equation used for the random number generator is:

Where X(n+1) is the next number, a is the multipler, X(n) is the current number, c is the increment and m is the modulus.

If you look further into Random, a, c and m are defined in the header of the class

private static final long multiplier = 0x5DEECE66DL;   //= 25214903917 -- 'a'
private static final long addend = 0xBL;               //= 11          -- 'c'
private static final long mask = (1L << 48) - 1;       //= 2 ^ 48 - 1  -- 'm'

and looking at the method protected int next(int bits) this is were the equation is implemented

nextseed = (oldseed * multiplier + addend) & mask;
//X(n+1) =  (X(n)   *      a     +    c  ) mod m

This implies that the method seedUniquifier() is actually getting X(n) or in the first case at initialisation X(0) which is actually 8682522807148012 * 181783497276652981, this value is then modified further by the value of System.nanoTime(). This algorithm is consistent with the equation above but with the following X(0) = 8682522807148012, a = 181783497276652981, m = 2 ^ 64 and c = 0. But as the mod m of is preformed by the long overflow the above equation just becomes

Looking at the paper, the value of a = 1181783497276652981 is for m = 2 ^ 64, c = 0. So it appears to just be a typo and the value 8682522807148012 for X(0) which appears to be a seeming randomly chosen number from legacy code for Random. As seen here. But the merit of these chosen numbers could still be valid but as mentioned by Thomas B. probably not as "good" as the one in the paper.

EDIT - Below original thoughts have since been clarified so can be disregarded but leaving it for reference

This leads me the conclusions:

1. The reference to the paper is not for the value itself but for the methods used to obtain the values due to the different values of a, c and m

2. It is mere coincidence that the value is otherwise the same other than the leading 1 and the comment is misplaced (still struggling to believe this though)

OR

There has been a serious misunderstanding of the tables in the paper and the developers have just chosen a value at random as by the time it is multiplied out what was the point in using the table value in the first place especially as you can just provide your own seed value any way in which case these values are not even taken into account

So to answer your question

Could other numbers have been chosen that would have worked as well as these two numbers? Why or why not?

Yes, any number could have been used, in fact if you specify a seed value when you Instantiate Random you are using any other value. This value does not have any effect on the performance of the generator, this is determined by the values of a,c and m which are hard coded within the class.

---

As per the link you provided, they have chosen (after adding the missing 1 :) ) the best yield from 2^64 because long can't have have a number from 2^128

참고URL : https://stackoverflow.com/questions/18092160/whats-with-181783497276652981-and-8682522807148012-in-random-java-7