2010/1/5 Sebastian Pancratz <s...@pancratz.org>: > Dear John, > >> 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? > > Well, as long as the behaviour is clearly documented, I think if a > user chooses to supply a non-reduced element, there shouldn't be any > harm in returning an element which isn't completely reduced. However, > there are two possible problems. Firstly, if GCD computations are > prohibitively expensive, the simple attempt to reduce something as > part of the computation might cause problems. (Note that this is the > case in the current implementation.) Secondly, one might prefer to > return completely non-reduced output in the case of non-reduced > input. Even if GCD computations are feasible, without introducing > flags, we would have to actually compute the GCDs in order to check > whether the input is reduced, introducing unnecessary overhead. > >> 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. > > It is at least possible to think of cases where elements cannot > feasibly be reduced at all, that is, when for computing (a/b)*(c/d) > even computing GCD(a,d) and GCD(c,b) instead of GCD(ac,bd) does not > help, however, in such cases the current implementation would be > equally bad. > > In this case, having a flag (per element) as you suggest would help. > In fact, I think the two points one should ideally take into account > are the user's choice of reduction and the availability of a GCD > routine. (It wouldn't be enough to work over a Euclidean domain > rather than a principal ideal domain. It's about actually being able > to compute GCDs in reasonable time.) Then, rather than carrying flags > and handling exceptions everywhere, it would be nice to have separate > classes of fraction fields so that this information would all be > available at the time when the fraction field is created. However, if > this is possible in the current framework at all, it sounds like a big > project rather than a small update. > > For the purpose of making this a small and easy update, I think it > would be nice to not introduce new flags, provided one can get away > with it. I think the following policy might be OK: > > - For exact rings with a GCD implementation, all user-callable > methods other than initialization (and perhaps suitable private helper > methods) should assume that the input is reduced and always return > reduced results. If the input is not reduced, the output should still > be mathematically correct, but might not be in reduced form. > - For exact rings without a GCD implementation, no assumptions are > placed on the input and no reduction takes place. > - For inexact rings, no assumptions are placed on the input and no > reduction takes place. > > Does this seem reasonable?
This sounds reasonable to me. There are lots of related issues we will want to consider at some point (such as the representation of elements of Q(x) where begin reduced is not at all the whole story!) but I'm in favour of implementing the relatively small change you are proposing now an leaving those for another day. It seems that Burcin's patch would b a good start for what you are proposing (and it goes further -- I had never heard of henrici!) John > > 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
