Opened 12 years ago
Closed 11 years ago
#2357 closed enhancement (fixed)
[with patch, with positive review] make FLINT the default for ZZ['x']
Reported by: | mhansen | Owned by: | burcin |
---|---|---|---|
Priority: | critical | Milestone: | sage-3.0.4 |
Component: | basic arithmetic | Keywords: | editor_craigcitro |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Attachments (6)
Change History (22)
comment:1 Changed 11 years ago by
- Owner changed from malb to boothby
comment:2 Changed 11 years ago by
- Component changed from commutative algebra to basic arithmetic
- Owner changed from boothby to burcin
- Priority changed from major to critical
- Status changed from new to assigned
- Type changed from defect to enhancement
attachment:trac2357_make_flint_default_for_ZZx.patch replaces sage/rings/polynomial/polynomial_integer_dense_ntl.*
in the tree with sage/rings/polynomial/polynomial_integer_dense_flint.*
and makes FLINT the default backend for ZZ[x] arithmetic.
FLINT 1.0.10 is required for the patch, you can get the spkg here:
http://sage.math.washington.edu/home/burcin/spkg/flint-1.0.10.spkg
comment:3 Changed 11 years ago by
- Summary changed from make FLINT the default for ZZ['x'] to [with patch, needs review] make FLINT the default for ZZ['x']
comment:4 Changed 11 years ago by
- Keywords editor_craigcitro added
comment:5 Changed 11 years ago by
Now wait a second.... what if I *want* to use the NTL backend? Don't I even have that option any more? Why are we deleting all that code?
comment:6 Changed 11 years ago by
No, no, we're not. Don't worry. There was some miscommunication about this at some point, but we're definitely keeping all the code, and we're going to have the polynomial ring constructor take a flag that lets you choose between FLINT and NTL, with FLINT being the new default.
I'm going to implement this soon (within a week, I think).
comment:7 Changed 11 years ago by
Ok great.
(BTW the ticket number is so cool! Four consecutive primes!)
comment:8 Changed 11 years ago by
- Summary changed from [with patch, needs review] make FLINT the default for ZZ['x'] to [with patch, needs doctest] make FLINT the default for ZZ['x']
Builds fine, all tests pass. Coverage report:
Missing doctests: * div(self, other) Possibly wrong (function name doesn't occur in doctests): * Integer content(self) * _repr(self, name=None, bint latex=False) * _latex_(self, name=None) * bint is_zero(self) * _pari_(self, variable=None)
comment:9 Changed 11 years ago by
- Summary changed from [with patch, needs doctest] make FLINT the default for ZZ['x'] to [with patch, needs additional patch] make FLINT the default for ZZ['x']
This needs someone (I'm going to do it soon, unless someone does it before me) to write some code that allows one to use ZZ['x']
via NTL if one wishes, as a flag to the polynomial constructor.
Changed 11 years ago by
Changed 11 years ago by
comment:10 Changed 11 years ago by
- Summary changed from [with patch, needs additional patch] make FLINT the default for ZZ['x'] to [with patch, needs review] make FLINT the default for ZZ['x']
I've attached two patches. The first, trac2357_make_flint_default_for_ZZx-edited.patch, is a hand-edited version of Burcin's patch that does not delete the NTL wrapper. The second patch, trac2357-poly-ring-implementation.patch, adds an "implementation=" parameter to PolynomialRing?, so that you get:
sage: PolynomialRing(ZZ, 'x') Univariate Polynomial Ring in x over Integer Ring sage: PolynomialRing(ZZ, 'x', implementation='NTL') Univariate Polynomial Ring in x over Integer Ring (using NTL)
(the first version uses FLINT, which is the default).
comment:11 Changed 11 years ago by
I haven't tried the code yet, but two comments just from glancing over it:
- sparsenes => sparseness
- Somewhere, possibly in the docstring for the polynomial ring constructor, should include a WARNING that FLINT's data representation is extremely bad for certain polynomials. It is a "more dense" representation than NTL, in the sense that each coefficient takes up the same amount of space, even zero coefficients. This means for example that you try to create the polynomial
2^10000000 x^10000000
, the NTL implementation is probably okay with that, but the FLINT one will run out of memory.
comment:12 Changed 11 years ago by
attachment:trac2357_make_flint_default_for_ZZx-v2.patch fixes some problems with my previous patch. This version supersedes the older files.
Changes:
- Add signal wrapper macros in various places to allow the user to interrupt the computation.
- Handle division by zero in
__floordiv__
, which led to a crash with the previous patch.
comment:13 Changed 11 years ago by
- Summary changed from [with patch, needs review] make FLINT the default for ZZ['x'] to [with patch, under review by craigcitro before 7/2] make FLINT the default for ZZ['x']
comment:14 Changed 11 years ago by
- Summary changed from [with patch, under review by craigcitro before 7/2] make FLINT the default for ZZ['x'] to [with patch, with positive review, needs review of third patch] make FLINT the default for ZZ['x']
REFEREE REPORT:
This looks great!
- The FLINT wrapper is excellent. I haven't tried out too many corner cases beyond what the doctests do, but everything looks good. Of course, with FLINT, things are really fast: William and I tried out a benchmark that gets used in modular symbols code, and FLINT is something like 10-12X faster than NTL, and 2X as fast as Magma. And now it's in by default ...
- Carl's work on setting up the
implementation='NTL'
is also great. It's very easy to use NTL if you choose, and Carl was also quite conscientious about this: notice the changes in the doctests, for instance.
Given how much work was already done, I've just gone ahead and fixed the small issues I ran into in another patch. There were a handful of small typos, and a few functions that weren't doctested, so I've added doctests for all of these. Both polynomial_integer_dense_ntl.pyx
and polynomial_integer_dense_flint.pyx
are now at 100% coverage.
In doing this, I noticed that the div
function has the same functionality as //
(i.e. __floordiv__
), so I removed it uniformly throughout sage. (I first removed it in this code, and then found out this was used elsewhere, so it had to go elsewhere, too.) In doing so, I also noticed that our convention for a%b
in the case of b<0
also went against all the standard conventions, so I fixed that.
Someone should probably look over the changes I've made, and give them a positive review. Once that happens, this is ready to get merged. One can merge the three patches in order, or just use the bundle (which actually only has those three changesets) I've attached.
comment:15 Changed 11 years ago by
- Summary changed from [with patch, with positive review, needs review of third patch] make FLINT the default for ZZ['x'] to [with patch, with positive review] make FLINT the default for ZZ['x']
I looked over the new patch added by Craig (the referee) and I'm happy with it.
comment:16 Changed 11 years ago by
- Milestone changed from sage-3.1.1 to sage-3.0.4
- Resolution set to fixed
- Status changed from assigned to closed
Merged default-flint-polys.hg in Sage 3.0.4.alpha2
I think Tom wanted to look into this.