I'm not saying every polynomial multiplication program can be shown to be correct; just the method I suggested happens to be pretty simple.
If you write a polynomial multiplication program that has certain breakpoints, e.g. switching to a different method like Karatsuba or FFT at size 3000, then clearly a demonstration of correctness at size 0,1,2,3 will not extend to 3000. The bug report doesn't really say what was wrong, but it looks like disabling some special component, znpoly, fixes the problem. It could be that there is some kind of overflow of coefficients, since the coefficients are supposed to be elements in a finite field. Careless calculation of bounds, or doing too much arithmetic before doing a modular reduction might be the problem in FLINT. If you write (or in this case, just use) a complicated program, it is plausible to be more suspicious of correctness. No surprise there. I note that the fact that FLINT is open source does not enter into the fix here: the program with the bug is apparently just disabled. > > A few weeks ago we had a strange bug in a prerelease version of Sage, > where it would square univariate polynomials (modulo the cube of the > prime 10007) and work fine for degrees up to about 3000, then suddenly > get everything wrong when the degree exceeded about 3000 (on all > operating systems and hardware) -- > seehttp://trac.sagemath.org/sage_trac/ticket/5817. We only discovered > it because we had a test case involving computation of the matrix of > Frobenius on certain Monsky-Washnitzer cohomology groups -- the input > and output of the computation were very simple, but the intermediate > steps involved arithmetic with univariate polynomials of large degree. > The bug was sufficiently subtle that it wasn't picked up at all by > the responsible library's very extensive test suites. > > William --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
