Изменить: Итак, в основном то, что я пытаюсь написать, - это 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
java
random
double
bit-manipulation
probability
гвласов
источник
источник
doubleValue % 1 > 0.5, но это было бы слишком грубо, поскольку в некоторых случаях он может вводить видимые закономерности (все значения находятся в диапазоне длины 1). Если это слишком крупно, то стоит ли нам попробовать меньшие диапазоны, напримерdoubleValue % 1e-10 > 0.5e-10? Ну да. И использование только последнего бита в качестве хеша для adouble- это то, что происходит, когда вы следуете этому подходу до конца с наименьшим возможным модулем.(lastbit & 3) == 0хотя бы сработает, как ни странно.Ответы:
Потому что nextDouble работает так: ( источник )
public double nextDouble() { return (((long) next(26) << 27) + next(27)) / (double) (1L << 53); }next(x)делаетxслучайные биты.Почему это так важно? Поскольку примерно половина чисел, сгенерированных первой частью (до деления), меньше
1L << 52, и, следовательно, их значение не полностью заполняет 53 бита, которые оно могло бы заполнить, что означает, что наименее значимый бит мантиссы всегда равен нулю для них.Из-за того количества внимания, которое ему уделяется, вот некоторые дополнительные объяснения того, как
doubleдействительно выглядит a в Java (и многих других языках) и почему это имеет значение в этом вопросе.В основном это
doubleвыглядит так: ( источник )Очень важная деталь, не видимая на этом рисунке, заключается в том, что числа «нормализованы» на 1 , так что 53-битная дробь начинается с 1 (выбирая такой показатель степени), что 1 затем опускается. Вот почему изображение показывает 52 бита для дроби (мантиссы), но фактически в ней 53 бита.
Нормализация означает, что если в коде
nextDoubleустановлен 53-й бит, этот бит является неявным ведущим 1 и уходит, а остальные 52 бита копируются буквально в мантиссу полученного результатаdouble. Однако, если этот бит не установлен, оставшиеся биты необходимо сдвинуть влево, пока он не станет установленным.В среднем половина сгенерированных чисел попадает в тот случай, когда мантисса вообще не сдвигалась влево (и примерно половина из них имеет нулевой младший бит), а другая половина сдвигается как минимум на 1 (или просто полностью ноль), поэтому их младший бит всегда равен 0.
1: не всегда, ясно, что это невозможно сделать для нуля, у которого нет наивысшего 1. Эти числа называются денормальными или субнормальными числами, см. Wikipedia: денормальное число .
источник
random.nextDouble()обычно является «лучшим» способом для того, для чего он предназначен, но большинство людей не пытается произвести 1-битный хеш из своего случайного двойника. Вы ищете равномерное распределение, устойчивость к криптоанализу или что-то еще?nextдолжен возвращатьint, так что в любом случае он может иметь не более 32 битИз документов :
Но в нем также говорится следующее (выделено мной):
Эта заметка была там по крайней мере, начиная с Java 5 (документы для Java <= 1.4 находятся за входом в систему, слишком ленив, чтобы проверить). Это интересно, потому что проблема, по-видимому, все еще существует даже в Java 8. Возможно, «исправленная» версия никогда не тестировалась?
источник
Этот результат меня не удивляет, учитывая, как представлены числа с плавающей запятой. Предположим, у нас есть очень короткий тип с плавающей точкой с точностью всего 4 бита. Если бы мы сгенерировали случайное число от 0 до 1, распределенное равномерно, было бы 16 возможных значений:
0.0000 0.0001 0.0010 0.0011 0.0100 ... 0.1110 0.1111Если так они выглядели в машине, вы могли бы протестировать младший бит, чтобы получить распределение 50/50. Однако числа с плавающей запятой IEEE представлены как степень, умноженная на 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Но я не уверен, что такое распространение ожидает большинство программистов, поэтому, вероятно, это не стоит того. Кроме того, это не очень выгодно, когда значения используются для генерации целых чисел, как это часто бывает со случайными значениями с плавающей запятой.)
источник