Rrooom
@Rrooom

Как генерировать случайное число на промежутке?

Как программно генерировать ДЕЙСТВИТЕЛЬНО близкие к случайным числа на промежутке?

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

Но... Я мало что знаю, как их смешивать? Как случайный поток байт превратить в число на отрезке, что бы оно оставалось достаточно случайным?

Можете либо объяснить, либо указать путь для изучения этого вопроса?
  • Вопрос задан
  • 3649 просмотров
Пригласить эксперта
Ответы на вопрос 3
barkalov
@barkalov
Собираете всю энтропию побитно (паравозиком) в одно сообщение. Берете хеш-функцию с подходящим размером и распределением, например, MD5 и пропускаете сообщение через нее. На выходе получите равномерно распределенное случайное 128-битное число. То есть от 0 до (2^128)-1, если представлять беззнаково. Делите (или берете остаток, если нужны целые), прибавляете - получаете нужный вам диапазон.

PS: MD5 здесь в качестве примера, лучше не используйте его в суровом продакшене, он скомпрометирован. Выбирайте хеш-функцию с количеством внутренних состояний, соответствующим предполагаемой длине энтропии.
Ответ написан
Deerenaros
@Deerenaros
Программист, математик, задрот и даже чуть инженер
Ой, какие сложности. А отстаток брать не учили? А потом добавляем нижнюю границу.

Смешивать можно как угодно. Можно побайтово xor'ить, можно складывать, можно умножать. К слову, побайтовый xor - наверное, лучший способ перемешать. Только он побайтовый и даёт едва ли не лучшее распределение.

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

Number RandomBeetwen(Number min, Number max):
    return min + Random() % (max - min);
Ответ написан
jcmvbkbc
@jcmvbkbc
http://dilbert.com/strip/1998-08-24
Я читал, что для этого берут несколько источников случайных чисел - /dev/urandom, железные генераторы, посылают движения мышкой пользователя и смешивают вместе... Я мало что знаю, как их смешивать?

Если у вас есть /dev/urandom то всё уже смешано как надо, берите случайные биты оттуда.
Как случайный поток байт превратить в число на отрезке, что бы оно оставалось достаточно случайным?

Зависит от того, нужны ли вам целые числа на вашем отрезке или плавающие.

С целыми числами нужно взять столько случайных бит, сколько покрывает нужный вам отрезок, значения которые не вписываются в отрезок выкинуть и сместить полученное значение к началу отрезка. Для плавающих чисел ещё проще: нужно взять единицу вашего плавающего типа, заменить биты мантиссы (23 для float, 52 для double) случайными битами и отнять 1. Получится случайное число в диапазоне [0, 1), умножить его на длину отрезка и сместить к его началу.

В частном случае, если криптостойкость не нужна, то для получения раномерно распределённых на отрезке [a, b) плавающих чисел проще всего взять drand48: r = drand48() * (b - a) + a.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы