Fast lexicographic iterator for module over ZZ/nZZ

[videlec]

We implement a reasonably fast lexicographic iterator for modules over ZZ/nZZ. We integrate a minimum_weight method that could be used as an alternative to GAP in some part of sage.codings.

Setup

sage: R = IntegerModRing(6)
sage: M = FreeModule(R, 4)
sage: U = M.span([M((1,1,0,2)), M((2,2,3,0))])

Before

sage: timeit('for u in M: pass')
25 loops, best of 3: 9.11 ms per loop

sage: timeit('for u in U: pass')
625 loops, best of 3: 641 µs per loop

After

sage: timeit('for u in M: pass')
625 loops, best of 3: 283 µs per loop

sage: timeit('for u in U: pass')
625 loops, best of 3: 41.5 µs per loop

Depends on #6452

CC: @johanrosenkilde @sagetrac-dlucas

Component: coding theory

Author: Vincent Delecroix

Branch/Commit: u/vdelecroix/19345 @ 5773c78

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

[videlec]

Dependencies: u/vdelecroix/19345

[videlec]

Changed branch from #6452 to u/vdelecroix/19345

[videlec]

New commits:

708863f	Trac 6452: free module over ZZ/nZZ and submodules
ebb2092	Trac 6452: adapt some tests to facade
a5e3d23	Trac 6452: fix a doctest
acd707c	Trac 6452: cleaner code + more doc
ffbd6e8	Trac 6452: simplification + more tests
9d7a2cd	Trac 19345: iterator for vector_modn_dense

[videlec]

Commit: 9d7a2cd

[videlec]

Changed dependencies from u/vdelecroix/19345 to #6452

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

59ab945	Trac 6452: free modules over ZZ/nZZ and submodules
96ead16	Trac 6452: fix a doctest
5773c78	Trac 19345: iterator for vector_modn_dense

[sagetrac-git]

Changed commit from 9d7a2cd to 5773c78

[videlec]

comment:4

rebased on #6452

[slel]

Description changed:

--- 
+++ 
@@ -1,17 +1,23 @@
 We implement a reasonably fast lexicographic iterator for modules over `ZZ/nZZ`. We integrate a `minimum_weight` method that could be used as an alternative to GAP in some part of `sage.codings`.
+
+Setup
+
+```
+sage: R = IntegerModRing(6)
+sage: M = FreeModule(R, 4)
+sage: U = M.span([M((1,1,0,2)), M((2,2,3,0))])
+```
 
 Before
 
 ```
-sage: R = IntegerModRing(6)
-sage: M = FreeModule(R, 4)
 sage: timeit('for u in M: pass')
 25 loops, best of 3: 9.11 ms per loop
 
-sage: U = M.span([M((1,1,0,2)), M((2,2,3,0))])
 sage: timeit('for u in U: pass')
 625 loops, best of 3: 641 µs per loop
 ```
+
 After
 
 ```

[videlec]

comment:6

Apparently not ready...