Каков наилучший способ создания случайного двойного на POSIX?

Question

Я бы хотел получить равномерное распределение в диапазоне [0.0, 1.0)

Если возможно, позвольте реализации использовать случайные байты из / dev / urandom.

Было бы также неплохо, если бы ваше решение было поточно-безопасным . Если вы не уверены, укажите это.

См. какое-то решение Я подумал после прочтения других ответов.

Answer 1

Кажется, это очень хороший способ:

unsigned short int r1, r2, r3; // let r1, r2 and r3 hold random values double result = ldexp(r1, -48) + ldexp(r2, -32) + ldexp(r3, -16);

Это основано на реализации NetBSD drand48.

Answer 2

Простой : двойной тип имеет 52 бита с точностью до IEEE. Так что сгенерируйте случайное целое число без знака (52 бита или больше) (например, читая байты из dev / urandom), преобразуйте его в двойное и разделите на 2 ^ (количество битов).

Это дает численно равномерное распределение (в котором вероятность того, что значение находится в данном диапазоне пропорционально диапазону) вплоть до 52-й двоичной цифры.

Сложно : Однако в диапазоне [0,1) существует много двойных значений, которые не могут быть сгенерированы выше. Чтобы быть точным, половина значений в диапазоне [0,0.5) (те, у которых установлен их младший значащий бит) не может появиться. Три четверти значений в диапазоне [0,0.25) (те, у которых установлен хотя бы один из двух младших битов) не могут появиться и т. Д., Причем возможно только одно положительное значение меньше 2 ^ -51, несмотря на то, что двойник способен представлять миллиарды таких ценностей. Таким образом, нельзя сказать, что он действительно однороден в указанном диапазоне с полной точностью.

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

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

• Начните экспоненту с 52 и выберите 52-битное случайное целое число без знака (при условии, что у Мантиссы 52 бита).
• Если старший значащий бит целого числа равен 0, увеличьте показатель степени на единицу, сдвиньте целое число влево на единицу и заполните младший значащий бит новым случайным битом.
• Повторяйте до тех пор, пока вы не достигнете 1 в наиболее значимом месте, иначе показатель не станет слишком большим для вашего двойника (1023. Или, возможно, 1022).
• Если вы нашли 1, разделите ваше значение на 2 ^ экспоненты. Если вы получили все нули, верните 0 (я знаю, это на самом деле не особый случай, но он подчеркивает, насколько маловероятно возвращение 0 [Править: на самом деле это может быть особый случай - это зависит от того, хотите ли вы генерировать или нет) Денормс. Если нет, тогда, когда у вас будет достаточно 0 в ряду, вы отбрасываете все, что осталось, и возвращаете 0. Но на практике это так маловероятно, чтобы быть незначительным, если случайный источник не является случайным).

Я не знаю, есть ли какое-то практическое применение для такого случайного двойника, заметьте. Ваше определение случайного должно зависеть от того, для чего оно. Но если вы можете извлечь выгоду из того, что все 52 его значащих бита являются случайными, это может быть полезно.

Answer 3

/ dev / urandom не является POSIX и обычно недоступен.

Стандартный способ генерации двойного равномерно в [0,1) состоит в генерации целого числа в диапазоне [0,2 ^ N) и делении на 2 ^ N. Так что выберите свой любимый генератор случайных чисел и используйте его. Для моделирования, мой - это Mersenne Twister , так как он очень быстрый, но все еще не очень хорошо коррелированный. На самом деле, он может сделать это для вас, и даже имеет версию, которая даст большую точность для меньших чисел. Как правило, вы даете ему начальное значение, которое помогает повторить отладку или показать другим свои результаты. Конечно, вы можете получить в своем коде случайное число из / dev / urandom в качестве начального числа, если оно не указано.

Для криптографических целей вы должны использовать вместо этого одну из стандартных криптографических библиотек, такую ​​как openssl ), которая действительно будет использовать / dev / urandom, когда доступно.

Что касается безопасности потоков, большинство из них не будет, по крайней мере, со стандартными интерфейсами, поэтому вам нужно будет создать слой сверху или использовать их только в одном потоке. Те, которые являются поточно-ориентированными, дают вам возможность изменять их состояние, чтобы вместо этого вы эффективно запускали несколько не взаимодействующих генераторов случайных чисел, что может быть не тем, что вы ищете.

Answer 4

Хитрость в том, что вам нужен 54-битный рандомизатор, отвечающий вашим требованиям. Несколько строк кода с объединением, чтобы вставить эти 54 бита в мантиссу, и у вас есть ваш номер. Хитрость не в двойном плавающем трюке, это ваш желаемый рандомизатор.

Answer 5

Чтение из файлов является поточно-ориентированным AFAIK, поэтому использование fopen () для чтения из / dev / urandom даст «действительно случайные» байты.

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

Например:

FILE* f = fopen("/dev/urandom", "r");
int32_t int;
fread(&int, sizeof(int32_t), 1, f);
fclose(f);
double theRandomValue = int / (double) (2 ** 32 - 1);

Answer 6

#include <stdlib.h>
printf("%f\n", drand48());

/ DEV / случайно:

double c;
fd = open("/dev/random", O_RDONLY);
unsigned int a, b;
read(fd, &a, sizeof(a));
read(fd, &b, sizeof(b));
if (a > b)
   c = fabs((double)b / (double)a);
else
    c = fabs((double)a / (double)b);

c - ваше случайное значение