search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.22k stars 424 forks source link

Add a finite field implementation using FLINT's fq and fq_nmod modules #16664

Open jpflori opened 10 years ago

jpflori commented 10 years ago

Implement finite fields using flint fq and fq_nmod types.

Depends on #19646

CC: @defeo @pjbruin @sagetrac-erousseau

Component: finite rings

Keywords: flint finite field

Author: Jean-Pierre Flori

Branch/Commit: u/jpflori/flint_fq_nmod @ 9587ba6

Issue created by migration from https://trac.sagemath.org/ticket/16664

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from ea72beb to ef5c338

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

72dbde0Merge remote-tracking branch 'trac/develop' into flint_fq_nmod
fff00d4Cleanup/reorganization of FLINT imports
07780b1Merge remote-tracking branch 'trac/u/jdemeyer/ticket/16428' into flint_fq_nmod
ce22602Cleanup/reorganization of FLINT imports
ef5c338Merge remote-tracking branch 'trac/u/jdemeyer/ticket/16428' into flint_fq_nmod
jdemeyer commented 9 years ago
comment:29

Could you please explicitly list in "Dependencies" the tickets which are merged in this branch? I'm a bit lost in the git forest.

jdemeyer commented 9 years ago
comment:30

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?

jdemeyer commented 9 years ago
comment:31

Also, be aware of #16983 and #16855 which could potentially conflict.

jpflori commented 9 years ago
comment:32

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.

jdemeyer commented 9 years ago
comment:33

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.

jdemeyer commented 9 years ago
comment:34

Replying to @jpflori:

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.

Perhaps. I noticed you moved some functions to element_base.pyx in your branch, could that be made into a separate ticket?

jpflori commented 9 years ago
comment:35

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from ef5c338 to 3fb1b2c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

1607b8fMerge remote-tracking branch 'origin/develop' into ticket/15015
7725122Cosmetic changes
6957f17Merge remote-tracking branch 'origin/develop' into ticket/15015
aca71cbUpgrade to mpir-2.7.0-alpha12
67babebFix doctests due to changed xgcd results
8c7fbbdRe-enable "not tested" test from #4357
08fdc35Merge remote-tracking branch 'trac/u/jdemeyer/ticket/15015' into mpir
2cd2132Merge branch 'flint_pxd' into flint_fq_nmod
ab4e114Use flint long types.
3fb1b2cAvoid conversion from long to integer when building flint ff element.
jpflori commented 9 years ago

Changed dependencies from #15767 to #15767, #17165

jpflori commented 9 years ago
comment:38

Groumpf, I accidently merged #17148 and #15015 into this one... Not really a problem as we'll probably have to wait for a proper FLINT 2.5 for this one, and that should come after the actual MPIR 2.7.0 release.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 3fb1b2c to 6365775

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

6365775Use FLINT long types for FF classes.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

70df924Refactor some methods for finite fields elements.
6ffc64dCleanup unused code and move doctests for finite field elements.
a6649d2Merge branch 'ticket/17165' into flint_fq_nmod
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 6365775 to a6649d2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

c21dbbcMerge remote-tracking branch 'trac/develop' into flint_fq_nmod
bb465eeProper memory allocation for FLINT FF's modules.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from a6649d2 to bb465ee

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

0aed331Make modular exponentiation of polynomial using FLINT interruptable.
ef28e27Better fix for exponentiation of polys using FLINT nmod and test.
2bf519bMerge branch 'ticket/17470' into flint_fq_nmod
55ef7dfSimplify FLINT C types use.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from bb465ee to 55ef7df

jdemeyer commented 9 years ago

Changed dependencies from #15767, #17165 to ???

jdemeyer commented 9 years ago

Changed dependencies from ??? to #15015, #17470 ???

jpflori commented 9 years ago

Changed dependencies from #15015, #17470 ??? to #15015, #17470

jpflori commented 9 years ago
comment:45

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

53db8ccMerge branch 'ticket/17470' into flint_fq_nmod
07105b7Merge remote-tracking branch 'trac/develop' into flint_fq_nmod
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 55ef7df to 07105b7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 07105b7 to 7651317

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

08d4719Merge branch 'ticket/17165' into flint_fq_nmod
dcec4b9Merge branch 'ticket/17165' into flint_fq_nmod
44b6b40Merge remote-tracking branch 'trac/develop' into flint_fq_nmod
7651317Merge remote-tracking branch 'trac/u/jpflori/flint_fq_nmod' into flint_fq_nmod
jdemeyer commented 9 years ago
comment:49

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

2ef5f6bRemove rational reconstruction code from FF base class.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 7651317 to 2ef5f6b

jpflori commented 9 years ago

Work Issues: rebasing

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

a6d7614Fix `_cmp_` and cdefs.pxi for flint FF implem.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 2ef5f6b to a6d7614

jpflori commented 9 years ago

Changed work issues from rebasing to none

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

83e7194Merge branch 'develop' into flint_fq_nmod
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from a6d7614 to 83e7194

jpflori commented 9 years ago
comment:55

@jdemeyer: 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?

jdemeyer commented 9 years ago
comment:56

Replying to @jpflori:

@jdemeyer: 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 FLINT-related changes to module_list.py. The new ticket should probably depend on #18837.

jdemeyer commented 9 years ago
comment:57

Another small comment: you can replace

    ctypedef struct X:
        pass

by

    ctypedef struct X
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

d597b9aMerge remote-tracking branch 'trac/develop' into flint_fq_nmod
4b08519Metaclass for inheriting comparison functions
ac96e64Merge branch 'develop' into t/18329/ticket/18329
0e0301aFix documentation
f6058e7Use sage_getfile instead of inspect.getfile
54ff301Merge remote-tracking branch 'trac/u/jdemeyer/ticket/18329' into flint_fq_nmod
f5e05a4Remove comparison boilerplate.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 83e7194 to f5e05a4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

ac28f6cLet FLINT 2.4.5 pretty print fq_nmod elements.
a62af73Add FLINT fix for buggy fq_nmod traces.
822513dFix tests for latest Sage dev version.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from f5e05a4 to 822513d

jpflori commented 9 years ago
comment:60

Replying to @jdemeyer:

Replying to @jpflori:

@jdemeyer: 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.

jpflori commented 9 years ago
comment:61

Ok, there is also a slight modification to types.h.

jpflori commented 9 years ago
comment:62

Replying to @jdemeyer:

Another small comment: you can replace

    ctypedef struct X:
        pass

by

    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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

9587ba6Merge remote-tracking branch 'trac/develop' into flint_fq_nmod
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 822513d to 9587ba6