> Just because an algorithm is probabilistic > doesn't mean it necessarily gives wrong answers. By the way, see > > http://www-fourier.ujf-grenoble.fr/~parisse/publi/gcdheu.pdf > > which is I think a paper that proves correctness of the algorithm > we're talking about. (I've not carefully read the above short > paper, so I'm not vouching for it though.)
More precisely it fills a little gap in the proof of correctness for multivariate polynomials and extends the coefficients from Z to Z[i]. Gcdheu is one of about 4 main algorithms (ezgcd, gcdheu, modular with sparse and dense variants, subresultant), all implemented in Giac. http://www-fourier.ujf-grenoble.fr/~parisse/giac.html I have added a benchmark link with Fermat gcd tests, giac seems 5 to 10 * faster than maxima. I don't have magma, it is most probably another factor of 10 * faster. Sage developers may of course decide to write their own gcd algorithms, but that's a large piece of code to write and test. Why not make a link to giac (which is a C++ library) instead? Sage and giac could then benefit from improvements and more interesting piece of code could be written, like bivariate factorization (which would improve giac multivariate factorization) or absolute factorization over C. Moreover, sage could benefit from the calculus code of giac (series, integration, etc.). I would be ready to contribute to write such a link, but I would need help on the sage side, I don't know python at all. B. Parisse --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
