Почему это случайное значение имеет распределение 25/75 вместо 50/50?

Изменить:. Так что в основном то, что я пытаюсь написать, это хэш 1 бит для double.

Я хочу сопоставить double с true или false с вероятностью 50/50. Для этого я написал код, который выбирает некоторые случайные числа (как пример, я хочу использовать это на данных с регулярностью и все равно получить результат 50/50), проверяет их последний бит и увеличивает y, если он равен 1, или n, если оно равно 0.

Однако этот код постоянно приводит к 25% y и 75% n. Почему это не 50/50? И почему такое странное, но прямолинейное (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);
    }
}

Пример вывода:

250167 749833

Ответы

Ответ 1

Поскольку nextDouble работает так: (source)

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

next(x) делает x случайные биты.

Теперь почему это имеет значение? Поскольку около половины чисел, сгенерированных первой частью (перед делением), меньше 1L << 52, и поэтому их значение не полностью заполняет 53 бита, которые он может заполнить, то есть младший значащий бит значения всегда всегда равен нулю для тех.

Из-за большого количества внимания, которое это получает, вот какое-то дополнительное объяснение того, что на самом деле выглядит double на Java (и многих других языках) и почему это важно в этом вопросе.

В принципе, double выглядит следующим образом: (источник)

double layout

Очень важная деталь, которая не видна на этом рисунке, состоит в том, что числа "нормализованы" 1 так что 53-битная дроби начинается с 1 (путем выбора показателя, такого, что это так), что 1 затем опускается. Вот почему на рисунке показано 52 бита для фракции (значимо), но в ней есть 53 бит.

Нормализация означает, что если в коде для nextDouble установлен 53-й бит, этот бит является неявным ведущим 1, и он уходит, а остальные 52 бита копируются буквально в значение полученного результата double, Если этот бит не установлен, остальные биты должны быть сдвинуты влево до тех пор, пока он не будет установлен.

В среднем половина сгенерированных чисел попадает в случай, когда значение не было сдвинуто слева вообще (и примерно половина из них имеет 0 как младший значащий бит), а другая половина сдвигается по меньшей мере на 1 (или просто полностью равна нулю), поэтому их младший значащий бит всегда равен 0.

1: не всегда, очевидно, это невозможно сделать для нуля, который не имеет наивысшего значения 1. Эти числа называются денормальными или субнормальными числами, см. wikipedia: denormal номер.

Ответ 2

Из docs:

Метод nextDouble реализуется классом Random, как если бы:

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

Но в нем также говорится следующее (основное внимание):

[В ранних версиях Java результат был неправильно рассчитан как:

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

Это может показаться эквивалентным, если не лучше, но на самом деле он ввел большую неоднородность из-за смещения в округлении чисел с плавающей запятой: было в три раза вероятнее, что младший бит от значения будет 0, чем 1! Эта неоднородность, вероятно, практически не имеет большого значения на практике, но мы стремимся к совершенству.]

Эта заметка была там, по крайней мере, с тех пор, как Java 5 (документы для Java <= 1.4 находятся позади входа в систему, слишком ленив для проверки). Это интересно, потому что проблема, по-видимому, все еще существует даже в Java 8. Возможно, "исправленная" версия никогда не тестировалась?

Ответ 3

Этот результат не удивляет меня тем, как представлены числа с плавающей запятой. Предположим, что у нас был очень короткий тип с плавающей точкой с точностью до 4 бит. Если бы мы генерировали случайное число между 0 и 1, распределенное равномерно, было бы 16 возможных значений:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Если это так, как они выглядели в машине, вы можете протестировать бит младшего разряда, чтобы получить 50/50 дистрибутив. Однако поплавки IEEE представлены как мощность в 2 раза больше мантиссы; одно поле в поплавке - это значение 2 (плюс фиксированное смещение). Мощность 2 выбирается так, что часть "мантисса" всегда равна числу >= 1.0 и < 2,0. Это означает, что в действительности числа, отличные от 0.0000, будут представлены следующим образом:

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

(1 до того, как двоичная точка является подразумеваемым значением; для 32- и 64-битных поплавков бит фактически не назначен для хранения этого 1.)

Но если посмотреть на вышеизложенное, следует продемонстрировать, почему, если вы преобразуете представление в биты и посмотрите на бит, вы получите нулевой 75% времени. Это происходит из-за всех значений менее 0,5 (двоичный 0.1000), что является половиной возможных значений, с переводом их мантисса, в результате чего 0 появляется в младшем бите. Ситуация по существу такая же, когда мантисса имеет 52 бита (не включая подразумеваемый 1), как это делает double.

(На самом деле, как пояснил @sneftel в комментарии, мы могли бы включить более 16 возможных значений в распределение, создав:

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

Но я не уверен, что это будет распространяться большинство программистов, поэтому, вероятно, это не стоит. Плюс это не принесет вам многого, когда значения используются для генерации целых чисел, поскольку часто используются значения с плавающей запятой.)