LINUX.ORG.RU

Датчик ПСП

 , , ,


1

1
Линейный конгруэнтный генератор Лемера 1951
Наиболее популярным для получения псевдослучайных чисел является
метод вычетов по формуле:

U[i+1] = (U[i]*M)mod p = U[i]*M-p*int(U[i]*M/p)

R[i]=U[i]/p,где U[i],M,p-целые числа,0<R[i]<1,1<=U[i]<=p-1.

И само задание:

Исследовать при каких U[0],p,M длина последовательности неповторяющихся чисел будет не менее 10000, при «хороших» стохастических параметрах. Определить влияет ли величина R[0],при M и p=const на статические характеристики датчика. Если влияет, то определить область допустимых величин U[0]. Представить результаты тестирования генератора для оптимальных величин p,M,U[0].

Сообственно буду добавлять сейчас код потихоньку и нужно сделать сами числа R в интеревале от [0,1].

#include <iostream>
#include <vector>
const int M = 302;
const int p = 1003;
const float U0 = 0.5;
const int N = 10000;
std::vector<float> gen(float R0, int m, int p)
{
	std::vector<float> R;
	std::vector<float> U;
	U.push_back(R0);
	for (int i = 0; i < N; i++)
	{
		U.push_back(U.back()/*U[i]*/ * M - p*int(U.back()/*U[i]*/ * M / p));
		float r_ = U[i] / p;
		R.push_back(r_);
		std::cout <<R.back()<<" ";
	}
	return R;
}
int main()
{
	gen(U0,M,p);
	std::cin.ignore();
	return 0;
}
Вопрос 1й как проверить что при длине последовательности N=10000(в принципе не важна длина) нет повторяющихся последовательностей? Что можно использовать? map,pair,set? поясните я слаб в коллекциях?

Короче есть идея добавлять либо в set и в конце сравнить размеры vector.size() and set.size() если длины равны то значения уникальны,а если set меньше , то значит значения повторялись правильно?

Gremlin_ ()
Ответ на: комментарий от Gremlin_

Вот реализация этой мысли

#include <iostream>
#include <vector>
#include <set>
const int M = 302;
const int p = 1003;
const float U0 = 0.5;
const int N = 200;
std::vector<float> gen(float R0, int m, int p)
{
	std::vector<float> R;
	std::vector<float> U;
	std::set<float> sR;
	U.push_back(R0);
	for (int i = 0; i < N; i++)
	{
		U.push_back(U.back()/*U[i]*/ * M - p*int(U.back()/*U[i]*/ * M / p));
		float r_ = U[i] / p;
		R.push_back(r_);
		sR.insert(r_);
		//std::cout <<R.back()<<" ";
	}
	if (sR.size() == R.size())
		std::cout << "lengths equal" << std::endl;
	std::cout<<"sR="<<sR.size()<<" R="<<R.size();
	return R;
}
int main()
{
	gen(U0,M,p);
	std::cin.ignore();
	return 0;
}

Gremlin_ ()
Ответ на: комментарий от Gremlin_

Вот тест который должен доказать что выбор U0(R0) влияет или нет на саму генерацию

#include <iostream>
#include <vector>
#include <set>
const int M = 437;
const int p = 1003;
float U0 = 0;
const int N = 10000;
std::vector<float> gen(float R0, int m, int p)
{
	std::vector<float> R;
	std::vector<float> U;
	std::set<float> sR;
	U.push_back(R0);
	for (int i = 0; i < N; i++)
	{
		U.push_back(U.back()/*U[i]*/ * M - p*int(U.back()/*U[i]*/ * M / p));
		float r_ = U[i] / p;
		R.push_back(r_);
		sR.insert(r_);
		//std::cout <<R.back()<<" ";
	}
	if (sR.size() == R.size())
		std::cout << "lengths equal" << std::endl;
	std::cout<<"R0="<<R0<<" sR="<<sR.size()<<" R="<<R.size()<<std::endl;
	return R;
}
int main()
{
	for (float i = 0; i < p; i+=0.001) 
	{
		U0 = i;
		gen(U0, M, p);
	}
	std::cin.ignore();
	return 0;
}

Gremlin_ ()
Ответ на: комментарий от Gremlin_

Добавил нахождения повторений последовательностей состоящих из 2х чисел

#include <iostream>
#include <vector>
#include <set>
#include <ctime>
const int M = 437;
const int p = 1003;
float U0 = 1.5;
const int N = 10000;
std::vector<float> gen(float R0, int m, int p)
{
	srand(time(0));
	std::vector<float> R;
	std::vector<float> U;
	std::set<float> sR;
	std::pair<float,float> pair;
	std::vector<std::pair<float, float>> vectorpair;
	std::vector<int> vectorpairfind;
	U.push_back(R0);
	for (int i = 0; i < N; i++)
	{
		U.push_back(U.back()/*U[i]*/ * M - p*int(U.back()/*U[i]*/ * M / p));
		float r_ = U[i] / p;
		R.push_back(r_);
		sR.insert(r_);
		if (i == 0)
		{
			pair.first = r_;
		}
		else if (i == 1) 
		{
			pair.second = r_;
			vectorpair.push_back(pair);
			vectorpairfind.push_back(0);
			//std::cout << " " << vectorpair.back().first << " " << vectorpair.back().second << " ";
		}
		else
		{
			pair.first = pair.second;
			pair.second = r_;
			int counter = 0;
			for (int j = 0; j < vectorpair.size(); j++)
			{
				if (pair.first == vectorpair[j].first && pair.second == vectorpair[j].second)
				{
					counter++;
					break;
				}
			}
			if (counter == 0) 
			{
				vectorpair.push_back(pair);
				vectorpairfind.push_back(0);
			}
			//std::cout << " " << vectorpair.back().first << " " << vectorpair.back().second << " ";
		}
		//std::cout <<"R="<<R.back()<<" "<<std::endl;
	}
	if (sR.size() == R.size())
		std::cout << "lengths equal" << std::endl;
	std::cout<<"R0="<<R0<<" sR="<<sR.size()<<" R="<<R.size()<<std::endl;
	std::cout << "vectorpair.size() =" << vectorpair.size() << std::endl;
	std::cout << "vectorpairfind.size() =" << vectorpairfind.size() << std::endl;
	for (int i = 0; i < N-1; i++)
	{
		for(int j=0;j<vectorpair.size();j++)
		if (vectorpair[j].first == R[i] && vectorpair[j].second == R[i + 1])
			{
				vectorpairfind[j]++;
			}
	}
	int counter = 0;
	for (int j = 0; j<vectorpair.size(); j++)
		if (vectorpairfind[j] > 1)
		{
			counter++;
			std::cout << "find" << vectorpair[j].first << " " << vectorpair[j].second << " count=" << vectorpairfind[j] << std::endl;
		}
	std::cout << "Find " << counter << " matches" << std::endl; 
	std::cout << "runtime = " << clock() / 1000.0 << std::endl;
	return R;
}
int main()
{
	float i = 1.5;
	//for (i=0; i < p; i+=0.001) 
	{
		U0 = i;
		gen(U0, M, p);
	}
	std::cin.ignore();
	return 0;
}

Gremlin_ ()
Ответ на: комментарий от Deleted

Здесь можно. Но здесь это делать бессмысленно, глупо и не нужно. Что забавно — из доказательства корректности сразу вытекает ненужность чисел с плавающей точкой.

i-rinat ★★★★★ ()
Ответ на: комментарий от Gremlin_

http://effbot.org/pyfaq/why-are-floating-point-calculations-so-inaccurate.htm
Ъ:

> 1.2-1.0
0.19999999999999996

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

crutch_master ★★★★★ ()
Последнее исправление: crutch_master (всего исправлений: 1)
Ответ на: комментарий от Gremlin_

Что-то ты странное развёл. Вычислил, проверил, есть ли число в set, если нет - записал его туда, если есть, проверил n, если меньше 10к вывел, что есть повтор, если больше, обнулил n. В конце сделал n++.

crutch_master ★★★★★ ()
Последнее исправление: crutch_master (всего исправлений: 1)
Ответ на: комментарий от crutch_master

Я думаю что врятли можно на генерировать 10000 различных чисел в интервале от 0 до 1, поэтому проверяют пары чисел в этом порядке, а там где пары совпадают значит и больше 2 чисел будут совпадать, но я же не могу все варианты различных подпоследовательностей проверить это слишком затратно , учитывая что я ещё не подобрал M и P

Gremlin_ ()
Ответ на: комментарий от crutch_master

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

Gremlin_ ()
Ответ на: комментарий от Gremlin_

но я же не могу все варианты различных подпоследовательностей проверить это слишком затратно

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

crutch_master ★★★★★ ()
Ответ на: комментарий от crutch_master

Почему ты используешь вторую формулу, а не берешь остаток от >деления на p?

U*M-p*int(U*M/p) -так это и есть остаток от деления там же равенство

Да легко.

Не для этой формулы

Зачем тебе проверять варианты последовательностей? Вроде как >достаточно знать, что на определённом интервале нет двух >одинаковых значений, а для этого достаточно взять set.

1 2 3 4 5 и 5 4 3 2 1 разные подпоследовательности хотя и состоят из одних значений которые в сет не попадут поэтому беру по два значения 1 2 в последовательности 1 2 3 1 2 3 найдет совпадения плюс еще остальные 2 3 , 3 1 тоже будут показывать что совпадения есть поэтому беру более 1 совпадения

Gremlin_ ()
Ответ на: комментарий от Gremlin_

U*M-p*int(U*M/p) -так это и есть остаток от деления там же равенство

Так сделай (U * M) % p понятней же будет.

1 2 3 4 5 и 5 4 3 2 1

5 дублей из 5 на 10 значениях. Фейл.

1 2 3 1 2 3

Дубль на 4-м значении. Для N = 10к - фейл.
Тебе же надо:

Исследовать при каких U[0],p,M длина последовательности неповторяющихся чисел будет не менее 10000

Верно? В первом твоём примере повтор на 6-м. Во втором - на 4-м. Зачем тебе что-то еще выдумывать с парами/векторами?

crutch_master ★★★★★ ()
Ответ на: комментарий от crutch_master
#include <iostream>
#include <vector>
#include <set>
#include <ctime>
#include <fstream>
int M = 0;//349;
int p = 0;//1003;
double U0 = 2;
const int N = 10000;
std::vector<int> min;
std::vector<std::pair<int, int>> minparam;
std::ofstream fout("result.txt");
std::vector<double> gen(double R0, int m, int p/*,std::ofstream fout*/)
{
	std::vector<double> R;
	std::vector<double> U;
	std::set<double> sR;
	std::pair<double,double> pair;
	std::vector<std::pair<double, double>> vectorpair;
	std::vector<int> vectorpairfind;
	U.push_back(R0);
	for (int i = 0; i < N; i++)
	{
		U.push_back(U.back() * M - p*int(U.back() * M / p));
		double r_ = U[i] / p;
		R.push_back(r_);
		sR.insert(r_);
		if (i == 0)
		{
			pair.first = r_;
		}
		else if (i == 1) 
		{
			pair.second = r_;
			vectorpair.push_back(pair);
			vectorpairfind.push_back(0);
			//std::cout << " " << vectorpair.back().first << " " << vectorpair.back().second << " ";
		}
		else
		{
			pair.first = pair.second;
			pair.second = r_;
			int counter = 0;
			for (int j = 0; j < vectorpair.size(); j++)
			{
				if (pair.first == vectorpair[j].first && pair.second == vectorpair[j].second)
				{
					counter++;
					break;
				}
			}
			if (counter == 0) 
			{
				vectorpair.push_back(pair);
				vectorpairfind.push_back(0);
			}
			//std::cout << " " << vectorpair.back().first << " " << vectorpair.back().second << " ";
		}
		//std::cout <<"R="<<R.back()<<" "<<std::endl;
	}
	if (sR.size() == R.size())
		std::cout << "lengths equal" << std::endl;
	//std::cout<<"R0="<<R0<<" sR="<<sR.size()<<" R="<<R.size()<<std::endl;
	//std::cout << "vectorpair.size() =" << vectorpair.size() << std::endl;
	//std::cout << "vectorpairfind.size() =" << vectorpairfind.size() << std::endl;
	fout<< "R0=" << R0 << " sR=" << sR.size() << " R=" << R.size() << std::endl;
	fout<< "vectorpair.size() =" << vectorpair.size() << std::endl;
	fout<< "vectorpairfind.size() =" << vectorpairfind.size() << std::endl;
	for (int i = 0; i < N-1; i++)
	{
		for(int j=0;j<vectorpair.size();j++)
		if (vectorpair[j].first == R[i] && vectorpair[j].second == R[i + 1])
			{
				vectorpairfind[j]++;
			}
	}
	int counter = 0;
	for (int j = 0; j<vectorpair.size(); j++)
		if (vectorpairfind[j] > 1)
		{
			counter++;
			//std::cout << "find" << vectorpair[j].first << " " << vectorpair[j].second << " count=" << vectorpairfind[j] << std::endl;
		}
	//std::cout << "Find " << counter << " matches" << std::endl; 
	fout<< "Find " << counter << " matches" << std::endl;
	if (counter == 0) 
	{
		std::cout << "M= " << M << " p=" << p << std::endl;
	}
	fout << "M= " << M << " p=" << p << std::endl;
	//if (vectorpair.size() == N - 1)
	//{
	min.push_back(vectorpair.size()/*counter*/);
	std::pair<int, int> pairmin;
	pairmin.first = m;
	pairmin.second = p;
	minparam.push_back(pairmin);
	//}
	return R;
}
int main()
{
	srand(time(0));
	double ii = 2;
	//for (int j = 200; j < 300; j++)
	{
		M =  2;
		U0 = ii;
		//for (int jj = 200; jj < 300; jj++)
		{
			p = 655360001;
			gen(U0, M, p/*,fout*/);
		}
	}
	std::cout << "runtime = " << clock() / 1000.0 << std::endl;
	int max_ = 0;
	int ct = 0;
	for (int i = 0; i < min.size(); i++)
	{
		if (max_ < min[i]) 
		{
			max_ = min[i];
			ct = i;
		}
	}
	std::cout <<"ct="<<ct<<" max vector.size():" << min[ct] << " minparam: m=" << minparam[ct].first << " p=" << minparam[ct].second << std::endl;
	fout.close();
	std::cin.ignore();
	return 0;
}
Gremlin_ ()
Ответ на: комментарий от Gremlin_

то бишь в цикле прогнать U0 от 1 до p-1 но т.к. p большое придется брать понемногу чтобы не считать месяц и дольше вот код

#include <iostream>
#include <vector>
#include <set>
#include <ctime>
#include <fstream>
int M = 0;//349;
int p = 0;//1003;
double U0 = 2;
const int N = 10000;
std::vector<int> min;
std::vector<std::pair<int, int>> minparam;
std::ofstream fout("result.txt");
std::vector<double> gen(double R0, int m, int p/*,std::ofstream fout*/)
{
	std::vector<double> R;
	std::vector<double> U;
	std::set<double> sR;
	std::pair<double,double> pair;
	std::vector<std::pair<double, double>> vectorpair;
	std::vector<int> vectorpairfind;
	U.push_back(R0);
	for (int i = 0; i < N; i++)
	{
		U.push_back(U.back() * M - p*int(U.back() * M / p));
		double r_ = U[i] / p;
		R.push_back(r_);
		sR.insert(r_);
		if (i == 0)
		{
			pair.first = r_;
		}
		else if (i == 1) 
		{
			pair.second = r_;
			vectorpair.push_back(pair);
			vectorpairfind.push_back(0);
			//std::cout << " " << vectorpair.back().first << " " << vectorpair.back().second << " ";
		}
		else
		{
			pair.first = pair.second;
			pair.second = r_;
			int counter = 0;
			for (int j = 0; j < vectorpair.size(); j++)
			{
				if (pair.first == vectorpair[j].first && pair.second == vectorpair[j].second)
				{
					counter++;
					break;
				}
			}
			if (counter == 0) 
			{
				vectorpair.push_back(pair);
				vectorpairfind.push_back(0);
			}
			//std::cout << " " << vectorpair.back().first << " " << vectorpair.back().second << " ";
		}
		//std::cout <<"R="<<R.back()<<" "<<std::endl;
	}
	if (sR.size() == R.size())
		std::cout << "lengths equal" << std::endl;
	//std::cout<<"R0="<<R0<<" sR="<<sR.size()<<" R="<<R.size()<<std::endl;
	//std::cout << "vectorpair.size() =" << vectorpair.size() << std::endl;
	//std::cout << "vectorpairfind.size() =" << vectorpairfind.size() << std::endl;
	fout<< "R0=" << R0 << " sR=" << sR.size() << " R=" << R.size() << std::endl;
	fout<< "vectorpair.size() =" << vectorpair.size() << std::endl;
	fout<< "vectorpairfind.size() =" << vectorpairfind.size() << std::endl;
	for (int i = 0; i < N-1; i++)
	{
		for(int j=0;j<vectorpair.size();j++)
		if (vectorpair[j].first == R[i] && vectorpair[j].second == R[i + 1])
			{
				vectorpairfind[j]++;
			}
	}
	int counter = 0;
	for (int j = 0; j<vectorpair.size(); j++)
		if (vectorpairfind[j] > 1)
		{
			counter++;
			//std::cout << "find" << vectorpair[j].first << " " << vectorpair[j].second << " count=" << vectorpairfind[j] << std::endl;
		}
	//std::cout << "Find " << counter << " matches" << std::endl; 
	fout<< "Find " << counter << " matches" << std::endl;
	if (counter == 0) 
	{
		std::cout << "M= " << M << " p=" << p << std::endl;
	}
	fout << "M= " << M << " p=" << p << std::endl;
	//if (vectorpair.size() == N - 1)
	//{
	min.push_back(vectorpair.size()/*counter*/);
	std::pair<int, int> pairmin;
	pairmin.first = m;
	pairmin.second = p;
	minparam.push_back(pairmin);
	//}
	return R;
}
int main()
{
	srand(time(0));
	double ii = 2;
	for (int j = 1; j < 300; j++)
	{
		M =  2;
		U0 = j;
		//for (int jj = 200; jj < 300; jj++)
		{
			p = 655360001;
			gen(U0, M, p/*,fout*/);
		}
	}
	std::cout << "runtime = " << clock() / 1000.0 << std::endl;
	int max_ = 0;
	int ct = 0;
	for (int i = 0; i < min.size(); i++)
	{
		if (max_ < min[i]) 
		{
			max_ = min[i];
			ct = i;
		}
	}
	std::cout <<"ct="<<ct<<" max vector.size():" << min[ct] << " minparam: m=" << minparam[ct].first << " p=" << minparam[ct].second << std::endl;
	fout.close();
	std::cin.ignore();
	return 0;
}

Gremlin_ ()
Ответ на: комментарий от Gremlin_

то бишь в цикле прогнать U0 от 1 до p-1 но т.к. p большое придется брать понемногу чтобы не считать месяц и дольше вот код

Ты упёрся в оверинженеринг. Остановись! Тебе надо познать дао не нужного.

crutch_master ★★★★★ ()
Последнее исправление: crutch_master (всего исправлений: 1)
Ответ на: комментарий от Gremlin_

я матанщик-кодер-шифровальщик-параллельщик мне все по силам

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

crutch_master ★★★★★ ()
Ответ на: комментарий от i-rinat

Эм простые числа на места M and p, там много чисел первых 500 простых. Наилучшие стохастические параметры генератора при простых значениях. Забыл добавить в условие задачи. Короче сегодня сдал Лабу эту так что забейте на этот тред.

Gremlin_ ()