multiprecision, failed gcd tests (test_cpp_int.cpp)

[Stepan Podoskin <stepik-777@…>]

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();
          break;
      case 1:
          val += 1;
          break;
      case 2:
          val += (gen.max)() - 2;
          break;
      case 3:
          val += (gen.max)() - 1;
          break;
      }
   }
   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) - ​http://pastebin.com/iZdmX1bq

[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?

[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;
}

[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.

[John Maddock]

(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.