ceph/src/boost/libs/multiprecision/test/test_cpp_int_karatsuba.cpp

   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 //
   7 // Compare arithmetic results using fixed_int to GMP results.
   8 //
   9
  10 #ifdef _MSC_VER
  11 #define _SCL_SECURE_NO_WARNINGS
  12 #endif
  13
  14 //
  15 // This ensures all our code gets tested, even though it may
  16 // not be the fastest configuration in normal use:
  17 //
  18 #define BOOST_MP_USE_LIMB_SHIFT
  19
  20 #include <boost/multiprecision/gmp.hpp>
  21 #include <boost/multiprecision/cpp_int.hpp>
  22 #include <boost/random/mersenne_twister.hpp>
  23 #include <boost/random/uniform_int.hpp>
  24 #include <boost/timer.hpp>
  25 #include "test.hpp"
  26
  27 #ifdef _MSC_VER
  28 #pragma warning(disable : 4127) //  Conditional expression is constant
  29 #endif
  30
  31 #ifndef TEST
  32 #define TEST 0
  33 #endif
  34
  35 template <class T>
  36 T generate_random(unsigned bits_wanted)
  37 {
  38    static boost::random::mt19937               gen;
  39    typedef boost::random::mt19937::result_type random_type;
  40
  41    T        max_val;
  42    unsigned digits;
  43    if (std::numeric_limits<T>::is_bounded && (bits_wanted == (unsigned)std::numeric_limits<T>::digits))
  44    {
  45       max_val = (std::numeric_limits<T>::max)();
  46       digits  = std::numeric_limits<T>::digits;
  47    }
  48    else
  49    {
  50       max_val = T(1) << bits_wanted;
  51       digits  = bits_wanted;
  52    }
  53
  54    unsigned bits_per_r_val = std::numeric_limits<random_type>::digits - 1;
  55    while ((random_type(1) << bits_per_r_val) > (gen.max)())
  56       --bits_per_r_val;
  57
  58    unsigned terms_needed = digits / bits_per_r_val + 1;
  59
  60    T val = 0;
  61    for (unsigned i = 0; i < terms_needed; ++i)
  62    {
  63       val *= (gen.max)();
  64       val += gen();
  65    }
  66    val %= max_val;
  67    return val;
  68 }
  69
  70 template <class T>
  71 struct is_checked_cpp_int : public boost::mpl::false_
  72 {};
  73 template <unsigned MinBits, unsigned MaxBits, boost::multiprecision::cpp_integer_type SignType, class Allocator, boost::multiprecision::expression_template_option ET>
  74 struct is_checked_cpp_int<boost::multiprecision::number<boost::multiprecision::cpp_int_backend<MinBits, MaxBits, SignType, boost::multiprecision::checked, Allocator>, ET> > : public boost::mpl::true_
  75 {};
  76
  77 template <class N>
  78 typename boost::enable_if_c<boost::multiprecision::backends::is_fixed_precision<typename N::backend_type>::value && !is_checked_cpp_int<N>::value>::type test(const N&)
  79 {
  80    using namespace boost::multiprecision;
  81
  82    static unsigned last_error_count = 0;
  83
  84    boost::timer tim;
  85
  86    do
  87    {
  88       // Test modular arithmetic by filling all the bits of our test type:
  89       mpz_int f = generate_random<mpz_int>(std::numeric_limits<N>::digits + 2);
  90       mpz_int g = generate_random<mpz_int>(std::numeric_limits<N>::digits + 2);
  91       mpz_int mask(1);
  92       mask <<= std::numeric_limits<N>::digits;
  93       --mask;
  94       f &= mask;
  95       g &= mask;
  96       mpz_int r = (f * g) & mask;
  97
  98       N f1(f);
  99       N g1(g);
 100       N r1 = f1 * g1;
 101       BOOST_CHECK_EQUAL(r1.str(), r.str());
 102
 103       if (last_error_count != (unsigned)boost::detail::test_errors())
 104       {
 105          last_error_count = boost::detail::test_errors();
 106          std::cout << std::hex << std::showbase;
 107          std::cout << f1 << std::endl;
 108          std::cout << f << std::endl;
 109          std::cout << g1 << std::endl;
 110          std::cout << g << std::endl;
 111          std::cout << r1 << std::endl;
 112          std::cout << r << std::endl;
 113       }
 114
 115       static boost::random::mt19937             gen;
 116       boost::random::uniform_int_distribution<> d(12, std::numeric_limits<N>::digits);
 117       f = generate_random<mpz_int>(d(gen));
 118       g = generate_random<mpz_int>(d(gen));
 119       r = (f * g) & mask;
 120
 121       f1 = N(f);
 122       g1 = N(g);
 123       r1 = f1 * g1;
 124       BOOST_CHECK_EQUAL(r1.str(), r.str());
 125
 126       if (last_error_count != (unsigned)boost::detail::test_errors())
 127       {
 128          last_error_count = boost::detail::test_errors();
 129          std::cout << std::hex << std::showbase;
 130          std::cout << f1 << std::endl;
 131          std::cout << f << std::endl;
 132          std::cout << g1 << std::endl;
 133          std::cout << g << std::endl;
 134          std::cout << r1 << std::endl;
 135          std::cout << r << std::endl;
 136       }
 137
 138 #ifndef CI_SUPPRESS_KNOWN_ISSUES
 139       if (tim.elapsed() > 200)
 140 #else
 141       if (tim.elapsed() > 25)
 142 #endif
 143       {
 144          std::cout << "Timeout reached, aborting tests now....\n";
 145          break;
 146       }
 147
 148    } while (true);
 149    //
 150    // Special cases:
 151    //
 152    mpz_int mask;
 153    if (std::numeric_limits<N>::is_bounded)
 154       mask = mpz_int((std::numeric_limits<N>::max)());
 155    mpz_int a, b;
 156    N       x, y;
 157
 158    unsigned upper_limit = std::numeric_limits<N>::is_bounded ? std::numeric_limits<N>::digits - 1 : 8192 * 2;
 159    for (unsigned i = 1024; i < upper_limit; i *= 2)
 160    {
 161       a = 1;
 162       a <<= i;
 163       --a;
 164       x = 1;
 165       x <<= i;
 166       --x;
 167
 168       b = a * a;
 169       if (std::numeric_limits<N>::is_bounded)
 170          b &= mask;
 171       y = x * x;
 172
 173       BOOST_CHECK_EQUAL(y.str(), b.str());
 174
 175       if (last_error_count != (unsigned)boost::detail::test_errors())
 176       {
 177          last_error_count = boost::detail::test_errors();
 178          std::cout << std::hex << std::showbase;
 179          std::cout << a << std::endl;
 180          std::cout << x << std::endl;
 181          std::cout << b << std::endl;
 182          std::cout << y << std::endl;
 183       }
 184    }
 185 }
 186 template <class N>
 187 typename boost::disable_if_c<boost::multiprecision::backends::is_fixed_precision<typename N::backend_type>::value && !is_checked_cpp_int<N>::value>::type test(const N&)
 188 {
 189    using namespace boost::multiprecision;
 190
 191    static unsigned last_error_count = 0;
 192
 193    boost::timer tim;
 194
 195    mpz_int mask;
 196    if (std::numeric_limits<N>::is_bounded)
 197       mask = mpz_int((std::numeric_limits<N>::max)());
 198    do
 199    {
 200       // Test modular arithmetic by filling all the bits of our test type:
 201       static boost::random::mt19937             gen;
 202       boost::random::uniform_int_distribution<> d(12, std::numeric_limits<N>::is_bounded ? std::numeric_limits<N>::digits : 100000);
 203       mpz_int                                   f = generate_random<mpz_int>(d(gen));
 204       mpz_int                                   g = generate_random<mpz_int>(d(gen));
 205       mpz_int                                   r = f * g;
 206       if (std::numeric_limits<N>::is_bounded)
 207          r &= mask;
 208
 209       N f1(f);
 210       N g1(g);
 211       N r1 = f1 * g1;
 212       BOOST_CHECK_EQUAL(r1.str(), r.str());
 213
 214       if (last_error_count != (unsigned)boost::detail::test_errors())
 215       {
 216          last_error_count = boost::detail::test_errors();
 217          std::cout << std::hex << std::showbase;
 218          std::cout << f1 << std::endl;
 219          std::cout << f << std::endl;
 220          std::cout << g1 << std::endl;
 221          std::cout << g << std::endl;
 222          std::cout << r1 << std::endl;
 223          std::cout << r << std::endl;
 224       }
 225
 226 #ifndef CI_SUPPRESS_KNOWN_ISSUES
 227       if (tim.elapsed() > 200)
 228 #else
 229       if (tim.elapsed() > 25)
 230 #endif
 231       {
 232          std::cout << "Timeout reached, aborting tests now....\n";
 233          break;
 234       }
 235
 236    } while (true);
 237    //
 238    // Special cases:
 239    //
 240    mpz_int a, b;
 241    N       x, y;
 242
 243    unsigned upper_limit = std::numeric_limits<N>::is_bounded ? std::numeric_limits<N>::digits - 1 : 8192 * 2;
 244    for (unsigned i = 1024; i < upper_limit; i *= 2)
 245    {
 246       a = 1;
 247       a <<= i;
 248       --a;
 249       x = 1;
 250       x <<= i;
 251       --x;
 252
 253       b = a * a;
 254       if (std::numeric_limits<N>::is_bounded)
 255          b &= mask;
 256       y = x * x;
 257
 258       BOOST_CHECK_EQUAL(y.str(), b.str());
 259
 260       if (last_error_count != (unsigned)boost::detail::test_errors())
 261       {
 262          last_error_count = boost::detail::test_errors();
 263          std::cout << std::hex << std::showbase;
 264          std::cout << a << std::endl;
 265          std::cout << x << std::endl;
 266          std::cout << b << std::endl;
 267          std::cout << y << std::endl;
 268       }
 269    }
 270 }
 271
 272 int main()
 273 {
 274    using namespace boost::multiprecision;
 275
 276 #if (TEST == 1) || (TEST == 0)
 277    test(cpp_int());
 278 #endif
 279 #if (TEST == 2) || (TEST == 0)
 280    test(number<cpp_int_backend<8192, 8192, signed_magnitude, unchecked, void> >());
 281 #endif
 282 #if (TEST == 3) || (TEST == 0)
 283    test(number<cpp_int_backend<8192, 8192, signed_magnitude, unchecked, std::allocator<char> > >());
 284 #endif
 285 #if (TEST == 4) || (TEST == 0)
 286    test(number<cpp_int_backend<8192, 8192, unsigned_magnitude, unchecked> >());
 287 #endif
 288    return boost::report_errors();
 289 }