Opened 8 years ago
Last modified 6 years ago
#16664 needs_work enhancement
Add a finite field implementation using FLINT's fq and fq_nmod modules
Reported by:  JeanPierre Flori  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  finite rings  Keywords:  flint finite field 
Cc:  Luca De Feo, Peter Bruin, erousseau  Merged in:  
Authors:  JeanPierre Flori  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/jpflori/flint_fq_nmod (Commits, GitHub, GitLab)  Commit:  9587ba65d705fd9480d380908e31ba000565d676 
Dependencies:  #19646  Stopgaps: 
Description (last modified by )
Implement finite fields using flint fq and fq_nmod types.
Change History (73)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
Branch:  → u/jpflori/flint_fq 

Commit:  → 1ba3dbfd2f4700471bbf6eb86296d9f39451ee74 
New commits:
1ba3dbf  First draty implementation of finite fields using FLINT's fq module.

comment:3 Changed 8 years ago by
Cc:  Luca De Feo Peter Bruin added 

Summary:  Add a finite field implementation using FLINT's fq[_zech] module → Add a finite field implementation using FLINT's fq[_zech/_nmod] module 
comment:4 Changed 8 years ago by
Commit:  1ba3dbfd2f4700471bbf6eb86296d9f39451ee74 → fa877df7449b292bd63d09163ba308aa34036e7d 

comment:5 Changed 8 years ago by
Commit:  fa877df7449b292bd63d09163ba308aa34036e7d → ae3034c2d3254fe2c843bb7d26d682e47d7824ea 

Branch pushed to git repo; I updated commit sha1. New commits:
ae3034c  Make sure that the fq_ctx_t object is initialized when attempting to clean it.

comment:6 Changed 8 years ago by
Commit:  ae3034c2d3254fe2c843bb7d26d682e47d7824ea → c7990f8fb70f3c6d052d00c57fc09bd2716fe78d 

Branch pushed to git repo; I updated commit sha1. New commits:
c7990f8  Implement correct polynomial method for FiniteFieldElement_flint_fq.

comment:7 Changed 8 years ago by
Commit:  c7990f8fb70f3c6d052d00c57fc09bd2716fe78d → e9bfa5887be1c77dd1869d898f89af03c7f0479f 

comment:8 Changed 8 years ago by
Commit:  e9bfa5887be1c77dd1869d898f89af03c7f0479f → 4efb03a482b3ad3118876c75da52b1563a960415 

Branch pushed to git repo; I updated commit sha1. New commits:
4efb03a  Fix comparison for gf flint implem.

comment:9 Changed 8 years ago by
Commit:  4efb03a482b3ad3118876c75da52b1563a960415 → 96d5d9db45a9d62d1777b0a6ae0b7e3d3d10840b 

Branch pushed to git repo; I updated commit sha1. New commits:
96d5d9d  Fix return value of type for gf flint implem.

comment:10 Changed 8 years ago by
Commit:  96d5d9db45a9d62d1777b0a6ae0b7e3d3d10840b → 4b8c871640d032621f41bd2bf7c324b9f67c6fd1 

comment:11 Changed 8 years ago by
Commit:  4b8c871640d032621f41bd2bf7c324b9f67c6fd1 → 9e9d2efc8a3c52ed963e36ecf448e2fe9207cd13 

Branch pushed to git repo; I updated commit sha1. New commits:
9e9d2ef  Fix for pari conversion of flint implem of GF.

comment:12 Changed 8 years ago by
Dependencies:  → #15767 

Description:  modified (diff) 
Status:  new → needs_review 
Summary:  Add a finite field implementation using FLINT's fq[_zech/_nmod] module → Add a finite field implementation using FLINT's fq module 
Not thouroughly tested but it at least passes its testsuite.
Comments welcome.
comment:13 Changed 8 years ago by
I've also pushed another branch including an implem using the fq_nmod type at u/jpflori/flint_fq_nmod
.
Note that you'll need a FLINT version including my latest git commits from https://github.com/jpflori/flint2
At least now, FLINT seems to provide implementation faster than PARI for basic arithmetic over all ranges.
Doing the same thing for the fq_zech type should be as easy as for the fq_nmod type. But there is so much code duplication that it should definitely be templated (that should already be done for the fq and fq_nmod types alone). And not sure that the fq_zech type will be so useful as we have Givaro.
comment:14 Changed 8 years ago by
Authors:  → JeanPierre Flori 

Branch:  u/jpflori/flint_fq → u/jpflori/flint_fq_nmod 
Commit:  9e9d2efc8a3c52ed963e36ecf448e2fe9207cd13 → b2021706d46596756ff50faaef67bdafda42b7ef 
Description:  modified (diff) 
Summary:  Add a finite field implementation using FLINT's fq module → Add a finite field implementation using FLINT's fq and fq_nmod modules 
comment:15 Changed 8 years ago by
I'll do the templating stuff in a later tickets. It really needs more thoughts than what I already did here, especially if I want to convert some other implementations to it.
comment:16 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:17 Changed 8 years ago by
Commit:  b2021706d46596756ff50faaef67bdafda42b7ef → 5eaa6bbcc00f4d8273d4b7ca4b7be309da8002a3 

comment:18 Changed 8 years ago by
Commit:  5eaa6bbcc00f4d8273d4b7ca4b7be309da8002a3 → 80079e426c92a207966a260219573a212e69cdf3 

comment:19 Changed 8 years ago by
Commit:  80079e426c92a207966a260219573a212e69cdf3 → bc8168002652630cdfd760a2317e8f23068b98bd 

comment:20 Changed 8 years ago by
Commit:  bc8168002652630cdfd760a2317e8f23068b98bd → 0661730ac7103071624b93cbee8ba22a1ed81c58 

Branch pushed to git repo; I updated commit sha1. New commits:
0661730  Produce different (and nonzero...) hashes for FLINT implems of FFs.

comment:21 Changed 8 years ago by
Commit:  0661730ac7103071624b93cbee8ba22a1ed81c58 → 16243d1af505576bb260aee467c8b80b5cbb0921 

Branch pushed to git repo; I updated commit sha1. New commits:
16243d1  Fix comparison for FLINT implems of FFs.

comment:22 Changed 8 years ago by
Commit:  16243d1af505576bb260aee467c8b80b5cbb0921 → de8d00fae0ea6040ce69e69f76fdbe4ff60df03d 

comment:23 Changed 8 years ago by
Commit:  de8d00fae0ea6040ce69e69f76fdbe4ff60df03d → b4fa9ea343e1cdd141918193a358f05608d27c67 

Branch pushed to git repo; I updated commit sha1. New commits:
b4fa9ea  Fix for FFs implem using flint fq_nmod module.

comment:25 Changed 8 years ago by
Commit:  b4fa9ea343e1cdd141918193a358f05608d27c67 → dfef37bb379c05d3dc35b347c40aa081eaf7fb4c 

Branch pushed to git repo; I updated commit sha1. New commits:
dfef37b  A little more info for fmpz_poly struct.

comment:26 Changed 8 years ago by
Commit:  dfef37bb379c05d3dc35b347c40aa081eaf7fb4c → ea72beba1a744f569b26e9157f644d9e59682da7 

Branch pushed to git repo; I updated commit sha1. New commits:
ea72beb  Merge remotetracking branch 'trac/develop' into flint_fq_nmod

comment:27 Changed 8 years ago by
Should merge cleanly now.
Still needs a git version of FLINT though.
comment:28 Changed 8 years ago by
Commit:  ea72beba1a744f569b26e9157f644d9e59682da7 → ef5c3384da2ee07672bd5863872b329e43fa9104 

Branch pushed to git repo; I updated commit sha1. New commits:
72dbde0  Merge remotetracking branch 'trac/develop' into flint_fq_nmod

fff00d4  Cleanup/reorganization of FLINT imports

07780b1  Merge remotetracking branch 'trac/u/jdemeyer/ticket/16428' into flint_fq_nmod

ce22602  Cleanup/reorganization of FLINT imports

ef5c338  Merge remotetracking branch 'trac/u/jdemeyer/ticket/16428' into flint_fq_nmod

comment:29 Changed 8 years ago by
Could you please explicitly list in "Dependencies" the tickets which are merged in this branch? I'm a bit lost in the git forest.
comment:30 Changed 8 years ago by
I don't really like the fact that element_flint_fq_nmod.pyx
and element_flint_fq.pyx
are almost identical. Wouldn't it make sense to implement a common base class for them or use templating techniques?
comment:31 Changed 8 years ago by
comment:32 followups: 33 34 Changed 8 years ago by
This is really work in progress, so it's not really ready for review.
I thought very hard of templating but it was too much work for the time I had.
Note that the pari_ffelt
class at least (and maybe the pari_mod
one) is also very similar, so the templating/common base class should surely cover a wider area.
I'll fill in the dependencies asap.
comment:33 Changed 8 years ago by
Replying to jpflori:
This is really work in progress, so it's not really ready for review.
Sure, I just wanted to give some comments based on a first glance.
comment:34 Changed 8 years ago by
Replying to jpflori:
Note that the
pari_ffelt
class at least (and maybe thepari_mod
one) is also very similar, so the templating/common base class should surely cover a wider area.
Perhaps. I noticed you moved some functions to element_base.pyx
in your branch, could that be made into a separate ticket?
comment:35 Changed 8 years ago by
Ok, I'll try to do that (because I do agree it would be the good way to go and feel guilty about my dirty commits). There are also some other things related to the PARI FF implem that I'll try to move out of this ticket.
comment:36 Changed 8 years ago by
Commit:  ef5c3384da2ee07672bd5863872b329e43fa9104 → 3fb1b2c7a379d21a377470049637ee0b26f221ea 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
1607b8f  Merge remotetracking branch 'origin/develop' into ticket/15015

7725122  Cosmetic changes

6957f17  Merge remotetracking branch 'origin/develop' into ticket/15015

aca71cb  Upgrade to mpir2.7.0alpha12

67babeb  Fix doctests due to changed xgcd results

8c7fbbd  Reenable "not tested" test from #4357

08fdc35  Merge remotetracking branch 'trac/u/jdemeyer/ticket/15015' into mpir

2cd2132  Merge branch 'flint_pxd' into flint_fq_nmod

ab4e114  Use flint long types.

3fb1b2c  Avoid conversion from long to integer when building flint ff element.

comment:37 Changed 8 years ago by
Dependencies:  #15767 → #15767, #17165 

comment:38 Changed 8 years ago by
comment:39 Changed 8 years ago by
Commit:  3fb1b2c7a379d21a377470049637ee0b26f221ea → 63657757e4a1a72fbfa827f3eb48301f88cd8ee6 

Branch pushed to git repo; I updated commit sha1. New commits:
6365775  Use FLINT long types for FF classes.

comment:40 Changed 8 years ago by
Commit:  63657757e4a1a72fbfa827f3eb48301f88cd8ee6 → a6649d20a035ece47107b152b91e4c06ab9dae3e 

comment:41 Changed 8 years ago by
Commit:  a6649d20a035ece47107b152b91e4c06ab9dae3e → bb465ee801dc2dd650c4c215a0840085476cb1ba 

comment:42 Changed 8 years ago by
Commit:  bb465ee801dc2dd650c4c215a0840085476cb1ba → 55ef7dfcc3190f574a833c7c5f8587a6c25886b8 

Branch pushed to git repo; I updated commit sha1. New commits:
0aed331  Make modular exponentiation of polynomial using FLINT interruptable.

ef28e27  Better fix for exponentiation of polys using FLINT nmod and test.

2bf519b  Merge branch 'ticket/17470' into flint_fq_nmod

55ef7df  Simplify FLINT C types use.

comment:43 Changed 8 years ago by
Dependencies:  #15767, #17165 → ??? 

comment:44 Changed 8 years ago by
Dependencies:  ??? → #15015, #17470 ??? 

comment:45 Changed 8 years ago by
Dependencies:  #15015, #17470 ??? → #15015, #17470 

I guess the dependencies are correct now.
Apart from bug fixing and heavy testing, the real question is whether I should try to make some code factoring/templating now.
comment:46 Changed 8 years ago by
Commit:  55ef7dfcc3190f574a833c7c5f8587a6c25886b8 → 07105b7292261e537ee3e23f62d15860aeaf4ab5 

comment:47 Changed 8 years ago by
Commit:  07105b7292261e537ee3e23f62d15860aeaf4ab5 → 76513171cd0217c216bed2bb3be6d89ee7c12e5a 

Branch pushed to git repo; I updated commit sha1. New commits:
08d4719  Merge branch 'ticket/17165' into flint_fq_nmod

dcec4b9  Merge branch 'ticket/17165' into flint_fq_nmod

44b6b40  Merge remotetracking branch 'trac/develop' into flint_fq_nmod

7651317  Merge remotetracking branch 'trac/u/jpflori/flint_fq_nmod' into flint_fq_nmod

comment:48 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:49 Changed 8 years ago by
Like I said before, I still don't like that the fq
files are almost identical to the fq_nmod
files.
And instead of writing comments like
# JPF: the following should definitely go into element_base.pyx.
just do it (on a different ticket please, same for def rational_reconstruction
comment:50 Changed 8 years ago by
Commit:  76513171cd0217c216bed2bb3be6d89ee7c12e5a → 2ef5f6bb5ddd910d30d707f50c4e76bdbe4d107e 

Branch pushed to git repo; I updated commit sha1. New commits:
2ef5f6b  Remove rational reconstruction code from FF base class.

comment:51 Changed 8 years ago by
Status:  needs_review → needs_work 

Work issues:  → rebasing 
comment:52 Changed 8 years ago by
Commit:  2ef5f6bb5ddd910d30d707f50c4e76bdbe4d107e → a6d7614c0fd0dc5b31ed307e86b6edeb3f167d9c 

Branch pushed to git repo; I updated commit sha1. New commits:
a6d7614  Fix _cmp_ and cdefs.pxi for flint FF implem.

comment:53 Changed 8 years ago by
Status:  needs_work → needs_review 

Work issues:  rebasing 
comment:54 Changed 7 years ago by
Commit:  a6d7614c0fd0dc5b31ed307e86b6edeb3f167d9c → 83e71947185a138af370142c42ee56bdcc6c1f73 

Branch pushed to git repo; I updated commit sha1. New commits:
83e7194  Merge branch 'develop' into flint_fq_nmod

comment:55 followup: 56 Changed 7 years ago by
@Jeroen: where would you put the distutils magic to simplify linking with flint?
In only one pxd file in src/sage/libs/flint
which is included by all other ones?
Or in each of them?
comment:56 followup: 60 Changed 7 years ago by
Replying to jpflori:
@Jeroen: where would you put the distutils magic to simplify linking with flint? In only one pxd file in
src/sage/libs/flint
which is included by all other ones? Or in each of them?
First of all, I would prefer to move all changes to libs/flint
to a different ticket.
If you want distutils
magic, I would put it in every .pxd
file which defines library functions (in practice, this is probably all of them except types.pxd
).
Note #18837 which makes FLINTrelated changes to module_list.py
. The new ticket should probably depend on #18837.
comment:57 followup: 62 Changed 7 years ago by
Another small comment: you can replace
ctypedef struct X: pass
by
ctypedef struct X
comment:58 Changed 7 years ago by
Commit:  83e71947185a138af370142c42ee56bdcc6c1f73 → f5e05a4c15655a5590f0f3684a4d4fb340418610 

Branch pushed to git repo; I updated commit sha1. New commits:
d597b9a  Merge remotetracking branch 'trac/develop' into flint_fq_nmod

4b08519  Metaclass for inheriting comparison functions

ac96e64  Merge branch 'develop' into t/18329/ticket/18329

0e0301a  Fix documentation

f6058e7  Use sage_getfile instead of inspect.getfile

54ff301  Merge remotetracking branch 'trac/u/jdemeyer/ticket/18329' into flint_fq_nmod

f5e05a4  Remove comparison boilerplate.

comment:59 Changed 7 years ago by
Commit:  f5e05a4c15655a5590f0f3684a4d4fb340418610 → 822513dd822a392bd6fd20a6d3369be63a503e35 

comment:60 followup: 64 Changed 7 years ago by
Replying to jdemeyer:
Replying to jpflori:
@Jeroen: where would you put the distutils magic to simplify linking with flint? In only one pxd file in
src/sage/libs/flint
which is included by all other ones? Or in each of them?First of all, I would prefer to move all changes to
libs/flint
to a different ticket.
I only add new files needed by this ticket, I'm not sure it would make sense to add these files in another ticket.
comment:62 Changed 7 years ago by
Replying to jdemeyer:
Another small comment: you can replace
ctypedef struct X: passby
ctypedef struct X
Noted.
Note though that the other types in types.h
use the syntax with pass
.
So I'm not sure if we should not modify all of them at once later.
comment:63 Changed 7 years ago by
Commit:  822513dd822a392bd6fd20a6d3369be63a503e35 → 9587ba65d705fd9480d380908e31ba000565d676 

Branch pushed to git repo; I updated commit sha1. New commits:
9587ba6  Merge remotetracking branch 'trac/develop' into flint_fq_nmod

comment:64 followup: 65 Changed 7 years ago by
Replying to jpflori:
I only add new files needed by this ticket, I'm not sure it would make sense to add these files in another ticket.
But you were talking about adding # distutils: libraries = flint
, weren't you? I would suggest to do this on a new ticket. So, when you're changing libs/flint
anyway, you might as well add the new files too.
comment:65 Changed 7 years ago by
Replying to jdemeyer:
Replying to jpflori:
I only add new files needed by this ticket, I'm not sure it would make sense to add these files in another ticket.
But you were talking about adding
# distutils: libraries = flint
, weren't you? I would suggest to do this on a new ticket. So, when you're changinglibs/flint
anyway, you might as well add the new files too.
Oh yes, the distutils part should definitely be done elsewhere.
comment:66 followup: 67 Changed 7 years ago by
Hello,
In _element_constructor_
the following case should not happen
if isinstance(x, self.element_class) and x.parent() is self:
as if parent(x)
is self
then this is catched by the __call__
of Parent
. See line 10801083 of parent.pyx
cdef R = parent_c(x) cdef bint no_extra_args = len(args) == 0 and len(kwds) == 0 if R is self and no_extra_args: return x
Instead of making __nonzero__
relies on is_unit
I would rather implement __nonzero__
and call it in bot is_unit
and is_zero
. BTW for the latter this is what is in Element.is_zero
by default, so you can even remove it. The reason why is that there is a special slot for __nonzero__
in Python objects. So the fastest (Python) way to do things should be
if not my_element: XYZ
and not
if my_element.is_zero(): XYZ
What are the status of the flint patches? Are there incorporated in flint2.5? If that is so, it would make sense to first include it into Sage.
Vincent
comment:67 followup: 68 Changed 7 years ago by
Replying to vdelecroix:
Hello,
In
_element_constructor_
the following case should not happenif isinstance(x, self.element_class) and x.parent() is self:as if
parent(x)
isself
then this is catched by the__call__
ofParent
. See line 10801083 ofparent.pyx
cdef R = parent_c(x) cdef bint no_extra_args = len(args) == 0 and len(kwds) == 0 if R is self and no_extra_args: return xInstead of making
__nonzero__
relies onis_unit
I would rather implement__nonzero__
and call it in botis_unit
andis_zero
. BTW for the latter this is what is inElement.is_zero
by default, so you can even remove it. The reason why is that there is a special slot for__nonzero__
in Python objects. So the fastest (Python) way to do things should beif not my_element: XYZand not
if my_element.is_zero(): XYZ
Thanks, I'll have a look at both of these. Not that the code is mainly cpoied/pasted from the PARI wrapper by Peter Bruin. I'll also check the PARI wrapper. Note the PARI wrapper is Python rather than Cython (as we have already have a cython "proxy" for PARI elements).
What are the status of the flint patches? Are there incorporated in flint2.5? If that is so, it would make sense to first include it into Sage.
I guess so. Integrating flint 2.5 first is a good idea anyway. It will also allow to use the lacking in flint 2.4 fq_div function.
Vincent
comment:68 Changed 7 years ago by
Replying to jpflori:
Replying to vdelecroix:
What are the status of the flint patches? Are there incorporated in flint2.5? If that is so, it would make sense to first include it into Sage.
I guess so. Integrating flint 2.5 first is a good idea anyway. It will also allow to use the lacking in flint 2.4 fq_div function.
This is #19009 (needs review).
comment:69 Changed 7 years ago by
Status:  needs_review → needs_work 

Conflicts with the flint upgrade (#19009).
comment:70 Changed 7 years ago by
Dependencies:  #15015, #17470 → #19646 

comment:71 Changed 7 years ago by
Conflicts with 6.10.beta6. If you fix this conflict, I can easily merge #19646.
comment:72 Changed 6 years ago by
Cc:  erousseau added 

comment:73 Changed 6 years ago by
I guess the branch here is now completely broken. A more current implementation can be found at https://github.com/defeo/ffisom/
I've set up something at
u/jpflori/flint_fq
. Completely incomplete though.