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 <map>
26 
27 template <class Clock>
28 struct stopwatch
29 {
30    typedef typename Clock::duration duration;
stopwatchstopwatch31    stopwatch()
32    {
33       m_start = Clock::now();
34    }
elapsedstopwatch35    duration elapsed()
36    {
37       return Clock::now() - m_start;
38    }
resetstopwatch39    void reset()
40    {
41       m_start = Clock::now();
42    }
43 
44  private:
45    typename Clock::time_point m_start;
46 };
47 
48 extern unsigned allocation_count;
49 
50 extern std::map<std::string, double> results;
51 extern double                        min_time;
52 
53 template <class IntType>
test_miller_rabin(const char * name)54 boost::chrono::duration<double> test_miller_rabin(const char* name)
55 {
56    using namespace boost::random;
57 
58    stopwatch<boost::chrono::high_resolution_clock> c;
59 
60    independent_bits_engine<mt11213b, 256, IntType> gen;
61    //
62    // We must use a different generator for the tests and number generation, otherwise
63    // we get false positives.
64    //
65    mt19937  gen2;
66    unsigned result_count = 0;
67 
68    for (unsigned i = 0; i < 1000; ++i)
69    {
70       IntType n = gen();
71       if (boost::multiprecision::miller_rabin_test(n, 25, gen2))
72          ++result_count;
73    }
74    boost::chrono::duration<double> t = c.elapsed();
75    double                          d = t.count();
76    if (d < min_time)
77       min_time = d;
78    results[name] = d;
79    std::cout << "Time for " << std::setw(30) << std::left << name << " = " << d << std::endl;
80    std::cout << "Number of primes found = " << result_count << std::endl;
81    return t;
82 }
83 
84 boost::chrono::duration<double> test_miller_rabin_gmp();
85 
86 void test01();
87 void test02();
88 void test03();
89 void test04();
90 void test05();
91 void test06();
92 void test07();
93 void test08();
94 void test09();
95 void test10();
96 void test11();
97 void test12();
98 void test13();
99 void test14();
100 void test15();
101 void test16();
102 void test17();
103 void test18();
104 void test19();
105