rand > RAND_MAX - C/C++

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

А>Требуется генерировать случайные числа в диапазоне от 0 до больше чем RAND_MAX, и чтоб распределение было более менее равномерное.
А>ну и скорость чтоб не самая медленная. и еще чтоб кроссплатформенно.

ну ты хоть пояснил бы -- целые числа тебе нужны или нецелые. Какой результирующий тип нужен? uint64_t?

Здравствуйте, Аноним, Вы писали:

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

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

Если бы мне был нужен заведомо более-менее быстрый генератор, я взял бы исходник RC4, отломил бы от него смешивание псевдослучайной последовательности с данными (поскольку нужна только псевдослучайная последовательность), в качестве ключа использовал бы какое-нибудь разумное количество байтов из системного генератора, и первый килобайт сгенерированной последовательности отправлял бы в /dev/null — говорят, у RC4 первый килобайт не очень хороший.

Здравствуйте, Аноним, Вы писали:

здесь

int random(int lim)
{
    g_RandSeed = g_RandSeed * 0x8088405 + 1;
    return __int64(g_RandSeed) * lim >> 32;
}

Здравствуйте, dilmah, Вы писали:

А>>Требуется генерировать случайные числа в диапазоне от 0 до больше чем RAND_MAX, и чтоб распределение было более менее равномерное.
А>>ну и скорость чтоб не самая медленная. и еще чтоб кроссплатформенно.

D>ну ты хоть пояснил бы -- целые числа тебе нужны или нецелые. Какой результирующий тип нужен? uint64_t?

обычного uint 32 бита хватит, хотя сойдет и double от 0 до 1

Здравствуйте, Bell, Вы писали:

B>Здравствуйте, Аноним, Вы писали:

B>здесь

не хотелось бы тянуть целый буст к проекту из за одной функции...

Здравствуйте, thesynapse1, Вы писали:

T>не хотелось бы тянуть целый буст к проекту из за одной функции...

Зачем весь? Можно по частям.
здесь

#define XRAND_MAX (RAND_MAX*(RAND_MAX + 2))
unsigned int xrand (void) {
    return rand () * (RAND_MAX + 1) + rand ();
}

Здравствуйте, thesynapse1, Вы писали:

T>

T>#define XRAND_MAX (RAND_MAX*(RAND_MAX + 2))
T>unsigned int xrand (void) {
T>    return rand () * (RAND_MAX + 1) + rand ();
T>}
T>

можно и так

Здравствуйте, thesynapse1, Вы писали:

T>Здравствуйте, dilmah, Вы писали:

А>>>Требуется генерировать случайные числа в диапазоне от 0 до больше чем RAND_MAX, и чтоб распределение было более менее равномерное.
А>>>ну и скорость чтоб не самая медленная. и еще чтоб кроссплатформенно.

D>>ну ты хоть пояснил бы -- целые числа тебе нужны или нецелые. Какой результирующий тип нужен? uint64_t?

T>обычного uint 32 бита хватит, хотя сойдет и double от 0 до 1

Последний вариант реализуется совсем просто. Можно также создать на его основе небольшой дополнительный набор перегрузок.

double random() { return rand() / double(RAND_MAX + 1); }
double random(double upper) { return random() * upper; }
double random(double lower, double upper) { return lower + random(upper - lower); }

Возможно, возникнет вопрос о разрешающей способности генератора. Этот вопрос легко решается незначительным усложнением первой функции.

Здравствуйте, thesynapse1, Вы писали:

T>

T>#define XRAND_MAX (RAND_MAX*(RAND_MAX + 2))
T>unsigned int xrand (void) {
T>    return rand () * (RAND_MAX + 1) + rand ();
T>}
T>

Только надо не забывать, что в этом случае различных чисел будет все равно не больше RAND_MAX, только размазанных по большем интервалу.

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, thesynapse1, Вы писали:

T>>Здравствуйте, dilmah, Вы писали:

А>>>>Требуется генерировать случайные числа в диапазоне от 0 до больше чем RAND_MAX, и чтоб распределение было более менее равномерное.
А>>>>ну и скорость чтоб не самая медленная. и еще чтоб кроссплатформенно.

D>>>ну ты хоть пояснил бы -- целые числа тебе нужны или нецелые. Какой результирующий тип нужен? uint64_t?

T>>обычного uint 32 бита хватит, хотя сойдет и double от 0 до 1

R>Последний вариант реализуется совсем просто. Можно также создать на его основе небольшой дополнительный набор перегрузок.
R>

R>double random() { return rand() / double(RAND_MAX + 1); }
R>double random(double upper) { return random() * upper; }
R>double random(double lower, double upper) { return lower + random(upper - lower); }
R>

R>Возможно, возникнет вопрос о разрешающей способности генератора. Этот вопрос легко решается незначительным усложнением первой функции.

насколько мне кажется в варианте
double random() { return rand() / double(RAND_MAX + 1); }
некоторые числа не быдут выпадать никогда тоесть у нас остаеться те же RAND_MAX комбинаций

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, thesynapse1, Вы писали:

T>>

T>>#define XRAND_MAX (RAND_MAX*(RAND_MAX + 2))
T>>unsigned int xrand (void) {
T>>    return rand () * (RAND_MAX + 1) + rand ();
T>>}
T>>

_DA>Только надо не забывать, что в этом случае различных чисел будет все равно не больше RAND_MAX, только размазанных по большем интервалу.

почему? этот вариант должен же генерить от 0 до XRAND_MAX.

Здравствуйте, thesynapse1, Вы писали:

T>Здравствуйте, _DAle_, Вы писали:

_DA>>Здравствуйте, thesynapse1, Вы писали:

T>>>

T>>>#define XRAND_MAX (RAND_MAX*(RAND_MAX + 2))
T>>>unsigned int xrand (void) {
T>>>    return rand () * (RAND_MAX + 1) + rand ();
T>>>}
T>>>

_DA>>Только надо не забывать, что в этом случае различных чисел будет все равно не больше RAND_MAX, только размазанных по большем интервалу.

T>почему? этот вариант должен же генерить от 0 до XRAND_MAX.

Потому что значение, возвращаемое rand, однозначно определяется предыдущим значением.

A>функцию можно использовать такую

A>

A>int random(int lim)
A>{
A>    g_RandSeed = g_RandSeed * 0x8088405 + 1;
A>    return __int64(g_RandSeed) * lim >> 32;
A>}
A>

а что это за магическое число 0x8088405?
и насколько распределенная последовательность у всего этого получится?

Здравствуйте, thesynapse1, Вы писали:

T>а что это за магическое число 0x8088405?
T>и насколько распределенная последовательность у всего этого получится?

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

Здравствуйте, _DAle_, Вы писали:

_DA>Потому что значение, возвращаемое rand, однозначно определяется предыдущим значением.

Вы хотите сказать нам, что rand() выдает коррелированные значения?

Здравствуйте, Abyx, Вы писали:

A>Здравствуйте, thesynapse1, Вы писали:

T>>а что это за магическое число 0x8088405?
T>>и насколько распределенная последовательность у всего этого получится?

A>Прочитайте про линейный конгруэнтный метод, хотя бы в википедии. Там есть таблица примеров чисел, это одно из них (используется в делфи).

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

Здравствуйте, Abyx, Вы писали:

T>>#define XRAND_MAX (RAND_MAX*(RAND_MAX + 2))
T>>unsigned int xrand (void) {
T>> return rand () * (RAND_MAX + 1) + rand ();
T>>}

A>можно и так

Нельзя. Диапазон хоть и стал XRAND_MAX, количество всех возможных чисел остается равным RAND_MAX. С тем же успехом мог просто умножить на константу.

Здравствуйте, Abyx, Вы писали:

A>Здравствуйте, _DAle_, Вы писали:

_DA>>Потому что значение, возвращаемое rand, однозначно определяется предыдущим значением.

A>Вы хотите сказать нам, что rand() выдает коррелированные значения?

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

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, Abyx, Вы писали:

A>>Здравствуйте, _DAle_, Вы писали:

_DA>>>Потому что значение, возвращаемое rand, однозначно определяется предыдущим значением.

A>>Вы хотите сказать нам, что rand() выдает коррелированные значения?

_DA>Я хочу сказать, что в линейном конгруэнтном методе псевдослучайное значение получается из предыдущего.

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

Здравствуйте, rg45, Вы писали:

A>>>Вы хотите сказать нам, что rand() выдает коррелированные значения?

_DA>>Я хочу сказать, что в линейном конгруэнтном методе псевдослучайное значение получается из предыдущего.

R>Ну и что, это всего навсего деталь реализации псевдослучайной последовательности чисел. Это вовсе не означает, что каждый раз после выпадения некоторого числа X следующим всегда будет выпадать одно и то же число Y. При решении большинства практических задач мы вполне можем считать эти числа случайными и равновероятными. То же самое можно сказать и последовательно выпадающих парах чисел — вероятности выпадения различных пар чисел тоже можно считать равными.

Не означает, но на практике в большинстве случаев так и будет. Поэтому такой способ будет не сильно лучше rand() * (double)NEW_RAND_MAX / RAND_MAX. А уж дальше пускай каждый сам решает, достаточно ли ему такой случайности или нет.

Здравствуйте, _DAle_, Вы писали:

_DA>Я хочу сказать, что в линейном конгруэнтном методе псевдослучайное значение получается из предыдущего.

Оно получается не из предыдущего, а из seed. Посмотрите внимательно на код rand(). Возвращается log2(RAND_MAX + 1) разрядов seed, по этому никакого однозначного соответствия между двумя последовательными результатами rand() нет.
Для 32 разрядного seed возможны 2^(32-log2(RAND_MAX + 1)+1) пар последовательных значений. Для log2(RAND_MAX + 1) = 16 это означает что два последовательных результата rand() никак не связаны.

Здравствуйте, Кодёнок, Вы писали:

Кё>Нельзя. Диапазон хоть и стал XRAND_MAX, количество всех возможных чисел остается равным RAND_MAX. С тем же успехом мог просто умножить на константу.

int32 seed;
int32 RAND_MAX = 0xFFFF;
int32 rand()
{
    seed = seed * A + B;
    return seed % (RAND_MAX + 1);
}

int32 rand2()
{
   return rand() + rand() * (RAND_MAX + 1);
}

подставляем rand в rand2, получаем

int32 rand2()
{
    seed = seed * A + B;
    return seed;
}

значит rand2 может вернуть RAND_MAX * RAND_MAX значений. ч.т.д.

Да, это зависит от реализации стандартной библиотеки.
Да, стандартные библиотеки gcc и msvc реализованы примерно одинаково и в них этот код будет работать.
Да, для то чтобы не быть привязанным к конкретным библиотекам лучше написать свою rand(), пример кода я уже приводил.

Здравствуйте, Abyx, Вы писали:

A>Здравствуйте, _DAle_, Вы писали:

_DA>>Я хочу сказать, что в линейном конгруэнтном методе псевдослучайное значение получается из предыдущего.

A>Оно получается не из предыдущего, а из seed. Посмотрите внимательно на код rand(). Возвращается log2(RAND_MAX + 1) разрядов seed, по этому никакого однозначного соответствия между двумя последовательными результатами rand() нет.
A>Для 32 разрядного seed возможны 2^(32-log2(RAND_MAX + 1)+1) пар последовательных значений. Для log2(RAND_MAX + 1) = 16 это означает что два последовательных результата rand() никак не связаны.

Согласен, почему-то рассматривал только вариант с seed и RAND_MAX одинаковой разрядности. Но вроде бы такое тоже не редкость, в g++, например, RAND_MAX равен 2^31-1.

Здравствуйте, _DAle_, Вы писали:

_DA>Согласен, почему-то рассматривал только вариант с seed и RAND_MAX одинаковой разрядности. Но вроде бы такое тоже не редкость, в g++, например, RAND_MAX равен 2^31-1.

у меня в gcc 4.5

#define    RAND_MAX    0x7FFF

Впрочем если бы у ТСа RAND_MAX был бы равен 2^31-1, он скорее всего не создал бы такую тему

	От:	Аноним
	Дата:	24.08.10 23:15
	Оценка:

	От:	dilmah
	Дата:	24.08.10 23:22
	Оценка:

От:	Pzz	https://github.com/alexpevzner
Дата:	25.08.10 00:09
Оценка:

	От:	Bell
	Дата:	25.08.10 02:43
	Оценка:	+2

	От:	Abyx
	Дата:	25.08.10 05:29
	Оценка:	19 (2)

	От:	Кодёнок
	Дата:	25.08.10 10:40
	Оценка:	-1