Opened 5 years ago

Closed 5 years ago

#8133 closed Bugs (fixed)

multiprecision, failed gcd tests (test_cpp_int.cpp)

Reported by: Stepan Podoskin <stepik-777@…> Owned by: John Maddock
Milestone: To Be Determined Component: multiprecision
Version: Boost 1.53.0 Severity: Problem
Keywords: Cc:


I modified test_cpp_int.cpp to generate random numbers with a lot of ones or zeros.

I modified T generate_random(unsigned bits_wanted):

   T val = 0;
   for(unsigned i = 0; i < terms_needed; ++i)
      val *= (gen.max)();
      switch (gen() % 5)
      case 0:
          val += gen();
      case 1:
          val += 1;
      case 2:
          val += (gen.max)() - 2;
      case 3:
          val += (gen.max)() - 1;
   val %= max_val;
   return (val == 0)? val : 1;

This caused some tests related to gcd computation to fail. Here is output (I removed some parts of it with results of operations) -

Attachments (0)

Change History (4)

comment:1 Changed 5 years ago by John Maddock

Thanks for the report - However I'm having trouble reproducing here, note that your random generator code above either returns 0 or 1, I assume the last line should read:

return (val == 0) ? 1 : val;


However, even then neither random numbers generated as above, nor the specific test values printed out in your log trigger errors for me. What compiler/platform is this? I'm testing on Win32 VC10 here, but I can switch to 64-bit Linux if that's the thing I'm missing.

BTW the report you outputted, contains line numbers that don't match up to anything in test_cpp_int.cpp - I guess because you modified that file?

comment:2 Changed 5 years ago by Stepan Podoskin <stepik-777@…>

Yes, you are right, it should be (val == 0) ? 1 : val;

This line is there because tests will fail with division by zero otherwise.

I'm testing it on 32-bit Windows with GCC 4.7.2 and MSVC 2010. I'm using boost 1.53.0, not the latest trunk. Following program outputs 1 1 1 3 when compiled with GCC and 3 3 1 3 and when complied with MSVC.

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using boost::multiprecision::gcd;

int main()
    cpp_int a("0xffffffee00000095fffffd0000000a8fffffe4e10000348bffffb1a100005ae3ffffade700003955ffffe19900000bd2fffffcdb00000076fffffffffffffffd");

    // correct gcd is 1
    std::cout << gcd(a, 4294967295) << '\n';
    std::cout << gcd(4294967295, a) << '\n';
    std::cout << gcd(a, cpp_int("4294967295")) << '\n';
    std::cout << gcd(cpp_int("4294967295"), a) << '\n';
    return 0;

comment:3 Changed 5 years ago by John Maddock

Thanks, reproduced.

It's a bug in the subtraction routine for subtracting an unsigned int - wrongly uses a carry when subtracting ~static_cast<unsigned>(0).

Testing a fix now.

comment:4 Changed 5 years ago by John Maddock

Resolution: fixed
Status: newclosed

(In [83080]) Fix bug in subtraction of a limb_type. Fix bug in division/modulus algorithms that results in incorrect sign when source and destination overlap. Tweak performance of GCD algorithms. Add test cases for bug reports. Fixes #8133. Fixes #8126.

Modify Ticket

Change Properties
Set your email in Preferences
as closed The owner will remain John Maddock.
The resolution will be deleted.

Add Comment

E-mail address and name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.