What you are saying is this: assuming that gcd(a,b)=gcd(c,d)=1 then instead of setting (a/b) * (c/d) = (a*c//g)/(b*d//g) where g=gcd(a*c,b*d) you instead use the same formula with g=gcd(a,d)*gcd(b,c). That seems very sensible to me.
I don't know about the policy regarding reduction on creation of elements: does anyone? Although my instinct would be do do that, I can see that there are situations in which it better to wait and reduce later. This is an issue which must have been considered by a lot of other CA systems in the past! At present we cannot rely on the input to + being reduced, since they might have been created with reduce=False; in which case the value returned by + (after using your idea) would not be reduced either -- is there any harm in that? It would be possible for every element to keep a "reduced" boolean flag which is set to False unless the element has been reduced. then, when a reduced representative is required, it would save checking (by doing a gcd computation) when that would be redundant. Surely that would not be expensive to implement? Also, we could have each FractionField (i.e. the parent of a FractionFieldElement) have a "reduction policy" flag which specifies whether or not elements of that field should be reduced on creation; this could still be overridden in teh constructor for elements, but instead of the defaul in FractionFieldElement.__init__() being reduce=True it could be (say) reduce=None, and then (if None) the constructor would test the parent's policy and use that. John 2010/1/5 Sebastian Pancratz <s...@pancratz.org>: > Dear all, > > When looking at trac ticket #7730 (which essentially ends with saying > that GCD computations over multivariate polynomial rings are slow), I > noticed that the current implementation of multiplication in fraction > fields computes the product (a/b) * (c/d) by first computing a*c and > b*d, and then dividing out common factors (in the case of exact > underlying rings). > > I am wondering whether there is a good reason for doing this. > > Typically, assuming that (or even on the spot enforcing that!) a/b and > c/d are in lowest terms, it would be much faster to compute GCD(a,d) > and GCD(c,b) and to then divide out appropriately. If all elements > involved are of "size" n, say, this way all operations take inputs of > size at most n, as opposed to 2n as in the current implementation. > > To illustrate the usefulness... In the particular example from #7730, > this would allow a computation to happen essentially instantly, > whereas at the moment it takes close to 5 hours. I am not saying that > 5 hours is a reasonable time for Singular to take for the "large" GCD > computation or that this shouldn't be improved. However, improving > the fraction field implementation to this effect would basically help > anyone working with fraction fields whose underlying rings have an > expensive GCD (in the sense of "depending on the input size") right > away. > > Unless I am missing an important point for why this approach shouldn't > be followed here, I am happy to work on the patch in the next few > days, but before writing any code, I'd like to make sure that I > understand the idea behind reduction in fraction fields (in the > current implementation) properly. Is it just > > - If the ring is exact, automatically reduce all the time, unless > explicitly specified (with reduce=False) otherwise; > - If the ring is inexact, never reduce unless the method "reduce" is > called explicitly? > > Kind regards, > > Sebastian > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-devel > URL: http://www.sagemath.org > -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
