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
6 #define BOOST_CHRONO_HEADER_ONLY
8 #if !defined(TEST_MPZ) && !defined(TEST_TOMMATH) && !defined(TEST_CPP_INT)
15 #include <boost/multiprecision/gmp.hpp>
18 #include <boost/multiprecision/tommath.hpp>
21 #include <boost/multiprecision/cpp_int.hpp>
23 #include <boost/multiprecision/miller_rabin.hpp>
24 #include <boost/chrono.hpp>
27 template <class Clock>
30 typedef typename Clock::duration duration;
33 m_start = Clock::now();
37 return Clock::now() - m_start;
41 m_start = Clock::now();
45 typename Clock::time_point m_start;
48 unsigned allocation_count = 0;
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);
54 void* alloc_func(size_t n)
57 return (*alloc_func_ptr)(n);
60 void free_func(void* p, size_t n)
62 (*free_func_ptr)(p, n);
65 void* realloc_func(void* p, size_t old, size_t n)
68 return (*realloc_func_ptr)(p, old, n);
72 boost::chrono::duration<double> test_miller_rabin_gmp()
74 using namespace boost::random;
75 using namespace boost::multiprecision;
77 stopwatch<boost::chrono::high_resolution_clock> c;
79 independent_bits_engine<mt11213b, 256, mpz_int> gen;
81 for (unsigned i = 0; i < 1000; ++i)
84 mpz_probab_prime_p(n.backend().data(), 25);
90 std::map<std::string, double> results;
91 double min_time = (std::numeric_limits<double>::max)();
93 template <class IntType>
94 boost::chrono::duration<double> test_miller_rabin(const char* name)
96 using namespace boost::random;
98 stopwatch<boost::chrono::high_resolution_clock> c;
100 independent_bits_engine<mt11213b, 256, IntType> gen;
102 // We must use a different generator for the tests and number generation, otherwise
103 // we get false positives.
106 unsigned result_count = 0;
108 for (unsigned i = 0; i < 1000; ++i)
111 if (boost::multiprecision::miller_rabin_test(n, 25, gen2))
114 boost::chrono::duration<double> t = c.elapsed();
115 double d = t.count();
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;
124 void generate_quickbook()
126 std::cout << "[table\n[[Integer Type][Relative Performance (Actual time in parenthesis)]]\n";
128 std::map<std::string, double>::const_iterator i(results.begin()), j(results.end());
132 double rel = i->second / min_time;
133 std::cout << "[[" << i->first << "][" << rel << "(" << i->second << "s)]]\n";
142 using namespace boost::multiprecision;
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");
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;
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");
163 generate_quickbook();