Dev Faq
11
votes

Pourquoi aléatoire.NextLong ne génère-t-il pas toutes les valeurs longues possibles en Java?

Le Javadoc de la méthode suivante () de la classe aléatoire indique que

Parce que la classe aléatoire utilise une graine avec seulement 48 bits, cet algorithme ne retournera pas toutes les valeurs longues possibles. ( Javadoc au hasard ) < / p>

La mise en œuvre est la suivante: xxx

La manière dont je vois qu'il est comme suit: Pour créer une longue longue, nous devrions générer n'importe quel motif de bits possible de 64 bits avec une probabilité égale. Assumant les appels sur Suivant (int) Donnez-nous 32 bits aléatoires, la concaténation de ces bits sera une séquence de 64 bits aléatoires et que nous générons chaque motif de 64 bits avec une probabilité égale. Et donc toutes les valeurs longues possibles.

Je suppose que la personne qui a écrit le Javadoc connaît mieux et que mon raisonnement est une défaillance d'une manière ou d'une autre. Quelqu'un peut-il expliquer où mon raisonnement est incorrect et quel genre de longs sera retourné alors?

2 commentaires

Dupliqué possible de Pourquoi la graine de 48 bits en util de classe aléatoire?

Je suppose que cela ne peut pas générer des chiffres où la première moitié est égale à la seconde moitié. S'ils l'ont fait suivant (32) générerait toujours le même numéro. Ce qui signifierait que vous générez toujours de la même longue longtemps chaque fois que vous l'avez appelé.

3 Réponses :

0
votes

Les générateurs de nombres pseudo-aléatoires sont comme des anneaux géants de nombres. Vous commencez quelque part, puis passez autour de l'anneau étape par étape, lorsque vous tirez des chiffres. Cela signifie qu'avec une graine donnée - un état interne initial - tous les numéros suivants sont prédéterminés. Dans ce cas, étant donné que l'état interne n'est que de 48 bits de large, seuls 2 à la puissance 48 Les nombres aléatoires sont possibles. Donc, depuis que le numéro suivant est donné par le numéro précédent, il est maintenant clair que cette implémentation de NextLong ne générera pas toutes les valeurs longues possibles.

4 commentaires

Strictement parlant, pas la longueur de la valeur de la graine, mais la longueur de l'état interne du générateur est pertinente ici. Il semble être le même pour le générateur d'occasion (je n'ai pas cherché cela).

Je n'aichète pas ce raisonnement. Si je fais ensuite (n) avec n <= longueur de la graine, puis-je obtenir toutes les valeurs N-bits possibles? Vous devez prouver que cela est impossible, sinon, s'il est bien possible, je peux composer un certain nombre de longueurs de ce plus petit nombre de bits.

Notez que l'étape dans ce cas ne signifie pas que les valeurs augmenteront jusqu'à ce qu'ils enveloppent (comme vous pouvez le dire en imprimant quelques-uns). Cela signifie simplement que les valeurs sont prédéterminées par l'état initial.

La partie importante ici (doit être soulignée en gras de quelque chose) est le numéro suivant est donné par le numéro précédent

4
votes

Depuis aléatoire, c'est pseudo-aléatoire, nous savons que, compte tenu de la même graine, elle renvoie les mêmes valeurs. Prendre les docs à leur mot, il y a 48 morceaux de graines. Cela signifie qu'il y a au plus 2 ^ 48 valeurs uniques pouvant être imprimées. S'il y avait plus cela signifierait que certaines valeur que nous avons utilisées auparavant en position Si nous essayons de rejoindre deux résultats, que voyons-nous? P> 

|a|b|c|d|e|f|...|(2^48)-1|

0 commentaires
0
votes

Disons qu'un générateur de k-bit Pseudo aléatoire parfait est celui qui crée toutes les valeurs de graines 2 ^ k possibles dans 2 ^ k Trys. Nous ne pouvons pas faire mieux, car il n'y a que 2 ^ k États, et chaque état est complètement déterminé par l'état précédent et détermine l'état suivant.

suppose que nous écrivons la sortie du générateur 48 bits en binaire . Nous obtenons 2 ^ 48 * 48 bits de cette façon. Et maintenant, nous pouvons dire exactement combien de séquences 64 bits que nous pouvons obtenir en parcourant la liste et en notant les 64 bits suivants (emballage au début en cas de besoin). C'est exactement le nombre de bits que nous avons: 13510798882111488. Même si nous supposons que toutes ces séquences de 64 bits sont différentes (ce qui n'est pas du tout évident), nous avons un long chemin à parcourir jusqu'à 2 ^ 64: 18446744073709551616. P>

J'écris les chiffres à nouveau: P> 

18446744073709551616 pairwise different 64 bit sequences we need
   13510798882111488 64 bit sequences we can get with a 48 bit seed.

3 commentaires

Si le générateur a un état interne de 48 morceaux, il est clair qu'il existe au plus 2 ^ 48 états possibles. Ainsi, peu importe la façon dont vous dessinez 64 bits, il y a au plus 2 ^ 48 séquences de bits possibles au lieu de 2 ^ 64.

Un générateur de k-bit Pseudo aléatoire qui crée toutes les valeurs de 2 ^ k possibles dans 2 ^ k Tries est un générateur très médiocre. En fait, si pauvres, nous pouvons le distinguer. Penser le paradoxe d'anniversaire.

Vous avez raison, @HENRY, maintenant ça le voit aussi. Va éditer ma réponse en conséquence.

Articles qui pourrait vous intéresser :

Comment envoyer une liste vide à la clause IN
Code de réponse 403 inattendu lors de la récupération des données des API
Impossible de trouver la classe UnityPlayerActivity dans com.unity3d.player
Comment définir un tableau dans jsonobject