Форум программистов, компьютерный форум CyberForum.ru

Rand() как именно генерируются эти числа - C++

Восстановить пароль Регистрация
 
Scrapebs
0 / 0 / 0
Регистрация: 12.02.2014
Сообщений: 39
18.04.2014, 12:32     Rand() как именно генерируются эти числа #1
Функция rand(). Мне для ответа по ОПИ мало сказать что она возвращает псевдослучайные числа от 0 до RAND_MAX.
Надо рассказать как именно генерируются эти числа. Наверное, надо разбираться на основе текста функции.
В Linuxe, Windos по библиотекам stdlib.h лазил, целостного описания кажется не нашел,
зато нашел один файлик, кажется из папки с Builder-ом:
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* rand function */
#include <stdlib.h>
#include "xtls.h"
_STD_BEGIN
 
#define TSIZ    32  /* must be power of two */
#define TMSK    (TSIZ - 1)
#define XRND(x) (x) * 1664525L + 1013904223L
 
_TLS_DATA_DEF(_IMPLICIT_EXTERN, char, _Randinit, 0);
_TLS_DATA_DEF(_IMPLICIT_EXTERN, unsigned long, _Randseed, 1);
_TLS_DATA_DEF(static, unsigned long, idx, 0);
_TLS_ARR_DEF(static, unsigned long, rv, TSIZ);
 
int (rand)(void)
    {   /* compute pseudo-random value */
    char *pinit = _TLS_DATA_PTR(_Randinit);
    unsigned long *pseed = _TLS_DATA_PTR(_Randseed);
    unsigned long *pidx = _TLS_DATA_PTR(idx);
    unsigned long *prv = _TLS_ARR(rv);
    int j;
 
    if (*pinit == 0)
        {   /* warm up, then initialize shuffle table */
        for (j = 0; j < 8; ++j)
            *pseed = XRND(*pseed);
        for (j = 0; j < TSIZ; ++j)
            prv[j] = (*pseed = XRND(*pseed));
        *pidx = prv[TSIZ - 1];
        *pinit = 1;
        }
    *pseed = XRND(*pseed);
    j = *pidx & TMSK;
    *pidx = prv[j];
    prv[j] = *pseed;
 
 #if _ILONG
    return (*pidx & RAND_MAX);
 
 #else /* _ILONG */
    return ((*pidx >> 16) & RAND_MAX);
 #endif /* _ILONG */
 
    }
_STD_END
 
/*
 * Copyright (c) 1992-2006 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V5.01:1422 */
Если это то что мне нужно, то как объяснить написанное словами?
Начать хотя бы с того, что такое "(x) * 1664525L + 1013904223L"?
Заранее спасибо!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
18.04.2014, 14:52     Rand() как именно генерируются эти числа #2
Цитата Сообщение от Scrapebs Посмотреть сообщение
как именно генерируются эти числа
С использованием невысокого качества PRNG: Linear congruential generator

В Borland, MSVC, GCC применена одна и та же схема.

Если нужен качественный PRNG (не для криптографии!), используйте Mersenne twister
Scrapebs
0 / 0 / 0
Регистрация: 12.02.2014
Сообщений: 39
20.04.2014, 18:26  [ТС]     Rand() как именно генерируются эти числа #3
Добавлено через 3 минуты
gazlan,
А каким образом осуществляется вычисления по этой формуле:
xn+1=(axn+c) mod m
Я правильно понял, что xn+1 равно остатку от деления скобки на число m?

В таком случае при подстановки переменных для Visual, взятых из таблицы в статье:
a=214013, c=2531011, m=232=4294967296.
Далее, возможно я не прав, если
srand(1);
x=rand();
x равно 41, значит его можно подставить вместо xn,
в таком случае скобка равна 11305544, значит при делении её на m=232, остаток от деления
будет равен самой этой скобке, а надо по идее получить 45, т.к.
srand(2);
x=rand();
x равен 45.

Подскажите пожалуйста, что я понял не так.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
20.04.2014, 22:48     Rand() как именно генерируются эти числа #4
Цитата Сообщение от Scrapebs Посмотреть сообщение
m=2^32 = 4294967296
Зависит от компилятора, но, скорее всего, это будет 16-битное значение.

Вот real code из MSVC 9.0 crt: rand.c

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/***
*rand.c - random number generator
*
*       Copyright (c) Microsoft Corporation. All rights reserved.
*
*Purpose:
*       defines rand(), srand() - random number generator
*
*******************************************************************************/
 
#include <cruntime.h>
#include <mtdll.h>
#include <stddef.h>
#include <stdlib.h>
 
 
/***
*void srand(seed) - seed the random number generator
*
*Purpose:
*       Seeds the random number generator with the int given.  Adapted from the
*       BASIC random number generator.
*
*Entry:
*       unsigned seed - seed to seed rand # generator with
*
*Exit:
*       None.
*
*Exceptions:
*
*******************************************************************************/
 
void __cdecl srand(unsigned int seed)
{
   _getptd()->_holdrand = (unsigned long)seed;
}
 
/***
*int rand() - returns a random number
*
*Purpose:
*       returns a pseudo-random number 0 through 32767.
*
*Entry:
*       None.
*
*Exit:
*       Returns a pseudo-random number 0 through 32767.
*
*Exceptions:
*
*******************************************************************************/
 
int __cdecl rand()
{
   _ptiddata ptd = _getptd();
 
   return( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}
В MFC код немного другой, там в srand() подмешивался ID текущего процесса.

Исходного кода нет, смотрел в дизассемблере.
Scrapebs
0 / 0 / 0
Регистрация: 12.02.2014
Сообщений: 39
21.04.2014, 11:06  [ТС]     Rand() как именно генерируются эти числа #5
gazlan,
Похоже, что в этом случае все проще чем я думал)
Только вот хотелось бы уточнить, что означает "& 0x7fff", а именно &.
Ведь в формуле стоит mod (остаток от деления - % ?), а тут амперсанд...
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
21.04.2014, 11:28     Rand() как именно генерируются эти числа #6
это не амперсанд, блин, а битовая операция "И"!
Сам догадаешься как в двоичном коде взять остаток от деления на степень двойки или тебе и это разжевать надо?
Может ты ещё не знаешь как битовыми сдвигами производить целочисленное деление на степень двойки??? OMG!
IrineK
Заблокирован
21.04.2014, 11:56     Rand() как именно генерируются эти числа #7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Может ты ещё не знаешь
вы это знаете?

Так помогите тому, кто хочет знать - чего стебаться.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
21.04.2014, 12:37     Rand() как именно генерируются эти числа #8
IrineK, не знаю и знать не хочу, а если бы и знал, не признался бы в этом. Одно могу сказать: такие вещи нужно читать в книгах. Причём в книгах, написанных самыми авторитетными в этом деле авторами. Потому, что как бы хорошо не знал Кузька Пупкин применение битовых операций передать эти знания так же доходчиво, как в книгах классиков он не сможет.
Добавь сюда неуклюжий формат "обучения" в виде кратких постов на форуме.
Добавь сюда то, что Кузька Пупкин с форума не может считаться хорошим учителем, даже если сам и вполне способен нормально программировать.
Добавь сюда и тго, что неизвестно, а действительно ли Кузька Пупкин сам всё верно знает о битовых операциях.
Добавь сюда, что на форуме тусуется с десяток таких Пупкиных, которые при попытке объяснить что-то дадут десяток десятков кусочков обрывочной, вырванной из контекста информации, которая вряд ли надолго задержится в памяти Scrapebs.
Ну и зачем тогда что-то объяснять?
Нет, конечно, есть вопросы, которые вполне подходят под формат форума, но не такие же основы основ, без которых почти невозможно программирование?!
IrineK
Заблокирован
21.04.2014, 13:10     Rand() как именно генерируются эти числа #9
Kuzia domovenok,
Тогда в ваших горячих посылах незнающим говорите им:
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Одно могу сказать: такие вещи нужно читать в книгах.
Очень конструктивно.

Не по теме:

Вроде и послал, но в библиотеку же

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2014, 13:13     Rand() как именно генерируются эти числа
Еще ссылки по теме:

Rand() создает одинаковые числа C++
Rand: Во всех случаях генерируются одинаковые значения C++
C++ Почему в данной программе числа не генерируются, а остаются прежними?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Scrapebs
0 / 0 / 0
Регистрация: 12.02.2014
Сообщений: 39
21.04.2014, 13:13  [ТС]     Rand() как именно генерируются эти числа #10
Всем спасибо, разобрался. Действительно, книжки читать надо. Но в некоторых случаях, я думаю, можно прибегнуть и к помощи форумчан, не самых глупых людей.
Не обязательно же ожидать от кого-то четкого ответа на некорректно сформулированный вопрос, когда достаточно узнать названия разделов, с которыми необходимо ознакомиться для решения своей задачи
Yandex
Объявления
21.04.2014, 13:13     Rand() как именно генерируются эти числа
Ответ Создать тему
Опции темы

Текущее время: 05:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru