The current implementation of FLINT will not care which design choice
you make because integer polynomials are currently implemented with
all coefficients the same size anyway. So a common denominator is
absolutely fine. I also doubt that a version with individual
coefficient denominators could be made efficient for most problems.
In a general implementation, if you allow general denominators, then
you need to do n^2 rational arithmetic operations instead of n when
multiplying polynomials. I think that could be decidedly inefficient.
Once the length is > 12, FLINT uses the FFT anyway, in which case you
need everything over a common denominator.
Bill.
On 29 June, 23:16, David Roe <r...@math.harvard.edu> wrote:
> One interesting design decision with rational polynomials is whether to use
> a common denominator or individual denominators for each coefficient. The
> second choice is generally slower, but the first can cause explosion in
> coefficient size in some examples (eg x + x^2/2 + x^3/3 + x^4/4 + ... +
> x^10000 / 10000).
>
> I'd say the best option is to have two types of rational polynomials
> (defaulting to the single denominator implementation).
>
> Also take a look at sage.rings.polynomial.polynomial_integer_dense_flint.pyx
> for another, simpler example of wrapping FLINT. And if you want a bigger
> project, you could rewrite number field elements to use FLINT instead of NTL
> too. It's very similar code to rational polynomials. :-)
> David
>
> On Mon, Jun 29, 2009 at 5:29 PM, Martin Albrecht <
>
>
>
> m...@informatik.uni-bremen.de> wrote:
>
> > > You don't need to worry about the get_cparent() magic defined in the
> > > zmod_poly wrapper, since you won't need to keep track of a modulus for
> > > your polynomial objects.
>
> > One more thing: IIRC FLINT doesn't have a QQ['x'] type so I guess one would
> > define a struct
>
> > struct my_qqx {
>
> > fmpz_poly_t poly;
> > fmpz_t denominator;
>
> > }
>
> > and use that as the celement type?
>
> > Cheers,
> > Martin
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
