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

Priority:  major  Milestone:  sage6.4 
Component:  finite rings  Keywords:  flint finite field 
Cc:  defeo, pbruin, erousseau  Merged in:  
Authors:  JeanPierre Flori  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/jpflori/flint_fq_nmod (Commits)  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 6 years ago by
comment:2 Changed 6 years ago by
 Branch set to u/jpflori/flint_fq
 Commit set to 1ba3dbfd2f4700471bbf6eb86296d9f39451ee74
New commits:
1ba3dbf  First draty implementation of finite fields using FLINT's fq module.

comment:3 Changed 6 years ago by
 Cc defeo pbruin added
 Summary changed from Add a finite field implementation using FLINT's fq[_zech] module to Add a finite field implementation using FLINT's fq[_zech/_nmod] module
comment:4 Changed 6 years ago by
 Commit changed from 1ba3dbfd2f4700471bbf6eb86296d9f39451ee74 to fa877df7449b292bd63d09163ba308aa34036e7d
comment:5 Changed 6 years ago by
 Commit changed from fa877df7449b292bd63d09163ba308aa34036e7d to 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 6 years ago by
 Commit changed from ae3034c2d3254fe2c843bb7d26d682e47d7824ea to c7990f8fb70f3c6d052d00c57fc09bd2716fe78d
Branch pushed to git repo; I updated commit sha1. New commits:
c7990f8  Implement correct polynomial method for FiniteFieldElement_flint_fq.

comment:7 Changed 6 years ago by
 Commit changed from c7990f8fb70f3c6d052d00c57fc09bd2716fe78d to e9bfa5887be1c77dd1869d898f89af03c7f0479f
comment:8 Changed 6 years ago by
 Commit changed from e9bfa5887be1c77dd1869d898f89af03c7f0479f to 4efb03a482b3ad3118876c75da52b1563a960415
Branch pushed to git repo; I updated commit sha1. New commits:
4efb03a  Fix comparison for gf flint implem.

comment:9 Changed 6 years ago by
 Commit changed from 4efb03a482b3ad3118876c75da52b1563a960415 to 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 6 years ago by
 Commit changed from 96d5d9db45a9d62d1777b0a6ae0b7e3d3d10840b to 4b8c871640d032621f41bd2bf7c324b9f67c6fd1
comment:11 Changed 6 years ago by
 Commit changed from 4b8c871640d032621f41bd2bf7c324b9f67c6fd1 to 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 6 years ago by
 Dependencies set to #15767
 Description modified (diff)
 Status changed from new to needs_review
 Summary changed from Add a finite field implementation using FLINT's fq[_zech/_nmod] module to 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 6 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 6 years ago by
 Branch changed from u/jpflori/flint_fq to u/jpflori/flint_fq_nmod
 Commit changed from 9e9d2efc8a3c52ed963e36ecf448e2fe9207cd13 to b2021706d46596756ff50faaef67bdafda42b7ef
 Description modified (diff)
 Summary changed from Add a finite field implementation using FLINT's fq module to Add a finite field implementation using FLINT's fq and fq_nmod modules
comment:15 Changed 6 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 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:17 Changed 6 years ago by
 Commit changed from b2021706d46596756ff50faaef67bdafda42b7ef to 5eaa6bbcc00f4d8273d4b7ca4b7be309da8002a3
comment:18 Changed 6 years ago by
 Commit changed from 5eaa6bbcc00f4d8273d4b7ca4b7be309da8002a3 to 80079e426c92a207966a260219573a212e69cdf3
comment:19 Changed 6 years ago by
 Commit changed from 80079e426c92a207966a260219573a212e69cdf3 to bc8168002652630cdfd760a2317e8f23068b98bd
comment:20 Changed 6 years ago by
 Commit changed from bc8168002652630cdfd760a2317e8f23068b98bd to 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 6 years ago by
 Commit changed from 0661730ac7103071624b93cbee8ba22a1ed81c58 to 16243d1af505576bb260aee467c8b80b5cbb0921
Branch pushed to git repo; I updated commit sha1. New commits:
16243d1  Fix comparison for FLINT implems of FFs.

comment:22 Changed 6 years ago by
 Commit changed from 16243d1af505576bb260aee467c8b80b5cbb0921 to de8d00fae0ea6040ce69e69f76fdbe4ff60df03d
comment:23 Changed 6 years ago by
 Commit changed from de8d00fae0ea6040ce69e69f76fdbe4ff60df03d to b4fa9ea343e1cdd141918193a358f05608d27c67
Branch pushed to git repo; I updated commit sha1. New commits:
b4fa9ea  Fix for FFs implem using flint fq_nmod module.

comment:24 Changed 5 years ago by
 Status changed from needs_review to needs_work
Needs to be merged.
comment:25 Changed 5 years ago by
 Commit changed from b4fa9ea343e1cdd141918193a358f05608d27c67 to dfef37bb379c05d3dc35b347c40aa081eaf7fb4c
Branch pushed to git repo; I updated commit sha1. New commits:
dfef37b  A little more info for fmpz_poly struct.

comment:26 Changed 5 years ago by
 Commit changed from dfef37bb379c05d3dc35b347c40aa081eaf7fb4c to 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 5 years ago by
Should merge cleanly now.
Still needs a git version of FLINT though.
comment:28 Changed 5 years ago by
 Commit changed from ea72beba1a744f569b26e9157f644d9e59682da7 to 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 5 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 5 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 5 years ago by
comment:32 followups: ↓ 33 ↓ 34 Changed 5 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 in reply to: ↑ 32 Changed 5 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 in reply to: ↑ 32 Changed 5 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 5 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 5 years ago by
 Commit changed from ef5c3384da2ee07672bd5863872b329e43fa9104 to 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 5 years ago by
 Dependencies changed from #15767 to #15767, #17165
comment:38 Changed 5 years ago by
comment:39 Changed 5 years ago by
 Commit changed from 3fb1b2c7a379d21a377470049637ee0b26f221ea to 63657757e4a1a72fbfa827f3eb48301f88cd8ee6
Branch pushed to git repo; I updated commit sha1. New commits:
6365775  Use FLINT long types for FF classes.

comment:40 Changed 5 years ago by
 Commit changed from 63657757e4a1a72fbfa827f3eb48301f88cd8ee6 to a6649d20a035ece47107b152b91e4c06ab9dae3e
comment:41 Changed 5 years ago by
 Commit changed from a6649d20a035ece47107b152b91e4c06ab9dae3e to bb465ee801dc2dd650c4c215a0840085476cb1ba
comment:42 Changed 5 years ago by
 Commit changed from bb465ee801dc2dd650c4c215a0840085476cb1ba to 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 5 years ago by
 Dependencies changed from #15767, #17165 to ???
comment:44 Changed 5 years ago by
 Dependencies changed from ??? to #15015, #17470 ???
comment:45 Changed 5 years ago by
 Dependencies changed from #15015, #17470 ??? to #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 5 years ago by
 Commit changed from 55ef7dfcc3190f574a833c7c5f8587a6c25886b8 to 07105b7292261e537ee3e23f62d15860aeaf4ab5
comment:47 Changed 5 years ago by
 Commit changed from 07105b7292261e537ee3e23f62d15860aeaf4ab5 to 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 5 years ago by
 Status changed from needs_work to needs_review
comment:49 Changed 5 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 5 years ago by
 Commit changed from 76513171cd0217c216bed2bb3be6d89ee7c12e5a to 2ef5f6bb5ddd910d30d707f50c4e76bdbe4d107e
Branch pushed to git repo; I updated commit sha1. New commits:
2ef5f6b  Remove rational reconstruction code from FF base class.

comment:51 Changed 5 years ago by
 Status changed from needs_review to needs_work
 Work issues set to rebasing
comment:52 Changed 5 years ago by
 Commit changed from 2ef5f6bb5ddd910d30d707f50c4e76bdbe4d107e to 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 5 years ago by
 Status changed from needs_work to needs_review
 Work issues rebasing deleted
comment:54 Changed 5 years ago by
 Commit changed from a6d7614c0fd0dc5b31ed307e86b6edeb3f167d9c to 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 5 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 in reply to: ↑ 55 ; followup: ↓ 60 Changed 5 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 5 years ago by
Another small comment: you can replace
ctypedef struct X: pass
by
ctypedef struct X
comment:58 Changed 5 years ago by
 Commit changed from 83e71947185a138af370142c42ee56bdcc6c1f73 to 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 5 years ago by
 Commit changed from f5e05a4c15655a5590f0f3684a4d4fb340418610 to 822513dd822a392bd6fd20a6d3369be63a503e35
comment:60 in reply to: ↑ 56 ; followup: ↓ 64 Changed 5 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:61 Changed 5 years ago by
Ok, there is also a slight modification to types.h
.
comment:62 in reply to: ↑ 57 Changed 5 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 5 years ago by
 Commit changed from 822513dd822a392bd6fd20a6d3369be63a503e35 to 9587ba65d705fd9480d380908e31ba000565d676
Branch pushed to git repo; I updated commit sha1. New commits:
9587ba6  Merge remotetracking branch 'trac/develop' into flint_fq_nmod

comment:64 in reply to: ↑ 60 ; followup: ↓ 65 Changed 5 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 in reply to: ↑ 64 Changed 5 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 5 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 in reply to: ↑ 66 ; followup: ↓ 68 Changed 5 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 in reply to: ↑ 67 Changed 5 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 5 years ago by
 Status changed from needs_review to needs_work
Conflicts with the flint upgrade (#19009).
comment:70 Changed 4 years ago by
 Dependencies changed from #15015, #17470 to #19646
comment:71 Changed 4 years ago by
Conflicts with 6.10.beta6. If you fix this conflict, I can easily merge #19646.
comment:72 Changed 3 years ago by
 Cc erousseau added
comment:73 Changed 3 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/implementation
I've set up something at
u/jpflori/flint_fq
. Completely incomplete though.