Hi Nicolas, I have no time at the moment to look at this patch. I used it to do some computations which were completely undoable with the standard implementation of FractionField, and which became extremely fast using this implementation.
So the lukewarm (to say the least) reaction by some very much discouraged me. Anyway here is a working link http://emis.uhasselt.be/~vdbergh/sage_patches/fraction_field_cache/ The beef is contained in a cython file factor_cache.pyx which acts as a wrapper around RingElement but which caches information about factorizations (to take mock gcd's and lcm's). FractionField_cache is an implementation of FractionField which uses factor_cache to cache factorizations of the denominator. You can turn this behaviour on and off using "auto_reduce". It is quite likely that the files need to be adapted to work with the current version of Sage. Regards, Michel On Mar 9, 7:53 pm, "Nicolas M. Thiery" <nicolas.thi...@u-psud.fr> wrote: > Dear Michel, > > On Mon, Mar 09, 2009 at 12:03:34AM -0700, Michel wrote: > > A long time ago I made a FractionFIeld implementation which would > > cache factorizations of denominators. instead of taking gcd's all the > > time > > >http://markmail.org/message/7hxox5cbz5knxjse#query:new%20implementati... > > > It is usually much faster than the naive implementation but it is > > possible > > to make examples where it is slower (see the above thread). That's > > why it was rejected. > > Cool, thanks so much for your pointer and your patch! > > In combinatorics, when playing with rational generating series, we > have *lots* of fractions with denominators that factor well. So this > gives quite a few applications to your code. > > Let me dream a bit. I very much like the idea of Factored(Ring), where > elements are kept in factored form as long as possible, as is done in > FriCas (thanks Martin for the pointer). I would like to have several > variants to choose from: > > - PartiallyFactored(Ring) > The factors are not guaranteed to be relatively prime > - RelativelyPrimeFactored(Ring) > The factors are guaranteed to be relatively prime, but not necessarily > prime themselves > - FullyFactored(Ring) > The factors are all guaranteed to be prime > > In each case, the gcd function would do its best to exploit the > structure (e.g. remember which factors are readily relatively prime). > > As readily pointed out, this is very modular, and leaves the user with > the choice of the appropriate implementation of fraction field for his > particular application (as the discussion pointed out there won't be > one perfect implementation optimal in all cases). For example for my > application, I ideally would use Ring / > GcdFreePartiallyFactored(Ring). As a starter, I could do with > FractionField(PartiallyFactored(Ring)). > > How much work would it be to adapt your patch in this direction? I > definitely volunteer for testing and reviewing it! In fact, your > patch would be very welcome on the Sage-combinat patch server so that > we can easily start playing with it (even though it's not only about > combinatorics). > > Best regards, > Nicolas > -- > Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>http://Nicolas.Thiery.name/ --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
