Random и его аналоги.

← →
Thor © (2004-05-05 23:55) [0]

переносим обсуждение сюда.
кто какие алгоритмы генерации случайных чмсел знает, кроме всем родного random"а?
какие из нах работают быстро, какие дают более подходящий результат?

← →
Gero © (2004-05-05 23:57) [1]

Вот я - сам себе генератор.
Демонстрирую:
22.1
676.657
689.038
45.059698845
678.3

Все числа абсолютно случайны, никакой последовательности в них нет.

← →
Thor © (2004-05-06 00:01) [2]

> Gero © (05.05.04 23:57) [1]

приколист...

естественно программно!

← →
Undert © (2004-05-06 00:02) [3]

Thor ©

В компьютерныйх системах абсолютно-случайных чисел не бывает, любо они повторяются, либо есть какая-нить последовательность.

← →
Undert © (2004-05-06 00:02) [4]

Thor ©

В компьютерных системах абсолютно-случайных чисел не бывает, любо они повторяются, либо есть какая-нить последовательность.

← →
Thor © (2004-05-06 00:03) [5]

> Undert © (06.05.04 00:02) [3]

это я и сам знаю.
я предлагаю обсудить различные методы генерации и их эффективность.

← →
Undert © (2004-05-06 00:11) [6]

> Thor ©

Самый нормальный способ -
byte_bios_таймер*встроенный_dword_windows_таймер - и из этого чудовщиного числа брать нужный рандом, типа байтный таймер через себя перевернётся паруочку десятков миллионов раз, хрен знает что получится, но явно уже не обычный рандом будет :)

← →
tasman © (2004-05-06 00:12) [7]

Легче всего у Кнута про это почитать, если интересно конечно. У него во втором томе: Получисленные алгоритмы целая глава этому посвящена с очень хорошим и подробным анализом и разбором различных методов генерации случайных чисел. А так же что вообще есть хорошие и что есть плохие случайные числа :)

← →
Undert © (2004-05-06 00:15) [8]

Блин, вот взяли бы и в проц такой генератор на какой-нить атомной основе сделали бы и геммороя небыло бы глюкоделателям :))

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

← →
Mihey © (2004-05-06 00:15) [9]

Это надо сесть и попробовать состряпать что-нибудь.

← →
Thor © (2004-05-06 00:18) [10]

> Undert © (06.05.04 00:15) [8]

не только.
AFAIK еще и в криптовании информации.
там это особенно острая проблема.

← →
kaif © (2004-05-06 00:21) [11]

М-последовательности. Имеют хороший "равномерный спектр". Используются системами GPS (USA), Glonass (RUSSIA), Avax (USA).
Знаю, как сгенерировать ее на основе регистре сдвига (аппаратно). Программно, если надо, моделирую то же самое. Смысл в том, что с каких-то разрядов берется сигнал и складывается по модулю 2 (фенкция XOR). Делается сдвиг на один разряд, а результат XOR записывается в освободившийся младший разряд. То, какие из разрядов участвуют в XOR - целая наука. Кажется, это называется неприводимые многочлены. Точно не помню. Большинство теорем о таких многочленах держится в секрете.

← →
Ske4er © (2004-05-06 03:10) [12]

Я помню как DriveCrypt генерит случайные числа - при создании контейнера нужно раз 20-ть нажать нажать кнопку Pick, при этом дергая мышку в различных направлениях. Т.е. двигаете мышкой (а это аналоговый мир, кто знает куда ее дернет пользователь?) и пробелом жать на Кнопку, причем с различными задержками... ВОт так... Может и долго, зато уж точно случайно :)

← →
тихий вовочка © (2004-05-06 06:46) [13]

Зная нужную тебе плотность распределения вероятности или функцию распределения вероятности и пользуя стандартный random можно получить отличную выборку.

//какие из нах работают быстро, какие дают более подходящий результат?

А random для тебя медленный? Очень странно! А что значит более подходящий результат? Нормальный закон распределения для тебя наименее подходящий?

← →
Паниковский © (2004-05-06 07:04) [14]

http://algolist.manual.ru/

← →
cyborg © (2004-05-06 07:50) [15]

Как насчёт такого?

получить такты процессора - Val (64 битовое число).
result:=Val mod RndVal;

Правда в этом варианте нужно получать небольшие числа, не более нескольких миллионов, но лучше тысяч, чтобы какой-то разброс иметь, значения в большей степени будет зависеть от скорости процессора и от частоты вызова данной функции в определённый промежуток времени.

← →
тихий вовочка © (2004-05-06 08:43) [16]

<цитата>(Ну не любят на этом форуме Оперу!)В компьютерных системах абсолютно-случайных чисел не бывает, любо они повторяются, либо есть какая-нить последовательность.</цитата>

А "абсолютно-случайные" числа никогда не повторяются? Очень странно.
И что вы подразумеваете под компьютерными системами? Персоналки - потомки 8086?

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

← →
Reindeer Moss Eater © (2004-05-06 09:43) [17]

Прикладное решение задачи.
Устанавливаем какой-нибудь криптопровайдер (или используем поставляемые с ОС)
Инсталлируем какой-либо ДСЧ поддерживаемый провайдером (аппаратный, биологический, прочий)
Вызываем CPGenRandom и получаем случайное число.

← →
Gero © (2004-05-06 10:03) [18]

Кстати, случайные числа можно генерить комбинацией времени, даты, тиков, размером оперативки, объемом свободного менста на диске, частотой проца и его загруженностью.
Список далеко не полон.

← →
Vlad Oshin © (2004-05-06 10:05) [19]

> Gero © (06.05.04 10:03) [18]

и синусы какие-нибудь от этого брать, чтоб как стандарт Random (0;1) было.

← →
Gero © (2004-05-06 10:07) [20]

> Vlad Oshin © (06.05.04 10:05)

Ну это понятно.
Синусы, косинусы, можно для начала кубический корень найти.

← →
Vlad Oshin © (2004-05-06 10:09) [21]

> можно для начала кубический корень найти.

можно
законом не запрещается :)

← →
Паниковский © (2004-05-06 12:03) [22]

а можно еще человека за соседним компутером спросить "Назови число!".

"Здесь вам не Англия копать надо глубже!"

Генератор Парка-Миллера

Статья предоставлена
(c) Nikitine Valeri F. 2000,
web: algorithm.narod.ru

Самая простая последовательность, которую можно предложить для реализации генератора равномерного распределения:

I(j+1)=a*I(j)(mod m)

при соответствующем выборе констант. Константы были предложены Park и Miller:

a=75=16807, m=231-1=2147483647

и протестированы в исследованиях Lewis, Goodman, Miller (1969).

Прямое приложение этого метода возможно на языках ассемблера, но языки высокого уровня могут при этом зафиксировать переполнение. Для обхода этого Scharge предложил метод частичной факторизации модуля. Модуль разлагается в выражение:

m=a*q+r

Если r<q и 0<z<m-1, то при этом величины a*(z mod q) и r*[z/q] всегда лежат в интервале 0,...,m-1. Для умножения (a*z)(mod m) при этом используется алгоритм:

t = a(z mod q)-r[z/q]
если t<0, то t += m.
(a*z)(mod m)=t.

В случае констант Парка-Миллера можно использовать q=12773 и r=2836.

/* Minimal portable random generator by Park and Miller */

/* Lewis-Goodman-Miller constants */
#define IA 16807
#define IM 2147483647
#define AM (1./IM)
/* Scharge constants */
#define IQ 12773
#define IR 2836
/* Special mask to be explained below */
#define MASK 123456789

static long dummy;

/* initial seed, for all the generators here */
void Seed(long dum) {dummy=dum;}

/* returns random uniformly distributed between 0 and 1 */
float unirand0(void) {
long k;
float ans;
dummy^=MASK; /* avoid dummy==0 */
k=dummy/IQ;
if((dummy=IA*(dummy-k*IQ)-IR*k)<0) dummy+=IM;
ans=AM*dummy;
dummy^=MASK; /* restore unmasked dummy */
return(ans);
}

Использование маски связано с тем, что специфика алгоритма не позволяет устанавливать счетчик в нуль. Но, как показывает опыт, большинство пользователей счетчиков делают именно так. Маска гарантирует, что установленный счетчик не будет нулем. Если вы очень уверены в том, что человек не допустит подобной ошибки после вашего предупреждения, то можете убрать из программы все инструкции, связанные с маской.

Более продвинутая версия генератора Парка-Миллера.

В дополнение к предыдущему алгоритму, производит перетасовку по методу Bays и Durham, что позволяет уничтожить нежелательные корреляции между сериями сгенерированных случайных чисел.

/* Minimal random generator with Bays-Durham shuffle */

/* previous functions, variables and constants are described above.
Only additional follow */
#define NTAB 32
#define NWUP 8
#define NDIV (1+(IM-1)/NTAB)
#define EPS 1.2e-7
#define RNMX (1.0-EPS)

float unirand1(void) {
int j;
long k;
static long iy=0,iv[NTAB];
float temp;
/* initialize */
if(dummy<=0 || !iy) {
/* avoid negative or zero seed */
if(dummy<0) dummy=-dummy;
else if(dummy==0) dummy=1;
/* after NWUP warmups, initialize shuffle table */
for(j=NTAB+NWUP-1;j>=0;j--) {
k=dummy/IQ;
if((dummy=IA*(dummy-k*IQ)-IR*k)<0) dummy+=IM;
if(j<NTAB) iv[j]=dummy;
}
/* first specimen from the table */
iy=iv[0];
}
/* regular work: generate new number */
k=dummy/IQ;
if((dummy=IA*(dummy-k*IQ)-IR*k)<0) dummy+=IM;
/* shuffle output */
iy=iv[j=iy/NDIV];iv[j]=dummy;
/* return */
if((temp=AM*iy)>RNMX) return(RNMX);
else return(temp);
}

Заметим, что маска здесь не применяется, поскольку метод инициализации алгоритма отсекает ошибочные значения текущего счетчика.

Алгоритм Парка-Миллера с перетасовкой проходит все известные тесты, включая и те, где без перетасовки этот алгоритм дает сбой. Хорошее поведение наблюдается до значений числа вызовов счетчика порядка 108, где он начинает повторяться.

http://algolist.manual.ru/maths/generator/park_mil.php

← →
Vlad Oshin © (2004-05-06 12:26) [23]

> Вот я - сам себе генератор.
> Демонстрирую:
> 22.1
> 676.657
> 689.038
> 45.059698845

:)

- мне нужен генератор случайных чисел...
- 14.

← →
SergP © (2004-05-06 13:17) [24]

Самый простейший. Правда не очень хороший

генерит псевдослучайные числа в диапазоне от 0 до 1
следующий число вычисляется из предыдущего.

I(n+1)= дробная часть (11*I(n)+pi)

← →
Vlad Oshin © (2004-05-06 13:18) [25]

> SergP © (06.05.04 13:17) [24]

это что-то из теории простых чисел? Там, кажется, есть более полный(сложный) вариант?

← →
Sergey_Masloff (2004-05-06 14:03) [26]

Паниковский © (06.05.04 12:03) [22]

Самая простая последовательность, которую можно предложить для реализации генератора равномерного распределения:

I(j+1)=a*I(j)(mod m)

при соответствующем выборе констант. Константы были предложены Park и Miller:
a=75=16807, m=231-1=2147483647

А константы предложенные Борландом
a=134775813 c=1 m=2^32
И для их использования достаточно написать
Random (ну и не зыбыть Randomize)

← →
Паниковский © (2004-05-06 14:05) [27]

Sergey_Masloff
я вообще то про сабж высказывался

← →
Sergey_Masloff (2004-05-06 14:23) [28]

Паниковский © (06.05.04 14:05) [27]
>я вообще то про сабж высказывался
А, понятно... Просто это так редко теперь встречается что я и не заметил ;-) Что нужны именно аналоги...

> тихий вовочка © (06.05.04 06:46) [13]

меня все устраивает.
просто завел новую тему, чтобы в "Публичном заявлении" не флеймить. это все продолжение разговора оттуда про случайные числа. а разные алгоритмы дабы посмотреть, какой из них более подходит в том или ином случае, например, в игре, где тот же random может вызываться черт знает сколько раз подряд.

Undert ©
Блин, вот взяли бы и в проц такой генератор на какой-нить атомной основе сделали бы и геммороя небыло бы глюкоделателям :))

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

Давно он там живет.
http://www.intel.com/design/software/drivers/platform/security.htm

Вообще-то создать хороший генератор случайных чисел достаточно сложно. Нужно знать, какие требования к нему предъявляются. Например, физиков, при розыгрыше Монте-Карло интересует в основном спектр распределения. Поэтому они берут за основу генераторы с "равномерным распределением" и затем применяют простые математические методы для получения распределения нужной формы.
Многие наивно думают, что генератор случайных чисел - простая вещь и достаточно написать

> Вот я - сам себе генератор.
> Демонстрирую:
> 22.1
> 676.657
> 689.038
> 45.059698845

Эти числа случайны только потому что их мало.
Я тоже могу написать целую кучу случайных чисел:

13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13

Или например:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

Это тоже ряд случайных чисел.
Если кто-то думает иначе, пусть покажет, что вероятность такой случайной последовательности чем-то отличается от предыдущей:

19,14,20,1,13,9,7,15,3,4,18,6,2,8,12,11,10,16,17,5
----------------------------
Другой пример.
Возьмем две случайные величины с равномерным спектром, например A и B.
Вопрос такой: произведение A*B тоже случайное число?
Вроде бы да. Однако спектр величины C = A*B не будет равномерным.
Он будет иметь максимум в середине и спады по краям.
Если же взять бесконечное число случайных величин с равномерным спектром каждое _M = A*B*C*D*E....
То распределение _M станет гаусовским...
Если я правильно помню, это называется "предельная теорема".
Или что-то в этом духе.
--------------------
Криптографы часто до отчаяния доходят, придумывая алгоритмы генерации случайных чисел. Очень сложно получить псевдослучайность, близкую к "истинной" случайности.

А как сделать генератор чисел с неравномерным распределением???

>kaif © (06.05.04 18:20)
>Например, физиков, при розыгрыше Монте-Карло интересует в основном спектр
>распределения. Поэтому они берут за основу генераторы с "равномерным
>распределением" и затем применяют простые математические методы для
>получения распределения нужной формы.

Не подскажешь где посмотреть инфу по теме? Именно "простые математические методы". Все что нашел сводилось к алгоритму
1) сгенерить число стандартым генераторм
2) посчитать вероятность по нужной формуле
3) если вероятность устраивает, берем число, если нет GOTO 1
Хотелось бы более быстрый алгоритм.

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

2 Ajax © (06.05.04 20:44) [33]
Я, к сожалению, не помню. Но можно порассуждать. Я что-то такое писал для одного магазина, которому нужно было бутафорить продажи в соответствии с графиком спроса для налоговой.
Итак, допустим, у нас имеется некоторое распределение. Предположим, это график спроса. Дешевые товары в этом графике слева (по оси абсцисс - цена), дорогие - справа. График убывающий. По оси ординат - плотность вероятности продаж.
Нам нужно разбить ось абсцисс на интервалы, пропорциональные по ширине плотности вероятности и кидать на них точки простым рандомом. Если отрезок маленький, то и вероятность того, что на него что-то попадет - маленькая. Как разбить ось абсцисс на такие интервалы? Я помню, что в конце-концов решение этой задачи сводилось к получению интергала функции распределения. Но не помню как именно. Спроси у физиков. Copyr25 будет помнить. У физиков хорошая математическая подготовка. Но можешь и сам допереть (как я сделал тогда для магазина), ища попросту способ реализовать это дело по тому принципу, что я описал (ширина отрезка). То есть нужен массив вроде:
A[1] = 1000
A[2] = 1000
A[3] = 1000
A[4] = 1000
A[5] = 500
A[6] = 500
A[7] = 100

Затем можно генерить нужный спектр, просто вызывая
A[random(8)]
Так как вероятность того, что random вернет 1,2,3,4 в два раза выше, чем 5 или 6, то и в конечном спектре число 1000 будет возникать в два раза чаще, чем число 500.

Но это самое тупое, что мне сейчас в голову пришло.

Наверно, можно как-то упростить этот массив.
Например, сделать два массива:
A[1] = 1; B[1] = 1000;
A[2] = 5; B[2] = 500;
A[5] = 7; B[3] = 100;
Теперь нужно организовать быстрый поиск (делением пополам) в массиве A значения random. Допустим, random вернул число 6. Это соответствует элементу A[2], так как тот "обслуживает" значение random-а от 5 до 6 включитеьно. Если random вернул 7, то это A[5]. В первом случае выдаем B[2], во втором B[3]. Рандом чаще всего будет "находить" элемент массива A[1], так как тот "обслуживает" значения 1..4.
Ну что ж. Это вроде не так быстро, как первый тупой вариант, что я привел, но зато экономия памяти налицо - нужно держать ровно столько элементов массива A, сколько точек в функции распределения.
Как заполнить эти массивы?
Если пройтись равномерно по оси абсцисс графика распределения случайной величины и записать значения в B, а плотность вероятности прибавлять к некоторому X, которое писать в A, То мы получим в принципе то, что нам нужно. Вопрос в том, следует ли проходиться "равномерно". Видимо это для меня сейчас самый сложный вопрос, так как от задачи зависит, что мы хотим получить.
Но в любом случае, я оказался прав - наша X есть ни что иное, как интеграл функции распределения.

X := 0;
for i := 0 to Max do
begin
X := X + F[i]; //F - функция распределения величины i.
A[i] := X;
B[i] := i
end;
XMax = X;

Очевидно, что B[i] - лишний массив вообще.
Вот и имеем просто массив A[i] - интеграл функции распределения.
Остается искать в массиве A[i] делением пополам значение
random(XMax + 1).
Индекс найденного элемента массива и будет случайной величиной, распределенной согласно функции F[Index].
Можно индекс умножить на коэффициент и получить любой диапазон случайной величины с распределением F (масштабировать уже как угодно).
---------------
Значит я был прав. Это просто.
Но я не математик и пошел длинным путем, рассуждая просто на пальцах.

Пардон, описался:
A[1] = 1; B[1] = 1000;
A[2] = 5; B[2] = 500;
A[3] = 7; B[3] = 100;

Удалено модератором

Нужно сделать железку для PCI, ISA, USB, COM (наиболее легкий вариант) или еще как-нибудь!

Ставим диод (можно Шотки), пропускаем ток, через АЦП снимаем напряжение и все! )))

Можно подглядеть в любительской электронике генераторы белого шума и у же к ним приделывать АЦП!

← →
Sergey_Masloff (2004-05-07 09:11) [39]

WondeRu © (07.05.04 08:27) [38]
Кстати есть аппаратные генераторы случайных чисел, и есть уже очень давно. Только они не на таком принципе.

2Sergey_Masloff (07.05.04 09:11) [39]

знаю, но цены измеряются в сотнях,а то тыщах зеленых(

Random и его аналоги. Найти похожие ветки