#18585: Comparison of sparse polynomials
-------------------------+-------------------------------------------------
Reporter: bruno | Owner:
Type: PLEASE | Status: new
CHANGE | Milestone: sage-6.8
Priority: major | Keywords: polynomials
Component: | Authors: Bruno Grenet
commutative algebra | Report Upstream: N/A
Merged in: | Branch:
Reviewers: | u/bruno/compare_sparse_polynomials
Work issues: | Dependencies:
Commit: |
Stopgaps: |
-------------------------+-------------------------------------------------
Currently, the default `_cmp_` is written with dense polynomials in mind
since it creates an `xrange` of size the degree of the polynomial. For
sparse polynomials which can have very high degree, this is a problem:
{{{#!python
sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: x^2^100 == x^2^100
Traceback (most recent call last)
...
OverflowError: Python int too large to convert to C long
}}}
The patch introduces a `_cmp_` method in the class
`Polynomial_generic_sparse` to get rid of this problem:
{{{#!python
sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: x^2^100 == x^2^100
True
}}}
Note, as a side comment, that the comparison is faster for polynomials
that are indeed sparse with the new code, while the timings are equivalent
for quite dense polynomials.
Without the patch:
{{{#!python
sage: %timeit x^100 == x^100
1000 loops, best of 3: 224 µs per loop
}}}
With the patch:
{{{#!python
sage: %timeit x^100 == x^100
The slowest run took 7.61 times longer than the fastest. This could mean
that an intermediate result is being cached
10000 loops, best of 3: 24.6 µs per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/18585>
Sage <http://www.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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
