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)54boost::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