123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166 |
- ///////////////////////////////////////////////////////////////
- // Copyright 2012 John Maddock. Distributed under the Boost
- // Software License, Version 1.0. (See accompanying file
- // LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
- #define BOOST_CHRONO_HEADER_ONLY
- #if !defined(TEST_MPZ) && !defined(TEST_TOMMATH) && !defined(TEST_CPP_INT)
- #define TEST_MPZ
- #define TEST_TOMMATH
- #define TEST_CPP_INT
- #endif
- #ifdef TEST_MPZ
- #include <boost/multiprecision/gmp.hpp>
- #endif
- #ifdef TEST_TOMMATH
- #include <boost/multiprecision/tommath.hpp>
- #endif
- #ifdef TEST_CPP_INT
- #include <boost/multiprecision/cpp_int.hpp>
- #endif
- #include <boost/multiprecision/miller_rabin.hpp>
- #include <boost/chrono.hpp>
- #include <map>
- template <class Clock>
- struct stopwatch
- {
- typedef typename Clock::duration duration;
- stopwatch()
- {
- m_start = Clock::now();
- }
- duration elapsed()
- {
- return Clock::now() - m_start;
- }
- void reset()
- {
- m_start = Clock::now();
- }
- private:
- typename Clock::time_point m_start;
- };
- unsigned allocation_count = 0;
- void* (*alloc_func_ptr)(size_t);
- void* (*realloc_func_ptr)(void*, size_t, size_t);
- void (*free_func_ptr)(void*, size_t);
- void* alloc_func(size_t n)
- {
- ++allocation_count;
- return (*alloc_func_ptr)(n);
- }
- void free_func(void* p, size_t n)
- {
- (*free_func_ptr)(p, n);
- }
- void* realloc_func(void* p, size_t old, size_t n)
- {
- ++allocation_count;
- return (*realloc_func_ptr)(p, old, n);
- }
- #ifdef TEST_MPZ
- boost::chrono::duration<double> test_miller_rabin_gmp()
- {
- using namespace boost::random;
- using namespace boost::multiprecision;
- stopwatch<boost::chrono::high_resolution_clock> c;
- independent_bits_engine<mt11213b, 256, mpz_int> gen;
- for (unsigned i = 0; i < 1000; ++i)
- {
- mpz_int n = gen();
- mpz_probab_prime_p(n.backend().data(), 25);
- }
- return c.elapsed();
- }
- #endif
- std::map<std::string, double> results;
- double min_time = (std::numeric_limits<double>::max)();
- template <class IntType>
- boost::chrono::duration<double> test_miller_rabin(const char* name)
- {
- using namespace boost::random;
- stopwatch<boost::chrono::high_resolution_clock> c;
- independent_bits_engine<mt11213b, 256, IntType> gen;
- //
- // We must use a different generator for the tests and number generation, otherwise
- // we get false positives.
- //
- mt19937 gen2;
- unsigned result_count = 0;
- for (unsigned i = 0; i < 1000; ++i)
- {
- IntType n = gen();
- if (boost::multiprecision::miller_rabin_test(n, 25, gen2))
- ++result_count;
- }
- boost::chrono::duration<double> t = c.elapsed();
- double d = t.count();
- if (d < min_time)
- min_time = d;
- results[name] = d;
- std::cout << "Time for " << std::setw(30) << std::left << name << " = " << d << std::endl;
- std::cout << "Number of primes found = " << result_count << std::endl;
- return t;
- }
- void generate_quickbook()
- {
- std::cout << "[table\n[[Integer Type][Relative Performance (Actual time in parenthesis)]]\n";
- std::map<std::string, double>::const_iterator i(results.begin()), j(results.end());
- while (i != j)
- {
- double rel = i->second / min_time;
- std::cout << "[[" << i->first << "][" << rel << "(" << i->second << "s)]]\n";
- ++i;
- }
- std::cout << "]\n";
- }
- int main()
- {
- using namespace boost::multiprecision;
- #ifdef TEST_CPP_INT
- test_miller_rabin<number<cpp_int_backend<>, et_off> >("cpp_int (no Expression templates)");
- test_miller_rabin<cpp_int>("cpp_int");
- test_miller_rabin<number<cpp_int_backend<128> > >("cpp_int (128-bit cache)");
- test_miller_rabin<number<cpp_int_backend<256> > >("cpp_int (256-bit cache)");
- test_miller_rabin<number<cpp_int_backend<512> > >("cpp_int (512-bit cache)");
- test_miller_rabin<number<cpp_int_backend<1024> > >("cpp_int (1024-bit cache)");
- test_miller_rabin<int1024_t>("int1024_t");
- test_miller_rabin<checked_int1024_t>("checked_int1024_t");
- #endif
- #ifdef TEST_MPZ
- test_miller_rabin<number<gmp_int, et_off> >("mpz_int (no Expression templates)");
- test_miller_rabin<mpz_int>("mpz_int");
- std::cout << "Time for mpz_int (native Miller Rabin Test) = " << test_miller_rabin_gmp() << std::endl;
- #endif
- #ifdef TEST_TOMMATH
- test_miller_rabin<number<boost::multiprecision::tommath_int, et_off> >("tom_int (no Expression templates)");
- test_miller_rabin<boost::multiprecision::tom_int>("tom_int");
- #endif
- generate_quickbook();
- return 0;
- }
|