HLFX.Ru Forum - Random numbers generator

Собственно, генератор в волатиле, наговнянный по-быстрому и основанный на rand(), меня не устраивает, потому что он не портабельный и в разных компиляторах ведёт себя по-разному, да и длина серии rand() оставляет желать лучшего.
В ку3, скажем, используется очень просто линейный конгруэнтный метод (ЛКМ), что считается предсказуемым и вообще плохим. (rand, кстати, тоже обычно ЛКМ, хотя это остаётся на усмотрение автора библиотеки CRT/LIBC).

Единственный известный мне нормальный альтернативный генератор - в Xash3D - это по сути генератор из сорцов бетки хл2 (c перебитым копирайтом...). Мне даже удалось узнать, что автор генератора из бетки - и вовсе не Valve, а товарищи Press и Teukolsky, а Valve внесла кое-какие модификации косметической формы. Алгоритм также опубликован в Numeric Recipes (NR) (возвращаясь к копирайтам в ксаше - атата, Дядя Миша, у Numeric Recipes очень анальная лицензия!) Но пока не могу найти оригинальную статью (может, у кого есть?)

это только про игры, или вообще в программах?

Да без разницы -- я занимаюсь и волатилой, и молекулярной динамикой параллельно, вы же знаете.
Но всё же желательно быстрый.

Добавлено 19-01-2014 в 21:45:

Да, кстати, речь только о uniform-генераторах.

Добавлено 19-01-2014 в 21:46:

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

XaeroX

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

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

у тебя двухмерная или трёхмерная геометрия? как сортируешь частицы/дефрагментируешь массив, на каждом шаге?

>(NTP-ансамбль).
эт. что то из биологии. а можешь примерно назвать сколько по порядку частиц в системе, и размеры сетки?
>остальное аппроксимируется, угу.
ур-ем пуассона?
>Кол-во частиц постоянно
граничные условия что ли периодические?
>Да это не важно
ну интересно ж про работу узнать

>как сортируешь частицы/дефрагментируешь массив
ну я к тому, как ты различаешь ближние и дальние. или просто хранишь отдельный массив с индексами вместо пересортировки? а сколько Мб/Гб занимает вся функция распределения?

__________________
Вся сила лысого кощея,
Сокрыта в башне из костей
Воздвигнутой, под небесами
На месте похорон людей

fire64
Аппаратную часть прилагать к каждой копии ОИФД/Вольфрама, или предлагать покупать отдельно за $9.99 без учёта стоимости доставки?

__________________
Вся сила лысого кощея,
Сокрыта в башне из костей
Воздвигнутой, под небесами
На месте похорон людей

А что там с "/dev/urandom"? Как я понял, тоже имеет аппаратную природу? Под виндой аналог есть, какая-нибудь винапишная функция?

Добавлено 19-01-2014 в 22:56:

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

Номера первого и второго файла можно например вычислить из текущей даты и текущего времени. (это для первого раза). А потом прибавлять к ним те самые смещения, которые случайно прочлись из того или иного файла.

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

XaeroX

/dev/urandom не такой хаотичный как /dev/random, но последний медленнее.

thambs
Что понимается под "хаотичностью"? Неравномерность распределения случайной величины?

XaeroX

/dev/random собирает шум железа в текущий момент, /dev/urandom берёт шум из хранилища. поэтому, если шум там закончится, то то возможны повторы.

А, виноват, перепутал.
Хранилище это как создаётся, всё тем же /dev/random-ом? Ограничение по сути только на длину серии (у рандома ограничения нет)?

>Хранилище это как создаётся

не отвечу -- не знаю.

В любом случае не важно, мне нужны только портируемые решения.

В бусте этих рандом-генераторов целый вагон. И всё портабельно и под разрешительную лицензию. Они, кстати, тоже отсылают к NR в введении.

XaeroX, отсылают - мол, изучайте, "For a general introduction to random numbers in numerics". На чём их либа основана, я не знаю. И весь буст никто не заставляет тащить. Хотя там у рандома зависимости от других либ имеются, но их количество от конкретного случая зависит. Утаскиваешь ровно столько, сколько нужно и доволен, и даже компилять ничего не надо - всё в хидерах. Но я вообще к тому, что можно подсмотреть реализацию и не бояться анальной кары.

shoom();

к рандому оч серьёзно относится трукрипт и мегауплод. не зря там заставляют совершать развратные движения мышью. Там ребята решили просто: в машине случайным быть не может ничего. Сраные ТПМки юзать - прогнуться под ФБР и АНБ. Можно сэмплить шум с микрофона

__________________
"Злобным гениям не нужна харизма." © Shooter__Andy
"Making stuff for an "old ugly game" can be ten times more fun than grinding on a map for a dull, next-gen title." © Lunaran

В общем, я сконструировал свой конгруэнтный генератор на основе мултипликативного и AWC-генератора. Он немного быстрее и немного чотче хл2шного, а главное - никаких копирайтов, можно вешать свой.

Шутко. На самом деле главное - это период. У бетковского он 2^32, а у меня 2^32*2^58=2^90. Серии должны быть гораздо длиннее. Осталось его как следует потестить. И я не совсем уверен в правильности выбора стартовых семечек, возможно, этот момент можно сделать лучше.
Если кому интересно - могу выложить с пояснениями.

XaeroX он предиктабельный у тебя? seed поддерживает?

1	// Random generator, author: XaeroX, 2014

2	// Part of Volatile3D II Engine source code

3	// Code license:

4	// Creative Commons Attribution-Noncommercial-Share Alike

5	// http://creativecommons.org/licenses/by-nc-sa/4.0/

7	// could be local statics, but we reference them

8	// in two subroutines: srand and rand

9	// the initial values are arbitrary unsigned ints

10	static unsigned int awc0 = 0xf6a3d9;

11	static unsigned int awc1 = 0x159a55e5;

12	static unsigned int mult = 0x436cbae9;

13	static unsigned int carry = 1;

15	void xrxSRand( unsigned int seed )

17	// default seed comes from system timers

18	if ( !seed ) seed = ( unsigned int )time( NULL );

20	// initialize AWC and multiplicative seeds

21	awc0 = 0x10dcd * seed + 0xf6a3d9;

22	awc1 = 0x10dcd * seed + 0x159a55e5;

23	mult = seed & 0x7fffffff;

25	// carry flag initial value depends on awc seeds

26	carry = ( awc0 > awc1 ) ? 0 : 1;

29	unsigned int xrxRand( void )

31	// run AWC-generator

32	unsigned int awc = awc1 + ( awc0 + carry );

33	carry = ( awc > awc0 ) ? 0 : 1;

34	awc1 = awc0; awc0 = awc;

36	// run multiplicative generator

37	mult = 0x10dcd * mult + 0x3c6ef373;

39	// return random value

40	return awc + mult;

43	int Com_RandomLong( int low, int high )

45	static bool init = false;

46	unsigned int randNumber;

47	unsigned int randRange = high - low + 1;

49	assert( high >= low );

51	if ( randRange <= 1 )

52	return low;

54	if ( !init ) {

55	xrxSRand( 0 );

56	init = true;

59	// remapping to desired range keeping random value uniformly distributed

60	unsigned int maxAcceptable = 0xfffffffe - ( 0xffffffff % randRange );

61	do randNumber = xrxRand(); while ( randNumber > maxAcceptable );

63	return low + ( randNumber % randRange );

66	float Com_RandomFloat( float low, float high )

68	static bool init = false;

69	float randNumber;

70	float randRange = high - low;

72	assert( high >= low );

74	if ( randRange <= 0 )

75	return low;

77	if ( !init ) {

78	xrxSRand( 0 );

79	init = true;

82	randNumber = 0.2328306437e-9f * xrxRand();

83	return low + randNumber * randRange;

Кстати в C++11 появилась отличная библиотека <random> с кучей алгоритмов и распределений (и возможностью подключать свои), собственно там весьма винрарный вихрь мерсенна идет из коробки.

Производительность только надо б замерить, но мне чет лень.

Извиняюсь за поднятие старой темы. А как сослаться на http://hlfx.ru/forum/showthread.php...1218#post131218 если я хочу использовать эту имплементацию?

thambs
В исходниках - можешь прям эту ссылку в комментариях и разместить.
В статье - ссылайся на оригинальные работы. Моя реализация, по сути, на основе их идей.