java repetir Por que esse valor aleatório tem uma distribuição de 25/75 em vez de 50/50?



não repetir numeros random java (3)

Dos docs :

O método nextDouble é implementado pela classe Random como se fosse por:

public double nextDouble() {
  return (((long)next(26) << 27) + next(27))
      / (double)(1L << 53);
}

Mas também afirma o seguinte (ênfase minha):

[Nas primeiras versões do Java, o resultado foi calculado incorretamente como:

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);

Isso pode parecer equivalente, se não melhor, mas de fato introduziu uma grande não uniformidade devido ao viés no arredondamento dos números de ponto flutuante: era três vezes mais provável que o bit de baixa ordem do significando fosse 0 do que isso seria 1 ! Esta não-uniformidade provavelmente não importa muito na prática, mas nós nos esforçamos para a perfeição.]

Esta nota está lá desde o Java 5, pelo menos (docs para Java <= 1.4 estão atrás de um loginwall, com preguiça de checar). Isso é interessante, porque o problema aparentemente ainda existe mesmo no Java 8. Talvez a versão "fixa" nunca tenha sido testada?

Edit: Então, basicamente o que eu estou tentando escrever é um hash de 1 bit para o double .

Quero mapear um double para true ou false com 50/50 de chance. Para isso eu escrevi código que pega alguns números aleatórios (apenas como um exemplo, eu quero usar isso em dados com regularidades e ainda obter um resultado 50/50) , verifica seu último bit e incrementa y se for 1, ou n se é 0

No entanto, este código resulta constantemente em 25% y 75% n . Por que não é 50/50? E por que uma distribuição tão esquisita, mas direta (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);
    }
}

Exemplo de saída:

250167 749833

Answer #1

Este resultado não me surpreende, dado como os números de ponto flutuante são representados. Vamos supor que tivéssemos um tipo de ponto flutuante muito curto com apenas 4 bits de precisão. Se fôssemos gerar um número aleatório entre 0 e 1, distribuído uniformemente, haveria 16 valores possíveis:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Se é assim que eles apareciam na máquina, você poderia testar o bit de baixa ordem para obter uma distribuição 50/50. No entanto, os flutuadores IEEE são representados como uma potência de 2 vezes uma mantissa; um campo no flutuante é a potência de 2 (mais um deslocamento fixo). A potência de 2 é selecionada de modo que a parte "mantissa" seja sempre um número> = 1,0 e <2,0. Isso significa que, na verdade, os números diferentes de 0.0000 seriam representados assim:

0.0001 = 2^(-4) x 1.000
0.0010 = 2^(-3) x 1.000
0.0011 = 2^(-3) x 1.100
0.0100 = 2^(-2) x 1.000
... 
0.0111 = 2^(-2) x 1.110
0.1000 = 2^(-1) x 1.000
0.1001 = 2^(-1) x 1.001
...
0.1110 = 2^(-1) x 1.110
0.1111 = 2^(-1) x 1.111

(O 1 antes do ponto binário é um valor implícito; para flutuadores de 32 e 64 bits, nenhum bit é realmente alocado para manter este 1 )

Mas olhando para o acima deve demonstrar por que, se você converter a representação em bits e olhar para o bit baixo, você receberá zero 75% do tempo. Isso se deve a todos os valores menores que 0,5 (binário 0.1000 ), que é metade dos valores possíveis, fazendo com que suas mantissas mudem, fazendo com que 0 apareça no bit baixo. A situação é essencialmente a mesma quando a mantissa tem 52 bits (não incluindo o implícito 1) como um double .

(Na verdade, como @sneftel sugeriu em um comentário, poderíamos incluir mais de 16 valores possíveis na distribuição, gerando:

0.0001000 with probability 1/128
0.0001001 with probability 1/128
...
0.0001111 with probability 1/128
0.001000  with probability 1/64
0.001001  with probability 1/64
...
0.01111   with probability 1/32 
0.1000    with probability 1/16
0.1001    with probability 1/16
...
0.1110    with probability 1/16
0.1111    with probability 1/16

Mas eu não tenho certeza se é o tipo de distribuição que a maioria dos programadores esperaria, então provavelmente não vale a pena. Além disso, você não ganha muito quando os valores são usados ​​para gerar inteiros, como os valores aleatórios de ponto flutuante geralmente são.


Answer #2

Porque nextDouble funciona assim: ( source )

public double nextDouble()
{
    return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
}

next(x) faz x bits aleatórios.

Agora, por que isso importa? Porque cerca de metade dos números gerados pela primeira parte (antes da divisão) são menores que 1L << 52 e, portanto, o seu significante não preenche inteiramente os 53 bits que ele poderia preencher, significando que o bit menos significativo do significando é sempre zero para aqueles.

Por causa da quantidade de atenção que isso está recebendo, aqui está uma explicação extra do que realmente é um double em Java (e muitas outras linguagens) e por que isso importava nessa questão.

Basicamente, um double parece com isto: ( source )

Um detalhe muito importante não visível nesta figura é que os números são "normalizados" 1, de tal forma que a fração de 53 bits começa com 1 (escolhendo o expoente de tal forma que é assim), que 1 é então omitido. É por isso que a imagem mostra 52 bits para a fração (significand), mas existem efetivamente 53 bits nela.

A normalização significa que, se no código for nextDouble o 53rd bit estiver definido, esse bit será o 1 implícito e desaparecerá, e os outros 52 bits serão copiados literalmente para o significando do double resultante. Se esse bit não for definido, os bits restantes devem ser deslocados para a esquerda até que ele seja definido.

Em média, metade dos números gerados caem no caso em que o significando não foi deslocado para a esquerda (e cerca de metade deles tem um 0 como seu bit menos significativo), e a outra metade é deslocada em pelo menos 1 (ou é apenas completamente zero) para que seu bit menos significativo seja sempre 0.

1: nem sempre, claramente, não pode ser feito para zero, que não tem o mais alto 1. Esses números são chamados de números denormais ou subnormais, veja wikipedia: número denormal .





probability