Всегда ли значение RAND_MAX (2 ^ n) -1?

Question

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

Если RAND_MAX всегда (2 ^ n) -1, это упрощает решение проблемы, которая вызвала недавно перемещенный код из MinGW GCC в Linux GCC. RAND_MAX кажется больше (я не проверял, но, возможно, равен INT_MAX или какому-либо символу), поэтому какой-то старый, наивно написанный RAND_MAX-код не достаточно большой, чтобы его можно было обойти. Теперь мне нужно решить, насколько общей должна быть эта библиотека, учитывая аккуратность написания кода, который корректно справляется с возможностью переполнения, не делая предположений, например, о. ширина целого.

В любом случае, есть ли достаточно широко используемые компиляторы C ++, которые используют что-то отличное от (2 ^ n) -1 для RAND_MAX?

Кроме того, правильно ли я, что ((RAND_MAX | (RAND_MAX >> 1)) == RAND_MAX) всегда и только верно, если RAND_MAX равен ((2 ^ n) -1) для некоторого целого числа без знака n. Я считаю, что RAND_MAX технически является int, но не имеет смысла иметь отрицательное или дробное значение, поэтому я думаю, что могу смело обесценивать их. Меня ничего не беспокоит, но я продолжаю думать, что выражение выглядит неправильно, и не могу понять, почему.

Наконец, хотя я не буду счастлив, пока не получу свое собственное рабочее решение, что должен использовать для случайных чисел, а не писать его сам? Мне нужны случайные числа в диапазоне 0 <= x <параметр, и я особенно хочу, чтобы вероятности как равные, как и разумно возможные для всех чисел. Например, взятие (rand ()% upperbound) смещает в сторону меньших значений, особенно когда верхняя граница велика - я хочу этого избежать. </p>

Есть ли для этого Boost или C ++ 0x?

EDIT

После чего-то в бите «Связанные» на боковой стороне страницы показано, что действительно есть способ получить случайные числа с заданными нижними и верхними границами в усилении.

Answer 1

• Я не знаю ни одной реализации, для которой RAND_MAX не на единицу меньше степени двух, но это не предусмотрено стандартом;

• ((RAND_MAX | (RAND_MAX >> 1)) == RAND_MAX) действительно способ проверить, является ли RAND_MAX на единицу меньше, чем степень двух.

• Я использую

  int alea(int n){ 
    assert (0 < n && n <= RAND_MAX); 
    int partSize = 
      n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); 
    int maxUsefull = partSize * n + (partSize-1); 
    int draw; 
    do { 
      draw = rand(); 
    } while (draw > maxUsefull); 
    return draw/partSize; 
  }
  

чтобы сделать как можно более равномерное распределение случайных чисел из rand ().

Answer 2

Для реализаций rand, которые используют (вариант а) линейного конгруэнтного генератора (большинство из них), тогда RAND_MAX будет простым числом, необязательно в форме 2 ^ n - 1 ("простое число Мерсенна").

Кроме того, 2 ^ 31-1 является простым числом, но если n не является простым, 2 ^ n - 1 не является простым.

(Действительно, если n = ab,тогда 2 ^ n - 1 = (2 ^ a - 1) (1 + 2 ^ b + 2 ^ (2b) + ...))

Приблизительно 2 ^ 64, единственное простое число Мерсенна - 2 ^61 - 1.

И вам действительно следует избегать линейных конгруэнтных генераторов, если у вас есть полусерьезное требование о генерации случайных чисел.На самом деле, я бы сказал, что кроме игры в тетрис, вам следует избегать rand() из библиотеки C.

Answer 3

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

Я рекомендую Boost.Random .Генератор Mersenne twister представляет собой хороший компромисс между скоростью, использованием памяти и качеством.

Answer 4

Согласно ISO C (по крайней мере, от C99 до C17) и POSIX (выпуск 7, издание 2016 г.), RAND_MAX должно быть не менее 32767, т. Е. 2 ​​^ 15−1, и других ограничений нет.

В GNU / Linux, RAND_MAX гарантированно будет точно 2147483647 = 2 ^ 31−1 на всех архитектурах для согласованности с POSIX относительно функции random(): POSIX указывает, что возвращаемое значениенаходится в диапазоне от 0 до 2 ^ 31−1, а справочная страница Linux random (3) документирует диапазон от 0 до RAND_MAX.

Answer 5

В стандартном заголовочном файле GNU, stdlib.h, есть определение RAND_MAX, которое должно быть единственным определением в вашей системе:

#define RAND_MAX    2147483647

Значение 2147483647 = 0x7fffffff - это наибольшее 32-разрядное целое число без знака.

Функции rand, определенные в stdlib.h, надежны в стандартных средах GNU с одной оговоркой: многопоточным (pthread) средам для синхронизации rand (), srand () и Вызов rand_r (), поскольку они не реентерабельны. См. Справочную страницу для srand для объяснения.

RAND_MAX не должен быть определен где-либо еще в вашей системе. Если вы видите другое значение для RAND_MAX или видите определение RAND_MAX где-то, кроме stdlib.h, то это должна быть нестандартная непереносимая среда. Windows славится тем, что усложняет стандартизацию и переносимость (например, реализация сокетов и API).

Answer 6

В Embacadero C ++ Builder в stdlib.h определены две переменные:

/* Maximum value returned by "rand" function*/
#define RAND_MAX  0x7FFFU

/* Maximum value returned by "_lrand" function (also used by random() macro)*/
#define LRAND_MAX 0x7FFFFFFFU

Answer 7

В GCC (4.6) RAND_MAX = 0x7FFFFFFF (31 бит) В MS Visual Studio (2012) RAND_MAX = 0x7FFF (15 бит)