Насколько случайным является std :: random_shuffle? - PullRequest
Новая
       5

Насколько случайным является std :: random_shuffle?

1 голос
/ 29 декабря 2010

Я хотел бы сгенерировать случайное число разумно произвольной длины в C ++. Под «разумно произвольным» я подразумеваю ограничение по скорости и памяти главного компьютера.

Предположим:

  • Я хочу выбрать десятичное число (основание 10) длиной ceil(log10(MY_CUSTOM_RAND_MAX)) от 0 до 10^(ceil(log10(MY_CUSTOM_RAND_MAX))+1)-1

  • У меня есть vector<char>

  • Длина vector<char> составляет ceil(log10(MY_CUSTOM_RAND_MAX))

  • Каждый char на самом деле является целым числом, случайным числом от 0 до 9, выбираемым с помощью rand() или аналогичными методами

Если я использую std::random_shuffle, чтобы перетасовать вектор, я мог бы перебирать каждый элемент с конца, умножая его на умноженные на десять степеней, чтобы преобразовать его в unsigned long long или все, что отображается в моем конечном диапазоне.

Я не знаю, есть ли проблемы с std::random_shuffle с точки зрения того, насколько она случайна или нет, особенно когда выбирается последовательность rand() результатов для заполнения vector<char>.

Насколько схематичен std::random_shuffle для генерации случайного числа произвольной длины таким образом, в количественном смысле?

(Я понимаю, что в Boost есть библиотека для создания случайных int чисел. Не ясно, каковы ограничения диапазона, но это выглядит как MAX_INT. Тем не менее, я понимаю, что указанная библиотека существует. Это больше общего вопроса об этой части STL при генерации произвольно большого случайного числа. Заранее спасибо за то, что сосредоточили свои ответы на этой части.)

1 Ответ

7 голосов
/ 29 декабря 2010

Мне немного непонятно, каков фокус этого вопроса, но я постараюсь ответить на него с нескольких точек зрения:

  • Качество стандартной функции библиотеки rand () обычно низкое. Тем не менее, очень легко найти сменные генераторы случайных чисел, которые имеют более высокое качество (вы упомянули Boost.Random сами, так что вы точно знаете о других RNG). Также возможно повысить (без каламбура) качество вывода rand (), объединив результаты нескольких вызовов, если вы будете осторожны: http://www.azillionmonkeys.com/qed/random.html
  • Если вам не нужно десятичное представление в конце, нет смысла его генерировать, а затем преобразовывать в двоичное. Вы можете так же легко соединить несколько 32-битных случайных чисел (из rand () или где-либо еще) в произвольное случайное число шириной в битах.
  • Если вы генерируете отдельные цифры (двоичные или десятичные) в случайном порядке, то нет смысла их перетасовывать потом.
...