#4000: [with patch, needs work] Implement QQ['x'] via Flint ZZ['x'] +
denominator
------------------------------+---------------------------------------------
Reporter: malb | Owner: somebody
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: basic arithmetic | Keywords:
Reviewer: | Author: Martin Albrecht
Merged: |
------------------------------+---------------------------------------------
Comment(by spancratz):
Thanks for the quick debugging and making the code accessible in SAGE for
testing! I'll upload a new version of the patch later. Here are a few
(unsorted) remarks:
- The printing isn't "nice" yet: Rationals are still printed in the form
r/s even if s divides r. In fact, all coefficients are printed with the
common denominator of the polynomial. I've got an idea of how to fix
that, but I am not sure it'll work; I'll give it a try later.
- Say we set up to polynomial rings R[x] and S[y], one using the generic
implementation and one using FLINT. Then sometimes (usually?) coercion
like "f_flint = S(f_generic)" or "f_generic = R(f_flint)" works, but
sometimes it ends in a segfault. For two random polynomials f and d, of
two successive calls "q, s, t = xgcd(f, d)" the first one succeeded and
the second one ended in a segfault. This seems *very* strange to me!
- We achieve a performance gain except in the cases of addition and
subtraction. (See below.)
- The method xgcd doesn't give the right result yet, I'll look into that
later.
- I have no idea what you mean by "Note that there is still some
conversion code missing in polynomial_rational_flint.pyx." Are there any
examples of this in other files?
- I'll write up the doctests later. Regarding your comments on using the
"old" documentation style, I don't quite understand this.
Here is a complete (except for XGCD) list of performance comparisons,
using the local installation of SAGE 4.1.2.alpha0 plus this patch on my
laptop (Ubuntu 8.10, Intel Core 2 Duo). The first few tests, from
comparison through to power, involve random polynomials f and g of degrees
2000, the division tests use random polynomials f and d of degrees 800 and
560, and for the GCD test f and d have degree 60 and 42. In each case,
the first output line is for the generic implementation, the second output
line is for the new implementation using FLINT.
{{{
Comparison: f == g
1 loops, best of 3: 10 µs per loop
1 loops, best of 3: 954 ns per loop
Comparison: f < g
1 loops, best of 3: 11 µs per loop
1 loops, best of 3: 1.91 µs per loop
Addition: f + g
1 loops, best of 3: 373 µs per loop
1 loops, best of 3: 2.26 ms per loop
Subtraction: f - g
1 loops, best of 3: 474 µs per loop
1 loops, best of 3: 2.23 ms per loop
Negation: -f
1 loops, best of 3: 12.9 ms per loop
1 loops, best of 3: 39.8 µs per loop
Multiplication: f * g
1 loops, best of 3: 549 ms per loop
1 loops, best of 3: 15.9 ms per loop
Power: f ** 4
1 loops, best of 3: 15.1 s per loop
1 loops, best of 3: 63.7 ms per loop
Division: q, r = f.quo_rem(d)
1 loops, best of 3: 2.42 s per loop
1 loops, best of 3: 177 ms per loop
Division: q = f // d
1 loops, best of 3: 2.43 s per loop
1 loops, best of 3: 63.9 ms per loop
Division: r = f % d
1 loops, best of 3: 2.43 s per loop
1 loops, best of 3: 193 ms per loop
GCD
1 loops, best of 3: 1.81 s per loop
1 loops, best of 3: 88.9 µs per loop
}}}
Sebastian
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4000#comment:8>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
