ceph/src/boost/libs/multiprecision/performance/rational_determinant_bench.cpp

   1 //  Copyright 2020 John Maddock. Distributed under the Boost
   2 //  Software License, Version 1.0. (See accompanying file
   3 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
   4
   5 #include <iostream>
   6 #include <vector>
   7 #include <benchmark/benchmark.h>
   8 #include <boost/multiprecision/cpp_int.hpp>
   9 #include <boost/multiprecision/gmp.hpp>
  10
  11 #include <boost/math/special_functions/prime.hpp>
  12 #include <boost/math/special_functions/pow.hpp>
  13
  14 #include <gmpxx.h>
  15
  16 #include <boost/random/mersenne_twister.hpp>
  17 #include <boost/random/uniform_int.hpp>
  18
  19 template <class T>
  20 T generate_random(unsigned bits_wanted)
  21 {
  22    static boost::random::mt19937               gen;
  23    typedef boost::random::mt19937::result_type random_type;
  24
  25    T        max_val;
  26    unsigned digits;
  27    if (std::numeric_limits<T>::is_bounded && (bits_wanted == (unsigned)std::numeric_limits<T>::digits))
  28    {
  29       max_val = (std::numeric_limits<T>::max)();
  30       digits  = std::numeric_limits<T>::digits;
  31    }
  32    else
  33    {
  34       max_val = T(1) << bits_wanted;
  35       digits  = bits_wanted;
  36    }
  37
  38    unsigned bits_per_r_val = std::numeric_limits<random_type>::digits - 1;
  39    while ((random_type(1) << bits_per_r_val) > (gen.max)())
  40       --bits_per_r_val;
  41
  42    unsigned terms_needed = digits / bits_per_r_val + 1;
  43
  44    T val = 0;
  45    for (unsigned i = 0; i < terms_needed; ++i)
  46    {
  47       val *= (gen.max)();
  48       val += gen();
  49    }
  50    val %= max_val;
  51    return val;
  52 }
  53
  54 template <class T>
  55 const std::vector<std::vector<T> >& get_matrix_data(unsigned bits);
  56
  57 template <>
  58 const std::vector<std::vector<boost::multiprecision::cpp_rational> >& get_matrix_data(unsigned bits)
  59 {
  60    static std::map<unsigned, std::vector<std::vector<boost::multiprecision::cpp_rational> > > data;
  61    if (data[bits].size() == 0)
  62    {
  63       for (unsigned i = 0; i < 100; ++i)
  64       {
  65          std::vector<boost::multiprecision::cpp_rational> matrix;
  66          for (unsigned j = 0; j < 9; ++j)
  67          {
  68             boost::multiprecision::cpp_int a(generate_random<boost::multiprecision::cpp_int>(bits)), b(generate_random<boost::multiprecision::cpp_int>(bits));
  69             matrix.push_back(boost::multiprecision::cpp_rational(a, b));
  70          }
  71          data[bits].push_back(matrix);
  72       }
  73    }
  74    return data[bits];
  75 }
  76
  77 template <class T>
  78 const std::vector<std::vector<T> >& get_matrix_data(unsigned bits)
  79 {
  80    static std::map<unsigned, std::vector<std::vector<T> > > data;
  81    if (data[bits].empty())
  82    {
  83       const std::vector<std::vector<boost::multiprecision::cpp_rational> >& d = get_matrix_data<boost::multiprecision::cpp_rational>(bits);
  84       for (unsigned i = 0; i < 100; ++i)
  85       {
  86          std::vector<T> matrix;
  87          for (unsigned j = 0; j < 9; ++j)
  88          {
  89             matrix.push_back(T(d[i][j].str()));
  90          }
  91          data[bits].push_back(matrix);
  92       }
  93    }
  94    return data[bits];
  95 }
  96
  97 template <class T>
  98 T determinant(const std::vector<T>& data)
  99 {
 100    const T m01 = data[0] * data[4] - data[3] * data[1];
 101    const T m02 = data[0] * data[7] - data[6] * data[1];
 102    const T m12 = data[3] * data[7] - data[6] * data[4];
 103    return m01 * data[8] - m02 * data[5] + m12 * data[2];
 104 }
 105
 106 template <class Rational>
 107 static void BM_determinant(benchmark::State& state)
 108 {
 109    int                         bits = state.range(0);
 110    const std::vector<std::vector<Rational> >& data = get_matrix_data<Rational>(bits);
 111    for (auto _ : state)
 112    {
 113       for(unsigned i = 0; i < data.size(); ++i)
 114          benchmark::DoNotOptimize(determinant(data[i]));
 115    }
 116 }
 117
 118
 119 constexpr unsigned lower_range = 512;
 120 constexpr unsigned upper_range = 1 << 15;
 121
 122 BENCHMARK_TEMPLATE(BM_determinant, boost::multiprecision::cpp_rational)->RangeMultiplier(2)->Range(lower_range, upper_range)->Unit(benchmark::kMillisecond);
 123 BENCHMARK_TEMPLATE(BM_determinant, boost::multiprecision::mpq_rational)->RangeMultiplier(2)->Range(lower_range, upper_range)->Unit(benchmark::kMillisecond);
 124 BENCHMARK_TEMPLATE(BM_determinant, mpq_class)->RangeMultiplier(2)->Range(lower_range, upper_range)->Unit(benchmark::kMillisecond);
 125
 126 BENCHMARK_MAIN();