ceph/src/boost/libs/multiprecision/performance/miller_rabin_performance.hpp

   1 ///////////////////////////////////////////////////////////////
   2 //  Copyright 2012 John Maddock. Distributed under the Boost
   3 //  Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
   5
   6 #define BOOST_CHRONO_HEADER_ONLY
   7
   8 #if !defined(TEST_MPZ) && !defined(TEST_TOMMATH) && !defined(TEST_CPP_INT)
   9 #define TEST_MPZ
  10 #define TEST_TOMMATH
  11 #define TEST_CPP_INT
  12 #endif
  13
  14 #ifdef TEST_MPZ
  15 #include <boost/multiprecision/gmp.hpp>
  16 #endif
  17 #ifdef TEST_TOMMATH
  18 #include <boost/multiprecision/tommath.hpp>
  19 #endif
  20 #ifdef TEST_CPP_INT
  21 #include <boost/multiprecision/cpp_int.hpp>
  22 #endif
  23 #include <boost/multiprecision/miller_rabin.hpp>
  24 #include <boost/chrono.hpp>
  25 #include <boost/random.hpp>
  26 #include <map>
  27
  28 template <class Clock>
  29 struct stopwatch
  30 {
  31    typedef typename Clock::duration duration;
  32    stopwatch()
  33    {
  34       m_start = Clock::now();
  35    }
  36    duration elapsed()
  37    {
  38       return Clock::now() - m_start;
  39    }
  40    void reset()
  41    {
  42       m_start = Clock::now();
  43    }
  44
  45  private:
  46    typename Clock::time_point m_start;
  47 };
  48
  49 extern unsigned allocation_count;
  50
  51 extern std::map<std::string, double> results;
  52 extern double                        min_time;
  53
  54 template <class IntType>
  55 boost::chrono::duration<double> test_miller_rabin(const char* name)
  56 {
  57    using namespace boost::random;
  58
  59    stopwatch<boost::chrono::high_resolution_clock> c;
  60
  61    independent_bits_engine<mt11213b, 256, IntType> gen;
  62    //
  63    // We must use a different generator for the tests and number generation, otherwise
  64    // we get false positives.
  65    //
  66    mt19937  gen2;
  67    unsigned result_count = 0;
  68
  69    for (unsigned i = 0; i < 1000; ++i)
  70    {
  71       IntType n = gen();
  72       if (boost::multiprecision::miller_rabin_test(n, 25, gen2))
  73          ++result_count;
  74    }
  75    boost::chrono::duration<double> t = c.elapsed();
  76    double                          d = t.count();
  77    if (d < min_time)
  78       min_time = d;
  79    results[name] = d;
  80    std::cout << "Time for " << std::setw(30) << std::left << name << " = " << d << std::endl;
  81    std::cout << "Number of primes found = " << result_count << std::endl;
  82    return t;
  83 }
  84
  85 boost::chrono::duration<double> test_miller_rabin_gmp();
  86
  87 void test01();
  88 void test02();
  89 void test03();
  90 void test04();
  91 void test05();
  92 void test06();
  93 void test07();
  94 void test08();
  95 void test09();
  96 void test10();
  97 void test11();
  98 void test12();
  99 void test13();
 100 void test14();
 101 void test15();
 102 void test16();
 103 void test17();
 104 void test18();
 105 void test19();