O co chodzi z 181783497276652981 i 8682522807148012 w trybie losowym (Java 7)?

Dlaczego 181783497276652981i 8682522807148012dobrane Random.java?

Oto odpowiedni kod źródłowy z 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);

Tak więc, wywołanie new Random()bez żadnego parametru ziarna pobiera bieżący "identyfikator zarodka" i wykonuje go XOR System.nanoTime(). Następnie używa 181783497276652981do utworzenia kolejnego identyfikatora nasion, który ma być przechowywany na następny raz new Random().

Literały 181783497276652981Li 8682522807148012Lnie są umieszczane w stałych, ale nie pojawiają się nigdzie indziej.

Na początku komentarz daje mi łatwy trop. Wyszukiwanie tego artykułu w Internecie powoduje wyświetlenie faktycznego artykułu . 8682522807148012nie pojawiają się na papierze, ale 181783497276652981wydaje - jako podciąg inny numer 1181783497276652981, który jest 181783497276652981z 1poprzedzany.

Artykuł twierdzi, że 1181783497276652981jest to liczba, która daje dobrą „zasługę” dla liniowego generatora kongruencjalnego. Czy ten numer został po prostu nieprawidłowo skopiowany do Javy? Czy 181783497276652981ma akceptowalną wartość?

A dlaczego został 8682522807148012wybrany?

Wyszukiwanie w Internecie dla dowolnego numeru nie daje żadnego wyjaśnienia, tylko ta strona, która również odnotowuje spadek 1przed 181783497276652981.

Czy można było wybrać inne liczby, które działałyby równie dobrze jak te dwie liczby? Dlaczego lub dlaczego nie?

1. Czy ten numer został po prostu nieprawidłowo skopiowany do Javy?

   Tak, wygląda na literówkę.

2. Czy 181783497276652981 ma akceptowalną wartość?

   Można to określić za pomocą algorytmu oceny przedstawionego w artykule. Ale zasługa „oryginalnej” liczby jest prawdopodobnie wyższa.

3. A dlaczego wybrano 8682522807148012?

   Wydaje się przypadkowe. Może to być wynikiem działania System.nanoTime () podczas pisania kodu.

4. Czy można było wybrać inne liczby, które działałyby równie dobrze jak te dwie liczby?

   Nie każda liczba byłaby równie „dobra”. Więc nie.

Strategie wysiewu

Istnieją różnice w schemacie domyślnego inicjowania między różnymi wersjami i implementacją środowiska JRE.

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

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

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

Pierwsza z nich jest nie do przyjęcia, jeśli tworzysz wiele generatorów liczb losowych z rzędu. Jeśli czas ich utworzenia mieści się w tym samym zakresie milisekund, dadzą całkowicie identyczne sekwencje. (to samo ziarno => ta sama sekwencja)

Drugi nie jest bezpieczny wątkowo. Wiele wątków może otrzymać identyczne RNG podczas inicjalizacji w tym samym czasie. Ponadto początki kolejnych inicjalizacji są zwykle skorelowane. W zależności od aktualnej rozdzielczości zegara systemu, sekwencja nasion może wzrastać liniowo (n, n + 1, n + 2, ...). Jak stwierdzono w Jak różne muszą być losowe nasiona? oraz w przywołanym artykule Powszechne defekty w inicjalizacji generatorów liczb pseudolosowych , skorelowane ziarna mogą generować korelację między rzeczywistymi sekwencjami wielu RNG.

Trzecie podejście tworzy losowo rozmieszczone, a zatem nieskorelowane ziarna, nawet w wątkach i kolejnych inicjalizacjach. Tak więc obecna dokumentacja java:

Ten konstruktor ustawia ziarno generatora liczb losowych na wartość, która z dużym prawdopodobieństwem będzie inna niż jakiekolwiek inne wywołanie tego konstruktora.

można rozszerzyć o „w wątkach” i „nieskorelowane”

Jakość sekwencji nasion

Ale losowość sekwencji wysiewu jest tak dobra, jak podstawowa RNG. RNG używany do sekwencji inicjującej w tej implementacji Java używa multiplikatywnego generatora liniowej kongruencji (MLCG) z c = 0 im = 2 ^ 64. (Moduł 2 ^ 64 jest domyślnie określony przez przepełnienie 64-bitowych liczb całkowitych) Ze względu na zero c i moduł potęgi 2, "jakość" (długość cyklu, korelacja bitowa, ...) jest ograniczona . Jak mówi artykuł, poza całkowitą długością cyklu, każdy bit ma swoją własną długość cyklu, która maleje wykładniczo dla mniej znaczących bitów. W ten sposób niższe bity mają mniejszy wzorzec powtórzeń. (Wynik seedUniquifier () powinien być odwrócony bitowo, zanim zostanie obcięty do 48-bitów w rzeczywistym RNG)

Ale to jest szybkie! Aby uniknąć niepotrzebnych pętli porównujących i ustawiających, treść pętli powinna być szybka. To prawdopodobnie wyjaśnia użycie tego konkretnego MLCG, bez dodatku, bez xoringu, tylko po jednym mnożeniu.

A wspomniana praca przedstawia listę dobrych „mnożników” dla c = 0 im = 2 ^ 64, jako 1181783497276652981.

Podsumowując: A za wysiłek @ JRE-developers;) Ale jest literówka. (Ale kto wie, chyba że ktoś to oceni, istnieje możliwość, że brakująca wiodąca 1 faktycznie poprawia rozstawiającą RNG.)

Ale niektóre mnożniki są zdecydowanie gorsze: „1” prowadzi do stałej sekwencji. „2” prowadzi do sekwencji ruchu jednobitowego (w jakiś sposób skorelowanej) ...

Korelacja między sekwencjami dla RNG jest w rzeczywistości istotna dla symulacji (Monte Carlo), w których wiele losowych sekwencji jest tworzonych, a nawet równoległych. Dlatego też, aby uzyskać „niezależne” przebiegi symulacji, konieczna jest dobra strategia wysiewu. Dlatego standard C ++ 11 wprowadza koncepcję sekwencji nasion do generowania nieskorelowanych nasion.

Jeśli weźmiesz pod uwagę, że równanie użyte dla generatora liczb losowych to:

Gdzie X (n + 1) to następna liczba, a to mnożnik, X (n) to bieżąca liczba, c to przyrost, a m to moduł.

Jeśli przyjrzysz się dokładniej Random, a, c i m są zdefiniowane w nagłówku klasy

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'

i patrząc na metodę, w której protected int next(int bits)to równanie jest realizowane

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

Oznacza to, że metoda seedUniquifier()faktycznie pobiera X (n) lub w pierwszym przypadku podczas inicjalizacji X (0), która jest w rzeczywistości 8682522807148012 * 181783497276652981, ta wartość jest następnie modyfikowana o wartość System.nanoTime(). Algorytm ten jest zgodny z powyższym równaniem, ale z następującym X (0) = 8682522807148012, a = 181783497276652981, m = 2 ^ 64 i c = 0. Ale ponieważ mod m jest utworzony przez długi przepełnienie, powyższe równanie staje się po prostu

Patrząc na papier , wartość a = 1181783497276652981jest dla m = 2 ^ 64, c = 0. Więc wydaje się, że to po prostu literówka, a wartość 8682522807148012X (0), która wydaje się być pozornie losowo wybraną liczbą ze starego kodu dla Random. Jak widać tutaj. Ale zasługa tych wybranych liczb może nadal być aktualna, ale jak wspomniał Thomas B. prawdopodobnie nie jest tak „dobra” jak ta w artykule.

EDYCJA - Poniżej oryginalne myśli zostały wyjaśnione, więc można je zignorować, ale pozostawić je w celach informacyjnych

To prowadzi mnie do wniosków:

1. Odniesienie do artykułu nie dotyczy samej wartości, ale metod zastosowanych do uzyskania wartości ze względu na różne wartości a, c i m

2. To zwykły zbieg okoliczności, że wartość jest poza tym taka sama, niż wiodąca 1, a komentarz jest niewłaściwy (wciąż jednak trudno w to uwierzyć)

LUB

Doszło do poważnego niezrozumienia tabel w artykule, a programiści właśnie wybrali losową wartość, ponieważ do czasu jej pomnożenia, jaki był sens używania wartości tabeli w pierwszej kolejności, zwłaszcza że możesz po prostu podać swoją własna wartość ziarna w jakikolwiek sposób, w którym to przypadku wartości te nie są nawet brane pod uwagę

Więc odpowiadając na twoje pytanie

Czy można było wybrać inne liczby, które działałyby równie dobrze jak te dwie liczby? Dlaczego lub dlaczego nie?

Tak, można było użyć dowolnej liczby, w rzeczywistości, jeśli określisz wartość początkową podczas tworzenia instancji losowej, używasz dowolnej innej wartości. Wartość ta nie ma żadnego wpływu na wydajność generatora, jest to określone przez wartości a, c i m, które są zakodowane na stałe w klasie.

Zgodnie z podanym przez Ciebie linkiem wybrali ( po dodaniu brakującego 1 :) ) najlepszy zysk z 2 ^ 64, ponieważ długo nie mogą mieć liczby z 2 ^ 128