Документ: Интегрированные информационные системы, информационно-управляющие системы, имитационное моделирование и конфликтология, страницы 106-110

ВЫПУСК № 2 (10), 2017

ISSN 2307-177X

методах получения случайных последовательностей.

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

		(	)	(2)
где:	- модуль	(	); –	множитель
(	); –	приращение (		);
— начальное значение (				).
	Последовательность случайных чисел,

полученных с помощью (2), называется линейной конгруэнтной последовательностью. Многие авторы [1,3,5] называют линейную конгруэнтную последовательность

при = 0 мультипликативным конгруэнтным методом, а при ≠ 0 —смешанным конгруэнтным методом.

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

Генераторы случайных чисел XORShift [6] представляют собой подмножество регистров сдвига с линейной обратной связью, которые обеспечивают особенно эффективную реализацию без использования чрезмерно разреженных многочленов. Генераторы подобного класса генерируют следующее число в своей последовательности, повторно беря логически исключенное или побитно сдвинутую версию самого себя. Вариант генерации 32-битового целого выглядит так:

( (	))			(3)
( (	)) (	(	))

Использование битовых операций обеспечивает быстроту вычислений, но подобные методы требуют тщательного подбора параметров, чтобы достичь длительного периода.

Запаздывающие генераторы Фибоначчи – это генераторы псевдослучайных чисел, также называемые аддитивными генераторами [7]. В отличие от генераторов, использующих линейный конгруэнтный алгоритм, генераторы Фибоначчи можно использовать в статистических алгоритмах, требующих высокого разрешения.

Один из широко распространѐнных фибоначчиевых генераторов основан на следующей формуле:

{

(4)

где – вещественные числа из диапазона [0,1), и – целые положительные числа, называемые лагами. При реализации через целые числа достаточно формулы:

		(5)
Для	работы	генератору Фибоначчи
требуется	*	+ предыдущих сгенериро-

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

Для проведения вычислительного эксперимента было построено три генератора случайных чисел для каждого описанного выше метода – Си-генератор, использующих стандартную функцию rand() языка Си, XORShift-генератор с простым подбором и Генератор Фибоначчи по алгоритму, описанному (4) и (5). В соответствии свыше изложенным программно были реализованы шесть функций, реализующих частотный тест, проверку по - критерию и четыре оценки формы распределения (среднее, стандартное отклонение, коэффициент асимметрии и эксцесса). Оценка расхождения экспериментально полученных и ожидаемых результатов осуществлялась аналогич-

но [3].

105

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В СТРОИТЕЛЬНЫХ, СОЦИАЛЬНЫХ И ЭКОНОМИЧЕСКИХ СИСТЕМАХ

По результатам вычислительного экс-									размаха (табл. 2),					ниже медианы (табл. 3) и
перимента		был проведен сравнительный							выше медианы (табл. 4)) для каждого гене-
анализ результатов частотного теста для трех									ратора с ожидаемым теоретическим значе-
интервалов		(в пределах интерквантильного							нием и оценено расхождение в %.
																Таблица 2
						Результаты частотного теста в диапазоне (0.2113;0.7887)
N		Си генератор						XORShift						Генератор Фибоначчи
	(0.2113;			% отклонения			(0.2113;			%			(0.2113;		%
	0.7887)						0.7887)			отклонения			0.7887)			отклонения
10	60%		3%				60%			3%			50%		7%
20	60%		3%				65%			8%			45%		12%
30	56.6%		0.33%				46.6%			10.3%			60%		3%
40	57.5%		0.5%				55%			2%			50%		7%
50	64%		7%				64%			7%			49%		8%
																Таблица 3
								Результаты частотного теста в диапазоне (0;0.5)
N		Си генератор						XORShift						Генератор Фибоначчи
	(0;0.5)			%			(0;0.5)				%		(0;0.5)		%
				отклонения								отклонения				отклонения
10	51%			1%			55%				5%		40%		10%
20	55%			5%			50%				0%		60%		10%
30	43.3%			6.7%			48%				2%		43.3%		6.7%
40	40%			10%			44%				6%		62.5%		12.5%
50	43.3%			6.7%			52.5%				2.5%		70%		20%
																Таблица 4
								Результаты частотного теста в диапазоне (0.5;1)
N		Си генератор						XORShift						Генератор Фибоначчи

	(0.5;1)			% откло-			(0.5;1)				% откло-		(0.5;1)		%
					нения							нения			отклонения
10	49%			1%			45%					5%	60%		10%
20	45%			5%			50%					0%	40%		10%
30	56.7%			6.7%			52%			2%			56.6%		6.7%
40	60%			10%			56%			6%			37.5%		12.5%
50	56.6%			6.7%			47.5%			2.5%			30%		20%
																Таблица 5
					Результаты теста по -критерию при пропорциональной выборке
N		Си генератор							XORShift					Генератор Фибоначчи

					отклонение							отклонение				отклонение
10		10.92			1.62			11.16				1.82		9.92		0.62

20		20.28			0.94			22.7				2.1		19.2		0.14

30		31.85			2.51			30.89				1.5		28.8		0.51

40		40.76			1.32			41.19				1.85		39.2		0.32

50		50.91			1.58			51,43				2.1		49.55		0.22

106

ВЫПУСК № 2 (10), 2017																ISSN 2307-177X
	Сравнение генераторов				по			-			Анализ характеристик формы произво-
критерию был построен аналогичным обра-										дился аналогично на основе расчета откло-
зом. Чтобы выявить наилучший результат,										нений среднего (табл. 6), стандартного от-
было проведено сравнение полученного ре-										клонения (табл. 7), коэффициентов асиммет-
зультата с ожидаемым, теоретическим (табл.										рии и эксцесса (табл. 8-9) от теоретических
5). Так как, значение критерия					вычисляет-					значений, получены:
ся как квадраты разностей между получен-											(	)		;
ным количеством чисел и «эталонным», в
идеальном случае отклонение будет стре-												;
миться к нулю, независимо от количества												.
чисел в последовательности.
																		Таблица 6
			Среднее арифметическое математического ожидания генераторов при
								пропорциональной и непропорциональной выборке
	Выборка			Си генератор							XORShift					Генератор
																Фибоначчи
				Мат. ож.		Откл.,%				Мат. ож.		Откл.,%			Мат. ож.			Откл.,%

	Пропорциональная			0,45		11.11%				0,51		1.96%			0,47			6.38%
	Непропорциональная			0,522		4.21%				0,49		2.04%			0,502			0.40%
				0,522		4.21%				0,49		2.04%			0,502			0.40%
																		Таблица 7
		Среднеквадратичного отклонения генераторов при пропорциональной и
													непропорциональной выборке
	Выборка			Си генератор							XORShift					Генератор
																Фибоначчи
				СКО	Откл.,%			СКО			Откл., %					СКО				Откл.,
																			%

	Пропорциональная		0.31		12.90%			0.28			Непропорциональная					0.31			12.90%

	Непропорциональная		0.26		3.85%			0.27			Непропорциональная					0.26			3.85%

																		Таблица 8
	Значения коэффициента асимметрии генераторов при пропорциональной и
													непропорциональной выборке
	Выборка			Си генератор							XORShift					Генератор
																Фибоначчи
			Асимметрия				Откл.,		Асимметрия				Откл.,		Асимметрия					Откл.,
							%						%							%
	Пропорциональная		0.008				0.008		-0.0078				0.0078		0.0042					0.0042
	Непропорциональная		0.003				0,003		0.0022				0.0022		-0,00012					0.00012
			0.003				0,003		0.0022				0.0022		-0,00012					0.00012
																		Таблица 9
		Значения коэффициента эксцесса генераторов при пропорциональной и
													непропорциональной выборке
	Выборка			Си генератор							XORShift					Генератор
																Фибоначчи
			Эксцесс			Откл., %				Эксцесс		Откл., %			Эксцесс		Откл., %
	Пропорциональная		-0.9			0.3			0.88			2.08			-0,64		0,56
	Непропорциональная		0.46			1.66			-0.33			0.87			0,25		1.45

107

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В СТРОИТЕЛЬНЫХ, СОЦИАЛЬНЫХ И ЭКОНОМИЧЕСКИХ СИСТЕМАХ

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

чающих за равномерность стремятся к значениям эталонного генератора случайных чисел.

Для наглядности было построено распределение для диапазона от 0 до 1 при последовательности в 10000 случайных чисел, для каждого из разработанных генераторов (рис.1, рис.2, рис.3).

Рис. 1. Диаграмма распределения генератора языка Си

Рис. 2. Диаграмма распределения XORShift генератора

Рис. 3. Диаграмма распределения генератора на основе метода Фибоначчи

108

ВЫПУСК № 2 (10), 2017 ISSN 2307-177X

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

казатели по каждому из проведенных тестов.			1. Кнут, Д.Э. Искусство программирова-
Он прост в реализации и может быть исполь-			ния. Том 2. Получисленные алгоритмы Учеб.
зован в прикладных и не затратных задачах,			пособ. / Кнут Дональд Эрвин. – Третье издание.
			Перевод с английского. Под общей			редакцией
не очень требовательных к качеству случай-
			Ю.В. Козаченко – М: Издательский дом «Виль-
ных чисел.
			ямс», 2001. – 839с.
XORShift генератор проходит оба теста
			2. Крамер Г. Математические методы
с результатом выше среднего. При проверке
			статистики / Г. Крамер. - М.: Мир, 1975 г. –
на частоту попаданий в интервал, удавалось
			648с.
добиться практически эталонных значений,
			3. Львович, И.Я. Сравнение			способов
но конечно при намного большей выборке
			представления справочных показателей дли-
такие результаты недостижимы. Тем не ме-
			ны и массы тела детей/ И.Я. Львович, О.В.
нее, алгоритм генерации достаточно просто в
			Минакова, В.П. Ситникова, Л.И. Стахурло-
реализации и может быть использован как на
			ва// Системный анализ и управление в био-
одном уровне с генератором языка Си, так и
			медицинских системах: журнал			практиче-
в более требовательных к случайности зада-
			ской и теоретической биологии и медицины.
чах. Дело в том, что XORShiftгенератор ис-
			М., 2007. Т. 6. № 3. – С.737-741.
пользует в качестве источника энтропии так
			4. Минакова,	О.В.,	Квантильно -
называемые «magicnumbers», на основе ко-
			регрессионные модели в решении задач со-
торых и происходит генерация. Подобрав
			циально-экономического		мониторинга
нужные числа, можно получать практически
			[Текст]: монография	/ О.В. Минакова, И.Я.
любые псевдо - случайные последовательно-
			Львович И. Я. – Воронеж, Научная книга,
сти, но подбор таких чисел, очень трудоем-
			2011. – 151 с.
кая и кропотливая задача.
			5. Поршнев, С.В. Компьютерное моде-
Генератор на основе метода Фибоначчи
			лирование физических процессов			в пакете
с запаздываниями, имеет хорошие показате-
			MATLAB / С.В. Поршнев. – Изд-во Горячая
ли при тесте по критерию , и оптимальные
			Линия - Телеком, 2003. – 592 с.
при частотном тесте. В отличие от предыду-
			6. Marsaglia,	George,	2003,	Xorshift
щих генераторов, фибоначчиевский		алго-
			RNGs, Journal Statistical Software, 8, Issue 14
ритм при большом размере выборки позво-
			7. Ross Anderson On		Fibonacci Key-
ляет получать практически идеально равно-
			stream Generators. — Computer Laboratory,.
мерно распределенную	последовательность
			Pembroke Street, Cambridge CB2 3QG
случайных чисел, но при этом имеет не та-
			8. stratum.ac.ru	[Электронный ресурс].
кую простую реализацию, как предыдущие
			– Электронные данные –		Режим	доступа:

	генераторы. Также из-за сложности алгорит-	http://stratum.ac.ru/education/textbooks/modelir
	ма требуется больше времени и памяти для	http://stratum.ac.ru/education/textbooks/modelir
	ма требуется больше времени и памяти для	/lection22.html
	генерации чисел. Так или иначе, генератор	/lection22.html
	генерации чисел. Так или иначе, генератор
	случайных чисел на основе метода Фибонач-

109

Материал: Интегрированные информационные системы, информационно-управляющие системы, имитационное моделирование и конфликтология

Смотрите также: