On Tue, Jun 30, 2009 at 3:04 AM, Bill Hart<goodwillh...@googlemail.com> wrote:
>
> 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.
I wonder -- what does PARI use? I suspect the coefficient have
individual denominators, since in PARI I think the coefficients are in
fact arbitary Pari objects (i.e., they don't really have a notion of
"polynomials over R"). Pari is more like Sage symbolics:
pari> f = 2/3 + 4/3*x - I*x^2 + sqrt(2)*x^3 + 5*x^4
5*x^4 + 1.414213562373095048801688724*x^3 - I*x^2 + 4/3*x + 2/3
> 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.
Indeed. Below is some benchmarking in Sage (on my core2 32-bit OSX
laptop build of Sage). The conclusions for that *one random degree
100 example* below:
* rewriting QQ[x] polys as suggested in this thread would give a
speedup of a factor of 25
* PARI doesn't seem to clear denoms, since in that example multiplying
over QQ takes over 4 times as long as multiplying the poly over ZZ
after clearing denoms.
* in the example below, FLINT is nearly 7 times faster than NTL. Hence
there may be a substantial speedup if we switch the number
field arithmetic from NTL to FLINT (hence we *should* make said switch).
sage: R.<x> = QQ[]
sage: f = R.random_element(degree=100); f
-x^100 + 66*x^99 + 3*x^98 + 1/4*x^95 + 4*x^93 - 4*x^92 + x^91 -
1/2*x^90 - x^89 - x^86 - 2/3*x^85 - 1/2*x^84 + 2*x^82 + 2/7*x^80 -
1/3*x^79 + 2*x^78 + 3*x^77 + 2*x^76 + 5/2*x^75 - x^74 + 2/5*x^73 +
x^72 + 9/2*x^71 - x^69 - 2/5*x^68 + 5*x^67 - 59*x^66 + x^65 -
3/56*x^63 - x^62 - 1/2*x^60 + x^59 - x^57 + x^56 + 31*x^55 + 2*x^54 -
2/15*x^53 + 2*x^52 - x^51 + 35/11*x^50 + 41/3*x^49 - 1/24*x^48 +
1/8*x^46 + 2*x^45 - x^44 + 9*x^43 - x^42 - 1/5*x^41 - 3/2*x^37 -
2/87*x^36 - 16*x^35 - 1/2*x^34 + 23/9*x^33 + 26*x^32 + x^31 - x^30 +
11*x^29 - x^28 + 1/4*x^27 - 1/2*x^26 - 1/2*x^25 + 2*x^24 - x^23 -
7*x^22 - 2*x^20 + 1/5*x^19 - x^17 + x^16 - 2/3*x^15 - 1/2*x^14 +
1/46*x^13 - x^12 - 1/6*x^11 - 3*x^10 + x^9 - 3*x^8 - 2/3*x^7 - x^6 -
x^5 + 17*x^2 - 2*x - 2
sage: d = f.denominator()
sage: timeit('f*f')
625 loops, best of 3: 1.57 ms per loop
sage: ff = pari(f)
sage: timeit('ff*ff')
625 loops, best of 3: 1.54 ms per loop
sage: g = (d*f).change_ring(ZZ)
sage: timeit('g*g')
625 loops, best of 3: 58.8 µs per loop
sage: gg = pari(g)
sage: timeit('gg*gg')
625 loops, best of 3: 435 µs per loop
sage: 1.57/0.058
27.0689655172414
sage: h = ntl.ZZX(g.list())
sage: timeit('h*h')
625 loops, best of 3: 389 µs per loop
>
> 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
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
