cpp_alex

Linear polynomic random generator analysis

Sep 16th, 2021
1,226
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6.  
  7. class Generator {
  8.   std::vector<int64_t> ratios, elements;
  9.  
  10.   int64_t current_number;
  11.   public:
  12.   Generator(std::vector<int64_t> input_ratio, std::vector<int64_t> input_elem)
  13.       : ratios(input_ratio), elements(input_elem) {}
  14.  
  15.   int64_t getNextValue() {
  16.     int64_t temp = current_number;
  17.     current_number = (ratios[0] * elements[2] + ratios[1] * elements[1] +
  18.         ratios[2] * elements[0]) % ratios[3];
  19.  
  20.     elements[0] = elements[1], elements[1] = elements[2],
  21.     elements[2] = current_number;
  22.  
  23.     return current_number;
  24.   }
  25.  
  26.   bool operator==(Generator& object) {
  27.     return elements[0] == object.elements[0] &&
  28.         elements[1] == object.elements[1] && elements[2] == object.elements[2];
  29.   }
  30.  
  31.   bool operator!=(Generator& object) {
  32.     return !(object == *this);
  33.   }
  34. };
  35.  
  36.  
  37. class Analyzer {
  38.   std::vector<int64_t> ratios, elements;
  39.  
  40.   public:
  41.   Analyzer(std::vector<int64_t> input_ratio,
  42.            std::vector<int64_t> input_elem) :
  43.            ratios(input_ratio), elements(input_elem) {}
  44.  
  45.   int64_t FindPeriod() {
  46.     Generator turtle(ratios, elements), ahill(ratios, elements);
  47.  
  48.     turtle.getNextValue();
  49.     while (turtle != ahill) {
  50.       turtle.getNextValue();
  51.       turtle.getNextValue();
  52.  
  53.       ahill.getNextValue();
  54.     }
  55.     turtle.getNextValue();
  56.  
  57.     int64_t period = 1;
  58.     while (turtle != ahill) {
  59.       turtle.getNextValue();
  60.       ++period;
  61.     }
  62.  
  63.     return period;
  64.   }
  65.  
  66.   int64_t FindPrePeriod(uint64_t period) {
  67.     Generator start_generator(ratios, elements),
  68.         next_generator(ratios, elements);
  69.  
  70.     for (uint64_t i = 0; i < period; ++i) {
  71.       next_generator.getNextValue();
  72.     }
  73.  
  74.     uint64_t n = 0;
  75.     while (next_generator != start_generator) {
  76.       next_generator.getNextValue();
  77.       start_generator.getNextValue();
  78.  
  79.       ++n;
  80.     }
  81.  
  82.     return n;
  83.   }
  84.  
  85.   long double getGoodness() {
  86.     std::vector<long double> res(400, 0.0);
  87.     Generator gen(ratios, elements);
  88.  
  89.     std::vector<int64_t> counts(20, 0);
  90.  
  91.     for (int i = 0; i < counts.size(); ++i) {
  92.       long double new_number = gen.getNextValue() * 1.0 / ratios.back();
  93.       ++counts[std::trunc(new_number * 20.0)];
  94.     }
  95.  
  96.     long double ans = 0.0l;
  97.  
  98.     for (int i = 0; i < counts.size(); ++i) {
  99.       ans += ((counts[i] - 20) * (counts[i] - 20)) / 400.0;
  100.     }
  101.    
  102.     ans = std::sqrt(ans);
  103.  
  104.     return ans;
  105.   }
  106. };
  107.  
  108. int main() {
  109.   int64_t a, b, c, d, x0, x1, x2;
  110.  
  111.   std::cin >> a >> b >> c >> d >> x0 >> x1 >> x2;
  112.  
  113.   Analyzer analyzer({a, b, c, d}, {x0, x1, x2});
  114.  
  115.   auto p = analyzer.FindPeriod();
  116.  
  117.   std::cout << p << "\n";
  118.   std::cout << analyzer.FindPrePeriod(p) << "\n" << analyzer.getGoodness();
  119.  
  120.   return 0;
  121. }
  122.  
RAW Paste Data