samedi 15 août 2015

Why is Mersenne twister faster than the linear congruential generator?

I tested with the gcc C++ standard library's Mersenne twister implementation. It outperforms both the linear congruential generator and the C rand, which is most likely an LCG. A boost documentation also seems to give a similar result, but favoring Mersenne twister even more. Can anyone explain this?

#include <cstdlib>
#include <iostream>
#include <chrono>
#include <random>

class Timer
{
private:
  std::chrono::high_resolution_clock::time_point start_time;
  std::chrono::high_resolution_clock::time_point stop_time;

public:
  void start()
  {
    start_time = std::chrono::high_resolution_clock::now();
  }

  void stop()
  {
    stop_time = std::chrono::high_resolution_clock::now();
  }

  double measure()
  {
    using namespace std::chrono;
    return duration_cast<microseconds>
    (stop_time - start_time).count() / 1000000.0;
  }
};

template<typename T>
class Random
{
private:
  T generator;

public:
  Random()
  : generator
  (std::chrono::high_resolution_clock::now().time_since_epoch().count())
  {
  }

  int generate_integer(int begin, int end)
  {
    return std::uniform_int_distribution<int>(begin, end + 1)(generator);
  }
};

int main()
{
  constexpr int n = 300000000;
  Random<std::minstd_rand> mr;
  Random<std::mt19937> mt;
  Timer t;
  for (int j = 0; j < 3; ++j)
  {
    t.start();
    for (int i = 0; i < n; ++i)
    {
      static_cast<volatile void>(mr.generate_integer(0, 10));
    }
    t.stop();
    std::cout << "minstd " << t.measure() << std::endl;
    t.start();
    for (int i = 0; i < n; ++i)
    {
      static_cast<volatile void>(mt.generate_integer(0, 10));
    }
    t.stop();
    std::cout << "mersenne " << t.measure() << std::endl;
    t.start();
    for (int i = 0; i < n; ++i)
    {
      static_cast<volatile void>(std::rand() % 10);
    }
    t.stop();
    std::cout << "rand " << t.measure() << std::endl;
  }
}

result

minstd 4.70876
mersenne 1.55853
rand 4.11873
minstd 4.53199
mersenne 1.55928
rand 4.15159
minstd 4.5374
mersenne 1.55667
rand 4.13715




Aucun commentaire:

Enregistrer un commentaire