[java] Random (Java 7)에서 181783497276652981 및 8682522807148012는 무엇입니까?

Program / 글쓴이

왜 한 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()시드 매개 변수없이 호출 하면 현재 “시드 고유 식”을 취하고이를 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의 실제 시퀀스간에 상관 관계를 생성 할 수 있습니다.

세 번째 접근 방식은 스레드 및 후속 초기화에서도 무작위로 분산되어 상관 관계가없는 시드를 생성합니다. 그래서 현재 자바 문서 :

이 생성자는 난수 생성기의 시드를이 생성자의 다른 호출과 구별 될 가능성이 높은 값으로 설정합니다.

“스레드 간”및 “비 상관”에 의해 확장 될 수 있습니다.

종자 순서 품질

그러나 시딩 시퀀스의 무작위성은 기본 RNG만큼만 우수합니다. 이 자바 구현에서 시드 시퀀스에 사용 된 RNG는 c = 0 및 m = 2 ^ 64 인 MLCG (Multiplicative Linear Congruential Generator)를 사용합니다. (모듈러스 2 ^ 64는 64 비트 long 정수의 오버플로에 의해 암시 적으로 제공됩니다.) 0 c와 2의 거듭 제곱으로 인해 “품질”(사이클 길이, 비트 상관 관계, …)이 제한됩니다. . 논문에 따르면 전체 사이클 길이 외에 모든 단일 비트에는 자체 사이클 길이가 있으며, 이는 덜 중요한 비트에 대해 기하 급수적으로 감소합니다. 따라서 하위 비트는 더 작은 반복 패턴을 갖습니다. (seedUniquifier ()의 결과는 실제 RNG에서 48 비트로 잘 리기 전에 비트 반전되어야합니다.)

하지만 빠르다! 불필요한 비교 및 ​​설정 루프를 방지하려면 루프 본문이 빨라야합니다. 이것은 아마도이 특정 MLCG의 사용을 설명 할 것입니다.

그리고 언급 된 논문은 1181783497276652981과 같이 c = 0 및 m = 2 ^ 64에 대한 좋은 “승수”목록을 제공합니다.

전체적으로 : JRE 개발자의 노력에 대한 A;) 그러나 오타가 있습니다. (그러나 누군가가 그것을 평가하지 않는 한, 누락 된 선행 1이 실제로 시드 RNG를 개선 할 가능성이 있다는 것을 누가 압니다.)

그러나 일부 승수는 확실히 더 나쁩니다. “1”은 일정한 시퀀스로 이어집니다. “2”는 단일 비트 이동 시퀀스로 이어집니다 (어떻게 든 상관 관계가 있음) …

RNG에 대한 시퀀스 간 상관 관계는 실제로 여러 임의 시퀀스가 ​​인스턴스화되고 병렬화되는 (Monte Carlo) 시뮬레이션과 관련이 있습니다. 따라서 “독립적 인”시뮬레이션 실행을 위해서는 좋은 시드 전략이 필요합니다. 따라서 C ++ 11 표준은 상관되지 않은 시드를 생성하기위한 시드 시퀀스 개념을 도입합니다 .

답변

난수 생성기에 사용되는 방정식은 다음과 같습니다.

LCGE 방정식

여기서 X (n + 1)은 다음 숫자, a는 다 중기, X (n)은 현재 숫자, c는 증분, m은 모듈러스입니다.

자세히 살펴보면 Randoma, c 및 m이 클래스의 헤더에 정의되어 있습니다.

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'

그리고 방법을 보면 protected int next(int bits)이것은 방정식이 구현되었습니다

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

이것은 메소드 seedUniquifier()가 실제로 X (n)을 얻거나 초기화시 첫 번째 경우 X (0) 실제로이며이 8682522807148012 * 181783497276652981값은 값에 의해 추가로 수정된다는 것을 의미합니다 System.nanoTime(). 이 알고리즘은 위의 방정식과 일치하지만 다음과 같은 X (0) = 8682522807148012, a = 181783497276652981, m = 2 ^ 64 및 c = 0입니다. 그러나 mod m이 긴 오버플로에 의해 수행됨에 따라 위의 방정식은 다음과 같습니다.

eq2

논문을 보면 a = 값은 1181783497276652981m = 2 ^ 64, c = 0에 대한 것입니다. 따라서 8682522807148012레거시 코드에서 무작위로 선택된 숫자로 보이는 X (0) 값과 오타 인 것 같습니다. 대한 Random. 여기에서 볼 수 있습니다. 그러나 이러한 선택된 숫자의 장점은 여전히 ​​유효 할 수 있지만 Thomas B.가 언급 한 바와 같이 아마도 논문에 나오는 것처럼 “좋은”것은 아닙니다.

편집-아래의 원래 생각이 명확 해 졌으므로 무시할 수 있지만 참고 용으로 남겨 둡니다.

이것은 결론을 이끌어냅니다.

  1. 논문에 대한 참조는 값 자체가 아니라 a, c 및 m의 다른 값으로 인해 값을 얻는 데 사용되는 방법에 대한 것입니다.

  2. 값이 선두 1과 같지 않고 주석이 잘못 배치 된 것은 우연의 일치입니다 (여전히 이것을 믿기 위해 고군분투합니다).

또는

논문의 표에 대한 심각한 오해가 있었으며 개발자는 처음에 표 값을 사용하는 요점이 무엇인지 곱할 때까지 무작위로 값을 선택했습니다. 이러한 값이 고려되지 않은 경우 자체 시드 값

그래서 당신의 질문에 대답하기 위해

이 두 숫자만큼 잘 작동 할 다른 숫자를 선택할 수 있습니까? 그 이유는 무엇?

예, 임의의 숫자를 사용할 수 있습니다. 실제로 임의 인스턴스화시 시드 값을 지정하면 다른 값을 사용하고 있습니다. 이 값은 생성기의 성능에 영향을주지 않으며 클래스 내에서 하드 코딩 된 a, c 및 m의 값에 의해 결정됩니다.

답변

제공 한 링크에 따라 ( 누락 된 1을 추가 한 후 🙂 ) 2 ^ 64에서 가장 좋은 수익률을 선택했습니다. long은 2 ^ 128에서 숫자를 가질 수 없기 때문입니다.

답변