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)
Ответ на: комментарий от PPP328

Что-то как-то странно твой xrand() работает.

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

#define _RAND_MAX 7

unsigned int myrand(void) {
    return rand() % (_RAND_MAX + 1);
}

unsigned int xrand(unsigned int limit)
{
   unsigned int rand_limit = (_RAND_MAX / limit) * limit;
   unsigned int result = myrand();
   while (result > rand_limit)
      result = myrand();

   return result % limit;
}

int main(void) {
    unsigned count[8] = {};

    for (int k = 0; k < 100 * 1000 * 1000; k++) {
        count[xrand(3)] += 1;
        // count[myrand()] += 1;
    }

    for (int k = 0; k < 8; k++)
        printf("%u\n", count[k]);

    return 0;
}

Для чистоты эксперимента возьмём не rand() с её большим RAND_MAX, который срезает все неравномерности, а myrand(), которая выдаёт от 0 до 7. Можно посмотреть распределение, которое она выдаёт:

12493877
12496457
12499627
12500440
12502970
12503696
12500913
12502020

Ровненько. А вот если посмотреть, что выдаст xrand(3), получится:

42857004
28570166
28572830
0
0
0
0
0

Неслабый такой перекос.

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

i-rinat ★★★★★
()
Ответ на: Intel от menangen

Объясни это

asm volatile ("rdrand %0" : "=r" (*rand));

Я так понимаю, что в этом коде используется аппаратная реализация из Sandy/IvyBridge?

Twissel ★★★★★
()

Последние времена. Главный лоровский кукаретик программирования взялся за сишечку. Вносите царя, я хочу видеть эту битву!

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

1 + rand() %5;
%

В прежние годы ман предупреждал против такого беспредела. Правильно так:

int get_random(int g_rand_max)
{
    return (int) ((g_rand_max + 1.0) * rand() / (RAND_MAX + 1.0));
}

saahriktu ★★★★★
()
Последнее исправление: saahriktu (всего исправлений: 1)
Ответ на: комментарий от Freyr69
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sysexits.h>
#include <time.h>

#define X_PRIME         1021
#define X_NONPRIME      (1 << 16)
#define BASE            10
#define ITERS           100000000

static volatile uint64_t r = 0;

static uint64_t rnd()
{
        r ^= (r << 21);
        r ^= (r >> 35);
        r ^= (r << 4);

        return r;
}

int main(int _argc, char** _argv)
{
        (void)_argc;
        (void)_argv;
        size_t p_basket[BASE] = {0,};
        size_t q_basket[BASE] = {0,};

        srand(time(NULL));
        r = rand();

        for (size_t i = 0; i < ITERS; i++)
        {
//              int p = rnd() % X_PRIME;
//              int q = rnd() % X_NONPRIME;
                int p = rand() % X_PRIME;
                int q = rand() % X_NONPRIME;

                p_basket[p % BASE]++;
                q_basket[q % BASE]++;
        }

        printf("%s", "# p q\n");
        for (size_t i = 0; i < BASE; i++)
        {
                printf("%zu %zu %zu\n", i, p_basket[i], q_basket[i]);
        }

        exit(EX_OK);
}
$ icc test.c -O3 -o test

$ ./test | column -t    
#  p         q
0  10089663  9999205
1  9990400   10005347
2  9989107   9997447
3  9993000   10004499
4  9986341   10001433
5  9992309   9997622
6  9989316   9995989
7  9989636   9998124
8  9990691   9997104
9  9989537   10003230

Ладно, согласен, с нулём херня. Я правильно воспроизвёл?

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

Из репозитория убунту установил gsl-bin (подтянуло за собой еще одну библиотеку). (не обязательно ставить ведь с того сайта, правильно? версия 2.1 в репах) fatal error: gsl/gsl_rng.h: Нет такого файла или каталога

mul4 ★★★★★
()
Последнее исправление: mul4 (всего исправлений: 1)
Ответ на: комментарий от i-rinat

У него ошибка

- while (result > rand_limit)
+ while (result >= rand_limit)

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

Ну да, так лучше будет. :)
Только, как выше отметил, бага есть.

anonymous
()

Правильный кроссплатформенный random на Си. Уже было?

#include <stdio.h>

int random_data(void* data, size_t size);

int main(void)
{
    int i;
    unsigned int x;
    for(i = 0; i<5; ++i)
    {
        random_data(&x, sizeof(x));
        printf("%u\n", x);
    }
    return 0;
}

#ifdef _WIN32

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <wincrypt.h>

int random_data(void* data, size_t size)
{
    HCRYPTPROV hProv;
    BOOL rv;
    rv = CryptAcquireContextW(&hProv, NULL, NULL, PROV_RSA_FULL, CRYPT_SILENT | CRYPT_VERIFYCONTEXT);
    if(!rv) return 0;
    rv = CryptGenRandom(hProv, (DWORD)size, data);
    CryptReleaseContext(hProv, 0);
    return rv ? 1 : 0;
}

#else

int random_data(void* data, size_t size)
{
    FILE* f;
    if(size < 1 || !data)
    {
        return 0;
    }
    f = fopen("/dev/urandom", "r");
    if(!f)
    {
        return 0;
    }
    size = fread(data, size, 1, f);
    fclose(f);
    return size ? 1 : 0;
}

#endif // _WIN32

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

Да, быстрый и хороший рандом. У amd тоже есть какая-то либа для таких вещей. В haswell и выше, вроде, есть крипто-стойкий рандом. «Типа» :)

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

Ну ты чего, дружище? Почему я, арчешкольник, должен тебе подсказывать очевидные убунту-хинты?

Хедеры вместе с либой, как это заведено в DEB-based, идут в пакетах с -dev суффиксом, то бишь libgsl-dev или libgsl0-dev смотри в своих репах.

А то, что ты установил — это другое.

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

Правильный кроссплатформенный random на Си. Уже было?

Который использует urandom вместо random и открывает/закрывает файл на каждый вызов. Очень правильный, да.

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

Не виноват что юниксы и, в частности, ляликс, такие кривые, что там все через файлы.

А так, один хрен, надо помногу сразу брать, даже с обычными PRNG.

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

И что что быстрее? Вам на атомные электростанции чтоли нужны случайные числа? В GPS-навигаторы? Или чо?

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

Спасибо большое, EXL, utf8nowhere, что бы я без вас делал, прям не знаю.

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

кроссплатформенный

#ifdef

В приличном обществе за такое убивают.

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

Я правильно воспроизвёл?

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

Freyr69 ★★★
()
Последнее исправление: Freyr69 (всего исправлений: 2)
Ответ на: комментарий от lovesan
    if(size < 1 || !data)
    {
        return 0;
    }

Зачем?

    size = fread(data, size, 1, f);
    return size ? 1 : 0;

А если прочиталось меньше, чем size, но не ноль?

Ещё по POSIX fread упасть с EINTR может. Говно написал, короче.

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

зачем там две операции деления с остатком

Какие именно?

на практике большой разницы не будет

Ты же видишь, что разница есть.

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

Вот тебе нормальный кроссплатформенный (на всех линуксах будет работать: хоть под ARM, хоть под MIPS) инициализатор рандома.

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

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

Должно делить RAND_MAX+1 без остатка, а не быть кратным чему угодно.

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

А причём тут простота, уважаемый? Здесь важно, чтобы X был кратен (MAX_RAND + 1).

Ерунду написали. Он должен делить без остатка, а не быть кратным.

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

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

Да что вы все тут сговорились что ли?!

Pythagoras ★★
()
4 мая 2017 г.
Ответ на: комментарий от lovesan

в частности, ляликс, такие кривые, что там все через файлы.

getrandom(2).

Deleted
()

Я вот так рандом инициализирую:

long throw_random_seed(){
	long r_ini;
	int fail = 0;
	int fd = open("/dev/random", O_RDONLY);
	do{
		if(-1 == fd){
			perror(_("Can't open /dev/random"));
			fail = 1; break;
		}
		if(sizeof(long) != read(fd, &r_ini, sizeof(long))){
			perror(_("Can't read /dev/random"));
			fail = 1;
		}
		close(fd);
	}while(0);
	if(fail){
		double tt = dtime() * 1e6;
		double mx = (double)LONG_MAX;
		r_ini = (long)(tt - mx * floor(tt/mx));
	}
	return (r_ini);
}

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