Генератор псевдослучайных чисел

@bambino · Регистрация: 05.08.2010

Всем привет. Как такое "чудо" пишеться, примерный алгоритм, если можно на псевдокоде:

Написать генератор псевдослучайных чисел по алгоритму
f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) ( f0 = f1 = f2 = f3 = 1)
r = fn mod 211. ( 0 - 210)
Подсчитать частоту каждого числа при выборке 100000

Спасибо.

Добавлено через 24 минуты
хоть на словах, как это выглядит

@Thinker · 22.09.2011, 22:40

Держите вашу рекуррентную последовательность:

C++

#include<iostream>
 
int main()
{
   long f, f0, f1, f2, f3, i, n;
   n = 100;
   f0 = f1= f2= f3 = 1;
   for (i = 0; i < n; i++)
   {
      f = (f0 + f1 + f2 + f3) % 211;
      std::cout << f << " ";
      f0 = f1; f1 = f2; f2 = f3; f3 = f;
   }
   return 0;
}

@bambino · 22.09.2011, 22:50 **[ТС]**

Thinker, Спасибо, а как вынести это в отдельную функцию ? Делаю так, что-то не то:

C++

#include<iostream>
 
int get_rnd()
{
   int f, f0, f1, f2, f3;
   f0 = f1 = f2 = f3 = 1;
   f = (f0 + f1 + f2 + f3) % 211;
   f0 = f1; f1 = f2; f2 = f3; f3 = f;
   return f;
}
 
int main()
{
   int n = 10;
   for (int i = 0; i < n; i++)
      std::cout << get_rnd() << " ";
   return 0;
}

@Thinker · 22.09.2011, 22:52

А вот с выводом частот:

C++

#include<iostream>
 
#define MOD 211
#define N 100000
 
int main()
{
 
   long f, f0, f1, f2, f3, i;
   long count[MOD] = {0};
   f0 = f1 = f2= f3 = 1;
   for (i = 0; i < N; i++)
   {
      f = (f0 + f1 + f2 + f3) % MOD;
      count[f]++;
      //std::cout << f << " ";
      f0 = f1; f1 = f2; f2 = f3; f3 = f;
   }
   for (i = 0; i < MOD; i++)
   {
      std::cout << i << " " << count[i] << "\n";
   }
   return 0;
}

@Sylvos · 22.09.2011, 22:58

Сообщение от Thinker

А вот с выводом частот:

C++

#include<iostream>
 
#define MOD 211
#define N 100000
 
int main()
{
 
   long f, f0, f1, f2, f3, i;
   long count[MOD] = {0};
   f0 = f1 = f2= f3 = 1;
   for (i = 0; i < N; i++)
   {
      f = (f0 + f1 + f2 + f3) % MOD;
      count[f]++;
      //std::cout << f << " ";
      f0 = f1; f1 = f2; f2 = f3; f3 = f;
   }
   for (i = 0; i < MOD; i++)
   {
      std::cout << i << " " << count[i] << "\n";
   }
   return 0;
}

Очень страшный алгоритм

, почему бы просто не использовать обычный rand() ?

@Thinker · 22.09.2011, 23:08

Сообщение от bambino

Thinker, Спасибо, а как вынести это в отдельную функцию ? Делаю так, что-то не то.

C

#define MOD 211
#define N 100
 
int get_rnd()
{
   static int f = 1, f0 = 1, f1 = 1, f2 = 1, f3 = 1;
   f = (f0 + f1 + f2 + f3) % MOD;
   f0 = f1; f1 = f2; f2 = f3; f3 = f;
   return f;
}
 
int main()
{
 
   int i;
   for (i = 0; i < N; i++)
      printf("%d ", get_rnd());
   getchar();
   return 0;
}

Сообщение от Sylvos

Очень страшный алгоритм, почему бы просто не использовать обычный rand() ?

ТС не ищет легких путей)

@alex_x_x · 22.09.2011, 23:58

Не по теме:

Сообщение от Sylvos

Очень страшный алгоритм, почему бы просто не использовать обычный rand() ?

обычный rand сам по себе довольно слабый ГСЧ
могут быть специфические требования к последовательности

@jonson · 23.09.2011, 00:11

Не по теме:

Сообщение от alex_x_x

обычный rand сам по себе довольно слабый ГСЧ
могут быть специфические требования к последовательности

интересно, с чего такой вывод?

@Sylvos · 23.09.2011, 00:28

Не по теме:

jonson, Это скорей всего такой тонкий юморок людей с опытом которые тут провели уже довольно длительное время:D

@alex_x_x · 23.09.2011, 00:32

Не по теме:

оттого что он действительно слабый - маленький период повтора последовательности, отсутствие криптостойкости (по части последовательности можно восстановить всю последующую)
если не путаю там обычно простейший линейный конгруэнтный метод

@Thinker · 23.09.2011, 10:46

Сообщение от alex_x_x

Не по теме:

оттого что он действительно слабый - маленький период повтора последовательности...

Не по теме:

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

@alex_x_x
	22.09.2011, 23:58 #7
	Не по теме: Сообщение от Sylvos Очень страшный алгоритм, почему бы просто не использовать обычный rand() ? обычный rand сам по себе довольно слабый ГСЧ могут быть специфические требования к последовательности 0

@jonson
	23.09.2011, 00:11 #8
	Не по теме: Сообщение от alex_x_x обычный rand сам по себе довольно слабый ГСЧ могут быть специфические требования к последовательности интересно, с чего такой вывод? 0

@Sylvos
	23.09.2011, 00:28 #9
	Не по теме: jonson, Это скорей всего такой тонкий юморок людей с опытом которые тут провели уже довольно длительное время:D 0

@alex_x_x
	23.09.2011, 00:32 #10
	Не по теме: оттого что он действительно слабый - маленький период повтора последовательности, отсутствие криптостойкости (по части последовательности можно восстановить всю последующую) если не путаю там обычно простейший линейный конгруэнтный метод 2

@Thinker 4258 / 2232 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	23.09.2011, 10:46	11
	Сообщение от alex_x_x Не по теме: оттого что он действительно слабый - маленький период повтора последовательности... Не по теме: Это правда. Не зря же существует целый комплекс алгоритмов, генерирующих псевдослучайные числа. Не даром же существует проблема генерации истинно случайных чисел, которую пытаются решить массой способов. 0