Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Рандом

Автор: FelikZ 12.3.2008, 22:00

Привет! Возможно ли предсказать какое значение вернет генератор случ. чисел? Если да то что для этого нужно знать. Спасибо!

Автор: Akina 12.3.2008, 23:20

Вообще-то на то он и рандом. Однако если это псевдорандом, то можно - для этого надо знать инициализирующее значение и номер текущего псевдослучайного.

Автор: FelikZ 13.3.2008, 01:40

Цитата(Akina @  12.3.2008,  23:20 ) инициализирующее значение и номер текущего псевдослучайного. Эм  Можно пожалуйста объяснить что-это для чайника :?)

Автор: marykone 13.3.2008, 10:00

random если не ошибаюсь работает по принципу  берется время к нему прибавляется число а вообще залезьте посмотрите описание ее

Автор: Akina 13.3.2008, 10:13

Цитата(marykone @  13.3.2008,  11:00 ) random если не ошибаюсь работает по принципу  Ошибаетесь

Автор: xvr 13.3.2008, 11:37

Цитата(FelikZ @ 12.3.2008,  22:00) Привет! Возможно ли предсказать какое значение вернет генератор случ. чисел? Если да то что для этого нужно знать. Спасибо! Ответ зависит от того какой именно генератор и какая его внутренняя информация доступна.

Автор: FelikZ 14.3.2008, 01:20

Цитата(xvr @  13.3.2008,  11:37 ) Ответ зависит от того какой именно генератор и какая его внутренняя информация доступна. Генератор на пхп. Числа генерятся раз в 10мин... Числа от 1 до 36, замечено что часто падают числа по принципу x y x/2 (например: 20 7 10 .... 34 1 17), вот я и подумал может все таки как то можно програмно это дело угадывать  Вроде все, что извесно

Автор: Denjs 14.3.2008, 02:26

Цитата Возможно ли предсказать какое значение вернет генератор случ. чисел? Если да то что для этого нужно знать. Вообще-то в высшей математике есть целый раздел посвященный данному вопросу. Там и алгоритмы, и параметры алгоритмов, и исследование цикличности. если вкратце вспомнить и поумничать - то генераторы псевдо случайных чисел  на самом деле цикличны - рано или поздно последовательность чисел начинает повторятся. По крайней мере для базовых алгоритмов это доказано - у которых для расчета следующего числа берется текущее. для таких "чистых алгоритмов" последовательность чисел после иницииации алгоритма всегда одна и та-же. По крайней мере если не примешивать туда "пракически" случайные составляющие - типа времени микросекунд момента выполнения. Вообще зная точные параметры генератора и алгоритм можно предсказать последовательность чисел - потому и алгоритмы названы псевдо случайными. Много посвящено исследованиям по получению равномерно-распределенных генераторов псевдо случайных чисел. кстати параметры хороших генераторов насколько я понимаю приравниваются к гос.тайне ;) такие последовательности могут использоваться в алгортмах шифрования. Есть алгоритмы построения на базе равномерно распределенного генератора дающего заданное распределение чисел - т.е. можно построить генератор который будет давать случайные числа от 0 до 9 - но 2 будет выпадать в 3 раза чаще чем 5 и т.п (потому , уважающие себя технари никогда не играют с компьютерными автоматами в азартные игры ;) ) Но в общем - это все - примерно четвертый-пятый курс технического вуза на большинстве ит-шных специальностей..  доучитесь - и вам все расскажут ;) ___________________ А если "по топику" только достав алгоритм можно что-то сказать. Попробуйте провести статистический анализ генерируемых им чисел - может и увидите закономерность..

Автор: Akina 14.3.2008, 08:31

Цитата(FelikZ @  14.3.2008,  02:20 ) Генератор на пхп. Значит, его исходный код доступен. Озаботьтесь. Вопросы отпадут, причем сразу все. Цитата(FelikZ @  14.3.2008,  02:20 ) Числа генерятся раз в 10мин Не влияет. Цитата(FelikZ @  14.3.2008,  02:20 ) замечено что часто падают числа по принципу x y x/2  Во-первых, это только кажется. Во-вторых, приведение случайных в диапазон может приводить к неравномерности.

Автор: FelikZ 14.3.2008, 12:37

Цитата(Akina @  14.3.2008,  08:31 ) Значит, его исходный код доступен. Озаботьтесь. Вопросы отпадут, причем сразу все. не доступен в этом и проблема :( Цитата(Akina @  14.3.2008,  08:31 ) Во-первых, это только кажется. Во-вторых, приведение случайных в диапазон может приводить к неравномерности ну просто совпадения такие примерно раз в 2 часа, с учетом интервала в 10мин, это раз в 12 раз примерно случается и уже не первый день  Цитата(Denjs @  14.3.2008,  02:26 ) если вкратце вспомнить и поумничать - то генераторы псевдо случайных чисел  на самом деле цикличны - рано или поздно последовательность чисел начинает повторятся. вот на это я и расчитываю  разгадать по какому принципу это происходит  Цитата(Denjs @  14.3.2008,  02:26 ) Но в общем - это все - примерно четвертый-пятый курс технического вуза на большинстве ит-шных специальностей..  доучитесь - и вам все расскажут ;) Будем ждать :(

Автор: Aikus 15.3.2008, 07:39

Цитата(FelikZ @  14.3.2008,  12:37 ) не доступен в этом и проблема :( Ктото прихватизировал пхп, вроде он был гнушный, гуглишь библиотеку и читаешь код.

Автор: mmvds 15.3.2008, 14:14

Поиск рулит http://forum.vingrad.ru/forum/topic-189808.html Правда обсуждали ГСЧП паскалевский

Автор: FelikZ 20.3.2008, 20:23

Немного покопавшись в исходном коде пхп, обнаружил, что рандом в пхп на самом деле тот же что и Cишный... Заглянув в исходники рандома(stdlib) а именно функции: srand(): Код void __cdecl srand (         unsigned int seed         ) {         _getptd()->_holdrand = (unsigned long)seed; } И самого rand(): Код int __cdecl rand (         void         ) {         _ptiddata ptd = _getptd();         return( ((ptd->_holdrand = ptd->_holdrand * 214013L             + 2531011L) >> 16) & 0x7fff ); } Можно увидеть что выщитывание псевдо случайного числа исходит от некой переменной "_holdrand" которую мы инициализируем текущим временем(по msdn в с++) с помощью функции srand() на этапе запуска программы. Из этого сделал вывод, что зная значение "_holdrand" можно спокойно "угадывать" следущие случ. числа... Теперь вопрос: Возможно ли узнать чему равен "_holdrand" зная некую последовательность чисел?

Автор: v2v 20.3.2008, 20:35

генерация holdrand посути и будет реализованным генератором в си. если тебе удастся найти алгоритм генерации , то возможно получится предсказывать  грядущие числа . НО как уже было сказано выше генератор случ. чисел на си  зависит от текущего времени (как минимум с точностью до миллисекунд )., так что ты должен учесть тот момент, что твоё предсказание будет иметь место только для конкретного момента времени (с точностью до миллисекунд) , а ты не можешь точно определить когда генерируется переменная holdrand .. p.s. при паралельном одновременном вызове сишной функции rand() ( 2 вызова в одну милисекунду) в паралельных потоках, генератор выдавал одинаковые числа! Добавлено через 3 минуты и 10 секунд Цитата(FelikZ @  14.3.2008,  12:37 ) генераторы псевдо случайных чисел  на самом деле цикличны - рано или поздно последовательность чисел начинает повторятся. вот на это я и расчитываю smile разгадать по какому принципу это происходит smile сгенерируй 2 * MAX_RAND чисел , сохрани их в файлик и посмотри как они меняются, или когда начнёт повторятся последовательность, начнёт ли.

Автор: maxim1000 20.3.2008, 20:40

для такого генератора можно попробовать такое: берём первое значение, старшие 16 бит его мы знаем значит, остаётся 65536 вариантов для младшей части (а значит 65536 всевозможных значений и для всего числа) создаём 65536 таких генераторов у себя (т.е. по сути, просто переменная и функция next) и запускаем их параллельно исследуемому на каждом шаге будут отсекаться какие-то генераторы по идее, в конце должен остаться только один... шагов будет максимум 2^32, хотя. наверное, можно доказать, что в самом худшем случае меньше

Автор: FelikZ 20.3.2008, 20:53

Цитата(v2v @  20.3.2008,  20:35 ) генерация holdrand посути и будет реализованным генератором в си. если тебе удастся найти алгоритм генерации , то возможно получится предсказывать  грядущие числа . НО как уже было сказано выше генератор случ. чисел на си  зависит от текущего времени (как минимум с точностью до миллисекунд )., так что ты должен учесть тот момент, что твоё предсказание будет иметь место только для конкретного момента времени (с точностью до миллисекунд) , а ты не можешь точно определить когда генерируется переменная holdrand .. p.s. при паралельном одновременном вызове сишной функции rand() ( 2 вызова в одну милисекунду) в паралельных потоках, генератор выдавал одинаковые числа! Ну дело в том, что код который я привел выше, на сколько я и понимаю, и есть весь алгоритм образования случ. числа   , а если это так, то этот алгоритм зависит от времени лишь при инициализации рандома функцией srand(), а это делается 1раз в начале программы, если верить докам... То есть не важно когда вызывается rand() главное вычислить исходное значение "_holdrand", а оно по сути и есть то самое время(мс), когда запускается функция srand(). Но вот опять же вопрос, как сделать как бы "обратный алгоритм" зная "исходный алгоритм" для случ. чисел, чтобы из последовательности чисел (ну штук 30 вполне можно знать) сгенерированных rand(), получить заведомое "_holdrand".  Цитата(v2v @  20.3.2008,  20:35 ) сгенерируй 2 * MAX_RAND чисел , сохрани их в файлик и посмотри как они меняются, или когда начнёт повторятся последовательность, начнёт ли. В процессе

Автор: v2v 20.3.2008, 21:02

ты забываешь про функцию _getptd(); где и инициализируется holdrand  , там наверняка учитывается текущее время!

Автор: FelikZ 20.3.2008, 21:03

Цитата(maxim1000 @  20.3.2008,  20:40 ) берём первое значение Проблема в том, что известеное значение не есть "реальное" случ. число, оно получено в результате формулы: Код (rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min) Где  range_min - минимальное генерируемое число range_max - максимальное соответственно

Автор: v2v 20.3.2008, 21:03

там уже будет сложнее , она ссылается на виндовые библиотеке, которые не доступны в исходниках (

Автор: FelikZ 20.3.2008, 21:13

Цитата(v2v @  20.3.2008,  21:02 ) ты забываешь про функцию _getptd(); где и инициализируется holdrand  , там наверняка учитывается текущее время!  неа, через отладку глянул, ф-я _getptd() просто возвращает указатель на структуру где содержится _holdrand... Реально единственное, что изменяет его это  Код ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff в функции rand() и значание текущего времени, при инициализации рандома в srand() Добавлено через 3 минуты и 45 секунд Цитата(v2v @  20.3.2008,  21:03 ) там уже будет сложнее , она ссылается на виндовые библиотеке, которые не доступны в исходниках (  хз меня пускает в отладку этих функций

Автор: xvr 20.3.2008, 23:06

Цитата(v2v @ 20.3.2008,  21:02) ты забываешь про функцию _getptd(); где и инициализируется holdrand  , там наверняка учитывается текущее время! Бред. Код *_ptiddata _getptd(void) - get per-thread data structure for the current thread * *Purpose: * *Entry: *       unsigned long tid * *Exit: *       success = pointer to _tiddata structure for the thread *       failure = fatal runtime exit * *Exceptions: * *******************************************************************************/ _ptiddata __cdecl _getptd (         void         ) {         _ptiddata ptd;         DWORD   TL_LastError;         TL_LastError = GetLastError();         if ( (ptd = FLS_GETVALUE(__tlsindex)) == NULL ) {             /*              * no per-thread data structure for this thread. try to create              * one.              */             if ( ((ptd = _calloc_crt(1, sizeof(struct _tiddata))) != NULL) &&                 FLS_SETVALUE(__tlsindex, (LPVOID)ptd) ) {                 /*                  * Initialize of per-thread data                  */                 _initptd(ptd);                 ptd->_tid = GetCurrentThreadId();                 ptd->_thandle = (uintptr_t)(-1);             }             else                 _amsg_exit(_RT_THREAD); /* write message and die */             }         SetLastError(TL_LastError);         return(ptd); } Всего лишь ссылка на глобальные данные thread'а, т.е. holdrand можно считать просто глобалом

Автор: v2v 20.3.2008, 23:07

Код                 /*                  * Initialize of per-thread data                  */                 _initptd(ptd); тут смотрел?

Автор: Alexandr87 22.3.2008, 09:50

Зачем мозги парить. Два раза вызовите srand с одним и тем же seed  и посмотрите на результаты вызова функции rand после этого.

Автор: xvr 22.3.2008, 10:33

Цитата(v2v @ 20.3.2008,  23:07) Код                 /*                  * Initialize of per-thread data                  */                 _initptd(ptd); тут смотрел? Смотрел конечно Код /*** *void _initptd(_ptiddata ptd) - initialize a per-thread data structure * *Purpose: *       This routine handles all of the per-thread initialization *       which is common to _beginthread, _beginthreadex, _mtinit *       and _getptd. * *Entry: *       pointer to a per-thread data block * *Exit: *       the common fields in that block are initialized * *Exceptions: * *******************************************************************************/ void __cdecl _initptd (         _ptiddata ptd         ) {         ptd->_pxcptacttab = (void *)_XcptActTab;         ptd->_holdrand = 1L; #ifdef _M_MRX000         /*          * MIPS per-thread data          */         ptd->_MipsPtdDelta =         ptd->_MipsPtdEpsilon = -1L ; #endif  /* _M_MRX000 */ } Еще куда посмотреть? (Для справки: 1L - это константа   )

Автор: FelikZ 23.3.2008, 10:04

Цитата(Alexandr87 @  22.3.2008,  09:50 ) Зачем мозги парить. Два раза вызовите srand с одним и тем же seed  и посмотрите на результаты вызова функции rand после этого.  Результаты будут одинаковые. И как это поможет в поиске seed'а для множества чисел :?)

Автор: Alexandr87 23.3.2008, 12:45

FelikZ, этот пост был к людям спорящим о зависимости выдаваемых чисел от вермени. А так как он независим, тут прокатывает вариант предолженный maxim1000

Автор: v2v 23.3.2008, 18:06

ок. таки да к времени никакой привязки. но всё же чего то не хватает для предсказаний. попытался написать вот такой кусочек кода: Код     unsigned long holder = 1L;     unsigned int seed = 1;     int r1;     holder=(unsigned long)seed;     srand(seed);     for (int ii=0; ii<5; ii++)     {      printf("\nPredict  : %d", ( holder=holder*214013L+2531011L ) >> 16 & 0x7fff);      r1=rand();      printf("\nRandom: %d",r1);     } предсказания не верны. что не правильно?

Автор: maxdiver 23.3.2008, 22:30

У меня вывод совпадает

Автор: v2v 23.3.2008, 22:38

Правда? Прикольно!!  Какая ОСь? MVS используешь? похоже, что рассчёт ещё и компиляторо зависимый.

Автор: maxdiver 24.3.2008, 00:35

VS2008 сомневаюсь, что от него что-то зависит. если ты взял константы из исходников RTL _своего_ компилятора, то и у тебя должно работать.

Автор: v2v 24.3.2008, 21:25

я писал пример в борланд с++ 5.02 , там он не работал : числа предсказывались не правильно. поставил вс2008 - предсказания сбываются).

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)