Edit: Donc, fondamentalement, ce que j'essaie d'écrire est un hachage de 1 bit double.
Je veux mapper un doubleà trueou falseavec une chance de 50/50. Pour cela, j'ai écrit du code qui sélectionne des nombres aléatoires (juste à titre d'exemple, je veux l'utiliser sur des données avec des régularités et obtenir toujours un résultat 50/50) , vérifie leur dernier bit et incrémente ys'il est 1, ou ns'il est 0.
Cependant, ce code aboutit constamment à 25% yet 75% n. Pourquoi n'est-ce pas 50/50? Et pourquoi une distribution aussi étrange, mais simple (1/3)?
public class DoubleToBoolean {
@Test
public void test() {
int y = 0;
int n = 0;
Random r = new Random();
for (int i = 0; i < 1000000; i++) {
double randomValue = r.nextDouble();
long lastBit = Double.doubleToLongBits(randomValue) & 1;
if (lastBit == 1) {
y++;
} else {
n++;
}
}
System.out.println(y + " " + n);
}
}Exemple de sortie:
250167 749833
java
random
double
bit-manipulation
probability
gvlasov
la source
la source
doubleValue % 1 > 0.5, mais ce serait trop grossier car cela peut introduire des régularités visibles dans certains cas (toutes les valeurs sont dans la plage de longueur 1). Si c'est trop gros, devrions-nous probablement essayer des gammes plus petites, commedoubleValue % 1e-10 > 0.5e-10? Hé bien oui. Et prendre juste le dernier bit comme hachage de a,doublec'est ce qui se passe lorsque vous suivez cette approche jusqu'à la fin, avec le moins de modulo possible.(lastbit & 3) == 0fonctionnerait cependant, aussi étrange que cela puisse paraître.Réponses:
Parce que nextDouble fonctionne comme ceci: ( source )
next(x)faitxdes bits aléatoires.Maintenant, pourquoi est-ce important? Parce qu'environ la moitié des nombres générés par la première partie (avant la division) sont inférieurs à
1L << 52, et donc leur significand ne remplit pas entièrement les 53 bits qu'il pourrait remplir, ce qui signifie que le bit le moins significatif du significande est toujours zéro pour ceux-ci.En raison de l'attention que cela suscite, voici une explication supplémentaire de ce à quoi
doubleressemble vraiment un en Java (et de nombreux autres langages) et pourquoi il était important dans cette question.En gros, un
doubleressemble à ceci: ( source )Un détail très important non visible sur cette image est que les nombres sont "normalisés" 1 telle sorte que la fraction de 53 bits commence par un 1 (en choisissant l'exposant tel qu'il en soit ainsi), que 1 est alors omis. C'est pourquoi l'image montre 52 bits pour la fraction (significande) mais il y a effectivement 53 bits dedans.
La normalisation signifie que si le code
nextDoubledu 53e bit est défini, ce bit est le premier implicite 1 et il disparaît, et les 52 autres bits sont copiés littéralement dans le significande du résultatdouble. Cependant, si ce bit n'est pas mis à 1, les bits restants doivent être décalés vers la gauche jusqu'à ce qu'il soit mis à 1.En moyenne, la moitié des nombres générés tombent dans le cas où le significand n'a pas du tout été décalé vers la gauche (et environ la moitié de ceux-ci ont un 0 comme bit le moins significatif), et l'autre moitié est décalée d'au moins 1 (ou est juste complètement zéro) donc leur bit le moins significatif est toujours 0.
1: pas toujours, il est clair que cela ne peut pas être fait pour zéro, qui n'a pas le plus élevé 1. Ces nombres sont appelés nombres dénormaux ou sous-normaux, voir wikipedia: nombre dénormal .
la source
random.nextDouble()est généralement la "meilleure" manière pour ce à quoi il est destiné, mais la plupart des gens n'essaient pas de produire un hachage 1 bit à partir de leur double aléatoire. Cherchez-vous une distribution uniforme, une résistance à la cryptanalyse, ou quoi?nextdoit renvoyer unint, donc il ne peut avoir que 32 bits de toute façonÀ partir de la documentation :
Mais il déclare également ce qui suit (c'est moi qui souligne):
Cette note existe depuis Java 5 au moins (les documents pour Java <= 1.4 sont derrière un loginwall, trop paresseux pour être vérifié). Ceci est intéressant, car le problème persiste apparemment même en Java 8. Peut-être que la version "fixe" n'a jamais été testée?
la source
Ce résultat ne me surprend pas compte tenu de la représentation des nombres à virgule flottante. Supposons que nous ayons un type à virgule flottante très court avec seulement 4 bits de précision. Si nous devions générer un nombre aléatoire entre 0 et 1, distribué uniformément, il y aurait 16 valeurs possibles:
Si c'est à cela qu'ils ressemblaient dans la machine, vous pouvez tester le bit de poids faible pour obtenir une distribution 50/50. Cependant, les flotteurs IEEE sont représentés comme une puissance de 2 fois une mantisse; un champ dans le flotteur est la puissance de 2 (plus un décalage fixe). La puissance de 2 est choisie de sorte que la partie "mantisse" soit toujours un nombre> = 1.0 et <2.0. Cela signifie qu'en effet, les nombres autres que ceux
0.0000qui seraient représentés comme ceci:(L'
1avant le point binaire est une valeur implicite; pour les flottants 32 et 64 bits, aucun bit n'est réellement alloué pour contenir cela1.)Mais regarder ce qui précède devrait démontrer pourquoi, si vous convertissez la représentation en bits et regardez le bit faible, vous obtiendrez zéro 75% du temps. Cela est dû au fait que toutes les valeurs inférieures à 0,5 (binaire
0.1000), qui est la moitié des valeurs possibles, ont leurs mantisses décalées, provoquant l'apparition de 0 dans le bit bas. La situation est essentiellement la même lorsque la mantisse a 52 bits (sans compter le 1 implicite) comme adouble.(En fait, comme @sneftel l'a suggéré dans un commentaire, nous pourrions inclure plus de 16 valeurs possibles dans la distribution, en générant:
Mais je ne suis pas sûr que ce soit le type de distribution auquel la plupart des programmeurs s'attendent, donc cela n'en vaut probablement pas la peine. De plus, cela ne vous rapporte pas beaucoup lorsque les valeurs sont utilisées pour générer des entiers, comme le sont souvent les valeurs aléatoires à virgule flottante.)
la source