LINUX.ORG.RU

правильный рандом на си

 


2

2

что то не получается рандом на си. взял способ отсюда: http://www.mir-koda.ru/full_leson.php?id=8


#!/usr/bin/tcc -run

#include <stdio.h>
#include <stdlib.h>

int random5(){
   return 1 + rand() %5;
}

int one = 0;
int two = 0;
int three = 0;
int four = 0;
int five = 0;

int test(){
   int r = random5();
   if(r == 1) one++;
   if(r == 2) two++;
   if(r == 3) three++;
   if(r == 4) four++;
   if(r == 5) five++;
   return 0;
}

int i = 10000000;
int saved = 10000000;


int main(){
   while(i--){
      test();
   }
   printf("%d", one);
   printf("%d", two);
   printf("%d", three);
   printf("%d", four);
   printf("%d", five);
   printf("checksum: %d", one + two + three + four + five == saved);
   
   return 0;
}


//>>>>1998464
//>>>>1999544
//>>>>1999008
//>>>>2001252
//>>>>2001732
//>>>>checksum: 1
//>>>>
//>>>>1998464
//>>>>1999544
//>>>>1999008
//>>>>2001252
//>>>>2001732
//>>>>checksum: 1
//>>>>
//>>>>1998464
//>>>>1999544
//>>>>1999008
//>>>>2001252
//>>>>2001732
//>>>>checksum: 1
//>>>>
//>>>>1998464
//>>>>1999544
//>>>>1999008
//>>>>2001252
//>>>>2001732
//>>>>checksum: 1
//>>>>
//>>>>1998464
//>>>>1999544
//>>>>1999008
//>>>>2001252
//>>>>2001732
//>>>>checksum: 1
//>>>>
//>>>>1998464
//>>>>1999544
//>>>>1999008
//>>>>2001252
//>>>>2001732
//>>>>checksum: 1
//>>>>
//>>>>1998464
//>>>>1999544
//>>>>1999008
//>>>>2001252
//>>>>2001732
//>>>>checksum: 1
//>>>>
//>>>>1998464
//>>>>1999544
//>>>>1999008
//>>>>2001252
//>>>>2001732
//>>>>checksum: 1
//>>>>

тут несколько выхлопов, по которым видно, что распределение не равномерное, на бОльших числах получается больше. Как исправить?

И еще. Там же, по ссылке, написано, что rand() без аргументов возвращает одно и то же число. Я попробовал, возвращает разные.



Последнее исправление: linearisation (всего исправлений: 1)

Не забываем seed'ить. ;) → man 3 srand

beastie ★★★★★
()

man rand -> EXAMPLE

Deleted
()

Не используйте rand(), в <rand> c++11 есть нормальные генераторы типа mersenne twister. И не надо читать всякие левые статьи, есть хотя бы cppreference.com

anonymous
()

И еще. Там же, по ссылке, написано, что rand() без аргументов возвращает одно и то же число. Я попробовал, возвращает разные.

Одно и то же число при одном и том же вызове (по номеру, так сказать).

То есть, вызовешь его в программе три раза, будут какие-то числа (условно 1 3 13). При следующем запуске числа будут такие же.

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

Чтобы задать зерно, нужно воспользоваться предложенной комментаторами выше функцией srand(), в которую скормить что-то уникальное, например текущее время.

В общем, это работает так, в man rand должны быть примеры.

evilface ★★
()
Ответ на: комментарий от anonymous

Не используйте rand(), в <rand> c++11 есть нормальные генераторы типа mersenne twister. И не надо читать всякие левые статьи, есть хотя бы cppreference.com

Где у автора хоть слово о том, что он пишет на C++?

Явно сказано же «си».

evilface ★★
()

Во-первых rand() % X всегда опасен и не является правильным распределением - потому что MAX_U32 / X дает остаток, man матан. Тебе нужно гонять rand() до тех пор пока выданное им число по верхней границе упрется в ограничение твоего X. Т.е. while (x = rand() >= MAX_U32 / X * X). Примерно так. Ну или проще while (x = rand() >= x).

PPP328 ★★★★★
()
Ответ на: комментарий от PPP328

ну, после добавления srand(time(NULL)), вроде, дает приемлемую рандомность и так

linearisation
() автор топика
Ответ на: комментарий от PPP328

Всё так, только не MAX_U32, а RAND_MAX.

anonymous
()
Ответ на: комментарий от PPP328

Нифига не матанщик, ответь, при равномерном распределении входных данных, каково будет распределение последовательности последних цифр из входных данных?

anonymous
()
Ответ на: комментарий от anonymous

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

MAX_RAND = 100

rand() % 5:
0 : 20 раз
1 : 20 раз
2 : 20 раз
3 : 20 раз
4 : 20 раз

rand() % 4:
0 : 25 раз
1 : 25 раз
2 : 25 раз
3 : 25 раз

rand() % 6:
0 : 17 раз <<<
1 : 17 раз <<<
2 : 17 раз <<<
3 : 17 раз <<<
4 : 16 раз
5 : 16 раз

Теперь понятно?

PPP328 ★★★★★
()
Ответ на: комментарий от post-factum

Насколько понял, если упростить, и взять последовательность, из которой выбирается, поменьше. Например [0..10], то при равномерном распределении на входе и x % 10, ноль будет встречаться чаще.

anonymous
()
Ответ на: комментарий от PPP328

Ещё раз благодарю.
Пля, надо взять топор побольше, и сделать зарубку поглубже :)
Про то, что на компе, почти всегда, работа идёт над конечным множеством.

anonymous
()
Ответ на: комментарий от PPP328

Правильно ли я понимаю, что работая с rand от 0 до 32767 и всё время беря остаток rand % 100 то это будет неверные результаты? И источник этих ошибок 32768 / 100 = 327,68 вот эта дробность?

А если мы используем рандомайзинг для блоков данных кратных два-в-степени (например 4 8 16 32 бита), то такая проблема возникает или нет?

I-Love-Microsoft ★★★★★
()
Ответ на: комментарий от PPP328

И пользуясь возможностью, задам еще один вопрос специалисту :)

А хорошо ли от одного генератора псевдослучайных чисел подергать тысячу чисел и беря % 150, потом 10 тысяч по остатку % 123 и так далее, т.е. в одной программе по ходу ее работу доить один генератор разное число раз и беря разные остаточки? Мне кажется это лишь приблизительно будут равномерные распределения, что достаточно для моих простейших задач.

В аппаратных реализациях конечно используются PRBS из которых доят только нужное число битиков, причем генераторы разные для разных блоков линков и так далее. А вот в одной программе у нас ведь один генератор. И что делать если мы хотим получить математически корректные равномерные распределения? Сохранять/восстанавливать сиды для разных участков программы? Или как?

И раз позориться, так по полной: MAX_RAND это где? Его можно менять, задавать своё? Мне казалось это константа, причем под UNIX и оффтопе она разная получается.

I-Love-Microsoft ★★★★★
()
Ответ на: комментарий от I-Love-Microsoft

А хорошо ли

Нужно делать расчеты.

И что делать если мы хотим получить математически корректные равномерные распределения? Сохранять/восстанавливать сиды для разных участков программы? Или как?

Использовать для разных задач разные источники чтобы не сбивать последовательность. Но, ЕМНИП, если из последовательности rand() выкинуть скажем 50 чисел подряд все равно там глобально сохранится распределение. Нужно смотреть сорцы и делать опыты.

MAX_RAND это где?

stdlib.

Его можно менять, задавать своё?

#define

Мне казалось это константа, причем под UNIX и оффтопе она разная получается.

Она везде, она может быть разной даже под UNIX. По стандарту она >32к минимум, верхний предел не стандартизирован This value is library-dependent, but is guaranteed to be at least 32767 on any standard library implementation.

PPP328 ★★★★★
()

Если тебе нужен CSPRNG, то используй arc4random на BSD (в т.ч. macOS), getrandom на Linux (только учти, что он появился относительно недавно), /dev/urandom на других *nix, либо RtlGenRandom на Windows.

Deleted
()
Ответ на: комментарий от PPP328

Давайте я вас же процитирую?

Она везде, она может быть разной даже под UNIX. По стандарту она >32к минимум, верхний предел не стандартизирован This value is library-dependent, but is guaranteed to be at least 32767 on any standard library implementation.

Так что так, как я написал. В общем случае.

Monkeyno
()
Ответ на: комментарий от Monkeyno

Кратно степени двойки потому что компьютеры еще не научились делать числа с дробным количеством бит. Каким был ни был RAND_MAX, он будет кратен степени двойки.

PPP328 ★★★★★
()
Ответ на: комментарий от I-Love-Microsoft

И раз позориться, так по полной: MAX_RAND это где? Его можно менять, задавать своё? Мне казалось это константа, причем под UNIX и оффтопе она разная получается.

% cd /usr/include
% grep -R 'define.*RAND_MAX' 
stdlib.h:#define	RAND_MAX	2147483647


В инклудах всё хорошо грепается, так, на будущее. )

evilface ★★
()

Я использую такой рандом.

// random от 0 до bound
int random (int bound)
{
    return (int) ((bound + 1.0) * rand () / (RAND_MAX + 1.0));
}

В отличие от rand() % (num+1), такой метод даёт гораздо более лучший рандом на системах в которых младшие биты гораздо менее случайные чем старшие.

fsb4000 ★★★★★
()
Ответ на: комментарий от I-Love-Microsoft

Ну, это касалось того, где он определён.

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

evilface ★★
()
Последнее исправление: evilface (всего исправлений: 1)
Ответ на: комментарий от PPP328

Кратен степени двойки.

Это ограничение бессмысленно, так как ничего не вносит. Любое целое число кратно единице, которая является нулевой степенью двойки.

i-rinat ★★★★★
()
Ответ на: комментарий от PPP328

Так лучше?

Нет, потому что в стандарте вообще нет требований к RAND_MAX быть числом вида 2ⁿ-1.

i-rinat ★★★★★
()
Ответ на: комментарий от PPP328

Т.е., исходя из всего ниже написанного, и не учитывая лимиты, как-то так?:

int xrand(int wt)
{
    int bin_wt = pow(2, ceil(log(wt) / log(2)));

    int rnd = 0;
    while ((rnd = rand() % bin_wt) >= wt)
        ;
    return rnd;
}

anonymous
()
Ответ на: комментарий от post-factum

Вот как раз для этого X должен быть простым числом.

Это почему?

Пусть у тебя rand() возвращает числа от 0 до 3, распределение равномерное (P(0) = 0.25, P(1) = 0.25, P(2) = 0.25, P(3) = 0.25)

Тогда для rand()%3 получишь P(0) = 0.5, P(1) = 0.25, P(2) = 0.25

Вот тебе простое число. В чем я ошибаюсь?

Freyr69 ★★★
()
Ответ на: комментарий от anonymous

Вообще самым математически лучшим вариантом будет

unsigned result;
do {
    result = rand();
} while (result > N);
Но он медленный.

Вот так быстрее:

int xrand(int limit)
{
   int rand_limit = (RAND_MAX / limit) * limit;
   int result = rand();
   while (result > rand_limit)
      result = rand();
      
   return result % limit;
}

PPP328 ★★★★★
()
Ответ на: комментарий от post-factum

Так ну тогда %4, а не %3. Меньше ведь, а не меньше-равно.

Чего? Что меньше? Что меньше-равно?

С кратными X все ок:

rand()%2 — P(0) = 0.5, P(1) = 0.5

Потому что степень двойки. X должен делить MAX_RAND+1 без остатка. Так как MAX_RAND+1 обычно 2^n, то как раз X может быть только степенью двойки. Из простых чисел — только 2

Freyr69 ★★★
()
Последнее исправление: Freyr69 (всего исправлений: 2)

Intel

Компилируем мой код на всемогущем Интеле, господа:

int rdrand16_step(uint16_t *rand)

{
    
    asm volatile ("rdrand %0" : "=r" (*rand));
    
    return 1;
}

unsigned int get_random(int min, int max) {
    uint16_t seed;
    rdrand16_step(&seed);
    //NSLog(@"[%i]", seed % 3 + 1);    
    return seed % max + min;
}

menangen ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.