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)

trac2357_make_flint_default_for_ZZx.patch (77.8 KB) - added by burcin 11 years ago.
change ZZ[x] backend to FLINT
trac2357_make_flint_default_for_ZZx-edited.patch (45.0 KB) - added by cwitty 11 years ago.
trac2357-poly-ring-implementation.patch (20.8 KB) - added by cwitty 11 years ago.
trac2357_make_flint_default_for_ZZx-v2.patch (45.8 KB) - added by burcin 11 years ago.
revised patch adding FLINT wrappers for ZZ[x]
trac-2357-pt3.patch (27.8 KB) - added by craigcitro 11 years ago.
apply after burcin's v2 patch and carl's patch
default-flint-polys.hg (14.6 KB) - added by craigcitro 11 years ago.
single bundle with all three relevant patches

Download all attachments as: .zip

Change History (22)

comment:1 Changed 11 years ago by malb

  • Owner changed from malb to boothby

I think Tom wanted to look into this.

Changed 11 years ago by burcin

change ZZ[x] backend to FLINT

comment:2 Changed 11 years ago by burcin

  • 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 burcin

  • 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 craigcitro

  • Keywords editor_craigcitro added

comment:5 Changed 11 years ago by dmharvey

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 craigcitro

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 dmharvey

Ok great.

(BTW the ticket number is so cool! Four consecutive primes!)

comment:8 Changed 11 years ago by boothby

  • 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 craigcitro

  • 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 cwitty

comment:10 Changed 11 years ago by cwitty

  • 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 dmharvey

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.

Changed 11 years ago by burcin

revised patch adding FLINT wrappers for ZZ[x]

comment:12 Changed 11 years ago by burcin

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 craigcitro

  • 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']

Changed 11 years ago by craigcitro

apply after burcin's v2 patch and carl's patch

Changed 11 years ago by craigcitro

single bundle with all three relevant patches

comment:14 Changed 11 years ago by craigcitro

  • 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 was

  • 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 mabshoff

  • 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

Note: See TracTickets for help on using tickets.