#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):
Actually, I am not quite sure about this. When working with a random
polynomial of degree 2000, which will have lots of non-zero entries all of
type fmpz_t, it shouldn't really matter whether we manually initialise a
few more for the denominators.
I've tried implementing the denominator with the convention that it is
either ``NULL`` (which should be interpreted as one) or initialised to a
positive integer. But this didn't really change the performance.
Another idea, which will sometimes help to keep numbers small, is to
instead represented the polynomial over the rationals as ``(num / dem)
prim`` where ``num / dem`` is a rational number in reduced form and
``prim`` is a primitive integer polynomial with positive leading
coefficient. Obviously, this change vastly improved the performance of
negation (which then only operates on the rational number and leaves the
integer polynomial part alone). But it didn't change much apart from
that. Anyway, given we need to compute the content of the numerator
anyway to ensure that it is coprime to the denominator, we might as well
store it separately. I'll implement this throughout the patch and upload
a new version later today.
This still leaves the problem: How can we speed up addition?
At the moment, I don't have any further ideas. In fact, I think it might
perhaps be the case that we simply can't, since in this kind of
implementation we have to at least do a few polynomial scalar
multiplications (and perhaps polynomial scalar divisions as well as
integer gcd computations to maintain the form of the representation) plus
all the coefficient additions. In contrast to this, implementing
polynomials as an array of coefficients one only has to do the (rational!)
coefficient additions.
So the next things I'll do are
- Change the fmpq_poly_t data type
- Change all the methods accordingly
- Write docstrings
Does anyone have any ideas about the addition?
Sebastian
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4000#comment:11>
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
-~----------~----~----~----~------~----~------~--~---
