Martin Rubey wrote: > I am currently trying to correct a performance bug of my guessing package, and > found out that exquo is in general not extremely intelligent. > > In axiom, what exquo really does is to perform division and return "failed" if > it's not exact. (I.e., it is in fact slower than quo.quotient) > > What I need is a fast algorithm, that simply assumes that the division is > exact, and should benefit from that assumption. (If the assumption is not > true, the computer may crash, if necessary...) As far as I know, using some > tricks performance even better than n^2 (n being the size of the input) is > achievable. > > Most important would be such an implementation for the polynomial rings. > > Anybody interested? >
I am interested in Axiom performance. But do you have reasons to supect exquo? I mean, did you look at profile of some problematic run? While I agree that perfroming division and checking that remainder is zero is not very smart, it should not matter much for polynomials (at least for polynomials in single variable, for multivariate polynomials division is not defined, so you must do something smarter anyway). Concerning complexity: for dense univariate polynomials with coefficients in small finite fields both multiplication and division have complexity of n times logarithmic terms. For practical problem sizes logarithmic terms behave like constants, and you end up comparing your "constants" with n. For dense multivariate polynomials one have similar results, but complexity grows exponentially with dimension (for fixed dimension you have some constat coefficent, but it grows exponentially with dimension). Unbouded integer coefficents essentially add one dimension to the problem (so one variable integer problem have similar complexity like two variable modular one). Sparse problems have some similarity to multidimensional ones. I was thinking about adding fast operations on dense polynomials with coefficients in small finite fields -- such operations are key to many fast algorithms. Unfortunatly, they fit rather poorly into existing algebra. More precisely, to be fast such operations would have to work directly at Lisp level (or maybe even at C level). But that would require building a new set of domains and adding calls to them from various places in algebra. In particular that would change import relations in the algebra. Currently (before database bootstrap is integrated) such changes are likely to cause bootstrap failure... -- Waldek Hebisch [EMAIL PROTECTED] _______________________________________________ Axiom-developer mailing list Axiom-developer@nongnu.org http://lists.nongnu.org/mailman/listinfo/axiom-developer