Boost C++ Libraries: Ticket #8133: multiprecision, failed gcd tests (test_cpp_int.cpp)

John Maddock — Thu, 21 Feb 2013 13:54:27 GMT

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?

Thu, 21 Feb 2013 14:46:49 GMT

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 — Thu, 21 Feb 2013 18:36:18 GMT

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.

status changed; resolution set

John Maddock — Fri, 22 Feb 2013 10:37:38 GMT

status new → closed
resolution → fixed

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