fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdint>
  3.  
  4. template<class T>
  5. T mod(T a, T b)
  6. {
  7.     a %= b;
  8.     return a>0?a:a+b;
  9. }
  10.  
  11. void ext_euclid(int64_t a, int64_t b, int64_t *lastx, int64_t *lasty)
  12. {
  13.     int64_t x = 0;
  14.     int64_t y = 1;
  15.     *lastx = 1;
  16.     *lasty = 0;
  17.     int64_t q, r;
  18.     int64_t tmp;
  19.  
  20.     while (b != 0)
  21.     {
  22.         q = a / b;
  23.         r = a % b;
  24.         tmp = x; x = *lastx - q * x; *lastx = tmp;
  25.         tmp = y; y = *lasty - q * y; *lasty = tmp;
  26.         a = b; b = r;
  27.     }
  28. }
  29.  
  30. class ReversibleLCG {
  31.     int64_t x;
  32.     int64_t a;
  33.     int64_t m;
  34.     int64_t c;
  35.     int64_t ainverse;
  36. public:
  37.     ReversibleLCG(int seed) : x(seed), a(1103515245), m(1u<<31u), c(12345)
  38.     {
  39.         int64_t x, q;
  40.         ext_euclid(a, m, &x, &q);
  41.         ainverse =  mod(x, int64_t(m));
  42.     }
  43.     unsigned int next()
  44.     {
  45.         return x = (a*x + c) % m;
  46.     }    
  47.     unsigned int prev()
  48.     {
  49.         return x= (ainverse*mod(x - c, m)) % m;
  50.     } 
  51. };
  52.  
  53. int main()
  54. {
  55.     ReversibleLCG rng(42);
  56.     std::cout << "forward:\n";
  57.     for(int i = 0;i<5;++i)
  58.         std::cout << rng.next() << std::endl;
  59.     std::cout << "\nbackward:\n";
  60.     for(int i = 0;i<5;++i)
  61.         std::cout << rng.prev() << std::endl;
  62. }
Success #stdin #stdout 0s 2852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
forward:
1250496027
1116302264
1000676753
1668674806
908095735

backward:
1668674806
1000676753
1116302264
1250496027
42
https://ideone.com/gPbDte
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!