Facebook
From Queen Owl, 6 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 250
  1. #include <iostream>
  2. #include <random>
  3. #include <cmath>
  4. #include <fstream>
  5. using namespace std;
  6.  
  7. void vfun_ReadDatas(int &iXmax, int &iN, int &iX0);
  8. void vfun_LCG(const int &iXmax, int &iX0, const int &iN);
  9. int ifun_SetC(int& iModule);
  10. int ifun_Random(int iFirst, const int iLast);
  11. bool bfun_NWD(int iA, int iB);
  12. void vfun_RandomizeLCG(const int &iModule, const int &iA, const int &iIncrease, const int &iX0, const int &iN);
  13. void vfun_SaveToFile(const string sName, int iValue);
  14. int *ifun_MakeTab(const int iSize);
  15.  
  16.  
  17.  
  18. int main() {
  19.         int iXmax, iN, iX0;
  20.         vfun_ReadDatas(iXmax, iN, iX0);
  21.         vfun_LCG(iXmax, iX0, iN);
  22.  
  23.         return 0;
  24. }
  25.  
  26.  
  27. /**
  28. * Funckja pobierająca dane do generatora
  29. * @param iXmax xmax
  30. * @param iN liczba wyrazów
  31. * @param iX0 ziarno
  32. */
  33. void vfun_ReadDatas(int &iXmax, int &iN, int &iX0)      {
  34.         cin >> iXmax >> iN >> iX0;
  35.  
  36.         while (iN < 0 || iXmax < 0 || iX0 < 0 || iX0 >= iXmax) {
  37.                 cout << "!" << endl;
  38.                 cin >> iXmax >> iN >> iX0;
  39.         }
  40. }
  41.  
  42. /**
  43. * Zbieranie danych do generatora losujący metodą liniową
  44. * @param iXmax xmax
  45. * @param iX0 ziarno
  46. * @param iN liczba wyrazów
  47. */
  48. void vfun_LCG(const int &iXmax, int &iX0, const int &iN, int *iPrimeNumbersTab) {
  49.         int iModule = iXmax + 1;
  50.         int iC = ifun_SetC(iModule);
  51.         ifun_PrimeNumbers(iModule);
  52.         int iMultiplier = ifun_SetA(iModule, iPrimeNumbersTab);
  53.         vfun_RandomizeLCG(iModule, iMultiplier, iC, iX0, iN);
  54. }
  55.  
  56. /**
  57. * Wyznaczanie przyrostu c
  58. * @param iModule moduł m
  59. * @return wartosc przyrostu c
  60. */
  61. int ifun_SetC(int &iModule) {
  62.         int iIncrease = ifun_Random(1, iModule);
  63.  
  64.         while (bfun_NWD(iModule, iIncrease)) {
  65.                 iIncrease = ifun_Random(1, iModule);
  66.         }
  67.  
  68.         return iIncrease;
  69. }
  70.  
  71. /**
  72. * Losowanie liczby
  73. * @param iFirst wyraz od ktorego losujemy
  74. * @param iLast wyraz do ktorego losujemy
  75. * @return dist(rd) wylosowana liczba
  76. */
  77. int ifun_Random(int iFirst, const int iLast) {
  78.         random_device rd;
  79.         uniform_int_distribution<int>dist(iFirst, iLast - 1);
  80.         return dist(rd);
  81. }
  82.  
  83. /**
  84. * Najwiekszy wspolny dzielnik
  85. * @param iA liczba pierwsza
  86. * @param iB liczba druga
  87. * @return false gdy NWD=1
  88. * @return true gdy NWD!=1
  89. */
  90. bool bfun_NWD(int iA, int iB) {
  91.         do {
  92.                 if (iA > iB) {
  93.                         iA = iA - iB;
  94.                 }
  95.                 else {
  96.                         iB = iB - iA;
  97.                 }
  98.         } while (iA != iB);
  99.  
  100.         if (iA == 1) {
  101.                 return false;
  102.         }
  103.         else {
  104.                 return true;
  105.         }
  106. }
  107.  
  108. /**
  109. * Zapisywanie do pliku
  110. * @param sName nazwa pliku
  111. * @param iValue wartość x ze wzoru
  112. */
  113. void vfun_SaveToFile(const string sName, int iValue) {
  114.         ofstream fsFile;
  115.         fsFile.open(sName, ios::app);
  116.         fsFile << iValue << endl;
  117.         fsFile.close();
  118. }
  119.  
  120. /**
  121. * Podstawienie wartości do wzoru głównego
  122. * iModule moduł m
  123. * iA mnożnik a
  124. * iIncrease przyrost c
  125. * iX0 ziarno x0
  126. * iN liczba wyrazów
  127. */
  128. void vfun_RandomizeLCG(const int &iModule, const int &iA, const int &iIncrease, const int &iX0, const int &iN) {
  129.         int x = iX0;
  130.  
  131.         for (int i = 0; i < iN; i++) {
  132.                 x = (iA * x + iIncrease) % iModule;
  133.                 vfun_SaveToFile("Wyniki.txt", x);
  134.         }
  135. }
  136.  
  137. /**
  138. * Proba tworzenia tablicy
  139. * @param iSize rozmiar
  140. * @return iTab tablica jeśli udało się stworzyć
  141. */
  142. int *ifun_MakeTab(const int iSize) {
  143.         int *iTab;
  144.  
  145.         try {
  146.                 iTab = new int[iSize];
  147.         }
  148.         catch (bad_alloc &bad) {
  149.                 cout << "!";
  150.                 exit(EXIT_FAILURE);
  151.         }
  152.  
  153.         return iTab;
  154. }
  155.  
  156. /**
  157. * Zlicza czynniki pierwsze liczby
  158. * @param iValue liczba sprawdzana
  159. * @return iCont liczba pierwszych
  160. */
  161. int ifun_CountPrime(int iValue) {
  162.         int iK = 2, iCount = 0;
  163.        
  164.         while (iValue>1) {
  165.                 while (iValue%iK == 0){
  166.                         iCount++;
  167.                         iValue /= iK;
  168.                 }
  169.                 iK++;
  170.         }
  171.        
  172.         return iCount;
  173. }
  174.  
  175. /**
  176. * Wypelnia tablice dzielnikami pierwszymi liczby
  177. * @param iValue liczba
  178. * @return iPrimeNumbersTab wypelniona tablica
  179. */
  180. int *ifun_PrimeNumbers(int iValue) {
  181.         int iSize = ifun_CountPrime(iValue);
  182.         int *iPrimeNumbersTab = ifun_MakeTab(iSize);
  183.         int g = sqrt(iValue);
  184.  
  185.         for (int i = 2, j=0; i <= g; i++) {
  186.                 while (iValue % i == 0)
  187.                 {
  188.                         iPrimeNumbersTab[j] = i;
  189.                         iValue /= i;
  190.                         j++;
  191.                 }
  192.         }
  193.         return iPrimeNumbersTab;
  194. }
  195.  
  196. /**
  197. * Sprawdza z teorią
  198. * @param iA podstawa do potegowania
  199. * @param iPrimeNumbersTab tablica dzielnikow ktore sa pierwsze
  200. * @param iValue moduł m
  201. * @return true zgodne ze wszystkim
  202. * @return false jesli sie nie zgadza
  203. */
  204. bool bfun_CheckWithTheory(int iA, int *iPrimeNumbersTab, int iModule)
  205. {
  206.         int b = iA - 1;
  207.         int iSize = ifun_CountPrime(iModule);
  208.         for (int i = 0; i < iSize; i++)
  209.         {
  210.                 if (b % iPrimeNumbersTab[i] != 0)
  211.                 {
  212.                         return false;
  213.                 }
  214.         }
  215.         if (iModule % 4 == 0)
  216.         {
  217.                 if (b % 4 == 0)
  218.                 {
  219.                         return true;
  220.                 }
  221.                 else
  222.                 {
  223.                         return false;
  224.                 }
  225.         }
  226. }
  227.  
  228. int ifun_SetA(int iModule, int *iPrimeNumbersTab) {
  229.         int iA, iLambda, iMaksLambda = 0, iCount = 0;
  230.         int *iTabA = ifun_MakeTab(100);
  231.        
  232.         for (int i = 0; i < 100; i++) {
  233.                 iTabA[i] = 0;
  234.         }
  235.  
  236.         for (iA = 2, iLambda = 1; iA < iModule; iA++, iLambda++) {
  237.                 int iPowAandLambda = pow(iA, iLambda);
  238.        
  239.                 while (bfun_NWD(iA, iModule) == false) {       
  240.                         while (iPowAandLambda % iModule == 1) {
  241.                                 if (iLambda > iMaksLambda) {           
  242.                                         for (int i = 0; i < 100; i++) {
  243.                                                 iTabA[i] = 0;
  244.                                         }
  245.  
  246.                                         iCount = 1;                                    
  247.                                         iMaksLambda = iLambda;
  248.                                         iTabA[iCount] = iA;
  249.                                 }
  250.                                 if (iLambda == iMaksLambda) {
  251.                                         iCount++;
  252.                                         iTabA[iCount] = iA;
  253.                                 }
  254.                         }
  255.                 }
  256.         }
  257.  
  258.         for (int i = 0; i < iCount; i++) {
  259.                 if (bfun_CheckWithTheory(iA, iPrimeNumbersTab, iModule) == true) {
  260.                         iA = iTabA[i];
  261.                 }
  262.                 else {
  263.                         iA = iTabA[iCount];
  264.                 }
  265.         }
  266. }