> 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 original proof of the correctness of the gcdheu algorithm for multivariate polynomials, and extends the coefficients from Z to Z[i]. Gcdheu is just one of about 4 main algorithms for GCD: ezgcd, modular (with a sparse variant), gcdheu, subresultant. Giac implements all of them, gcdheu being used for small problems. I have just created a benchmark page with Fermat tests: http://www-fourier.ujf-grenoble.fr/~parisse/giac.html follow the benchmark link. It seems giac is faster than maxima (around 5 to 10 times on these tests), I do not have access to magma which is most probably another factor of 10 * faster. Sage may of course decide to implement it's own algorithms, but as Roman Pearce said, it is a large piece of code to write and moreover test. Why not integrate giac and help me improve giac code instead? There are more interesting piece of codes to write, e.g. bivariate factorization (which would improve giac multivariate factorization), or absolute factorization over C. And once there is a link between sage and giac, sage could benefit from all the calculus code of giac (series, integration, etc.) which I believe is not the main interest of Sage developers. I would of course contribute to such a link, but I do not have time to do all the work myself. 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 -~----------~----~----~----~------~----~------~--~---
