ceph/src/boost/libs/multiprecision/test/test_cpp_int.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 http://www.boost.org/LICENSE_1_
   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 #if !defined(TEST1) && !defined(TEST2) && !defined(TEST3)
  32 #define TEST1
  33 #define TEST2
  34 #define TEST3
  35 #endif
  36
  37 template <class T>
  38 T generate_random(unsigned bits_wanted)
  39 {
  40    static boost::random::mt19937 gen;
  41    typedef boost::random::mt19937::result_type random_type;
  42
  43    T max_val;
  44    unsigned digits;
  45    if(std::numeric_limits<T>::is_bounded && (bits_wanted == (unsigned)std::numeric_limits<T>::digits))
  46    {
  47       max_val = (std::numeric_limits<T>::max)();
  48       digits = std::numeric_limits<T>::digits;
  49    }
  50    else
  51    {
  52       max_val = T(1) << bits_wanted;
  53       digits = bits_wanted;
  54    }
  55
  56    unsigned bits_per_r_val = std::numeric_limits<random_type>::digits - 1;
  57    while((random_type(1) << bits_per_r_val) > (gen.max)()) --bits_per_r_val;
  58
  59    unsigned terms_needed = digits / bits_per_r_val + 1;
  60
  61    T val = 0;
  62    for(unsigned i = 0; i < terms_needed; ++i)
  63    {
  64       val *= (gen.max)();
  65       val += gen();
  66    }
  67    val %= max_val;
  68    return val;
  69 }
  70
  71 template <class T>
  72 struct is_checked_cpp_int : public boost::mpl::false_ {};
  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 template <class Number>
  77 struct tester
  78 {
  79    typedef Number test_type;
  80    typedef typename test_type::backend_type::checked_type checked;
  81
  82    unsigned last_error_count;
  83    boost::timer tim;
  84
  85    boost::multiprecision::mpz_int a, b, c, d;
  86    int si;
  87    unsigned ui;
  88    test_type a1, b1, c1, d1;
  89
  90
  91    void t1()
  92    {
  93       using namespace boost::multiprecision;
  94       BOOST_CHECK_EQUAL(a.str(), a1.str());
  95       BOOST_CHECK_EQUAL(b.str(), b1.str());
  96       BOOST_CHECK_EQUAL(c.str(), c1.str());
  97       BOOST_CHECK_EQUAL(d.str(), d1.str());
  98       BOOST_CHECK_EQUAL(mpz_int(a+b).str(), test_type(a1 + b1).str());
  99       BOOST_CHECK_EQUAL((mpz_int(a)+=b).str(), (test_type(a1) += b1).str());
 100       BOOST_CHECK_EQUAL((mpz_int(b)+=a).str(), (test_type(b1) += a1).str());
 101       BOOST_CHECK_EQUAL(mpz_int(a-b).str(), test_type(a1 - b1).str());
 102       BOOST_CHECK_EQUAL((mpz_int(a)-=b).str(), (test_type(a1) -= b1).str());
 103       BOOST_CHECK_EQUAL(mpz_int(mpz_int(-a)+b).str(), test_type(test_type(-a1) + b1).str());
 104       BOOST_CHECK_EQUAL(mpz_int(mpz_int(-a)-b).str(), test_type(test_type(-a1) - b1).str());
 105       BOOST_CHECK_EQUAL(mpz_int(c * d).str(), test_type(c1 * d1).str());
 106       BOOST_CHECK_EQUAL((mpz_int(c)*=d).str(), (test_type(c1) *= d1).str());
 107       BOOST_CHECK_EQUAL((mpz_int(d)*=c).str(), (test_type(d1) *= c1).str());
 108       BOOST_CHECK_EQUAL(mpz_int(c * -d).str(), test_type(c1 * -d1).str());
 109       BOOST_CHECK_EQUAL(mpz_int(-c * d).str(), test_type(-c1 * d1).str());
 110       BOOST_CHECK_EQUAL((mpz_int(c)*=-d).str(), (test_type(c1) *= -d1).str());
 111       BOOST_CHECK_EQUAL((mpz_int(-d)*=c).str(), (test_type(-d1) *= c1).str());
 112       BOOST_CHECK_EQUAL(mpz_int(b * c).str(), test_type(b1 * c1).str());
 113       BOOST_CHECK_EQUAL(mpz_int(a / b).str(), test_type(a1 / b1).str());
 114       BOOST_CHECK_EQUAL((mpz_int(a)/=b).str(), (test_type(a1) /= b1).str());
 115       BOOST_CHECK_EQUAL(mpz_int(a / -b).str(), test_type(a1 / -b1).str());
 116       BOOST_CHECK_EQUAL(mpz_int(-a / b).str(), test_type(-a1 / b1).str());
 117       BOOST_CHECK_EQUAL((mpz_int(a)/=-b).str(), (test_type(a1) /= -b1).str());
 118       BOOST_CHECK_EQUAL((mpz_int(-a)/=b).str(), (test_type(-a1) /= b1).str());
 119       BOOST_CHECK_EQUAL(mpz_int(a / d).str(), test_type(a1 / d1).str());
 120       BOOST_CHECK_EQUAL(mpz_int(a % b).str(), test_type(a1 % b1).str());
 121       BOOST_CHECK_EQUAL((mpz_int(a)%=b).str(), (test_type(a1) %= b1).str());
 122       BOOST_CHECK_EQUAL(mpz_int(a % -b).str(), test_type(a1 % -b1).str());
 123       BOOST_CHECK_EQUAL((mpz_int(a)%=-b).str(), (test_type(a1) %= -b1).str());
 124       BOOST_CHECK_EQUAL(mpz_int(-a % b).str(), test_type(-a1 % b1).str());
 125       BOOST_CHECK_EQUAL((mpz_int(-a)%=b).str(), (test_type(-a1) %= b1).str());
 126       BOOST_CHECK_EQUAL(mpz_int(a % d).str(), test_type(a1 % d1).str());
 127       BOOST_CHECK_EQUAL((mpz_int(a)%=d).str(), (test_type(a1) %= d1).str());
 128
 129       if(!std::numeric_limits<test_type>::is_bounded)
 130       {
 131          test_type p = a1 * b1;
 132          test_type r;
 133          divide_qr(p, b1, p, r);
 134          BOOST_CHECK_EQUAL(p, a1);
 135          BOOST_CHECK_EQUAL(r, test_type(0));
 136
 137          p = a1 * d1;
 138          divide_qr(p, d1, p, r);
 139          BOOST_CHECK_EQUAL(p, a1);
 140          BOOST_CHECK_EQUAL(r, test_type(0));
 141
 142          divide_qr(p, test_type(1), p, r);
 143          BOOST_CHECK_EQUAL(p, a1);
 144          BOOST_CHECK_EQUAL(r, test_type(0));
 145       }
 146    }
 147
 148    void t2()
 149    {
 150       using namespace boost::multiprecision;
 151       // bitwise ops:
 152       BOOST_CHECK_EQUAL(mpz_int(a|b).str(), test_type(a1 | b1).str());
 153       BOOST_CHECK_EQUAL((mpz_int(a)|=b).str(), (test_type(a1) |= b1).str());
 154       if(!is_checked_cpp_int<test_type>::value)
 155       {
 156          BOOST_CHECK_EQUAL(mpz_int(-a|b).str(), test_type(-a1 | b1).str());
 157          BOOST_CHECK_EQUAL((mpz_int(-a)|=b).str(), (test_type(-a1) |= b1).str());
 158          BOOST_CHECK_EQUAL(mpz_int(a|-b).str(), test_type(a1 | -b1).str());
 159          BOOST_CHECK_EQUAL((mpz_int(a)|=-b).str(), (test_type(a1) |= -b1).str());
 160          BOOST_CHECK_EQUAL(mpz_int(-a|-b).str(), test_type(-a1 | -b1).str());
 161          BOOST_CHECK_EQUAL((mpz_int(-a)|=-b).str(), (test_type(-a1) |= -b1).str());
 162       }
 163       BOOST_CHECK_EQUAL(mpz_int(a&b).str(), test_type(a1 & b1).str());
 164       BOOST_CHECK_EQUAL((mpz_int(a)&=b).str(), (test_type(a1) &= b1).str());
 165       if(!is_checked_cpp_int<test_type>::value)
 166       {
 167          BOOST_CHECK_EQUAL(mpz_int(-a&b).str(), test_type(-a1 & b1).str());
 168          BOOST_CHECK_EQUAL((mpz_int(-a)&=b).str(), (test_type(-a1) &= b1).str());
 169          BOOST_CHECK_EQUAL(mpz_int(a&-b).str(), test_type(a1 & -b1).str());
 170          BOOST_CHECK_EQUAL((mpz_int(a)&=-b).str(), (test_type(a1) &= -b1).str());
 171          BOOST_CHECK_EQUAL(mpz_int(-a&-b).str(), test_type(-a1 & -b1).str());
 172          BOOST_CHECK_EQUAL((mpz_int(-a)&=-b).str(), (test_type(-a1) &= -b1).str());
 173       }
 174       BOOST_CHECK_EQUAL(mpz_int(a^b).str(), test_type(a1 ^ b1).str());
 175       BOOST_CHECK_EQUAL((mpz_int(a)^=b).str(), (test_type(a1) ^= b1).str());
 176       if(!is_checked_cpp_int<test_type>::value)
 177       {
 178          BOOST_CHECK_EQUAL(mpz_int(-a^b).str(), test_type(-a1 ^ b1).str());
 179          BOOST_CHECK_EQUAL((mpz_int(-a)^=b).str(), (test_type(-a1) ^= b1).str());
 180          BOOST_CHECK_EQUAL(mpz_int(a^-b).str(), test_type(a1 ^ -b1).str());
 181          BOOST_CHECK_EQUAL((mpz_int(a)^=-b).str(), (test_type(a1) ^= -b1).str());
 182          BOOST_CHECK_EQUAL(mpz_int(-a^-b).str(), test_type(-a1 ^ -b1).str());
 183          BOOST_CHECK_EQUAL((mpz_int(-a)^=-b).str(), (test_type(-a1) ^= -b1).str());
 184       }
 185       // Shift ops:
 186       for(unsigned i = 0; i < 128; ++i)
 187       {
 188          if(!std::numeric_limits<test_type>::is_bounded)
 189          {
 190             BOOST_CHECK_EQUAL(mpz_int(a << i).str(), test_type(a1 << i).str());
 191             BOOST_CHECK_EQUAL(mpz_int(-a << i).str(), test_type(-a1 << i).str());
 192          }
 193          else if(!is_checked_cpp_int<test_type>::value)
 194          {
 195             test_type t1(mpz_int(a << i).str());
 196             test_type t2 = a1 << i;
 197             BOOST_CHECK_EQUAL(t1, t2);
 198             t1 = test_type(mpz_int(-a << i).str());
 199             t2 = -a1 << i;
 200             BOOST_CHECK_EQUAL(t1, t2);
 201          }
 202          BOOST_CHECK_EQUAL(mpz_int(a >> i).str(), test_type(a1 >> i).str());
 203          if(!is_checked_cpp_int<test_type>::value)
 204          {
 205             BOOST_CHECK_EQUAL(mpz_int(-a >> i).str(), test_type(-a1 >> i).str());
 206          }
 207       }
 208       // gcd/lcm
 209       BOOST_CHECK_EQUAL(mpz_int(gcd(a, b)).str(), test_type(gcd(a1, b1)).str());
 210       BOOST_CHECK_EQUAL(mpz_int(lcm(c, d)).str(), test_type(lcm(c1, d1)).str());
 211       BOOST_CHECK_EQUAL(mpz_int(gcd(-a, b)).str(), test_type(gcd(-a1, b1)).str());
 212       BOOST_CHECK_EQUAL(mpz_int(lcm(-c, d)).str(), test_type(lcm(-c1, d1)).str());
 213       BOOST_CHECK_EQUAL(mpz_int(gcd(-a, -b)).str(), test_type(gcd(-a1, -b1)).str());
 214       BOOST_CHECK_EQUAL(mpz_int(lcm(-c, -d)).str(), test_type(lcm(-c1, -d1)).str());
 215       BOOST_CHECK_EQUAL(mpz_int(gcd(a, -b)).str(), test_type(gcd(a1, -b1)).str());
 216       BOOST_CHECK_EQUAL(mpz_int(lcm(c, -d)).str(), test_type(lcm(c1, -d1)).str());
 217       // Integer sqrt:
 218       mpz_int r;
 219       test_type r1;
 220       BOOST_CHECK_EQUAL(sqrt(a, r).str(), sqrt(a1, r1).str());
 221       BOOST_CHECK_EQUAL(r.str(), r1.str());
 222    }
 223
 224    void t3()
 225    {
 226       using namespace boost::multiprecision;
 227       // Now check operations involving signed integers:
 228       BOOST_CHECK_EQUAL(mpz_int(a + si).str(), test_type(a1 + si).str());
 229       BOOST_CHECK_EQUAL(mpz_int(a + -si).str(), test_type(a1 + -si).str());
 230       BOOST_CHECK_EQUAL(mpz_int(-a + si).str(), test_type(-a1 + si).str());
 231       BOOST_CHECK_EQUAL(mpz_int(si + a).str(), test_type(si + a1).str());
 232       BOOST_CHECK_EQUAL((mpz_int(a)+=si).str(), (test_type(a1) += si).str());
 233       BOOST_CHECK_EQUAL((mpz_int(a)+=-si).str(), (test_type(a1) += -si).str());
 234       BOOST_CHECK_EQUAL((mpz_int(-a)+=si).str(), (test_type(-a1) += si).str());
 235       BOOST_CHECK_EQUAL((mpz_int(-a)+=-si).str(), (test_type(-a1) += -si).str());
 236       BOOST_CHECK_EQUAL(mpz_int(a - si).str(), test_type(a1 - si).str());
 237       BOOST_CHECK_EQUAL(mpz_int(a - -si).str(), test_type(a1 - -si).str());
 238       BOOST_CHECK_EQUAL(mpz_int(-a - si).str(), test_type(-a1 - si).str());
 239       BOOST_CHECK_EQUAL(mpz_int(si - a).str(), test_type(si - a1).str());
 240       BOOST_CHECK_EQUAL((mpz_int(a)-=si).str(), (test_type(a1) -= si).str());
 241       BOOST_CHECK_EQUAL((mpz_int(a)-=-si).str(), (test_type(a1) -= -si).str());
 242       BOOST_CHECK_EQUAL((mpz_int(-a)-=si).str(), (test_type(-a1) -= si).str());
 243       BOOST_CHECK_EQUAL((mpz_int(-a)-=-si).str(), (test_type(-a1) -= -si).str());
 244       BOOST_CHECK_EQUAL(mpz_int(b * si).str(), test_type(b1 * si).str());
 245       BOOST_CHECK_EQUAL(mpz_int(b * -si).str(), test_type(b1 * -si).str());
 246       BOOST_CHECK_EQUAL(mpz_int(-b * si).str(), test_type(-b1 * si).str());
 247       BOOST_CHECK_EQUAL(mpz_int(si * b).str(), test_type(si * b1).str());
 248       BOOST_CHECK_EQUAL((mpz_int(a)*=si).str(), (test_type(a1) *= si).str());
 249       BOOST_CHECK_EQUAL((mpz_int(a)*=-si).str(), (test_type(a1) *= -si).str());
 250       BOOST_CHECK_EQUAL((mpz_int(-a)*=si).str(), (test_type(-a1) *= si).str());
 251       BOOST_CHECK_EQUAL((mpz_int(-a)*=-si).str(), (test_type(-a1) *= -si).str());
 252       BOOST_CHECK_EQUAL(mpz_int(a / si).str(), test_type(a1 / si).str());
 253       BOOST_CHECK_EQUAL(mpz_int(a / -si).str(), test_type(a1 / -si).str());
 254       BOOST_CHECK_EQUAL(mpz_int(-a / si).str(), test_type(-a1 / si).str());
 255       BOOST_CHECK_EQUAL((mpz_int(a)/=si).str(), (test_type(a1) /= si).str());
 256       BOOST_CHECK_EQUAL((mpz_int(a)/=-si).str(), (test_type(a1) /= -si).str());
 257       BOOST_CHECK_EQUAL((mpz_int(-a)/=si).str(), (test_type(-a1) /= si).str());
 258       BOOST_CHECK_EQUAL((mpz_int(-a)/=-si).str(), (test_type(-a1) /= -si).str());
 259       BOOST_CHECK_EQUAL(mpz_int(a % si).str(), test_type(a1 % si).str());
 260       BOOST_CHECK_EQUAL(mpz_int(a % -si).str(), test_type(a1 % -si).str());
 261       BOOST_CHECK_EQUAL(mpz_int(-a % si).str(), test_type(-a1 % si).str());
 262       BOOST_CHECK_EQUAL((mpz_int(a)%=si).str(), (test_type(a1) %= si).str());
 263       BOOST_CHECK_EQUAL((mpz_int(a)%=-si).str(), (test_type(a1) %= -si).str());
 264       BOOST_CHECK_EQUAL((mpz_int(-a)%=si).str(), (test_type(-a1) %= si).str());
 265       BOOST_CHECK_EQUAL((mpz_int(-a)%=-si).str(), (test_type(-a1) %= -si).str());
 266       if((si > 0) || !is_checked_cpp_int<test_type>::value)
 267       {
 268          BOOST_CHECK_EQUAL(mpz_int(a|si).str(), test_type(a1 | si).str());
 269          BOOST_CHECK_EQUAL((mpz_int(a)|=si).str(), (test_type(a1) |= si).str());
 270          BOOST_CHECK_EQUAL(mpz_int(a&si).str(), test_type(a1 & si).str());
 271          BOOST_CHECK_EQUAL((mpz_int(a)&=si).str(), (test_type(a1) &= si).str());
 272          BOOST_CHECK_EQUAL(mpz_int(a^si).str(), test_type(a1 ^ si).str());
 273          BOOST_CHECK_EQUAL((mpz_int(a)^=si).str(), (test_type(a1) ^= si).str());
 274          BOOST_CHECK_EQUAL(mpz_int(si|a).str(), test_type(si|a1).str());
 275          BOOST_CHECK_EQUAL(mpz_int(si&a).str(), test_type(si&a1).str());
 276          BOOST_CHECK_EQUAL(mpz_int(si^a).str(), test_type(si^a1).str());
 277       }
 278       BOOST_CHECK_EQUAL(mpz_int(gcd(a, si)).str(), test_type(gcd(a1, si)).str());
 279       BOOST_CHECK_EQUAL(mpz_int(gcd(si, b)).str(), test_type(gcd(si, b1)).str());
 280       BOOST_CHECK_EQUAL(mpz_int(lcm(c, si)).str(), test_type(lcm(c1, si)).str());
 281       BOOST_CHECK_EQUAL(mpz_int(lcm(si, d)).str(), test_type(lcm(si, d1)).str());
 282       BOOST_CHECK_EQUAL(mpz_int(gcd(-a, si)).str(), test_type(gcd(-a1, si)).str());
 283       BOOST_CHECK_EQUAL(mpz_int(gcd(-si, b)).str(), test_type(gcd(-si, b1)).str());
 284       BOOST_CHECK_EQUAL(mpz_int(lcm(-c, si)).str(), test_type(lcm(-c1, si)).str());
 285       BOOST_CHECK_EQUAL(mpz_int(lcm(-si, d)).str(), test_type(lcm(-si, d1)).str());
 286       BOOST_CHECK_EQUAL(mpz_int(gcd(-a, -si)).str(), test_type(gcd(-a1, -si)).str());
 287       BOOST_CHECK_EQUAL(mpz_int(gcd(-si, -b)).str(), test_type(gcd(-si, -b1)).str());
 288       BOOST_CHECK_EQUAL(mpz_int(lcm(-c, -si)).str(), test_type(lcm(-c1, -si)).str());
 289       BOOST_CHECK_EQUAL(mpz_int(lcm(-si, -d)).str(), test_type(lcm(-si, -d1)).str());
 290       BOOST_CHECK_EQUAL(mpz_int(gcd(a, -si)).str(), test_type(gcd(a1, -si)).str());
 291       BOOST_CHECK_EQUAL(mpz_int(gcd(si, -b)).str(), test_type(gcd(si, -b1)).str());
 292       BOOST_CHECK_EQUAL(mpz_int(lcm(c, -si)).str(), test_type(lcm(c1, -si)).str());
 293       BOOST_CHECK_EQUAL(mpz_int(lcm(si, -d)).str(), test_type(lcm(si, -d1)).str());
 294    }
 295
 296    void t4()
 297    {
 298       using namespace boost::multiprecision;
 299       // Now check operations involving unsigned integers:
 300       BOOST_CHECK_EQUAL(mpz_int(a + ui).str(), test_type(a1 + ui).str());
 301       BOOST_CHECK_EQUAL(mpz_int(-a + ui).str(), test_type(-a1 + ui).str());
 302       BOOST_CHECK_EQUAL(mpz_int(ui + a).str(), test_type(ui + a1).str());
 303       BOOST_CHECK_EQUAL((mpz_int(a)+=ui).str(), (test_type(a1) += ui).str());
 304       BOOST_CHECK_EQUAL((mpz_int(-a)+=ui).str(), (test_type(-a1) += ui).str());
 305       BOOST_CHECK_EQUAL(mpz_int(a - ui).str(), test_type(a1 - ui).str());
 306       BOOST_CHECK_EQUAL(mpz_int(-a - ui).str(), test_type(-a1 - ui).str());
 307       BOOST_CHECK_EQUAL(mpz_int(ui - a).str(), test_type(ui - a1).str());
 308       BOOST_CHECK_EQUAL((mpz_int(a)-=ui).str(), (test_type(a1) -= ui).str());
 309       BOOST_CHECK_EQUAL((mpz_int(-a)-=ui).str(), (test_type(-a1) -= ui).str());
 310       BOOST_CHECK_EQUAL(mpz_int(b * ui).str(), test_type(b1 * ui).str());
 311       BOOST_CHECK_EQUAL(mpz_int(-b * ui).str(), test_type(-b1 * ui).str());
 312       BOOST_CHECK_EQUAL(mpz_int(ui * b).str(), test_type(ui * b1).str());
 313       BOOST_CHECK_EQUAL((mpz_int(a)*=ui).str(), (test_type(a1) *= ui).str());
 314       BOOST_CHECK_EQUAL((mpz_int(-a)*=ui).str(), (test_type(-a1) *= ui).str());
 315       BOOST_CHECK_EQUAL(mpz_int(a / ui).str(), test_type(a1 / ui).str());
 316       BOOST_CHECK_EQUAL(mpz_int(-a / ui).str(), test_type(-a1 / ui).str());
 317       BOOST_CHECK_EQUAL((mpz_int(a)/=ui).str(), (test_type(a1) /= ui).str());
 318       BOOST_CHECK_EQUAL((mpz_int(-a)/=ui).str(), (test_type(-a1) /= ui).str());
 319       BOOST_CHECK_EQUAL(mpz_int(a % ui).str(), test_type(a1 % ui).str());
 320       BOOST_CHECK_EQUAL(mpz_int(-a % ui).str(), test_type(-a1 % ui).str());
 321       BOOST_CHECK_EQUAL((mpz_int(a)%=ui).str(), (test_type(a1) %= ui).str());
 322       BOOST_CHECK_EQUAL((mpz_int(-a)%=ui).str(), (test_type(-a1) %= ui).str());
 323       BOOST_CHECK_EQUAL(mpz_int(a|ui).str(), test_type(a1 | ui).str());
 324       BOOST_CHECK_EQUAL((mpz_int(a)|=ui).str(), (test_type(a1) |= ui).str());
 325       BOOST_CHECK_EQUAL(mpz_int(a&ui).str(), test_type(a1 & ui).str());
 326       BOOST_CHECK_EQUAL((mpz_int(a)&=ui).str(), (test_type(a1) &= ui).str());
 327       BOOST_CHECK_EQUAL(mpz_int(a^ui).str(), test_type(a1 ^ ui).str());
 328       BOOST_CHECK_EQUAL((mpz_int(a)^=ui).str(), (test_type(a1) ^= ui).str());
 329       BOOST_CHECK_EQUAL(mpz_int(ui|a).str(), test_type(ui|a1).str());
 330       BOOST_CHECK_EQUAL(mpz_int(ui&a).str(), test_type(ui&a1).str());
 331       BOOST_CHECK_EQUAL(mpz_int(ui^a).str(), test_type(ui^a1).str());
 332       BOOST_CHECK_EQUAL(mpz_int(gcd(a, ui)).str(), test_type(gcd(a1, ui)).str());
 333       BOOST_CHECK_EQUAL(mpz_int(gcd(ui, b)).str(), test_type(gcd(ui, b1)).str());
 334       BOOST_CHECK_EQUAL(mpz_int(lcm(c, ui)).str(), test_type(lcm(c1, ui)).str());
 335       BOOST_CHECK_EQUAL(mpz_int(lcm(ui, d)).str(), test_type(lcm(ui, d1)).str());
 336       BOOST_CHECK_EQUAL(mpz_int(gcd(-a, ui)).str(), test_type(gcd(-a1, ui)).str());
 337       BOOST_CHECK_EQUAL(mpz_int(lcm(-c, ui)).str(), test_type(lcm(-c1, ui)).str());
 338       BOOST_CHECK_EQUAL(mpz_int(gcd(ui, -b)).str(), test_type(gcd(ui, -b1)).str());
 339       BOOST_CHECK_EQUAL(mpz_int(lcm(ui, -d)).str(), test_type(lcm(ui, -d1)).str());
 340
 341       if(std::numeric_limits<test_type>::is_modulo && checked::value)
 342       {
 343          static mpz_int m = mpz_int(1) << std::numeric_limits<test_type>::digits;
 344          mpz_int t(a);
 345          test_type t1(a1);
 346          for(unsigned i = 0; i < 10; ++i)
 347          {
 348             t *= a;
 349             t %= m;
 350             t += a;
 351             t %= m;
 352             t1 *= a1;
 353             t1 += a1;
 354          }
 355          BOOST_CHECK_EQUAL(t.str(), t1.str());
 356       }
 357    }
 358
 359    void t5()
 360    {
 361       using namespace boost::multiprecision;
 362       //
 363       // Now integer functions:
 364       //
 365       mpz_int z1, z2;
 366       test_type t1, t2;
 367       divide_qr(a, b, z1, z2);
 368       divide_qr(a1, b1, t1, t2);
 369       BOOST_CHECK_EQUAL(z1.str(), t1.str());
 370       BOOST_CHECK_EQUAL(z2.str(), t2.str());
 371       BOOST_CHECK_EQUAL(integer_modulus(a, si), integer_modulus(a1, si));
 372       BOOST_CHECK_EQUAL(lsb(a), lsb(a1));
 373       BOOST_CHECK_EQUAL(msb(a), msb(a1));
 374
 375       for(unsigned i = 0; i < 1000; i += 13)
 376       {
 377          BOOST_CHECK_EQUAL(bit_test(a, i), bit_test(a1, i));
 378       }
 379       if(!std::numeric_limits<test_type>::is_modulo)
 380       {
 381          // We have to take care that our powers don't grow too large, otherwise this takes "forever",
 382          // also don't test for modulo types, as these may give a different result from arbitrary
 383          // precision types:
 384          BOOST_CHECK_EQUAL(mpz_int(pow(d, ui % 19)).str(), test_type(pow(d1, ui % 19)).str());
 385          BOOST_CHECK_EQUAL(mpz_int(powm(a, b, c)).str(), test_type(powm(a1, b1, c1)).str());
 386          BOOST_CHECK_EQUAL(mpz_int(powm(a, b, ui)).str(), test_type(powm(a1, b1, ui)).str());
 387          BOOST_CHECK_EQUAL(mpz_int(powm(a, ui, c)).str(), test_type(powm(a1, ui, c1)).str());
 388       }
 389       BOOST_CHECK_EQUAL(lsb(a), lsb(a1));
 390       BOOST_CHECK_EQUAL(msb(a), msb(a1));
 391    }
 392
 393    static void test_bug_cases()
 394    {
 395       if(!std::numeric_limits<test_type>::is_bounded)
 396       {
 397          // https://svn.boost.org/trac/boost/ticket/7878
 398          test_type a("0x1000000000000000000000000000000000000000000000000000000000000000");
 399          test_type b = 0xFFFFFFFF;
 400          test_type c = a * b + b;  // quotient has 1 in the final place
 401          test_type q, r;
 402          divide_qr(c, b, q, r);
 403          BOOST_CHECK_EQUAL(a + 1, q);
 404          BOOST_CHECK_EQUAL(r, 0);
 405
 406          b = static_cast<test_type>("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
 407          c = a * b + b;  // quotient has 1 in the final place
 408          divide_qr(c, b, q, r);
 409          BOOST_CHECK_EQUAL(a + 1, q);
 410          BOOST_CHECK_EQUAL(r, 0);
 411          //
 412          // Not a bug, but test some other special cases that don't otherwise occur through
 413          // random testing:
 414          //
 415          c = a * b; // quotient has zero in the final place
 416          divide_qr(c, b, q, r);
 417          BOOST_CHECK_EQUAL(q, a);
 418          BOOST_CHECK_EQUAL(r, 0);
 419          divide_qr(c, a, q, r);
 420          BOOST_CHECK_EQUAL(q, b);
 421          BOOST_CHECK_EQUAL(r, 0);
 422          ++c;
 423          divide_qr(c, b, q, r);
 424          BOOST_CHECK_EQUAL(q, a);
 425          BOOST_CHECK_EQUAL(r, 1);
 426       }
 427       // Bug https://svn.boost.org/trac/boost/ticket/8126:
 428       test_type a("-4294967296");
 429       test_type b("4294967296");
 430       test_type c("-1");
 431       a = (a / b);
 432       BOOST_CHECK_EQUAL(a, -1);
 433       a = -4294967296;
 434       a = (a / b) * c;
 435       BOOST_CHECK_EQUAL(a, 1);
 436       a = -23;
 437       b = 23;
 438       a = (a / b) * c;
 439       BOOST_CHECK_EQUAL(a, 1);
 440       a = -23;
 441       a = (a / b) / c;
 442       BOOST_CHECK_EQUAL(a, 1);
 443       a = test_type("-26607734784073568386365259775");
 444       b = test_type("8589934592");
 445       a = a / b;
 446       BOOST_CHECK_EQUAL(a, test_type("-3097548007973652377"));
 447       // Bug https://svn.boost.org/trac/boost/ticket/8133:
 448       a = test_type("0x12345600012434ffffffffffffffffffffffff");
 449       unsigned ui = 0xffffffff;
 450       a = a - ui;
 451       BOOST_CHECK_EQUAL(a, test_type("0x12345600012434ffffffffffffffff00000000"));
 452       a = test_type("0x12345600012434ffffffffffffffffffffffff");
 453 #ifndef BOOST_NO_LONG_LONG
 454       unsigned long long ull = 0xffffffffffffffffuLL;
 455       a = a - ull;
 456       BOOST_CHECK_EQUAL(a, test_type("0x12345600012434ffffffff0000000000000000"));
 457 #endif
 458       //
 459       // Now check that things which should be zero really are
 460       // https://svn.boost.org/trac/boost/ticket/8145:
 461       //
 462       a = -1;
 463       a += 1;
 464       BOOST_CHECK_EQUAL(a, 0);
 465       a = 1;
 466       a += -1;
 467       BOOST_CHECK_EQUAL(a, 0);
 468       a = -1;
 469       a += test_type(1);
 470       BOOST_CHECK_EQUAL(a, 0);
 471       a = 1;
 472       a += test_type(-1);
 473       BOOST_CHECK_EQUAL(a, 0);
 474       a = test_type("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
 475       a -= test_type("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
 476       BOOST_CHECK_EQUAL(a, 0);
 477       a = -test_type("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
 478       a += test_type("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
 479       BOOST_CHECK_EQUAL(a, 0);
 480       a = 2;
 481       a *= 0;
 482       BOOST_CHECK_EQUAL(a, 0);
 483       a = -2;
 484       a *= 0;
 485       BOOST_CHECK_EQUAL(a, 0);
 486       a = 2;
 487       a *= test_type(0);
 488       BOOST_CHECK_EQUAL(a, 0);
 489       a = -2;
 490       a *= test_type(0);
 491       BOOST_CHECK_EQUAL(a, 0);
 492       a = -2;
 493       a /= 50;
 494       BOOST_CHECK_EQUAL(a, 0);
 495       a = -test_type("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
 496       a /= (1 + test_type("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"));
 497       BOOST_CHECK_EQUAL(a, 0);
 498       // https://svn.boost.org/trac/boost/ticket/8160
 499       a = 1;
 500       a = 0 / test_type(1);
 501       BOOST_CHECK_EQUAL(a, 0);
 502       a = 1;
 503       a = 0 % test_type(25);
 504       BOOST_CHECK_EQUAL(a, 0);
 505 #ifndef TEST2
 506       // https://svn.boost.org/trac/boost/ticket/11364
 507       a = 0xfffffffeu;
 508       b = -2;
 509       c = a ^ b;
 510       test_type d = ~(a ^ ~b);
 511       BOOST_CHECK_EQUAL(c, d);
 512 #endif
 513 #if defined(TEST2) || defined(TEST3)
 514       // https://svn.boost.org/trac/boost/ticket/11648
 515       a = (std::numeric_limits<test_type>::max)() - 69;
 516       b = a / 139;
 517       ++b;
 518       c = a / b;
 519       test_type r = a % b;
 520       BOOST_CHECK(r < b);
 521       BOOST_CHECK_EQUAL(a - c * b, r);
 522 #endif
 523       for(ui = 0; ui < 1000; ++ui)
 524       {
 525          boost::multiprecision::mpz_int t;
 526          boost::multiprecision::mpz_int s1 = sqrt(boost::multiprecision::mpz_int(ui), t);
 527          a = sqrt(test_type(ui), b);
 528          BOOST_CHECK_EQUAL(a.str(), s1.str());
 529          BOOST_CHECK_EQUAL(b.str(), t.str());
 530       }
 531    }
 532
 533    void test()
 534    {
 535       using namespace boost::multiprecision;
 536
 537       test_bug_cases();
 538
 539       last_error_count = 0;
 540
 541       BOOST_CHECK_EQUAL(Number(), 0);
 542
 543       for(int i = 0; i < 10000; ++i)
 544       {
 545          a = generate_random<mpz_int>(1000);
 546          b = generate_random<mpz_int>(512);
 547          c = generate_random<mpz_int>(256);
 548          d = generate_random<mpz_int>(32);
 549
 550          si = d.convert_to<int>();
 551          ui = si;
 552
 553          a1 = static_cast<test_type>(a.str());
 554          b1 = static_cast<test_type>(b.str());
 555          c1 = static_cast<test_type>(c.str());
 556          d1 = static_cast<test_type>(d.str());
 557
 558          t1();
 559          t2();
 560 #ifndef SLOW_COMPILER
 561          t3();
 562          t4();
 563          t5();
 564 #endif
 565
 566          if(last_error_count != (unsigned)boost::detail::test_errors())
 567          {
 568             last_error_count = boost::detail::test_errors();
 569             std::cout << std::hex << std::showbase;
 570
 571             std::cout << "a    = " << a << std::endl;
 572             std::cout << "a1   = " << a1 << std::endl;
 573             std::cout << "b    = " << b << std::endl;
 574             std::cout << "b1   = " << b1 << std::endl;
 575             std::cout << "c    = " << c << std::endl;
 576             std::cout << "c1   = " << c1 << std::endl;
 577             std::cout << "d    = " << d << std::endl;
 578             std::cout << "d1   = " << d1 << std::endl;
 579             std::cout << "a + b   = " << a+b << std::endl;
 580             std::cout << "a1 + b1 = " << a1+b1 << std::endl;
 581             std::cout << std::dec;
 582             std::cout << "a - b   = " << a-b << std::endl;
 583             std::cout << "a1 - b1 = " << a1-b1 << std::endl;
 584             std::cout << "-a + b   = " << mpz_int(-a)+b << std::endl;
 585             std::cout << "-a1 + b1 = " << test_type(-a1)+b1 << std::endl;
 586             std::cout << "-a - b   = " << mpz_int(-a)-b << std::endl;
 587             std::cout << "-a1 - b1 = " << test_type(-a1)-b1 << std::endl;
 588             std::cout << "c*d    = " << c*d << std::endl;
 589             std::cout << "c1*d1  = " << c1*d1 << std::endl;
 590             std::cout << "b*c    = " << b*c << std::endl;
 591             std::cout << "b1*c1  = " << b1*c1 << std::endl;
 592             std::cout << "a/b    = " << a/b << std::endl;
 593             std::cout << "a1/b1  = " << a1/b1 << std::endl;
 594             std::cout << "a/d    = " << a/d << std::endl;
 595             std::cout << "a1/d1  = " << a1/d1 << std::endl;
 596             std::cout << "a%b    = " << a%b << std::endl;
 597             std::cout << "a1%b1  = " << a1%b1 << std::endl;
 598             std::cout << "a%d    = " << a%d << std::endl;
 599             std::cout << "a1%d1  = " << a1%d1 << std::endl;
 600          }
 601
 602          //
 603          // Check to see if test is taking too long.
 604          // Tests run on the compiler farm time out after 300 seconds,
 605          // so don't get too close to that:
 606          //
 607 #ifndef CI_SUPPRESS_KNOWN_ISSUES
 608          if(tim.elapsed() > 200)
 609 #else
 610          if (tim.elapsed() > 25)
 611 #endif
 612          {
 613             std::cout << "Timeout reached, aborting tests now....\n";
 614             break;
 615          }
 616
 617       }
 618    }
 619 };
 620
 621 int main()
 622 {
 623    using namespace boost::multiprecision;
 624
 625 #ifdef TEST1
 626    tester<cpp_int> t1;
 627    t1.test();
 628 #endif
 629 #ifdef TEST2
 630    tester<number<cpp_int_backend<2048, 2048, signed_magnitude, checked, void> > > t2;
 631    t2.test();
 632 #endif
 633 #ifdef TEST3
 634    // Unchecked test verifies modulo arithmetic:
 635    tester<number<cpp_int_backend<2048, 2048, signed_magnitude, unchecked, void> > > t3;
 636    t3.test();
 637 #endif
 638 #ifdef TEST4
 639    tester<number<cpp_int_backend<0, 2048, signed_magnitude, unchecked, std::allocator<void> > > > t4;
 640    t4.test();
 641 #endif
 642 #ifdef TEST5
 643    tester<number<cpp_int_backend<0, 2048, signed_magnitude, unchecked > > > t5;
 644    t5.test();
 645 #endif
 646    return boost::report_errors();
 647 }
 648
 649
 650