For anyone who is interested in when this bug was likely to bite, the *only* cases I can get it to trigger were when taking gcd(f, g) where either f or g, but not both, was divisible by x+1 or x-1 (there are other conditions on this polynomial, which I didn't quantify).
Typically one of the coefficients in the other polynomial (the largest) was very close to, but less than a power of 2. One also needed very precise quantities of bits in the coefficients and precisely corresponding lengths so that the bit packing was in some sense optimal (we round the number of bits for bit packing up to a multiple of 32/64, which hid the problem in most cases). Of course the heuristic gcd algorithm had to fail in the first place, which is also rare enough. It's pretty much impossible to give a complete list of conditions, but this was indeed a rare bug. On 17 February 2015 at 22:17, Bill Hart <goodwillh...@googlemail.com> wrote: > Someone (thanks Curtis Bright) has now reported that this passes on a 32 > bit machine. So it looks like this patch release is good to go. > > Bill. > > > On Tuesday, 17 February 2015 16:19:02 UTC+1, Bill Hart wrote: >> >> Hi all, >> >> Anton Mellit reported a bug in flint's heuristic GCD code which was hit >> in the wild. >> >> Anton also supplied a working patch for this issue, which we applied to >> our code. >> >> After generating lots of examples quite similar to Anton's, we also >> discovered another very subtle, very rare bug, which could also account for >> the original issue. >> >> That bug is hard to describe with few words, but essentially when bit >> packing we were not adding a bit for signed coefficients. The original code >> took notice of this, but the accommodation that had been made for this fact >> was not quite correct. >> >> Both bugs were only triggered extremely rarely. >> >> I have applied both of these fixes to flint/trunk and flint/2.4 in our >> repository and have issued a new bugfix release, flint-2.4.5, available on >> our website >> >> http://flintlib.org/ >> >> I have tested the fixes for some hours with hardened test code, including >> a regression test for the original issue, and found no further failures. >> >> However, I have no access to any 32 bit machines. It would be nice, for >> peace of mind, if someone with access to a 32 bit machine could test that >> the code works there too. >> >> The sequence of commands should be something like: >> >> wget http://mpir.org/mpir-2.7.0-alpha12.tar.bz2 >> wget http://www.mpfr.org/mpfr-current/mpfr-3.1.2.tar.bz2 >> wget http://flintlib.org/flint-2.4.5.tar.gz >> >> tar -xvf mpir-2.7.0-alpha12.tar.bz2 >> tar -xvf mpfr-3.1.2.tar.bz2 >> tar -xvf flint-2.4.5.tar.gz >> >> cd mpir-2.7.0 >> ./configure --enable-gmpcompat >> make -j >> >> cd ../mpfr-3.1.2 >> ./configure --with-gmp-build=/home/username/mpir-2.7.0 >> make -j >> >> cd ../flint2 >> ./configure --with-mpir=/home/username/mpir-2.7.0 >> --with-mpfr=/home/username/mpfr-3.1.2 >> make -j >> make check MOD=fmpz_poly >> >> Bill. >> >> -- > > --- > You received this message because you are subscribed to the Google Groups > "flint-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to flint-devel+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
