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 http://www.boost.org/LICENSE_1_
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 unsigned allocation_count = 0;
49
50 void *(*alloc_func_ptr) (size_t);
51 void *(*realloc_func_ptr) (void *, size_t, size_t);
52 void (*free_func_ptr) (void *, size_t);
53
alloc_func(size_t n)54 void *alloc_func(size_t n)
55 {
56 ++allocation_count;
57 return (*alloc_func_ptr)(n);
58 }
59
free_func(void * p,size_t n)60 void free_func(void * p, size_t n)
61 {
62 (*free_func_ptr)(p, n);
63 }
64
realloc_func(void * p,size_t old,size_t n)65 void * realloc_func(void * p, size_t old, size_t n)
66 {
67 ++allocation_count;
68 return (*realloc_func_ptr)(p, old, n);
69 }
70
71 #ifdef TEST_MPZ
test_miller_rabin_gmp()72 boost::chrono::duration<double> test_miller_rabin_gmp()
73 {
74 using namespace boost::random;
75 using namespace boost::multiprecision;
76
77 stopwatch<boost::chrono::high_resolution_clock> c;
78
79 independent_bits_engine<mt11213b, 256, mpz_int> gen;
80
81 for(unsigned i = 0; i < 1000; ++i)
82 {
83 mpz_int n = gen();
84 mpz_probab_prime_p(n.backend().data(), 25);
85 }
86 return c.elapsed();
87 }
88 #endif
89
90 std::map<std::string, double> results;
91 double min_time = (std::numeric_limits<double>::max)();
92
93 template <class IntType>
test_miller_rabin(const char * name)94 boost::chrono::duration<double> test_miller_rabin(const char* name)
95 {
96 using namespace boost::random;
97
98 stopwatch<boost::chrono::high_resolution_clock> c;
99
100 independent_bits_engine<mt11213b, 256, IntType> gen;
101 //
102 // We must use a different generator for the tests and number generation, otherwise
103 // we get false positives.
104 //
105 mt19937 gen2;
106 unsigned result_count = 0;
107
108 for(unsigned i = 0; i < 1000; ++i)
109 {
110 IntType n = gen();
111 if(boost::multiprecision::miller_rabin_test(n, 25, gen2))
112 ++result_count;
113 }
114 boost::chrono::duration<double> t = c.elapsed();
115 double d = t.count();
116 if(d < min_time)
117 min_time = d;
118 results[name] = d;
119 std::cout << "Time for " << std::setw(30) << std::left << name << " = " << d << std::endl;
120 std::cout << "Number of primes found = " << result_count << std::endl;
121 return t;
122 }
123
generate_quickbook()124 void generate_quickbook()
125 {
126 std::cout << "[table\n[[Integer Type][Relative Performance (Actual time in parenthesis)]]\n";
127
128 std::map<std::string, double>::const_iterator i(results.begin()), j(results.end());
129
130 while(i != j)
131 {
132 double rel = i->second / min_time;
133 std::cout << "[[" << i->first << "][" << rel << "(" << i->second << "s)]]\n";
134 ++i;
135 }
136
137 std::cout << "]\n";
138 }
139
main()140 int main()
141 {
142 using namespace boost::multiprecision;
143 #ifdef TEST_CPP_INT
144 test_miller_rabin<number<cpp_int_backend<>, et_off> >("cpp_int (no Expression templates)");
145 test_miller_rabin<cpp_int>("cpp_int");
146 test_miller_rabin<number<cpp_int_backend<128> > >("cpp_int (128-bit cache)");
147 test_miller_rabin<number<cpp_int_backend<256> > >("cpp_int (256-bit cache)");
148 test_miller_rabin<number<cpp_int_backend<512> > >("cpp_int (512-bit cache)");
149 test_miller_rabin<number<cpp_int_backend<1024> > >("cpp_int (1024-bit cache)");
150 test_miller_rabin<int1024_t>("int1024_t");
151 test_miller_rabin<checked_int1024_t>("checked_int1024_t");
152 #endif
153 #ifdef TEST_MPZ
154 test_miller_rabin<number<gmp_int, et_off> >("mpz_int (no Expression templates)");
155 test_miller_rabin<mpz_int>("mpz_int");
156 std::cout << "Time for mpz_int (native Miller Rabin Test) = " << test_miller_rabin_gmp() << std::endl;
157 #endif
158 #ifdef TEST_TOMMATH
159 test_miller_rabin<number<boost::multiprecision::tommath_int, et_off> >("tom_int (no Expression templates)");
160 test_miller_rabin<boost::multiprecision::tom_int>("tom_int");
161 #endif
162
163 generate_quickbook();
164
165 return 0;
166 }
167
168