Que sont les 181783497276652981 et 8682522807148012 dans Random (Java 7)?

Question

Pourquoi n'ont - 181783497276652981 et 8682522807148012 choisi en Random.java?

Voici le code source correspondant de 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);

Donc, en invoquant new Random() sans aucune graine de paramètres prend le courant "de la graine uniquifier" et XORs il avec System.nanoTime(). Il utilise ensuite l' 181783497276652981 pour créer une autre graine uniquifier être conservées pour la prochaine fois new Random() est appelé.

Les littéraux 181783497276652981L et 8682522807148012L ne sont pas placés dans des constantes, mais ils n'apparaissent pas n'importe où ailleurs.

Au premier abord, le commentaire donne-moi un facile. Recherche en ligne pour que l'article rendements de l'article. 8682522807148012 n'apparaît pas dans le livre, mais 181783497276652981 n'apparaissent que comme un sous-chaîne d'un autre nombre, 1181783497276652981, ce qui est 181783497276652981 avec un 1 ajouté.

Le rapport affirme que l' 1181783497276652981 est un nombre qui donne de bons "mérite" pour un générateur linéaire à congruence. A ce nombre tout simplement mal copié dans Java? N' 181783497276652981 ont un niveau acceptable de mérite?

Et pourquoi était - 8682522807148012 - il choisi?

Recherche en ligne pour nombre donne aucune explication, seulement cette page qui remarque également la tombée 1 face 181783497276652981.

D'autres chiffres ont été retenus qui aurait fonctionné aussi bien que ces deux nombres? Pourquoi ou pourquoi pas?

Answer 1

1. A ce nombre tout simplement mal copié dans Java?

   Oui, semble être une faute de frappe.

2. Ne 181783497276652981 acceptable mérite?

   Cela pourrait être déterminée à l'aide de l'évaluation de l'algorithme présenté dans le document. Mais le mérite de "l'original" le nombre est probablement plus élevé.

3. Et pourquoi était-8682522807148012 choisi?

   Semble être aléatoire. Il pourrait être le résultat de Système.nanoTime() lorsque le code a été écrit.

4. D'autres chiffres ont été retenus qui aurait fonctionné aussi bien que ces deux nombres?

   Pas chaque nombre serait tout aussi "bon". Donc, pas de.

L'Ensemencement Des Stratégies

Il y a des différences dans la valeur par défaut-semis de schéma entre les différentes versions et la mise en œuvre de la JRE.

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

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

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

Le premier n'est pas acceptable si vous créez plusieurs Rng dans une rangée. Si leur temps de création à l'automne de la même milliseconde, ils continueront de donner des séquences complètement identiques. (même seed => même séquence)

Le second n'est pas thread-safe. Plusieurs threads peuvent obtenir les mêmes Rng lors de l'initialisation en même temps. En outre, les graines de la suite des initialisations ont tendance à être corrélées. En fonction de la résolution du timer du système, la séquence des semences pourrait être linéairement croissante de (n, n+1, n+2, ...). Comme indiqué dans la Façon dont différents ne aléatoires, les graines doivent être? et référencés papier défauts les plus Courants lors de l'initialisation de générateurs de nombres pseudo-aléatoires, en corrélation les graines peuvent générer de corrélation entre les séquences de plusieurs Rng.

La troisième approche crée distribués de façon aléatoire et donc non corrélées graines, même à travers les fils et postérieure de l'initialisation. Donc le courant de java docs:

Ce constructeur définit la graine du générateur de nombres aléatoires pour un valeur très susceptibles d'être distinct de tout autre invocation de cette constructeur.

pourrait être étendu par "dans les threads" et "indépendantes"

Séquence Des Semences De Qualité

Mais le caractère aléatoire de l'ensemencement de la séquence est seulement aussi bon que le sous-jacent RNG. Le générateur de nombres aléatoires utilisé pour la séquence des semences dans cette implémentation java utilise un multiplicative générateur linéaire à congruence (MLCG) avec c=0 et m=2^64. (Le module 2^64 est implicitement donnée par le débordement de 64 bits entiers longs) En raison de la zero c et la puissance-de-2-module, la "qualité" (de la longueur du cycle, peu de corrélation, ...) est limitée. Comme le dit le rapport, en plus de l'ensemble de la longueur du cycle, chaque bit a une longueur de cycle, ce qui diminue de façon exponentielle pour les moins de bits significatifs. Ainsi, les bits de poids faible ont un plus petit modèle de répétition. (Le résultat de seedUniquifier() doit être peu inversé, avant il est tronqué à 48 bits dans le RNG)

Mais il est rapide! Et pour vous éviter de comparer-et-configurer-boucles, le corps de la boucle doit être rapide. C'est probablement ce qui explique l'utilisation de ce MLCG, sans plus, sans xoring, juste une multiplication.

Et le dit document présente une liste de bons "multiplicateurs" pour c=0 et m=2^64, comme 1181783497276652981.

Dans l'ensemble: Une pour l'effort de @ JRE-développeurs ;) Mais il y a une faute de frappe. (Mais qui sait, à moins que quelqu'un l'évalue, il est possible que le manque de leader 1 améliore réellement le semis RNG.)

Mais certains multiplicateurs sont certainement pire: "1" conduit à une constante de la séquence. "2" conduit à un seul bit de déplacement de la séquence (d'une certaine manière corrélée) ...

L'inter-séquence de corrélation pour le Rng est en fait pertinente pour (Monte Carlo) des Simulations, où de multiples séquences aléatoires sont instanciés et même parallélisée. Donc un bon semis stratégie est nécessaire pour obtenir des "indépendants" runs". Donc le C++11 introduit le concept de Semence de Séquence pour générer décorrélé de graines.

Answer 2

Si vous considérez que l'équation utilisée pour le générateur de nombre aléatoire est:

Où X(n+1) est le nombre suivant, est le multiplicateur, X(n) est le nombre actuel, c est l'incrément et m est le module.

Si vous regardez plus loin en Random, a, c et m sont définis dans l'en-tête de la classe

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'

et en regardant la méthode protected int next(int bits) c'est là que l'équation est mis en œuvre

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

Cela implique que la méthode seedUniquifier() est réellement obtenir X(n) ou, dans le premier cas, lors de l'initialisation de X(0), ce qui est réellement 8682522807148012 * 181783497276652981, cette valeur est ensuite multipliée par plus loin la valeur de System.nanoTime(). Cet algorithme est compatible avec l'équation ci-dessus, mais avec la suite X(0) = 8682522807148012, a = 181783497276652981, m = 2 ^ 64 et c = 0. Mais comme le mod m est préformé par le long de dépassement de l'équation ci-dessus devient

En regardant le papier, la valeur de a = 1181783497276652981 est pour m = 2 ^ 64, c = 0. Il semble juste être une faute de frappe et la valeur 8682522807148012 X(0), ce qui semble être un semblant choisi au hasard le numéro de code legacy pour Random. Comme on le voit ici. Mais le mérite de ces nombres choisis pourraient encore être valide, mais comme mentionné par Thomas B. probablement pas aussi "bon" que celui du papier.

EDIT - Dessous de réflexions originales ont depuis été clarifiée peut être ignoré, mais en le laissant pour référence

Ce qui m'amène aux conclusions:

1. La référence pour le papier n'est pas pour la valeur elle-même, mais pour les méthodes utilisées pour obtenir les valeurs en raison des différentes valeurs de a, c et m

2. C'est une simple coïncidence que la valeur est le même autre que le leader de la 1 et le commentaire est mal placé (encore du mal à le croire)

OU

Il y a eu une grave erreur d'interprétation des tableaux dans le document et les développeurs ont juste choisi une valeur au hasard, par le temps, il est multiplié quel était le point en utilisant le tableau de la valeur, en premier lieu, d'autant que vous pouvez de votre propre valeur de départ de toute façon dans ce cas, ces valeurs ne sont même pas pris en compte

Donc, pour répondre à votre question

D'autres chiffres ont été retenus qui aurait fonctionné aussi bien que ces deux nombres? Pourquoi ou pourquoi pas?

Oui, n'importe quel nombre pourrait avoir été utilisé, en fait, si vous spécifiez une valeur de départ lorsque vous Instanciez Aléatoire, vous utilisez toute autre valeur. Cette valeur n'a aucun effet sur le rendement du générateur, ce qui est déterminé par les valeurs de a,c et m qui sont codés en dur dans la classe.

Answer 3

Selon le lien que vous avez fourni, ils ont choisi (après  :) en ajoutant le 1 manquant ) le meilleur rendement possible de 2 ^ 64 car longtemps ne peut avoir un nombre compris entre 2 ^ 128