Sage: Ticket #25477: possibly improve the iterator for PermutationGroups
https://trac.sagemath.org/ticket/25477
<p>
Currently, the iterator looks like this.
</p>
<pre class="wiki">def __iter__(self):
from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet
return iter(RecursivelyEnumeratedSet(seeds=[self.one()],
successors=lambda g: (g._mul_(h) for h in self.gens())))
</pre><p>
Perhaps it would be faster to use a strong_generating_system to iterate through the group.
</p>
enusSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/25477
Trac 1.1.6moritzThu, 31 May 2018 09:17:26 GMTbranch set
https://trac.sagemath.org/ticket/25477#comment:1
https://trac.sagemath.org/ticket/25477#comment:1
<ul>
<li><strong>branch</strong>
set to <em>u/moritz/enumerate_PermutationGroup</em>
</li>
</ul>
TicketmoritzThu, 31 May 2018 09:18:44 GMTcommit set
https://trac.sagemath.org/ticket/25477#comment:2
https://trac.sagemath.org/ticket/25477#comment:2
<ul>
<li><strong>commit</strong>
set to <em>74488fe1548ff39225a13540fd98ffb3c227fe9b</em>
</li>
</ul>
<p>
I added an alternative suggestion <code>__iter_alt__</code> in the patch. However, sometimes calculation the strong_generating_system takes much longer than actually iterating with the standard iterator above. Here are some timing experiments:
</p>
<pre class="wiki">sage: p = [(i,i+1) for i in range(1,601,2)]
sage: q = [tuple(range(1+i,601,3)) for i in range(3)]
sage: A = PermutationGroup([p,q])
sage: A.cardinality()
60000
sage: time len(list(A))
CPU times: user 441 ms, sys: 58 ms, total: 499 ms
Wall time: 478 ms
60000
sage: time len(list(A.__iter_alt__()))
CPU times: user 3.39 s, sys: 690 ms, total: 4.08 s
Wall time: 4.1 s
60000
sage: P = PermutationGroup(SymmetricGroup(10).gens())
sage: time len(list(P))
CPU times: user 9.06 s, sys: 182 ms, total: 9.24 s
Wall time: 9.24 s
3628800
sage: time len(list(P.__iter_alt__()))
CPU times: user 3.64 s, sys: 144 ms, total: 3.79 s
Wall time: 3.79 s
3628800
</pre><p>
Any suggestions? What are good other groups to do benchmarking?
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=74488fe1548ff39225a13540fd98ffb3c227fe9b"><span class="icon"></span>74488fe</a></td><td><code>a suggestion for an alternative iterator</code>
</td></tr></table>
TicketmoritzThu, 31 May 2018 13:56:57 GMT
https://trac.sagemath.org/ticket/25477#comment:3
https://trac.sagemath.org/ticket/25477#comment:3
<p>
More timings:
</p>
<pre class="wiki">sage: P = CoxeterGroup(["E",7], implementation="permutation")
sage: time len(list(P.iteration(algorithm="depth", tracking_words=False)))
CPU times: user 4.55 s, sys: 525 ms, total: 5.07 s
Wall time: 5.14 s
2903040
sage: time len(list(P.__iter__()))
CPU times: user 21.2 s, sys: 693 ms, total: 21.8 s
Wall time: 21.8 s
2903040
sage: time len(list(P.__iter_alt__()))
CPU times: user 4.33 s, sys: 231 ms, total: 4.56 s
Wall time: 4.58 s
2903040
</pre>
TickettscrimThu, 31 May 2018 14:06:45 GMTtype changed
https://trac.sagemath.org/ticket/25477#comment:4
https://trac.sagemath.org/ticket/25477#comment:4
<ul>
<li><strong>type</strong>
changed from <em>PLEASE CHANGE</em> to <em>enhancement</em>
</li>
</ul>
<p>
You can probably get some more speed by doing the initial step in the <code>__iter__</code> function and then do the remaining steps with <code>SGS</code> being explicitly given. It is probably faster to also do
</p>
<div class="wikicode"><div class="code"><pre> S <span class="o">=</span> SGS<span class="o">.</span>pop<span class="p">()</span>
<span class="k">if</span> <span class="ow">not</span> SGS<span class="p">:</span>
<span class="k">for</span> g <span class="ow">in</span> S<span class="p">:</span>
<span class="k">yield</span> g
<span class="k">else</span><span class="p">:</span>
<span class="k">for</span> s <span class="ow">in</span> elements<span class="p">(</span><span class="bp">self</span><span class="p">,</span> SGS<span class="p">):</span>
<span class="k">for</span> g <span class="ow">in</span> S<span class="p">:</span>
<span class="k">yield</span> s<span class="o">.</span>_mul_<span class="p">(</span>g<span class="p">)</span>
</pre></div></div>
TicketgitThu, 31 May 2018 15:48:23 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:5
https://trac.sagemath.org/ticket/25477#comment:5
<ul>
<li><strong>commit</strong>
changed from <em>74488fe1548ff39225a13540fd98ffb3c227fe9b</em> to <em>3594002f0dfc1c6223efd316ffb348c8ed6446e7</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=3594002f0dfc1c6223efd316ffb348c8ed6446e7"><span class="icon"></span>3594002</a></td><td><code>directly yield in the last step</code>
</td></tr></table>
TicketmoritzThu, 31 May 2018 15:50:55 GMT
https://trac.sagemath.org/ticket/25477#comment:6
https://trac.sagemath.org/ticket/25477#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:4" title="Comment 4">tscrim</a>:
</p>
<blockquote class="citation">
<p>
You can probably get some more speed by doing the initial step in the <code>__iter__</code> function and then do the remaining steps with <code>SGS</code> being explicitly given.
</p>
</blockquote>
<p>
I don't quite follow. We would still have to compute SGS in this case, won't we? This seems to be the slow part, at least in the first example above with 60000 elements.
</p>
<blockquote class="citation">
<p>
It is probably faster to also do ...
</p>
</blockquote>
<p>
That makes it a little faster, thanks!
</p>
TicketgitThu, 31 May 2018 16:17:46 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:7
https://trac.sagemath.org/ticket/25477#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>3594002f0dfc1c6223efd316ffb348c8ed6446e7</em> to <em>3dc482208fd92d5d430bcd12dcaab68971216609</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=3dc482208fd92d5d430bcd12dcaab68971216609"><span class="icon"></span>3dc4822</a></td><td><code>removing the if from the loop</code>
</td></tr></table>
Ticketstumpc5Fri, 01 Jun 2018 10:44:12 GMT
https://trac.sagemath.org/ticket/25477#comment:8
https://trac.sagemath.org/ticket/25477#comment:8
<pre class="wiki">+ def elements(self, SGS=None):
+ S = SGS.pop()
</pre><p>
seems weird. I assume that you want to remove the <code>=None</code> ?
</p>
Ticketstumpc5Fri, 01 Jun 2018 10:53:49 GMTbranch changed
https://trac.sagemath.org/ticket/25477#comment:9
https://trac.sagemath.org/ticket/25477#comment:9
<ul>
<li><strong>branch</strong>
changed from <em>u/moritz/enumerate_PermutationGroup</em> to <em>u/stumpc5/enumerate_PermutationGroup</em>
</li>
</ul>
TicketmoritzFri, 01 Jun 2018 11:28:33 GMTbranch changed
https://trac.sagemath.org/ticket/25477#comment:10
https://trac.sagemath.org/ticket/25477#comment:10
<ul>
<li><strong>branch</strong>
changed from <em>u/stumpc5/enumerate_PermutationGroup</em> to <em>u/moritz/enumerate_PermutationGroup</em>
</li>
</ul>
TicketmoritzFri, 01 Jun 2018 11:29:32 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:11
https://trac.sagemath.org/ticket/25477#comment:11
<ul>
<li><strong>commit</strong>
changed from <em>3dc482208fd92d5d430bcd12dcaab68971216609</em> to <em>7780abcd25706bb54a6a4cf3e58380bb0d57c12d</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:8" title="Comment 8">stumpc5</a>:
</p>
<blockquote class="citation">
<pre class="wiki">+ def elements(self, SGS=None):
+ S = SGS.pop()
</pre><p>
seems weird. I assume that you want to remove the <code>=None</code> ?
</p>
</blockquote>
<p>
yes, and I just did. (Before seeing, that you did the same thing..)
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=7780abcd25706bb54a6a4cf3e58380bb0d57c12d"><span class="icon"></span>7780abc</a></td><td><code>remove 'None'</code>
</td></tr></table>
Ticketstumpc5Fri, 01 Jun 2018 11:57:34 GMT
https://trac.sagemath.org/ticket/25477#comment:12
https://trac.sagemath.org/ticket/25477#comment:12
<p>
I did some more, could you also merge that change in to the branch?
</p>
TicketgitFri, 01 Jun 2018 20:02:28 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:13
https://trac.sagemath.org/ticket/25477#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>7780abcd25706bb54a6a4cf3e58380bb0d57c12d</em> to <em>7d3d68f7b88a7d3ab74524bdbeb1c1cf66cf9e5c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=07faa6b9791a123f96b2bfb9a4fe2e13de377565"><span class="icon"></span>07faa6b</a></td><td><code>trivial simplifications!</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=7d3d68f7b88a7d3ab74524bdbeb1c1cf66cf9e5c"><span class="icon"></span>7d3d68f</a></td><td><code>Merge branch 'u/stumpc5/enumerate_PermutationGroup' of git://trac.sagemath.org/sage into enumerate_PermutationGroup</code>
</td></tr></table>
TicketvdelecroixSun, 03 Jun 2018 22:00:35 GMT
https://trac.sagemath.org/ticket/25477#comment:14
https://trac.sagemath.org/ticket/25477#comment:14
<p>
In <code>def elements(self, SGS):</code> the argument <code>self</code> is never used and you can remove it.
</p>
Ticketstumpc5Mon, 04 Jun 2018 11:05:56 GMT
https://trac.sagemath.org/ticket/25477#comment:15
https://trac.sagemath.org/ticket/25477#comment:15
<pre class="wiki">sage: time len(list(A.__iter_alt__()))
CPU times: user 3.39 s, sys: 690 ms, total: 4.08 s
Wall time: 4.1 s
60000
</pre><p>
This computation takes much less time in <code>gap</code> directly, I thus expect that doing
</p>
<pre class="wiki">SGS = self.strong_generating_system(base)
</pre><p>
directly in gap rather than in sage would improve the iteration in this case drastically. (I just tried for a bit but failed. The code in gap directly is
</p>
<pre class="wiki">#############################################################################
##
#F ElementsStabChain(<S>)
##
InstallGlobalFunction(ElementsStabChain,function ( S )
local elms, # element list, result
stb, # elements of the stabilizer
pnt, # point in the orbit of <S>
rep; # inverse representative for that point
# if <S> is trivial then it is easy
if Length(S.generators) = 0 then
elms := [ S.identity ];
# otherwise
else
# start with the empty list
elms := [];
# compute the elements of the stabilizer
stb := ElementsStabChain( S.stabilizer );
# loop over all points in the orbit
for pnt in S.orbit do
# add the corresponding coset to the set of elements
rep := S.identity;
while S.orbit[1] ^ rep <> pnt do
rep := LeftQuotient( S.transversal[pnt/rep], rep );
od;
UniteSet( elms, stb * rep );
od;
fi;
# return the result
return elms;
end);
</pre>
Ticketstumpc5Mon, 04 Jun 2018 11:06:33 GMTstatus changed; reviewer, author set
https://trac.sagemath.org/ticket/25477#comment:16
https://trac.sagemath.org/ticket/25477#comment:16
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
<li><strong>reviewer</strong>
set to <em>Christian Stump</em>
</li>
<li><strong>author</strong>
set to <em>Moritz Firsching</em>
</li>
</ul>
Ticketstumpc5Mon, 04 Jun 2018 15:36:07 GMTbranch changed
https://trac.sagemath.org/ticket/25477#comment:17
https://trac.sagemath.org/ticket/25477#comment:17
<ul>
<li><strong>branch</strong>
changed from <em>u/moritz/enumerate_PermutationGroup</em> to <em>u/stumpc5/enumerate_PermutationGroup</em>
</li>
</ul>
Ticketstumpc5Mon, 04 Jun 2018 15:39:12 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:18
https://trac.sagemath.org/ticket/25477#comment:18
<ul>
<li><strong>commit</strong>
changed from <em>7d3d68f7b88a7d3ab74524bdbeb1c1cf66cf9e5c</em> to <em>285524e6bc6d5bfee42b8d1a594fadb58b0effd7</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:14" title="Comment 14">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
In <code>def elements(self, SGS):</code> the argument <code>self</code> is never used and you can remove it.
</p>
</blockquote>
<p>
done.
</p>
<p>
I also made some tests and think that the permutation group method <code>strong_generating_system</code> is much slower than necessary (see the above example where this algo is slower than the brute force). In particular, there is a lot of talking back and forth between sage and gap. Anyway, for my purposes, this is a nonissue. @Dima, do you know how to <strong>easily</strong> make this method fast?
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=285524e6bc6d5bfee42b8d1a594fadb58b0effd7"><span class="icon"></span>285524e</a></td><td><code>removed self from elements arguments</code>
</td></tr></table>
TickettscrimTue, 05 Jun 2018 00:39:34 GMTcc changed
https://trac.sagemath.org/ticket/25477#comment:19
https://trac.sagemath.org/ticket/25477#comment:19
<ul>
<li><strong>cc</strong>
<em>dimpase</em> added
</li>
</ul>
<p>
Dima, see <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:18" title="Comment 18">comment:18</a>.
</p>
Ticketstumpc5Tue, 05 Jun 2018 07:47:45 GMT
https://trac.sagemath.org/ticket/25477#comment:20
https://trac.sagemath.org/ticket/25477#comment:20
<p>
posted question and code at <a class="extlink" href="https://groups.google.com/d/topic/sagedevel/wivuFBq7n7k/discussion"><span class="icon"></span>https://groups.google.com/d/topic/sagedevel/wivuFBq7n7k/discussion</a>.
</p>
Ticketstumpc5Tue, 05 Jun 2018 07:48:35 GMT
https://trac.sagemath.org/ticket/25477#comment:21
https://trac.sagemath.org/ticket/25477#comment:21
<pre class="wiki">def SGS_old(G): # taken from strong_generating_system
sgs = []
stab = G
base = G.base()
for j in base:
sgs.append(stab.transversals(j))
stab = stab.stabilizer(j)
return sgs
def SGS_new(G, gap_output=True):
S = G._gap_().StabChain()
gap.execute(gap_cosets)
cosets = S.CosetsStabChain()
if gap_output:
return cosets # <
elt_class = G._element_class()
gap2sage = lambda elt: elt_class(elt, G, check=False)
return [ [ gap2sage(elt) for elt in coset] # <
for coset in cosets ] # <
gap_cosets = """CosetsStabChain := function ( S )
local cosets, # element list, result
new_coset, #
pnt, # point in the orbit of <S>
rep; # inverse representative for that point
# if <S> is trivial then it is easy
if Length(S.generators) = 0 then
cosets := [ [S.identity] ];
# otherwise
else
# compute the elements of the stabilizer
cosets := CosetsStabChain( S.stabilizer );
# loop over all points in the orbit
new_coset := [];
for pnt in S.orbit do
# add the corresponding coset to the set of elements
rep := S.identity;
while S.orbit[1] ^ rep <> pnt do
rep := LeftQuotient( S.transversal[pnt/rep], rep );
od;
Add( new_coset, rep );
od;
Add( cosets, new_coset );
fi;
# return the result
return cosets;
end;
"""
</pre>
Ticketstumpc5Tue, 05 Jun 2018 07:49:20 GMT
https://trac.sagemath.org/ticket/25477#comment:22
https://trac.sagemath.org/ticket/25477#comment:22
<p>
The new method is much faster than the old, but then slowed down by casting the output to sage:
</p>
<pre class="wiki">sage: sage: p = [(i,i+1) for i in range(1,601,2)]
....: sage: q = [tuple(range(1+i,601,3)) for i in range(3)]
....: sage: A = PermutationGroup([p,q])
sage: %time XX = SGS_old(A)
CPU times: user 3.67 s, sys: 664 ms, total: 4.34 s
Wall time: 4.45 s
sage: %time XX = SGS_new(A, True)
CPU times: user 4.94 ms, sys: 712 µs, total: 5.65 ms
Wall time: 14 ms
sage: %time XX = SGS_new(A, False)
CPU times: user 2.48 s, sys: 116 ms, total: 2.59 s
Wall time: 2.61 s
</pre>
TicketvdelecroixTue, 05 Jun 2018 08:12:00 GMT
https://trac.sagemath.org/ticket/25477#comment:23
https://trac.sagemath.org/ticket/25477#comment:23
<p>
You should be using <code>libgap</code> and not <code>gap</code>. The communication would be much faster.
</p>
TicketvdelecroixTue, 05 Jun 2018 08:13:17 GMT
https://trac.sagemath.org/ticket/25477#comment:24
https://trac.sagemath.org/ticket/25477#comment:24
<p>
And why not using <code>StrongGeneratorsStabChain</code> that is builtin in GAP?
</p>
Ticketstumpc5Tue, 05 Jun 2018 08:17:51 GMT
https://trac.sagemath.org/ticket/25477#comment:25
https://trac.sagemath.org/ticket/25477#comment:25
<blockquote class="citation">
<blockquote>
<p>
You should be using libgap and not gap
</p>
</blockquote>
</blockquote>
<p>
Could you provide a code snippet in the above example of how to do that?
</p>
<blockquote class="citation">
<p>
And why not using <a class="missing wiki">StrongGeneratorsStabChain?</a> that is builtin in GAP?
</p>
</blockquote>
<p>
Because this provides a list of strong generators for the stabilizer chain, but not a list of coset reprs:
</p>
<pre class="wiki">gap> P := Group([(1,2),(1,2,3,4)]);
Group([ (1,2), (1,2,3,4) ])
gap> S := StabChain(P);
<stabilizer chain record, Base [ 1, 2, 3 ], Orbit length 4, Size: 24>
gap> CosetsStabChain(S);
[ [ () ], [ (), (3,4) ], [ (), (2,4,3), (2,3,4) ], [ (), (1,4)(2,3), (1,2)(3,4), (1,3)(2,4) ] ]
gap> StrongGeneratorsStabChain(S);
[ (3,4), (2,3,4), (1,2)(3,4), (1,4)(2,3) ]
</pre>
Ticketstumpc5Tue, 05 Jun 2018 08:28:29 GMT
https://trac.sagemath.org/ticket/25477#comment:26
https://trac.sagemath.org/ticket/25477#comment:26
<blockquote class="citation">
<p>
And why not using...
</p>
</blockquote>
<p>
Let me add that the gap code above is simply taken from the <code>ElementsStabChain</code> code from gap (see <code>PageSource(ElementsStabChain)</code>) and returning the cosets rather than the elements. If there was a builtin function that does this, I would be surprised if it is not used there (though it might be possible for speed reasons).
</p>
TicketdimpaseTue, 05 Jun 2018 08:49:58 GMT
https://trac.sagemath.org/ticket/25477#comment:27
https://trac.sagemath.org/ticket/25477#comment:27
<p>
Historically, little attention was paid to the problem at hand, and indeed, iteration over all the elements of a group G, rather than doing something more intelligent, is almost surely an indication of something done without enough thought.
</p>
<p>
E.g.,
</p>
<ul><li>would knowing the coset representatives of a subgroup H<G and generators for H suffice?
</li><li>would knowing the words in generators rather than permutations suffice?
</li><li>can an adavntage be taken of a short <a class="extlink" href="https://en.wikipedia.org/wiki/Base_(group_theory)"><span class="icon"></span>base</a> for G?
</li></ul>
TicketdimpaseTue, 05 Jun 2018 08:51:44 GMT
https://trac.sagemath.org/ticket/25477#comment:28
https://trac.sagemath.org/ticket/25477#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:23" title="Comment 23">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
You should be using <code>libgap</code> and not <code>gap</code>. The communication would be much faster.
</p>
</blockquote>
<p>
Yeah, if the iterator at hand uses (pexpect) GAP, merely converting it to libGAP would be quite a speedup, I suppose.
</p>
Ticketstumpc5Tue, 05 Jun 2018 08:57:47 GMT
https://trac.sagemath.org/ticket/25477#comment:29
https://trac.sagemath.org/ticket/25477#comment:29
<p>
Well, let me wrap up the discussion so for:
</p>
<ul><li>Moritz implemented an iteration using a short base and a stabilizer chain which are both implemented in gap (using the SchreierSims algorithm), see the attached branch. This already speeded the iteration in most situations drastically.
</li></ul><ul><li>Permutation group elements are faster multiplied in sage than in gap, so we want to do it there.
</li></ul><ul><li>The remaining bottleneck is the computation of the strong generating system for which I provided code in gap. This is now also really fast, <strong>except</strong> for the translation of the gap permutations to sage. I still need help to get this last issue disappear.
</li></ul>
TicketdimpaseTue, 05 Jun 2018 09:03:17 GMT
https://trac.sagemath.org/ticket/25477#comment:30
https://trac.sagemath.org/ticket/25477#comment:30
<p>
GAP has a function <code>Elements()</code> which enumerates the elements of a group, did you try it directly? Probably you're reinventing the wheel...
</p>
<p>
I cannot believe that permutation multiplication in (lib)GAP is slower than in Sage.
You are probably doing lots of slow conversions between Sage and pexpect GAP.
</p>
Ticketstumpc5Tue, 05 Jun 2018 09:16:47 GMT
https://trac.sagemath.org/ticket/25477#comment:31
https://trac.sagemath.org/ticket/25477#comment:31
<p>
Before comparing any of these functions, we should have a way to fast translate gap permutations to sage permutations. Otherwise, this would even much more so spoil the use of the gap function <code>Elements</code> which then results in all permutations to be translated from gap to sage.
</p>
<p>
Here are some preliminary timings for the Coxeter group of type <code>E7</code>:
</p>
<p>
In gap, the iteration needs 9.2 secs:
</p>
<pre class="wiki">gap> P := Group([(1,64)(3,12)(8,19)(15,23)(16,20)(21,26)(25,30)(27,33)(29,35)(31,34)(32,40)(36,41)(37,44)(38,43)(45,47)(49,52)(62,63)(66,75)(71,82)(78,86)(79,83)(84,89)(88,93)(90,96)(92,98)(94,97)(95,103)(99,104)(100,107)(101,106)(108,110)(112,115)(125,126), (2,65)(4,9)(8,15)(13,18)(14,24)(16,21)(19,23)(20,26)(22,28)(25,31)(27,36)(30,34)(33,41)(50,55)(54,56)(57,59)(58,60)(67,72)(71,78)(76,81)(77,87)(79,84)(82,86)(83,89)(85,91)(88,94)(90,99)(93,97)(96,104)(113,118)(117,119)(120,122)(121,123), (1,12)(3,66)(4,8)(9,15)(13,16)(14,25)(18,21)(22,27)(24,31)(28,36)(35,39)(40,42)(43,46)(44,48)(47,51)(52,53)(61,62)(64,75)(67,71)(72,78)(76,79)(77,88)(81,84)(85,90)(87,94)(91,99)(98,102)(103,105)(106,109)(107,111)(110,114)(115,116)(124,125), (2,9)(3,8)(4,67)(5,13)(11,14)(12,19)(17,22)(21,29)(26,35)(31,32)(34,40)(36,38)(41,43)(48,50)(51,54)(53,57)(60,61)(65,72)(66,71)(68,76)(74,77)(75,82)(80,85)(84,92)(89,98)(94,95)(97,103)(99,101)(104,106)(111,113)(114,117)(116,120)(123,124), (4,13)(5,68)(6,11)(8,16)(9,18)(10,17)(15,21)(19,20)(23,26)(32,37)(38,45)(40,44)(42,48)(43,47)(46,51)(57,58)(59,60)(67,76)(69,74)(71,79)(72,81)(73,80)(78,84)(82,83)(86,89)(95,100)(101,108)(103,107)(105,111)(106,110)(109,114)(120,121)(122,123), (5,11)(6,69)(7,10)(13,14)(16,25)(18,24)(20,30)(21,31)(26,34)(29,32)(35,40)(39,42)(45,49)(47,52)(51,53)(54,57)(56,59)(68,74)(70,73)(76,77)(79,88)(81,87)(83,93)(84,94)(89,97)(92,95)(98,103)(102,105)(108,112)(110,115)(114,116)(117,120)(119,122), (6,10)(7,70)(11,17)(14,22)(24,28)(25,27)(30,33)(31,36)(32,38)(34,41)(37,45)(40,43)(42,46)(44,47)(48,51)(50,54)(55,56)(69,73)(74,80)(77,85)(87,91)(88,90)(93,96)(94,99)(95,101)(97,104)(100,108)(103,106)(105,109)(107,110)(111,114)(113,117)(118,119)]);
<permutation group with 7 generators>
gap> Length(Elements(P)); time;
2903040
9255
</pre><p>
while in sage, it only takes 4.3 secs of which 0.7 secs are spend constructing the strong generating system:
</p>
<pre class="wiki">sage: P = CoxeterGroup(["E",7], implementation="permutation")
sage: %time X = P.strong_generating_system(P.base())
CPU times: user 632 ms, sys: 71.6 ms, total: 703 ms
Wall time: 718 ms
sage: P = CoxeterGroup(["E",7], implementation="permutation")
sage: %time len(list(P.__iter_alt__()))
CPU times: user 4.11 s, sys: 208 ms, total: 4.32 s
Wall time: 4.34 s
2903040
</pre><p>
So I expect this to go down below 4 sec if we speed the strong generating system.
</p>
TicketdimpaseTue, 05 Jun 2018 09:52:54 GMT
https://trac.sagemath.org/ticket/25477#comment:32
https://trac.sagemath.org/ticket/25477#comment:32
<p>
Do you know that GAP actually has iterators?
With P as in comment 31:
</p>
<pre class="wiki">gap> si:=IteratorStabChain(StabChain(P));
<iterator>
gap> l:=[];;
gap> for i in si do Add(l,i); od;
gap> Length(l);
</pre><p>
is about 30% faster than <code>Elements(P)</code>  the latter actually will also sort the elements, perhaps that's why.
</p>
<p>
Moreover, in <code>for i</code> loop about 60% of time is taken by <code>Add()</code>.
(I measured this by replacing <code>Add()</code> by a counter increment).
</p>
Ticketstumpc5Tue, 05 Jun 2018 10:05:38 GMT
https://trac.sagemath.org/ticket/25477#comment:33
https://trac.sagemath.org/ticket/25477#comment:33
<p>
Oh, I forgot that <code>Elements</code> sorts the output, thanks for the reminder and for improving the timing comparisons:
</p>
<pre class="wiki">gap> si:=IteratorStabChain(StabChain(P));; time;
4
gap> i:=0;;
gap> for j in si do i:=i+1; od; time;
2608
gap> i;
2903040
</pre><p>
vs.
</p>
<pre class="wiki">sage: i = 0
sage: %time for _ in P.__iter_alt__(): i+=1
CPU times: user 1.97 s, sys: 80.2 ms, total: 2.05 s
Wall time: 2.08 s
sage: i
2903040
</pre><p>
(Is this now the timing you think is optimal in gap?)
If this is the case, sage is still faster, and, again, 0.7secs are overhead that can be remomved from the sage timing, pushing it to roughly 1.5secs.
</p>
TicketdimpaseTue, 05 Jun 2018 10:41:47 GMT
https://trac.sagemath.org/ticket/25477#comment:34
https://trac.sagemath.org/ticket/25477#comment:34
<p>
I wonder whether the SGSs in these tests use the same base.
</p>
<p>
I must say that I also don't understand the recursive code in the branch on the ticket. I suspect it won't work correctly if SGS's elements are not involutions.
(E.g. if the group is cyclic, then there should be a loop over the powers of the only generator in SGS, no?)
</p>
Ticketstumpc5Tue, 05 Jun 2018 11:50:35 GMT
https://trac.sagemath.org/ticket/25477#comment:35
https://trac.sagemath.org/ticket/25477#comment:35
<p>
The algorithm in sage now is the very same as the one in gap, there is no structural difference. For a general description, see for example <a class="extlink" href="https://math.stackexchange.com/a/1706006/234820"><span class="icon"></span>https://math.stackexchange.com/a/1706006/234820</a>.
</p>
<p>
In particular, both use the same base and the same stabilizer chain.
</p>
<blockquote class="citation">
<p>
I suspect it won't work correctly if SGS's elements are not involutions.
</p>
</blockquote>
<p>
This is not correct if I understand it correctly. In particular, the elements in the SGS are usually not only involutions, for example
</p>
<pre class="wiki">sage: S = PermutationGroup([(1,2),(1,2,3)])
sage: S.strong_generating_system()
[[(), (1,2,3), (1,3,2)], [(), (2,3)], [()]]
</pre><p>
and the SGS is <strong>not</strong> a generating set for the group itself.
Another example of a cyclic group is
</p>
<pre class="wiki">sage: P = PermutationGroup([(1,2,3,4)])
sage: for elt in P.__iter_alt__(): print elt
()
(1,4,3,2)
(1,3)(2,4)
(1,2,3,4)
</pre><p>
and the stabilizer chain is trivial (i.e., the chain of cosets is a single coset of the trivial subgroup).
</p>
TicketdimpaseTue, 05 Jun 2018 13:16:40 GMT
https://trac.sagemath.org/ticket/25477#comment:36
https://trac.sagemath.org/ticket/25477#comment:36
<p>
ok, so these are <code>for g in S</code> loops that iterate over subgroups S, right?
</p>
<p>
What iterator is there? Do you want to use your iterator there, explicitly?
</p>
Ticketstumpc5Tue, 05 Jun 2018 13:28:03 GMT
https://trac.sagemath.org/ticket/25477#comment:37
https://trac.sagemath.org/ticket/25477#comment:37
<p>
Sorry, I am slightly lost now in what you are asking  let me try to answer anyway.
</p>
<p>
Let S be a permutation group in sage. The current iterator <code>for g in S</code> iterates by a brute force algorithm through the elements keeping the complete group in memory to check if an element was seen before.
</p>
<p>
The new algorithm reimplements the algorithm used in gap, and indeed takes the important ingredients from gap. gap computes a chain <code> e = S1 in S2 in ... in Sk = S</code> of subgroups (obtained using the SchreierSims algorithm) for which the cosets of <code>Si</code> inside <code> S{i+1} </code> are particularly easy to compute.
This yields a sequence of cosets <code>[e]=C1, C2, ..., Ck</code> such that every element in <code>S</code> has a unique representation <code>g = g1*...*gk</code> for <code>gi in Ci</code>.
</p>
<p>
In sage, the new algorithm is to
</p>
<ul><li>directly compute in gap the list <code>C1, C2, ..., Ck</code>
</li><li>translate the elements in all these lists to sage (this takes too long and should be improved)
</li><li>produce an iterator for all elements in <code>S</code> by iterating over all products of elements in these lists.
</li></ul><p>
Let me know if you meant something else...
</p>
TicketdimpaseTue, 05 Jun 2018 15:23:42 GMT
https://trac.sagemath.org/ticket/25477#comment:38
https://trac.sagemath.org/ticket/25477#comment:38
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:37" title="Comment 37">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
Let me know if you meant something else...
</p>
</blockquote>
<p>
I meant
</p>
<p>
<a class="extlink" href="https://github.com/sagemath/sagetracmirror/blob/285524e6bc6d5bfee42b8d1a594fadb58b0effd7/src/sage/groups/perm_gps/permgroup.py#L844"><span class="icon"></span>lines 844</a> and
<a class="extlink" href="https://github.com/sagemath/sagetracmirror/blob/u/stumpc5/enumerate_PermutationGroup/src/sage/groups/perm_gps/permgroup.py#L848"><span class="icon"></span>848</a>
</p>
<p>
in your patch, both say <code>for g in S:</code>  how do these iterations work? (I imagine <code>S</code> is a subgroup in the SGS chain).
</p>
Ticketstumpc5Tue, 05 Jun 2018 15:50:06 GMT
https://trac.sagemath.org/ticket/25477#comment:39
https://trac.sagemath.org/ticket/25477#comment:39
<blockquote class="citation">
<blockquote>
<p>
in your patch, both say for g in S:  how do these iterations work? (I imagine S is a subgroup in the SGS chain)
</p>
</blockquote>
</blockquote>
<p>
No, <code>S = SGS.pop()</code> so <code>S = Ci</code> is the next layer of coset representatives. Let us go through the code with the notation as above:
</p>
<pre class="wiki"> def elements(SGS):
S = SGS.pop()
if not SGS:
for g in S:
yield g
else:
for s in elements(SGS):
for g in S:
yield s._mul_(g)
</pre><p>
Given such a sequence <code>SGS = C1,C2,...,Ci</code>, <code>elements(SGS)</code> iterates over all elements in <code>Si</code>. This is done by recursively doing the computation for <code>C1,C2,..,C{i1} </code> and then yielding all elements in <code>S{i1} </code> multiplied with all elements in <code>S=Ci</code>.
</p>
<p>
<code>if not SGS</code> means that we have reached the trivial subgroup and <code>S = [()]</code>. So the first <code>for g in S: yield g</code> could be replaced with <code>yield S[0]</code>.
</p>
TicketdimpaseTue, 05 Jun 2018 16:10:58 GMT
https://trac.sagemath.org/ticket/25477#comment:40
https://trac.sagemath.org/ticket/25477#comment:40
<p>
Well, by right, SGS is a generating set. So your naming scheme (no other documentation :)) is misleading...
</p>
Ticketstumpc5Tue, 05 Jun 2018 18:38:19 GMT
https://trac.sagemath.org/ticket/25477#comment:41
https://trac.sagemath.org/ticket/25477#comment:41
<p>
SGS is a strong generating system taken from the sage naming scheme. The later might be misleading, though, since it is not a generating set but a sequence of coset reprs...
</p>
TicketgitTue, 05 Jun 2018 19:01:02 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:42
https://trac.sagemath.org/ticket/25477#comment:42
<ul>
<li><strong>commit</strong>
changed from <em>285524e6bc6d5bfee42b8d1a594fadb58b0effd7</em> to <em>8f70da5d918f87c50383bbb368f1c92eb5b5aee4</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=8f70da5d918f87c50383bbb368f1c92eb5b5aee4"><span class="icon"></span>8f70da5</a></td><td><code>speeded strong_generating_system</code>
</td></tr></table>
Ticketstumpc5Tue, 05 Jun 2018 19:08:38 GMT
https://trac.sagemath.org/ticket/25477#comment:43
https://trac.sagemath.org/ticket/25477#comment:43
<p>
with the new commit, the timings from the beginning become
</p>
<pre class="wiki">sage: p = [(i,i+1) for i in range(1,601,2)]
....: q = [tuple(range(1+i,601,3)) for i in range(3)]
....: A = PermutationGroup([p,q])
....: A.cardinality()
....:
60000
sage: time len(list(A))
CPU times: user 458 ms, sys: 56.2 ms, total: 514 ms
Wall time: 512 ms
60000
sage: time len(list(A.__iter_alt__()))
CPU times: user 2.97 s, sys: 167 ms, total: 3.13 s
Wall time: 3.23 s
60000
sage: time x = A.strong_generating_system(A.base())
CPU times: user 4.51 s, sys: 396 ms, total: 4.9 s
Wall time: 5.08 s
sage: time x = A.strong_generating_system(implementation="gap")
CPU times: user 2.67 s, sys: 80.3 ms, total: 2.75 s
Wall time: 2.77 s
</pre><p>
so the iterations are equally fast, but the translation from gap permutations to sage permutations takes 2.5 secs.
</p>
TicketdimpaseTue, 05 Jun 2018 19:27:12 GMT
https://trac.sagemath.org/ticket/25477#comment:44
https://trac.sagemath.org/ticket/25477#comment:44
<p>
Do you have a problem using libGAP rather than GAP?
</p>
Ticketstumpc5Tue, 05 Jun 2018 20:12:03 GMT
https://trac.sagemath.org/ticket/25477#comment:45
https://trac.sagemath.org/ticket/25477#comment:45
<blockquote class="citation">
<blockquote class="citation">
<p>
You should be using libgap and not gap
</p>
</blockquote>
<p>
Could you provide a code snippet in the above example of how to do that?
</p>
</blockquote>
<p>
No, I just do now know how to do it, see my above comment from <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:25" title="Comment 25">comment:25</a> .
</p>
TicketdimpaseTue, 05 Jun 2018 22:05:59 GMT
https://trac.sagemath.org/ticket/25477#comment:46
https://trac.sagemath.org/ticket/25477#comment:46
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:45" title="Comment 45">stumpc5</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<blockquote class="citation">
<p>
You should be using libgap and not gap
</p>
</blockquote>
<p>
Could you provide a code snippet in the above example of how to do that?
</p>
</blockquote>
<p>
No, I just do now know how to do it, see my above comment from <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:25" title="Comment 25">comment:25</a> .
</p>
</blockquote>
<p>
You can have a look at <a class="extlink" href="https://github.com/sagemath/sagetracmirror/blob/854f9764d14236110b8d7f7b35a7d52017e044f8/src/sage/graphs/generators/classical_geometries.py#L1222"><span class="icon"></span>CossidentePenttilaGraph()</a> for the use of <code>libgap.function_factory</code> (so that you can basically call your own GAP function via libgap).
</p>
<p>
So you can change your code as follows:
</p>
<pre class="wiki">gap_cosets = libgap.function_factory("""function ( S0 )
local CosetsStabChain;
CosetsStabChain := function(S) # for the recursive call
local cosets, # element list, result
new_coset, #
pnt, # point in the orbit of <S>
rep; # inverse representative for that point
# if <S> is trivial then it is easy
if Length(S.generators) = 0 then
cosets := [ [S.identity] ];
# otherwise
else
# compute the elements of the stabilizer
cosets := CosetsStabChain( S.stabilizer );
# loop over all points in the orbit
new_coset := [];
for pnt in S.orbit do
# add the corresponding coset to the set of elements
rep := S.identity;
while S.orbit[1] ^ rep <> pnt do
rep := LeftQuotient( S.transversal[pnt/rep], rep );
od;
Add( new_coset, rep );
od;
Add( cosets, new_coset );
fi;
# return the result
return cosets;
end;
return CosetsStabChain(S0);
end;""")
</pre><p>
Now one can do
</p>
<pre class="wiki">sage: G=libgap.AlternatingGroup(4)
sage: S=G.StabChain()
sage: gap_cosets(S)
[ [ () ], [ (), (2,4,3), (2,3,4) ], [ (), (1,4,3), (1,3,4), (1,2,4) ] ]
</pre><p>
another useful thing is syntax like <code>G=libgap(PermutationGroup([(1,2)]))</code> to convert
from Sage's group (implemented with pexpect GAP, I gather) to libgap.
</p>
Ticketstumpc5Wed, 06 Jun 2018 08:30:11 GMT
https://trac.sagemath.org/ticket/25477#comment:47
https://trac.sagemath.org/ticket/25477#comment:47
<p>
Thank you, Dima! I did these changes together with tons of small changes that had a huge impact on the running time.
</p>
<p>
Beside this, I arrived at the following, and wonder if this is okay doing: Given I have
</p>
<ul><li>a <code>PermutationGroupElement</code> "sample" and
</li><li>a <code>list</code> "new_perm" representing a permutation in oneline notation in the *same permutation group* as "sample"
</li></ul><p>
It seems that, oddly, we do not have a fast way of generating new permutations from these lists, despite the fact that we can multiply permutations very fast. I thus provide a new <code>PermutationGroupElement</code> method <code>_generate_new</code> that basically takes a copy from the given <code>PermutationGroupElement</code> and only overwrites its underlying c list. The code is basically copied from <code>_mul_</code>.
</p>
<p>
An example would be
</p>
<pre class="wiki">sage: S = PermutationGroup(SymmetricGroup(4).gens())
sage: sample = S([2,3,4,1])
sage: lst1 = []
sage: lst2 = [2,1]
sage: lst3 = [4,3,2,1]
sage: pi1 = sample._generate_new(lst1); pi1
()
sage: pi2 = sample._generate_new(lst2); pi2
(1,2)
sage: pi3 = sample._generate_new(lst3); pi3
(1,4)(2,3)
</pre>
TicketgitWed, 06 Jun 2018 08:37:53 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:48
https://trac.sagemath.org/ticket/25477#comment:48
<ul>
<li><strong>commit</strong>
changed from <em>8f70da5d918f87c50383bbb368f1c92eb5b5aee4</em> to <em>f5a48ddbd2134dbeb94fcfb0c8923bdf7edf1d2a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=f5a48ddbd2134dbeb94fcfb0c8923bdf7edf1d2a"><span class="icon"></span>f5a48dd</a></td><td><code>new permutation group element method _generate_new, improved speed for strong generating system</code>
</td></tr></table>
Ticketstumpc5Wed, 06 Jun 2018 08:40:18 GMT
https://trac.sagemath.org/ticket/25477#comment:49
https://trac.sagemath.org/ticket/25477#comment:49
<p>
And here is the new timings:
</p>
<pre class="wiki">sage: sage: p = [(i,i+1) for i in range(1,601,2)]
....: ....: q = [tuple(range(1+i,601,3)) for i in range(3)]
....: ....: A = PermutationGroup([p,q])
....: ....: A.cardinality()
....:
60000
sage: sage: time len(list(A))
CPU times: user 514 ms, sys: 52.2 ms, total: 566 ms
Wall time: 535 ms
60000
sage: sage: time len(list(A.__iter_alt__()))
CPU times: user 588 ms, sys: 91 ms, total: 679 ms
Wall time: 669 ms
60000
sage: sage: time len(list(A))
CPU times: user 469 ms, sys: 72.5 ms, total: 542 ms
Wall time: 529 ms
60000
sage: sage: time len(list(A.__iter_alt__()))
CPU times: user 375 ms, sys: 52.3 ms, total: 427 ms
Wall time: 419 ms
60000
sage: sage: time x = A.strong_generating_system(A.base())
CPU times: user 3.82 s, sys: 784 ms, total: 4.6 s
Wall time: 4.69 s
sage: sage: time x = A.strong_generating_system(implementation="gap")
CPU times: user 281 ms, sys: 127 µs, total: 281 ms
Wall time: 280 ms
</pre>
TicketgitWed, 06 Jun 2018 08:43:28 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:50
https://trac.sagemath.org/ticket/25477#comment:50
<ul>
<li><strong>commit</strong>
changed from <em>f5a48ddbd2134dbeb94fcfb0c8923bdf7edf1d2a</em> to <em>762d3188f87187f6f1d40b49729908a858e61461</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=762d3188f87187f6f1d40b49729908a858e61461"><span class="icon"></span>762d318</a></td><td><code>added doc for _generate_new</code>
</td></tr></table>
Ticketstumpc5Wed, 06 Jun 2018 08:45:52 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:51
https://trac.sagemath.org/ticket/25477#comment:51
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
I set this to "needs review" for a technical review of the code where I still hope for input for improvements (which will not only be relevant for my particular purpose!).
</p>
<p>
Once this is settled, I propose to use the now <code>PermutationGroup</code> iterator per default (and I would also be interested in examples where the old iterator is still faster).
</p>
Ticketstumpc5Wed, 06 Jun 2018 09:14:26 GMT
https://trac.sagemath.org/ticket/25477#comment:52
https://trac.sagemath.org/ticket/25477#comment:52
<p>
Comparing the gap and the sage iterators from <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:33" title="Comment 33">comment:33</a>, we now have:
</p>
<pre class="wiki">gap> si:=IteratorStabChain(StabChain(P));
<iterator>
gap> i:=0;;
gap> for j in si do i:=i+1; od; time;
2523
gap> i;
2903040
</pre><p>
vs.
</p>
<pre class="wiki">sage: sage: i = 0
....: sage: %time for _ in P.__iter_alt__(): i+=1
....:
CPU times: user 1.49 s, sys: 28.2 ms, total: 1.52 s
Wall time: 1.59 s
sage: i
2903040
</pre>
TicketdimpaseWed, 06 Jun 2018 09:28:34 GMT
https://trac.sagemath.org/ticket/25477#comment:53
https://trac.sagemath.org/ticket/25477#comment:53
<p>
The right thing to do (not on this ticket, I guess it's a nontrivial amount of work) is to convert the whole <code>sage/groups/perm_gps</code> to libGAP.
</p>
<p>
This ticket shows that the performance improvements are big.
</p>
Ticketstumpc5Wed, 06 Jun 2018 09:39:03 GMT
https://trac.sagemath.org/ticket/25477#comment:54
https://trac.sagemath.org/ticket/25477#comment:54
<blockquote class="citation">
<p>
This ticket shows that the performance improvements are big
</p>
</blockquote>
<p>
Let me remark that the biggest performance boost came from generating new permutation group elements from old using the new <code>_generate_new</code> method. The use of libGAP also played a role, though.
</p>
TicketdimpaseWed, 06 Jun 2018 09:57:10 GMT
https://trac.sagemath.org/ticket/25477#comment:55
https://trac.sagemath.org/ticket/25477#comment:55
<p>
1) Regarding the timing (GAP iterator vs your iterator). Am I right that they both operate with (lib)GAP data? (i.e. that <span class="underline">mul</span> call on permutations in <code>__iter_alt__</code>, is it actually in (lib)GAP?)
</p>
<p>
2) I don't understand the hack one._generate_new(libgap.<a class="missing wiki">ListPerm?</a>(elt).sage()).
I thought that libgap has a fast method to convert GAP permutations to Sage. E.g.
</p>
<pre class="wiki">sage: G=libgap.AlternatingGroup(4)
sage: gg=G.GeneratorsOfGroup()
sage: gg.sage()
[(1,2,3), (2,3,4)]
sage: type(g.sage()[0])
<type 'sage.groups.perm_gps.permgroup_element.PermutationGroupElement'>
sage: type(g[0])
<type 'sage.libs.gap.element.GapElement_Permutation'>
</pre>
Ticketstumpc5Wed, 06 Jun 2018 10:10:27 GMT
https://trac.sagemath.org/ticket/25477#comment:56
https://trac.sagemath.org/ticket/25477#comment:56
<blockquote class="citation">
<p>
i.e. that mul call on permutations in <span class="underline">iter_alt</span>, is it actually in (lib)GAP?
</p>
</blockquote>
<p>
No, this is pure cython and uses <code>PermutationGroupElement._mul_(left, _right)</code>, no (lib)GAP involved here.
</p>
<p>
Since both algorithms are the same, and the strong generating set in the Sage version is taken through libGAP, I suspect that the time advantage of Sage really comes from this superfast cython multiplication of permutation group elements.
</p>
<blockquote class="citation">
<p>
I thought that libgap has a fast method to convert GAP permutations to Sage
</p>
</blockquote>
<p>
This is not the case: libgap uses <code>GapElement_Permutation.sage</code> which returns <code>PermutationGroupElement(libgap.ListPerm(self).sage())</code>, so it goes through the ordinary permutation group element constructor that is <strong>very</strong> slow because of tons of checks. This is why I wrote <code>_generate_new</code> that just uses the data from a given element and overwrites its c array containing the permutation:
</p>
<pre class="wiki">sage: P = PermutationGroup([(1,2),(1,2,3,4)])
sage: one = P.one()
sage: l = [4,3,2,1]
sage: %timeit P(l)
1000 loops, best of 3: 579 µs per loop
sage: %timeit one._generate_new(l)
The slowest run took 39.93 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 203 ns per loop
</pre>
TicketdimpaseWed, 06 Jun 2018 10:25:48 GMT
https://trac.sagemath.org/ticket/25477#comment:57
https://trac.sagemath.org/ticket/25477#comment:57
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:56" title="Comment 56">stumpc5</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I thought that libgap has a fast method to convert GAP permutations to Sage
</p>
</blockquote>
<p>
This is not the case: libgap uses <code>GapElement_Permutation.sage</code> which returns <code>PermutationGroupElement(libgap.ListPerm(self).sage())</code>, so it goes through the ordinary permutation group element constructor that is <strong>very</strong> slow because of tons of checks. This is why I wrote <code>_generate_new</code> that just uses the data from a given element and overwrites its c array containing the permutation:
</p>
</blockquote>
<p>
Shouldn't then this be used to improve the code in src/sage/libs/gap/?
Cause that's what it does, you provide a better implementation for <code><libgap perm>.sage()</code>, right?
</p>
Ticketstumpc5Wed, 06 Jun 2018 10:33:13 GMT
https://trac.sagemath.org/ticket/25477#comment:58
https://trac.sagemath.org/ticket/25477#comment:58
<p>
Not really, because my method (A) makes use of the fact that one knows the permutation group the element lives in a priori, and (B) does not check the input whatsoever for correctness (and might result in segfaults if not used properly).
</p>
<p>
The first is an issue because <code><libgap perm></code> does not know which parent a gap permutation lives in (and neither does gap iirc), while the second might be neglected in case we expect that we always get something reasonable fromo gap.
</p>
TicketdimpaseWed, 06 Jun 2018 13:04:35 GMT
https://trac.sagemath.org/ticket/25477#comment:59
https://trac.sagemath.org/ticket/25477#comment:59
<p>
OK, I see. Still, libgap should be using the lowlevel C array with GAP permutation data,
rather than converting GAP list > Sage list > <a class="missing wiki">PermutationGroupElement?</a>
(creating, if needed, a parent permutation group along the way, no?)
</p>
<p>
I don't understand whether this involves calling pexpect GAP or not.
</p>
Ticketstumpc5Wed, 06 Jun 2018 13:09:53 GMT
https://trac.sagemath.org/ticket/25477#comment:60
https://trac.sagemath.org/ticket/25477#comment:60
<blockquote class="citation">
<blockquote>
<p>
I don't understand whether this involves calling pexpect GAP or not.
</p>
</blockquote>
</blockquote>
<p>
What involved pexpect GAP? This creation of a <code>PermutationGroupElement</code>? Then the answer is <strong>no</strong>, there is no gap object attached by default to a <code>PermutationGroupElement</code>.
</p>
TicketdimpaseThu, 07 Jun 2018 11:23:35 GMT
https://trac.sagemath.org/ticket/25477#comment:61
https://trac.sagemath.org/ticket/25477#comment:61
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:60" title="Comment 60">stumpc5</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<blockquote>
<p>
I don't understand whether this involves calling pexpect GAP or not.
</p>
</blockquote>
</blockquote>
<p>
What involved pexpect GAP? This creation of a <code>PermutationGroupElement</code>? Then the answer is <strong>no</strong>, there is no gap object attached by default to a <code>PermutationGroupElement</code>.
</p>
</blockquote>
<p>
OK, thanks  it's not immediately clear with all that methods using <code>_gap_</code> in that class.
</p>
<p>
Anyhow, I don't understand why libGAP creates <code>PermutationGroupElement</code> rather than
a <code>Permutation</code>.
It would be natural to me to have this as the default,
mostly as it does not involve constructing a parent (GAP permutations don't really have parents in GAP, they are all in every <code>SymmetricGroup()</code> of degree at least <code>LargestMovedPoint()</code> of the permutation.
Then your hack can be used for fast libgap>Sage conversion of permutations.
</p>
Ticketstumpc5Thu, 07 Jun 2018 12:19:28 GMT
https://trac.sagemath.org/ticket/25477#comment:62
https://trac.sagemath.org/ticket/25477#comment:62
<blockquote class="citation">
<p>
It would be natural to me to have this as the default
</p>
</blockquote>
<p>
I agree, this would get down the speed quite a bit
</p>
<pre class="wiki">sage: P = PermutationGroup([(1,2),(1,2,3,4,5,6,7,8)])
sage: l = [8,7,6,5,4,3,2,1]
sage: %timeit P(l, check=False)
The slowest run took 7.58 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 44.3 µs per loop
sage: %timeit Permutation(l, check_input=False)
The slowest run took 7.85 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 6.74 µs per loop
</pre><p>
but my hack would not work in this case because it uses the c structure underlying <code>PermutationGroupElement</code> which doesn't exist (caution: haven't rechecked!) for <code>Permutation</code>, and this hack is possibly still an order of magnitude faster
</p>
<pre class="wiki">sage: one = P.one()
sage: %timeit one._generate_new(l)
The slowest run took 128.70 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 241 ns per loop
</pre>
TicketgitSun, 10 Jun 2018 08:18:21 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:63
https://trac.sagemath.org/ticket/25477#comment:63
<ul>
<li><strong>commit</strong>
changed from <em>762d3188f87187f6f1d40b49729908a858e61461</em> to <em>952b29227535c6cf15979bcb8d7c1baea065f43a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=0986e6715983f7e3dddfc50cd5736a636ffd0884"><span class="icon"></span>0986e67</a></td><td><code>cosmetic change to SGS</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=952b29227535c6cf15979bcb8d7c1baea065f43a"><span class="icon"></span>952b292</a></td><td><code>yippie  I got the strong generating system computation really fast now by directly converting the gap list of c ints to an <int*>!</code>
</td></tr></table>
Ticketstumpc5Sun, 10 Jun 2018 08:27:10 GMT
https://trac.sagemath.org/ticket/25477#comment:64
https://trac.sagemath.org/ticket/25477#comment:64
<p>
Okay, now everything is as fast as I was expecting it to be possible! I now do not create a sage list from the libgap list and then fill a <code><int*></code> with this data, but create the latter directly from the libgap list entries. This removes all the overhead!
</p>
<p>
Here are the new timings:
</p>
<pre class="wiki">sage: p = [(i,i+1) for i in range(1,601,2)]
....: q = [tuple(range(1+i,601,3)) for i in range(3)]
....: A = PermutationGroup([p,q])
....: A.cardinality()
....:
60000
sage: i=0
sage: %time for _ in A.__iter__(): i+=1
CPU times: user 512 ms, sys: 40.3 ms, total: 552 ms
Wall time: 543 ms
sage: i
60000
sage: i=0
sage: %time for _ in A.__iter_alt__(): i+=1
CPU times: user 132 ms, sys: 23.7 ms, total: 156 ms
Wall time: 137 ms
sage: i
60000
sage: %time X = A.strong_generating_system(A.base())
CPU times: user 3.5 s, sys: 675 ms, total: 4.17 s
Wall time: 4.22 s
sage: [ len(x) for x in X ]
[600, 100]
sage: %time Y = A.strong_generating_system(implementation="gap")
CPU times: user 38.3 ms, sys: 129 µs, total: 38.5 ms
Wall time: 38.2 ms
sage: [ len(y) for y in Y ]
[1, 100, 600]
</pre>
Ticketstumpc5Sun, 10 Jun 2018 08:32:48 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:65
https://trac.sagemath.org/ticket/25477#comment:65
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
I consider it <strong>wrong</strong> to define (as I did) the method <code>_generate_perm(self, old)</code> for <code>libGAP_List</code> (handing over a <code>PermutationGroupElement old</code>. I think it should rather exist a method <code>_generate_new_libgap(self, gaplst</code> for <code>PermutationGroupElement</code> that takes as input a <code>libGAP_List gaplst</code>.
</p>
<p>
I was not able to do that due to import errors and my ignorance how to properly cast the objects into the correct types, but this seems only a matter of proper coding in <code>cython</code>. @Travis or @Dima, could you help with this?
</p>
<p>
I think once this is settled, the code is ready for review!
</p>
<p>
@Moritz: rather incredible speedup compared to your original call of <code>strong_generating_system</code>, hm?
</p>
TicketgitSun, 10 Jun 2018 08:36:48 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:66
https://trac.sagemath.org/ticket/25477#comment:66
<ul>
<li><strong>commit</strong>
changed from <em>952b29227535c6cf15979bcb8d7c1baea065f43a</em> to <em>d49798c44257f9959abe27b632f22ce1f872ff5b</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=d49798c44257f9959abe27b632f22ce1f872ff5b"><span class="icon"></span>d49798c</a></td><td><code>removed todo</code>
</td></tr></table>
TicketgitSun, 10 Jun 2018 08:38:37 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:67
https://trac.sagemath.org/ticket/25477#comment:67
<ul>
<li><strong>commit</strong>
changed from <em>d49798c44257f9959abe27b632f22ce1f872ff5b</em> to <em>2be32afc29cf43fe798fd5d12cba00f546f401b4</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=2be32afc29cf43fe798fd5d12cba00f546f401b4"><span class="icon"></span>2be32af</a></td><td><code>removed todo</code>
</td></tr></table>
TickettscrimSun, 10 Jun 2018 09:00:14 GMT
https://trac.sagemath.org/ticket/25477#comment:68
https://trac.sagemath.org/ticket/25477#comment:68
<p>
I can probably try it late tomorrow or the day after (I promised Darij I would review <a class="closed ticket" href="https://trac.sagemath.org/ticket/25326" title="enhancement: Schützenberger antiautomorphisms for WQSym and FQSym; fleshing out FQSym (closed: fixed)">#25326</a> first). So Dima, let me know if you are going to work on this tomorrow.
</p>
TicketmoritzMon, 11 Jun 2018 08:40:20 GMT
https://trac.sagemath.org/ticket/25477#comment:69
https://trac.sagemath.org/ticket/25477#comment:69
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:65" title="Comment 65">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
@Moritz: rather incredible speedup compared to your original call of <code>strong_generating_system</code>, hm?
</p>
</blockquote>
<p>
Yes, absolutely great! As I see it, the new <code>__iter_alt_</code> method is now faster then <code>__iter__</code> in all cases, right? Therefore I propose to replace <code>__iter__</code> with the <code>__iter_alt__</code> before puuting this ticket on review.
</p>
Ticketstumpc5Mon, 11 Jun 2018 08:43:09 GMT
https://trac.sagemath.org/ticket/25477#comment:70
https://trac.sagemath.org/ticket/25477#comment:70
<p>
No, not quite. The new <code>__iter_alt__</code> is still slower for small groups (size ~ <500 elts). I still propose to use <code>___iter_alt__</code> per default, but leave the option to use the brute force iteration if desired (in case you want to loop through <strong>many</strong> small groups.
</p>
<p>
The issue is that if the group is really small, waiting even for a tiny information from <code>libgap</code> is slower than exploring the group directly.
</p>
TicketdimpaseMon, 11 Jun 2018 09:47:48 GMT
https://trac.sagemath.org/ticket/25477#comment:71
https://trac.sagemath.org/ticket/25477#comment:71
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:68" title="Comment 68">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I can probably try it late tomorrow or the day after (I promised Darij I would review <a class="closed ticket" href="https://trac.sagemath.org/ticket/25326" title="enhancement: Schützenberger antiautomorphisms for WQSym and FQSym; fleshing out FQSym (closed: fixed)">#25326</a> first). So Dima, let me know if you are going to work on this tomorrow.
</p>
</blockquote>
<p>
I suggest that the documentation says that libGAP (rather than just GAP) is used.
That's all for me for the time being (swamped with other things).
</p>
TicketgitMon, 11 Jun 2018 10:02:15 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:72
https://trac.sagemath.org/ticket/25477#comment:72
<ul>
<li><strong>commit</strong>
changed from <em>2be32afc29cf43fe798fd5d12cba00f546f401b4</em> to <em>448202560fde1b721f3635c438c894d023b0afca</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=448202560fde1b721f3635c438c894d023b0afca"><span class="icon"></span>4482025</a></td><td><code>Merge branch 'develop' into t/25477/enumerate_PermutationGroup</code>
</td></tr></table>
TicketdimpaseMon, 18 Jun 2018 14:25:24 GMT
https://trac.sagemath.org/ticket/25477#comment:73
https://trac.sagemath.org/ticket/25477#comment:73
<p>
What is the current state here?
</p>
Ticketstumpc5Mon, 18 Jun 2018 14:30:46 GMT
https://trac.sagemath.org/ticket/25477#comment:74
https://trac.sagemath.org/ticket/25477#comment:74
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:65" title="Comment 65">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
I consider it <strong>wrong</strong> to define (as I did) the method <code>_generate_perm(self, old)</code> for <code>libGAP_List</code> (handing over a <code>PermutationGroupElement old</code>. I think it should rather exist a method <code>_generate_new_libgap(self, gaplst</code> for <code>PermutationGroupElement</code> that takes as input a <code>libGAP_List gaplst</code>.
</p>
<p>
I was not able to do that due to import errors and my ignorance how to properly cast the objects into the correct types, but this seems only a matter of proper coding in <code>cython</code>. @Travis or @Dima, could you help with this?
</p>
</blockquote>
<p>
I am still waiting for someone to have a look at this...
</p>
<p>
In principle, I think this implementation is a strong improvement to permutation groups in Sage, and since I am not very good in optimizing in cython, there might a few simple improvements left to be found. I don't think it is ready for a positive review, but it certainly is for a review of the technical details.
</p>
TicketdimpaseMon, 18 Jun 2018 14:55:20 GMT
https://trac.sagemath.org/ticket/25477#comment:75
https://trac.sagemath.org/ticket/25477#comment:75
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:74" title="Comment 74">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:65" title="Comment 65">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
I consider it <strong>wrong</strong> to define (as I did) the method <code>_generate_perm(self, old)</code> for <code>libGAP_List</code> (handing over a <code>PermutationGroupElement old</code>. I think it should rather exist a method <code>_generate_new_libgap(self, gaplst</code> for <code>PermutationGroupElement</code> that takes as input a <code>libGAP_List gaplst</code>.
</p>
<p>
I was not able to do that due to import errors and my ignorance how to properly cast the objects into the correct types, but this seems only a matter of proper coding in <code>cython</code>. @Travis or @Dima, could you help with this?
</p>
</blockquote>
<p>
I am still waiting for someone to have a look at this...
</p>
</blockquote>
<p>
Could you post a branch with this import problem?
It'd be much quicker to see what's going on this way?
(it need not become the new branch on this ticket, certainly)
</p>
TicketgitMon, 18 Jun 2018 15:09:23 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:76
https://trac.sagemath.org/ticket/25477#comment:76
<ul>
<li><strong>commit</strong>
changed from <em>448202560fde1b721f3635c438c894d023b0afca</em> to <em>85a01c55af86920e4f82948a3e99bc9850558026</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=85a01c55af86920e4f82948a3e99bc9850558026"><span class="icon"></span>85a01c5</a></td><td><code>not working attempt to move the permutation generation from libgap_list to PermutationGroupElement</code>
</td></tr></table>
Ticketstumpc5Mon, 18 Jun 2018 15:10:36 GMT
https://trac.sagemath.org/ticket/25477#comment:77
https://trac.sagemath.org/ticket/25477#comment:77
<blockquote class="citation">
<p>
Could you post a branch with this import problem? It'd be much quicker to see what's going on this way?
</p>
</blockquote>
<p>
I had deleted that attempt, but it was basically what I just pushed. My problem was that I didn't see how to handle <code>libGAP_INT_INTOBJ, libGAP_ELM_LIST</code> inside <code>permgroup_element.pyx</code>.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=85a01c55af86920e4f82948a3e99bc9850558026"><span class="icon"></span>85a01c5</a></td><td><code>not working attempt to move the permutation generation from libgap_list to PermutationGroupElement</code>
</td></tr></table>
TicketdimpaseTue, 19 Jun 2018 09:26:19 GMT
https://trac.sagemath.org/ticket/25477#comment:78
https://trac.sagemath.org/ticket/25477#comment:78
<p>
for starters, I think you need
</p>
<pre class="wiki">+++ b/src/sage/groups/perm_gps/permgroup_element.pyx
@@ 77,7 +77,7 @@ from sage.sets.finite_enumerated_set import FiniteEnumeratedSet
import sage.structure.coerce as coerce
from sage.structure.richcmp cimport richcmp_not_equal, rich_to_bool
from sage.libs.gap.element cimport libGAP_Obj, libGAP_INT_INTOBJ, libGAP_ELM_LIST
+from sage.libs.gap.gap_includes cimport libGAP_Obj, libGAP_INT_INTOBJ, libGAP_ELM_LIST
import operator
</pre><p>
after this one gets
</p>
<pre class="wiki">[sagelib8.3.beta5] Error compiling Cython file:
[sagelib8.3.beta5] 
[sagelib8.3.beta5] ...
[sagelib8.3.beta5] for i from vn <= i < old.n:
[sagelib8.3.beta5] new.perm[i] = i
[sagelib8.3.beta5] return new
[sagelib8.3.beta5]
[sagelib8.3.beta5] cpdef _generate_new_GAP(old, self):
[sagelib8.3.beta5] cdef libGAP_Obj obj = self.value
[sagelib8.3.beta5] ^
[sagelib8.3.beta5] 
[sagelib8.3.beta5]
[sagelib8.3.beta5] sage/groups/perm_gps/permgroup_element.pyx:894:34: Cannot convert Python object to 'libGAP_Obj'
[sagelib8.3.beta5] Traceback (most recent call last):
[sagelib8.3.beta5] File "/home/dima/sagetracmirror/local/lib/python2.7/sitepackages/Cython/Build/Dependencies.py", line 1164, in cythonize_one_helper
[sagelib8.3.beta5] return cythonize_one(*m)
[sagelib8.3.beta5] File "/home/dima/sagetracmirror/local/lib/python2.7/sitepackages/Cython/Build/Dependencies.py", line 1146, in cythonize_one
[sagelib8.3.beta5] raise CompileError(None, pyx_file)
[sagelib8.3.beta5] CompileError: sage/groups/perm_gps/permgroup_element.pyx
</pre><p>
which hopefully makes sense to you.
</p>
TicketgitTue, 19 Jun 2018 09:37:22 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:79
https://trac.sagemath.org/ticket/25477#comment:79
<ul>
<li><strong>commit</strong>
changed from <em>85a01c55af86920e4f82948a3e99bc9850558026</em> to <em>49b68c4f8aa6925e4ea0b721760ce8ed5c762c4a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=49b68c4f8aa6925e4ea0b721760ce8ed5c762c4a"><span class="icon"></span>49b68c4</a></td><td><code>here is the next import crash</code>
</td></tr></table>
Ticketstumpc5Tue, 19 Jun 2018 09:39:26 GMT
https://trac.sagemath.org/ticket/25477#comment:80
https://trac.sagemath.org/ticket/25477#comment:80
<p>
okay, here is the next one that doesn't. It now compiles but crashes on startup with the following import error:
</p>
<pre class="wiki">ImportError: /home/stumpc5/Programs/sage/local/lib/python2.7/sitepackages/sage/groups/perm_gps/permgroup_element.so: undefined symbol: libGAP_ElmListFuncs
</pre>
TicketdimpaseTue, 19 Jun 2018 10:13:40 GMT
https://trac.sagemath.org/ticket/25477#comment:81
https://trac.sagemath.org/ticket/25477#comment:81
<p>
You have this line:
</p>
<pre class="wiki">cdef GapElement_List self = <GapElement_List> self_tmp
</pre><p>
which does not make sense to me. Is it mean to be a C cast?
Something else?
</p>
Ticketstumpc5Tue, 19 Jun 2018 10:21:38 GMT
https://trac.sagemath.org/ticket/25477#comment:82
https://trac.sagemath.org/ticket/25477#comment:82
<p>
Yes, it is meant to be a C cast: <code>self_tmp</code> (sorry for the stupid names, I would make these nicer once it works) arrives as a python object because it is a <code>cpdef</code>, so to access its "C part", I needed to do this (actually without the <code><GapElement_List></code> cast, but only the <code>cdef GapElement_List self = self_tmp</code> iirc.
</p>
TicketdimpaseTue, 19 Jun 2018 10:31:10 GMT
https://trac.sagemath.org/ticket/25477#comment:83
https://trac.sagemath.org/ticket/25477#comment:83
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:82" title="Comment 82">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
Yes, it is meant to be a C cast: <code>self_tmp</code> (sorry for the stupid names, I would make these nicer once it works) arrives as a python object because it is a <code>cpdef</code>,
</p>
</blockquote>
<p>
I would be very surprised seeing a C cast magically converting a Python object into a GAP one.
</p>
<blockquote class="citation">
<p>
so to access its "C part", I needed to do this (actually without the <code><GapElement_List></code> cast, but only the <code>cdef GapElement_List self = self_tmp</code> iirc.
</p>
</blockquote>
Ticketstumpc5Tue, 19 Jun 2018 11:14:05 GMT
https://trac.sagemath.org/ticket/25477#comment:84
https://trac.sagemath.org/ticket/25477#comment:84
<blockquote class="citation">
<blockquote>
<p>
I would be very surprised seeing a C cast magically converting a Python object into a GAP one.
</p>
</blockquote>
</blockquote>
<p>
Well, please see that the very same code in <code>sage.libs.gap.element.GapElement_List._generate_perm</code> works, and it doesn't without the cast <code>cdef PermutationGroupElement tmp = <PermutationGroupElement> old</code>. I thought this is because it arrives as a python object <code>PermutationGroupElement</code> (which doesn't have access to the cython data structures) and I cast it into a cython object.
</p>
TicketdimpaseTue, 19 Jun 2018 11:41:00 GMT
https://trac.sagemath.org/ticket/25477#comment:85
https://trac.sagemath.org/ticket/25477#comment:85
<p>
Does one really need to make it cpdef? Perhaps start with cdef, make a cpdef wrapper then?
</p>
TicketdimpaseTue, 19 Jun 2018 12:04:04 GMT
https://trac.sagemath.org/ticket/25477#comment:86
https://trac.sagemath.org/ticket/25477#comment:86
<p>
now I am confused. The current branch works for me.
</p>
Ticketstumpc5Tue, 19 Jun 2018 12:13:25 GMT
https://trac.sagemath.org/ticket/25477#comment:87
https://trac.sagemath.org/ticket/25477#comment:87
<blockquote class="citation">
<p>
now I am confused. The current branch works for me.
</p>
</blockquote>
<p>
compiling, or also running sage? I got the import error as in <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:80" title="Comment 80">comment:80</a> only when running sage.
</p>
<blockquote class="citation">
<p>
Does one really need to make it cpdef? Perhaps start with cdef, make a cpdef wrapper then?
</p>
</blockquote>
<p>
I could try this, but it seems so simple: I have a cpdef function on class A that takes an element of class B as second argument, and I want to move this to a cpdef function on class B that takes an element of class A as second argument...
</p>
TicketdimpaseTue, 19 Jun 2018 12:19:36 GMT
https://trac.sagemath.org/ticket/25477#comment:88
https://trac.sagemath.org/ticket/25477#comment:88
<p>
OK, more precisely, all is fine on OSX, but on Linux Sage crashes at startup, with the import error as you posted!
</p>
<p>
from the crash report:
</p>
<pre class="wiki">...
/home/dima/sagetracmirror/local/lib/python2.7/sitepackages/sage/groups/perm_gps/permgroup.py in <module>()
131 # Distributed under the terms of the GNU General Public License (GPL)
...
145 from sage.interfaces.gap import gap, GapElement
> 146 from sage.groups.perm_gps.permgroup_element import PermutationGroupElement, standardize_generator
global sage.groups.perm_gps.permgroup_element = undefined
...
ImportError: /home/dima/sagetracmirror/local/lib/python2.7/sitepackages/sage/groups/perm_gps/permgroup_element.so: undefined symbol: libGAP_ElmListFuncs
</pre>
TicketdimpaseTue, 19 Jun 2018 12:28:31 GMT
https://trac.sagemath.org/ticket/25477#comment:89
https://trac.sagemath.org/ticket/25477#comment:89
<p>
And this is not a surprise:
</p>
<pre class="wiki">$ ldd local/lib/python2.7/sitepackages/sage/groups/perm_gps/permgroup_element.so
linuxvdso.so.1 => (0x00007fffe53f0000)
libpython2.7.so.1.0 => /home/dima/sagetracmirror/local/lib/libpython2.7.so.1.0 (0x00007c9a2c87c000)
libpthread.so.0 => /lib/x86_64linuxgnu/libpthread.so.0 (0x00007c9a2c65f000)
libc.so.6 => /lib/x86_64linuxgnu/libc.so.6 (0x00007c9a2c295000)
libdl.so.2 => /lib/x86_64linuxgnu/libdl.so.2 (0x00007c9a2c091000)
libutil.so.1 => /lib/x86_64linuxgnu/libutil.so.1 (0x00007c9a2be8e000)
libm.so.6 => /lib/x86_64linuxgnu/libm.so.6 (0x00007c9a2bb85000)
/lib64/ldlinuxx8664.so.2 (0x00007c9a2cedf000)
</pre><p>
it is not linked with libgap, that's why.
</p>
Ticketstumpc5Tue, 19 Jun 2018 12:32:49 GMT
https://trac.sagemath.org/ticket/25477#comment:90
https://trac.sagemath.org/ticket/25477#comment:90
<p>
I have no idea what that means! (Or rather how to fix this.)
</p>
TicketdimpaseTue, 19 Jun 2018 12:36:31 GMT
https://trac.sagemath.org/ticket/25477#comment:91
https://trac.sagemath.org/ticket/25477#comment:91
<p>
Compare this with the libgap.so extension:
</p>
<pre class="wiki">$ ldd local/lib/python2.7/sitepackages/sage/libs/gap/libgap.so
linuxvdso.so.1 => (0x00007ffe0d3fd000)
libgap.so.4 => /home/dima/sagetracmirror/local/lib/libgap.so.4 (0x00007f4959fa5000)
libpython2.7.so.1.0 => /home/dima/sagetracmirror/local/lib/libpython2.7.so.1.0 (0x00007f4959b85000)
libpthread.so.0 => /lib/x86_64linuxgnu/libpthread.so.0 (0x00007f4959968000)
libc.so.6 => /lib/x86_64linuxgnu/libc.so.6 (0x00007f495959e000)
libm.so.6 => /lib/x86_64linuxgnu/libm.so.6 (0x00007f4959295000)
libdl.so.2 => /lib/x86_64linuxgnu/libdl.so.2 (0x00007f4959091000)
libutil.so.1 => /lib/x86_64linuxgnu/libutil.so.1 (0x00007f4958e8e000)
/lib64/ldlinuxx8664.so.2 (0x00007f495ac26000)
</pre><p>
you see there libgap.so.4, so it can find the symbols there...
</p>
<p>
Surely it's some declaration missing somewhere, and that's all.
Or, perhaps, the corresponding GAP function should somehow be blessed in libgap extension.
</p>
Ticketstumpc5Tue, 19 Jun 2018 12:40:16 GMT
https://trac.sagemath.org/ticket/25477#comment:92
https://trac.sagemath.org/ticket/25477#comment:92
<p>
Does this mean I should rather not move the method and keep the current version?
</p>
TicketdimpaseTue, 19 Jun 2018 12:53:58 GMT
https://trac.sagemath.org/ticket/25477#comment:93
https://trac.sagemath.org/ticket/25477#comment:93
<p>
No, this just means we have to ask people who know Cython better.
It must be totally trivial to fix.
</p>
<p>
I have an idea how it is done via setup.py, but here it's done in some other way, and cannot see any trace anywhere of how and why libgap.so extension gets linked to the correct dynamic library.
</p>
TicketdimpaseTue, 19 Jun 2018 13:06:07 GMT
https://trac.sagemath.org/ticket/25477#comment:94
https://trac.sagemath.org/ticket/25477#comment:94
<p>
I've asked here: <a class="extlink" href="https://groups.google.com/d/msg/sagedevel/_d28OHHsnE4/WnYr1L6NCAAJ"><span class="icon"></span>https://groups.google.com/d/msg/sagedevel/_d28OHHsnE4/WnYr1L6NCAAJ</a>
</p>
TicketdimpaseTue, 19 Jun 2018 13:36:08 GMT
https://trac.sagemath.org/ticket/25477#comment:95
https://trac.sagemath.org/ticket/25477#comment:95
<p>
here is a fix that makes it work:
</p>
<pre class="wiki">$ git diff
diff git a/src/sage/groups/perm_gps/permgroup_element.pxd b/src/sage/groups/perm_gps/permgroup_element.pxd
index 08a928b..e261780 100644
 a/src/sage/groups/perm_gps/permgroup_element.pxd
+++ b/src/sage/groups/perm_gps/permgroup_element.pxd
@@ 1,3 +1,4 @@
+# distutils: libraries = gap
from sage.structure.element cimport MultiplicativeGroupElement, MonoidElement, Element
from sage.structure.list_clone cimport ClonableIntArray
</pre><p>
(at least with this I can start sage all right)
</p>
<p>
PS. Tests pass, too.
</p>
TicketdimpaseTue, 19 Jun 2018 13:42:43 GMTreviewer, author changed
https://trac.sagemath.org/ticket/25477#comment:96
https://trac.sagemath.org/ticket/25477#comment:96
<ul>
<li><strong>reviewer</strong>
changed from <em>Christian Stump</em> to <em>Christian Stump, Dima Pasechnik</em>
</li>
<li><strong>author</strong>
changed from <em>Moritz Firsching</em> to <em>Moritz Firsching, Christian Stump</em>
</li>
</ul>
TicketjdemeyerTue, 19 Jun 2018 13:59:12 GMT
https://trac.sagemath.org/ticket/25477#comment:97
https://trac.sagemath.org/ticket/25477#comment:97
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:95" title="Comment 95">dimpase</a>:
</p>
<blockquote class="citation">
<p>
here is a fix that makes it work:
</p>
<pre class="wiki">$ git diff
diff git a/src/sage/groups/perm_gps/permgroup_element.pxd b/src/sage/groups/perm_gps/permgroup_element.pxd
index 08a928b..e261780 100644
 a/src/sage/groups/perm_gps/permgroup_element.pxd
+++ b/src/sage/groups/perm_gps/permgroup_element.pxd
@@ 1,3 +1,4 @@
+# distutils: libraries = gap
from sage.structure.element cimport MultiplicativeGroupElement, MonoidElement, Element
from sage.structure.list_clone cimport ClonableIntArray
</pre></blockquote>
<p>
That fix shouldn't be needed (I created <a class="closed ticket" href="https://trac.sagemath.org/ticket/25608" title="enhancement: Further clean up of libGAP declarations (closed: fixed)">#25608</a> for that).
</p>
TicketgitTue, 19 Jun 2018 14:00:17 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:98
https://trac.sagemath.org/ticket/25477#comment:98
<ul>
<li><strong>commit</strong>
changed from <em>49b68c4f8aa6925e4ea0b721760ce8ed5c762c4a</em> to <em>6654f752bc716676c05f37e2845c4d7c1babc1fe</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=6654f752bc716676c05f37e2845c4d7c1babc1fe"><span class="icon"></span>6654f75</a></td><td><code>moved things around, ready for review</code>
</td></tr></table>
Ticketstumpc5Tue, 19 Jun 2018 14:03:15 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:99
https://trac.sagemath.org/ticket/25477#comment:99
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Okay, the method move is now finished, setting it back to review. Still open to see (maybe @tscrim?) if there is a "simple" way to further speed <code>_generate_new</code> and <code>_generate_new_GAP</code> in <code>permgroup_element</code>.
</p>
TicketjdemeyerTue, 19 Jun 2018 14:43:08 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:100
https://trac.sagemath.org/ticket/25477#comment:100
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Adding <code># distutils: gap</code> to <code>src/sage/groups/perm_gps/permgroup_element.pxd</code> is not correct since <code>permgroup_element.pxd</code> has nothing to do with libGAP. Only the <em>implementation</em> requires libGAP, so the distutils declaration should be in the <code>.pyx</code> file.
</p>
<p>
But really, you should just use <a class="closed ticket" href="https://trac.sagemath.org/ticket/25608" title="enhancement: Further clean up of libGAP declarations (closed: fixed)">#25608</a> instead and not add <code># distutils: gap</code>.
</p>
TicketgitTue, 19 Jun 2018 14:56:12 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:101
https://trac.sagemath.org/ticket/25477#comment:101
<ul>
<li><strong>commit</strong>
changed from <em>6654f752bc716676c05f37e2845c4d7c1babc1fe</em> to <em>70fbfffa7f8a9b04dcc5a13822016f13f877dd16</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=70fbfffa7f8a9b04dcc5a13822016f13f877dd16"><span class="icon"></span>70fbfff</a></td><td><code>Merge branch 'develop' into t/25477/enumerate_PermutationGroup</code>
</td></tr></table>
TicketgitTue, 19 Jun 2018 15:00:19 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:102
https://trac.sagemath.org/ticket/25477#comment:102
<ul>
<li><strong>commit</strong>
changed from <em>70fbfffa7f8a9b04dcc5a13822016f13f877dd16</em> to <em>f99aee18b8af58105d6464eee644284731660a37</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=44b9ee03c32890456b017ba60f132b3b6be14716"><span class="icon"></span>44b9ee0</a></td><td><code>Further clean up of libGAP declarations</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=99fa0d0e93eb39e12aedb853fe52772920fbb8bc"><span class="icon"></span>99fa0d0</a></td><td><code>Merge branch 't/25608/further_clean_up_of_libgap_declarations' into t/25477/enumerate_PermutationGroup</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=f99aee18b8af58105d6464eee644284731660a37"><span class="icon"></span>f99aee1</a></td><td><code>removed gap import in permgroup_element</code>
</td></tr></table>
TicketjdemeyerTue, 19 Jun 2018 15:01:18 GMT
https://trac.sagemath.org/ticket/25477#comment:103
https://trac.sagemath.org/ticket/25477#comment:103
<ol><li>You should use <code>range()</code> instead of this outdated syntax:
<pre class="wiki">for i from 0 <= i < vn:
</pre></li></ol><ol start="2"><li>Are you certain that <code>cdef int vn = lst.__len__()</code> won't overflow? As far as I know, both Python and libGAP support lists with over 2<sup>32</sup> elements. Better use <code>Py_ssize_t</code>, which is anyway the standard CPython type for lengths.
</li></ol><ol start="3"><li>Why did you write <code>lst.__len__()</code> instead of <code>len(lst)</code>?
</li></ol><ol start="4"><li>Why are the new methods <code>cpdef</code> instead of <code>def</code>? They are not called from Cython, so that's only a pessimization.
</li></ol><ol start="5"><li>Why <code>cdef PermutationGroupElement tmp = <PermutationGroupElement> self</code>?
</li></ol><ol start="6"><li>This is dangerous: <code><GapElement_List> lst_in</code> since you don't know that <code>lst_in</code> is a <code>GapElement_List</code>. Either do an explicit <code>isinstance()</code> check or use <code><GapElement_List?>lst_in</code>.
</li></ol>
TicketgitTue, 19 Jun 2018 15:05:46 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:104
https://trac.sagemath.org/ticket/25477#comment:104
<ul>
<li><strong>commit</strong>
changed from <em>f99aee18b8af58105d6464eee644284731660a37</em> to <em>c9b495e0e22d3c0af1f22fb7c9826d2f16ad3082</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=c9b495e0e22d3c0af1f22fb7c9826d2f16ad3082"><span class="icon"></span>c9b495e</a></td><td><code>fixed issues raised by jdemeyer</code>
</td></tr></table>
TicketgitTue, 19 Jun 2018 15:11:48 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:105
https://trac.sagemath.org/ticket/25477#comment:105
<ul>
<li><strong>commit</strong>
changed from <em>c9b495e0e22d3c0af1f22fb7c9826d2f16ad3082</em> to <em>1be187efe05a7ee899d3a715380cb636aa29c1c0</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=1be187efe05a7ee899d3a715380cb636aa29c1c0"><span class="icon"></span>1be187e</a></td><td><code>removed old artefact in code</code>
</td></tr></table>
Ticketstumpc5Tue, 19 Jun 2018 15:12:41 GMT
https://trac.sagemath.org/ticket/25477#comment:106
https://trac.sagemath.org/ticket/25477#comment:106
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:103" title="Comment 103">jdemeyer</a>:
</p>
<blockquote class="citation">
<ol><li>You should use <code>range()</code> instead of this outdated syntax:
</li></ol></blockquote>
<p>
done
</p>
<blockquote class="citation">
<ol start="2"><li>Are you certain that <code>cdef int vn = lst.__len__()</code> won't overflow? As far as I know, libGAP supports lists with over <code>2^32^</code> elements. Better use <code>Py_ssize_t</code>, which is anyway the standard CPython type for lengths.
</li></ol></blockquote>
<p>
done
</p>
<blockquote class="citation">
<ol start="3"><li>Why did you write <code>lst.__len__()</code> instead of <code>len(lst)</code>?
</li></ol></blockquote>
<p>
doesn't the second call the first? I thought that I'd rather use the first then.
</p>
<blockquote class="citation">
<ol start="4"><li>Why are the new methods <code>cpdef</code> instead of <code>def</code>? They are not called from Cython, so that's only a pessimization.
</li></ol></blockquote>
<p>
my impression is that these are now the fastest way to create new permutations in sage, so I want to propagate their use, especially in critical cythonized places.
</p>
<blockquote class="citation">
<ol start="5"><li>Why <code>cdef PermutationGroupElement tmp = <PermutationGroupElement> self</code>?
</li></ol></blockquote>
<p>
removed
</p>
<blockquote class="citation">
<ol start="6"><li>This is dangerous: <code><GapElement_List> lst_in</code> since you don't know that <code>lst_in</code> is a <code>GapElement_List</code>. Either do an explicit <code>isinstance()</code> check or use <code><GapElement_List?>lst_in</code>.
</li></ol></blockquote>
<p>
I would like to do <code>cpdef _generate_new_GAP(self, GapElement_List lst_in)</code> but do not know how
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=c9b495e0e22d3c0af1f22fb7c9826d2f16ad3082"><span class="icon"></span>c9b495e</a></td><td><code>fixed issues raised by jdemeyer</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=1be187efe05a7ee899d3a715380cb636aa29c1c0"><span class="icon"></span>1be187e</a></td><td><code>removed old artefact in code</code>
</td></tr></table>
TicketdimpaseTue, 19 Jun 2018 15:20:46 GMT
https://trac.sagemath.org/ticket/25477#comment:107
https://trac.sagemath.org/ticket/25477#comment:107
<p>
I don't understand why you're moving things back and forth  don't you want to provide an optimised replacement for <code>GapElement_Permutation</code> in <code>sage.libs.gap.element</code> ?
</p>
Ticketstumpc5Tue, 19 Jun 2018 15:35:13 GMT
https://trac.sagemath.org/ticket/25477#comment:108
https://trac.sagemath.org/ticket/25477#comment:108
<p>
No, I want to obtain an optimized way to create a <code>PermutationGroupElement</code> from a <code>GapElement_Permutation</code> given that I have given a permutation group element of the same parent. This thus became a method for <code>PermutationGroupElement</code> with argument <code>GapElement_List</code>. In particular, I have this method now for python lists and for gap list.
</p>
<p>
As a byproduct, one may call this from the <code>one</code> of the parent if only the parent is given but not the element.
</p>
<p>
See that this later is indeed slower:
</p>
<pre class="wiki">sage: P = PermutationGroup([(1,2),(1,2,3,4,5,6,7,8)])
sage: one = P.one()
sage: perm = libgap.eval('[]')
sage: %timeit one._generate_new_GAP(perm)
The slowest run took 138.45 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 174 ns per loop
sage: %timeit P.one()._generate_new_GAP(perm)
The slowest run took 77.00 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 220 ns per loop
</pre>
TicketjdemeyerTue, 19 Jun 2018 18:45:21 GMTdependencies set
https://trac.sagemath.org/ticket/25477#comment:109
https://trac.sagemath.org/ticket/25477#comment:109
<ul>
<li><strong>dependencies</strong>
set to <em>#25608</em>
</li>
</ul>
TicketgitTue, 03 Jul 2018 13:37:47 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:110
https://trac.sagemath.org/ticket/25477#comment:110
<ul>
<li><strong>commit</strong>
changed from <em>1be187efe05a7ee899d3a715380cb636aa29c1c0</em> to <em>82244f3b70201460fd979e8537b20007d5e99829</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=82244f3b70201460fd979e8537b20007d5e99829"><span class="icon"></span>82244f3</a></td><td><code>Merge branch 'develop' into t/25477/enumerate_PermutationGroup</code>
</td></tr></table>
TicketgitTue, 03 Jul 2018 14:30:55 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:111
https://trac.sagemath.org/ticket/25477#comment:111
<ul>
<li><strong>commit</strong>
changed from <em>82244f3b70201460fd979e8537b20007d5e99829</em> to <em>1d1e70cf8fb96c7381f655c534078be65766cfd9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=1d1e70cf8fb96c7381f655c534078be65766cfd9"><span class="icon"></span>1d1e70c</a></td><td><code>updated and extended doctests</code>
</td></tr></table>
Ticketstumpc5Tue, 03 Jul 2018 14:41:39 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:112
https://trac.sagemath.org/ticket/25477#comment:112
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Again ready for review!
</p>
<blockquote class="citation">
<blockquote class="citation">
<ol start="6"><li>This is dangerous: <code><GapElement_List> lst_in</code> since you don't know that <code>lst_in</code> is a <code>GapElement_List</code>. Either do an explicit <code>isinstance()</code> check or use <code><GapElement_List?>lst_in</code>.
</li></ol></blockquote>
<p>
I would like to do <code>cpdef _generate_new_GAP(self, GapElement_List lst_in)</code> but do not know how
</p>
</blockquote>
<p>
this is still open.
</p>
TickettscrimTue, 03 Jul 2018 14:58:27 GMTreviewer, branch, commit changed
https://trac.sagemath.org/ticket/25477#comment:113
https://trac.sagemath.org/ticket/25477#comment:113
<ul>
<li><strong>reviewer</strong>
changed from <em>Christian Stump, Dima Pasechnik</em> to <em>Christian Stump, Dima Pasechnik, Travis Scrimshaw</em>
</li>
<li><strong>branch</strong>
changed from <em>u/stumpc5/enumerate_PermutationGroup</em> to <em>u/tscrim/iteration_permutation_groups25477</em>
</li>
<li><strong>commit</strong>
changed from <em>1d1e70cf8fb96c7381f655c534078be65766cfd9</em> to <em>83d485a9e424a35566190d548aee64f7c89fe088</em>
</li>
</ul>
<p>
So I don't understand the comment about iterations. So I removed it. However, if SGS is not consistent across different computers, we have a problem with doctests. The RES is guaranteed to have a fixed iteration order, so I can only assume the SGS does not have such a guarantee. I changed the doctests to what I needed for them to pass, but I am guessing they will fail for you. If they pass for you and SGS is consistent, then the comment should have been removed anyways.
</p>
<p>
I made a few other tweaks.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=83d485a9e424a35566190d548aee64f7c89fe088"><span class="icon"></span>83d485a</a></td><td><code>Reviewer changes.</code>
</td></tr></table>
TickettscrimTue, 03 Jul 2018 14:59:26 GMTkeywords changed
https://trac.sagemath.org/ticket/25477#comment:114
https://trac.sagemath.org/ticket/25477#comment:114
<ul>
<li><strong>keywords</strong>
<em>days94</em> added
</li>
</ul>
Ticketstumpc5Tue, 03 Jul 2018 15:31:37 GMT
https://trac.sagemath.org/ticket/25477#comment:115
https://trac.sagemath.org/ticket/25477#comment:115
<p>
Thanks Travis!
</p>
<pre class="wiki"> G = libgap.Group(self.gens())
+ G = libgap(self) #libgap.Group(self.gens())
</pre><p>
I chose the first because it was slightly faster. Also I wanted to keep
</p>
<pre class="wiki"> # the following also works but is much slower:
 #gap2sage = lambda elt: one._generate_new(libgap.ListPerm(elt).sage())
 #gap2sage = lambda elt: libgap.ListPerm(elt)._generate_perm(one)
</pre><p>
to see the other but slower ways to do this.
</p>
<pre class="wiki"> in the two algorithms, and is not even guaranteed to always
 be the same for one of the two.
</pre><p>
This now depends on gap behaviour, also I prefer not to guarantee that I will not change the output when changing the implementation. Anyways, if you prefer to remove it, that's fine too.
</p>
TickettscrimTue, 03 Jul 2018 15:44:59 GMT
https://trac.sagemath.org/ticket/25477#comment:116
https://trac.sagemath.org/ticket/25477#comment:116
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:115" title="Comment 115">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
Thanks Travis!
</p>
<pre class="wiki"> G = libgap.Group(self.gens())
+ G = libgap(self) #libgap.Group(self.gens())
</pre><p>
I chose the first because it was slightly faster.
</p>
</blockquote>
<p>
I get the latter is faster:
</p>
<pre class="wiki">sage: A = PermutationGroup([(1,2),(1,2,3,4,5,6,7,8,9)])
sage: %timeit libgap.Group(A.gens())
The slowest run took 13.32 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 53.5 µs per loop
sage: %timeit libgap(A)
The slowest run took 4.21 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 35.6 µs per loop
</pre><blockquote class="citation">
<p>
Also I wanted to keep
</p>
<pre class="wiki"> # the following also works but is much slower:
 #gap2sage = lambda elt: one._generate_new(libgap.ListPerm(elt).sage())
 #gap2sage = lambda elt: libgap.ListPerm(elt)._generate_perm(one)
</pre><p>
to see the other but slower ways to do this.
</p>
</blockquote>
<p>
Commented out code gets removed quite quickly by other people and looks bad to put slower code. The data is in the history if someone wants to look it up.
</p>
<blockquote class="citation">
<pre class="wiki"> in the two algorithms, and is not even guaranteed to always
 be the same for one of the two.
</pre><p>
This now depends on gap behaviour, also I prefer not to guarantee that I will not change the output when changing the implementation. Anyways, if you prefer to remove it, that's fine too.
</p>
</blockquote>
<p>
If a particular version of GAP is consistent, than no comment is necessary (a number of doctests typically change when GAP upgrades). We have never guaranteed an output order for group iteration, so I don't see any point in mentioning it.
</p>
Ticketstumpc5Tue, 03 Jul 2018 15:47:07 GMT
https://trac.sagemath.org/ticket/25477#comment:117
https://trac.sagemath.org/ticket/25477#comment:117
<p>
Okay, let's see which doctests have to be undated (given the new ordering of the permgroup iteration).
</p>
Ticketstumpc5Wed, 04 Jul 2018 07:02:20 GMTbranch changed
https://trac.sagemath.org/ticket/25477#comment:118
https://trac.sagemath.org/ticket/25477#comment:118
<ul>
<li><strong>branch</strong>
changed from <em>u/tscrim/iteration_permutation_groups25477</em> to <em>u/stumpc5/iteration_permutation_groups25477</em>
</li>
</ul>
Ticketstumpc5Wed, 04 Jul 2018 07:03:57 GMTcc, commit changed
https://trac.sagemath.org/ticket/25477#comment:119
https://trac.sagemath.org/ticket/25477#comment:119
<ul>
<li><strong>cc</strong>
<em>rbeezer</em> added
</li>
<li><strong>commit</strong>
changed from <em>83d485a9e424a35566190d548aee64f7c89fe088</em> to <em>63d057d7e21b3f0f52ac990486ebd4efd07755de</em>
</li>
</ul>
<p>
I updated the permutation group iteration order in <code>judsonabstractalgebra</code> and cc'ed Rob Beezer her as requested there.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=63d057d7e21b3f0f52ac990486ebd4efd07755de"><span class="icon"></span>63d057d</a></td><td><code>fixed doctests in judsonabstractalgebra</code>
</td></tr></table>
Ticketstumpc5Wed, 04 Jul 2018 07:12:03 GMT
https://trac.sagemath.org/ticket/25477#comment:120
https://trac.sagemath.org/ticket/25477#comment:120
<p>
Currently, the slow iteration using <code>RecursivelyEnumeratedSet</code> uses depth first search with generators being the group generators. Which of the following would you prefer:
</p>
<ol><li>Depth or breadth first search ?
</li><li>Generators or generators plus their inverses?
</li></ol><p>
I would think that bfs would be a more natural ordering, especially for small groups that you actually look at and see how the Cayley graph is propagated. Using also inverses is another question and I don't actually have a preference. Sometimes generating sets for Cayley graphs are expected to also contain inverses, sometimes not.
</p>
TicketdimpaseWed, 04 Jul 2018 17:34:42 GMT
https://trac.sagemath.org/ticket/25477#comment:121
https://trac.sagemath.org/ticket/25477#comment:121
<p>
while you are at it, could you fix the doc for PermutationGroupElement?
It appears that what you get from <code>sage: PermutationGroupElement?</code> has not made it into the corresponding rst file, e.g. it's not possible to see an example with an explicit parent in the reference manual (in section <a class="extlink" href="http://doc.sagemath.org/html/en/reference/groups/sage/groups/perm_gps/permgroup_element.html"><span class="icon"></span>http://doc.sagemath.org/html/en/reference/groups/sage/groups/perm_gps/permgroup_element.html</a>)
</p>
<p>
Also, an example with an explicit parent out to be given in Examples, not in Tests only.
</p>
TicketgitWed, 04 Jul 2018 18:24:01 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:122
https://trac.sagemath.org/ticket/25477#comment:122
<ul>
<li><strong>commit</strong>
changed from <em>63d057d7e21b3f0f52ac990486ebd4efd07755de</em> to <em>596dc649a793f90cc072185d0fb2caa7d18eb3a5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=a2dd20215857b86daa784488e0c3aba57e706b9d"><span class="icon"></span>a2dd202</a></td><td><code>updated doctests for generic graph</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=596dc649a793f90cc072185d0fb2caa7d18eb3a5"><span class="icon"></span>596dc64</a></td><td><code>fixed some more doctests</code>
</td></tr></table>
Ticketstumpc5Wed, 04 Jul 2018 18:25:39 GMT
https://trac.sagemath.org/ticket/25477#comment:123
https://trac.sagemath.org/ticket/25477#comment:123
<p>
I fixed a few more doctests, not done yet. Let me mention that I find it questionable (and risky) that so many doctests fail due to this change of iteration...
</p>
TicketdimpaseWed, 04 Jul 2018 18:31:09 GMT
https://trac.sagemath.org/ticket/25477#comment:124
https://trac.sagemath.org/ticket/25477#comment:124
<p>
to me, this rather shows that make doctests depend upon an order which need to be preserved is not a good idea in the first place...
</p>
Ticketstumpc5Wed, 04 Jul 2018 18:40:45 GMT
https://trac.sagemath.org/ticket/25477#comment:125
https://trac.sagemath.org/ticket/25477#comment:125
<p>
yes, and even more is true: some doctest pick out some unspecified element
</p>
<pre class="wiki"> sage: SGA.group()
Symmetric group of order 4! as a permutation group
sage: SGA.an_element()
 () + 2*(1,2) + 4*(1,2,3,4)
+ () + (1,2,3,4) + 2*(1,3)(2,4) + 3*(1,4)(2,3)
</pre><p>
do stuff with it
</p>
<pre class="wiki">
sage: G = SymmetricGroup(4).algebra(QQ)
sage: G.retract_plain(G.an_element(), 3)
 () + 2*(1,2)
+ ()
</pre><p>
which might be boring for other elements (such as here), or even pick special elements with intended properties from it
</p>
<pre class="wiki"> sage: D = DihedralGroup(5)
sage: elements = D.list(); elements
 [(), (1,5)(2,4), (1,2,3,4,5), (1,4)(2,3), (1,3,5,2,4), (2,5)(3,4),
 (1,3)(4,5), (1,5,4,3,2), (1,4,2,5,3), (1,2)(3,5)]

~~~~~~~~~~~~~~~~~~~~~~ ::

 sage: rotate = elements[2]
 sage: flip = elements[3]
</pre>
TicketdimpaseWed, 04 Jul 2018 19:10:37 GMT
https://trac.sagemath.org/ticket/25477#comment:126
https://trac.sagemath.org/ticket/25477#comment:126
<p>
I would have rewritten the test
</p>
<pre class="wiki">sage: SGA.an_element()
...
</pre><p>
as
</p>
<pre class="wiki">sage: SGA.an_element() in SGA
True
</pre><p>
etc...
</p>
TicketgitThu, 05 Jul 2018 07:55:53 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:127
https://trac.sagemath.org/ticket/25477#comment:127
<ul>
<li><strong>commit</strong>
changed from <em>596dc649a793f90cc072185d0fb2caa7d18eb3a5</em> to <em>a9fb42bf2d314a6bde076d3d4ca0d2c1801c4a80</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=a9fb42bf2d314a6bde076d3d4ca0d2c1801c4a80"><span class="icon"></span>a9fb42b</a></td><td><code>fixed some more doctests</code>
</td></tr></table>
TicketgitThu, 05 Jul 2018 08:14:11 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:128
https://trac.sagemath.org/ticket/25477#comment:128
<ul>
<li><strong>commit</strong>
changed from <em>a9fb42bf2d314a6bde076d3d4ca0d2c1801c4a80</em> to <em>a6d7793fd090de56b0609d5ba6c6f22ab287b660</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=83d485a9e424a35566190d548aee64f7c89fe088"><span class="icon"></span>83d485a</a></td><td><code>Reviewer changes.</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=a6d7793fd090de56b0609d5ba6c6f22ab287b660"><span class="icon"></span>a6d7793</a></td><td><code>Merge branch 'u/tscrim/iteration_permutation_groups25477' into t/25477/enumerate_PermutationGroup</code>
</td></tr></table>
TicketgitThu, 05 Jul 2018 08:33:57 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:129
https://trac.sagemath.org/ticket/25477#comment:129
<ul>
<li><strong>commit</strong>
changed from <em>a6d7793fd090de56b0609d5ba6c6f22ab287b660</em> to <em>55d5c64a0e0e7d28ae5b78120f70d069f8cd028c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=55d5c64a0e0e7d28ae5b78120f70d069f8cd028c"><span class="icon"></span>55d5c64</a></td><td><code>implemented breadth and depth first search iteration</code>
</td></tr></table>
TicketgitThu, 05 Jul 2018 10:34:25 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:130
https://trac.sagemath.org/ticket/25477#comment:130
<ul>
<li><strong>commit</strong>
changed from <em>55d5c64a0e0e7d28ae5b78120f70d069f8cd028c</em> to <em>9504bc275b11c5f3deb57c7aab937f01858aa903</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=9504bc275b11c5f3deb57c7aab937f01858aa903"><span class="icon"></span>9504bc2</a></td><td><code>fixed more doctests</code>
</td></tr></table>
TicketgitThu, 05 Jul 2018 12:55:44 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:131
https://trac.sagemath.org/ticket/25477#comment:131
<ul>
<li><strong>commit</strong>
changed from <em>9504bc275b11c5f3deb57c7aab937f01858aa903</em> to <em>97ce6291fbc34d4d760b6433d32f9196b347a34d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=97ce6291fbc34d4d760b6433d32f9196b347a34d"><span class="icon"></span>97ce629</a></td><td><code>more doctests</code>
</td></tr></table>
TickettscrimThu, 05 Jul 2018 15:25:47 GMT
https://trac.sagemath.org/ticket/25477#comment:132
https://trac.sagemath.org/ticket/25477#comment:132
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:126" title="Comment 126">dimpase</a>:
</p>
<blockquote class="citation">
<p>
I would have rewritten the test
</p>
<pre class="wiki">sage: SGA.an_element()
...
</pre><p>
as
</p>
<pre class="wiki">sage: SGA.an_element() in SGA
True
</pre><p>
etc...
</p>
</blockquote>
<p>
Well, the generic element is usually generic enough to be useful. This test only works when testing <code>_an_element_</code>. It is used elsewhere to show how the element changes.
</p>
TickettscrimThu, 05 Jul 2018 15:27:37 GMT
https://trac.sagemath.org/ticket/25477#comment:133
https://trac.sagemath.org/ticket/25477#comment:133
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:123" title="Comment 123">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
I fixed a few more doctests, not done yet. Let me mention that I find it questionable (and risky) that so many doctests fail due to this change of iteration...
</p>
</blockquote>
<p>
I agree there is some risk, but a good review should be checking that it is just an order difference. So generically, I would say your concern is misplaced. However, I am very worried there is an order dependency on the machine, which means we have write more annoying doctests (i.e., calling <code>sorted</code> a lot).
</p>
TickettscrimThu, 05 Jul 2018 15:28:19 GMT
https://trac.sagemath.org/ticket/25477#comment:134
https://trac.sagemath.org/ticket/25477#comment:134
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:120" title="Comment 120">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
Currently, the slow iteration using <code>RecursivelyEnumeratedSet</code> uses depth first search with generators being the group generators. Which of the following would you prefer:
</p>
<ol><li>Depth or breadth first search ?
</li><li>Generators or generators plus their inverses?
</li></ol><p>
I would think that bfs would be a more natural ordering
</p>
</blockquote>
<p>
I would just let it run its default, but if I had to choose, I would say BFS as well.
</p>
TickettscrimThu, 05 Jul 2018 15:28:57 GMT
https://trac.sagemath.org/ticket/25477#comment:135
https://trac.sagemath.org/ticket/25477#comment:135
<p>
Also one little thing, but could you break the long output line in <code>sage/categories/finite_dimensional_lie_algebras_with_basis.py</code> (like how it was before).
</p>
Ticketstumpc5Thu, 05 Jul 2018 17:45:11 GMT
https://trac.sagemath.org/ticket/25477#comment:136
https://trac.sagemath.org/ticket/25477#comment:136
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:134" title="Comment 134">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I would just let it run its default, but if I had to choose, I would say BFS as well.
</p>
</blockquote>
<p>
Well, we now have the three options SGS, BFS, DFS. I think that should be okay now...
</p>
TickettscrimThu, 05 Jul 2018 17:48:16 GMT
https://trac.sagemath.org/ticket/25477#comment:137
https://trac.sagemath.org/ticket/25477#comment:137
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:136" title="Comment 136">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:134" title="Comment 134">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I would just let it run its default, but if I had to choose, I would say BFS as well.
</p>
</blockquote>
<p>
Well, we now have the three options SGS, BFS, DFS. I think that should be okay now...
</p>
</blockquote>
<p>
A better way would be to pass options to RES.
</p>
TicketrbeezerFri, 06 Jul 2018 02:08:19 GMT
https://trac.sagemath.org/ticket/25477#comment:138
https://trac.sagemath.org/ticket/25477#comment:138
<p>
Dear Christian,
</p>
<p>
Thanks very much for the cc on the changes to Judson's AATA. I'll be able to do a diff and even more quickly discern what has changed. I'm waiting on 8.3 to do a new update for the book, so this may miss that cutoff, but that should not be a crisis by any means. Thanks everyone for your work keeping this code working well.
</p>
<p>
Rob
</p>
TicketgitFri, 06 Jul 2018 08:46:29 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:139
https://trac.sagemath.org/ticket/25477#comment:139
<ul>
<li><strong>commit</strong>
changed from <em>97ce6291fbc34d4d760b6433d32f9196b347a34d</em> to <em>b586d0c3ab19a30a6004d04fb373286cb9d35a86</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=b586d0c3ab19a30a6004d04fb373286cb9d35a86"><span class="icon"></span>b586d0c</a></td><td><code>added examples of perm gp elts into documentation</code>
</td></tr></table>
Ticketstumpc5Fri, 06 Jul 2018 08:47:03 GMT
https://trac.sagemath.org/ticket/25477#comment:140
https://trac.sagemath.org/ticket/25477#comment:140
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:121" title="Comment 121">dimpase</a>:
</p>
<blockquote class="citation">
<p>
while you are at it, could you fix the doc for PermutationGroupElement?
</p>
</blockquote>
<p>
done.
</p>
TickettscrimSat, 11 Aug 2018 21:47:38 GMT
https://trac.sagemath.org/ticket/25477#comment:141
https://trac.sagemath.org/ticket/25477#comment:141
<p>
I know, I need to finish a review of this (including doing a rebase). This might also conflict with <a class="closed ticket" href="https://trac.sagemath.org/ticket/26045" title="enhancement: py3 some fixes in root_systems (closed: fixed)">#26045</a>. This is now been able to become high on my todo list.
</p>
TickettscrimFri, 24 Aug 2018 22:53:08 GMTcommit, dependencies, branch, milestone changed
https://trac.sagemath.org/ticket/25477#comment:142
https://trac.sagemath.org/ticket/25477#comment:142
<ul>
<li><strong>commit</strong>
changed from <em>b586d0c3ab19a30a6004d04fb373286cb9d35a86</em> to <em>ca2d1b3bdecc3544afd400f21151fe81d096a794</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#25608</em> to <em>#25608 #26045</em>
</li>
<li><strong>branch</strong>
changed from <em>u/stumpc5/iteration_permutation_groups25477</em> to <em>public/group_theory/improve_iterator_perm_gps25477</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage8.3</em> to <em>sage8.4</em>
</li>
</ul>
<p>
I have rebased it to 8.4.beta1 and over <a class="closed ticket" href="https://trac.sagemath.org/ticket/26045" title="enhancement: py3 some fixes in root_systems (closed: fixed)">#26045</a>. However, let's let this run on some patchbots to see if there is any machine dependency (in addition, if some of the other people here can do so). If there are no doctest failures, then we are safe to assume the SGS iterator is not machine dependent. With that, I would be okay setting a positive review.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=19f82d12c5f522f4f9b0ad05a30c492ffaaac2a2"><span class="icon"></span>19f82d1</a></td><td><code>various fixes for py3 in combinat and root_systems</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=7456780bfb55ddedbe65b6bc4f31f724c00e7cb8"><span class="icon"></span>7456780</a></td><td><code>pyflakes cleanup in one file</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=3c25ec35eeca78c629996eda6bae24dc201d72b3"><span class="icon"></span>3c25ec3</a></td><td><code>fix sorting key for affine root systems</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=4a2c24404774b1bff340fbf85843b902a3a060d1"><span class="icon"></span>4a2c244</a></td><td><code>Merge branch 'u/chapoton/26045' in 8.4.b1</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=79c25c93cdd01502e91ea7f459eb1d3248be28c6"><span class="icon"></span>79c25c9</a></td><td><code>Merge branch 'u/stumpc5/iteration_permutation_groups25477' of git://trac.sagemath.org/sage into public/group_theory/improve_iterator_perm_gps25477</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit?id=ca2d1b3bdecc3544afd400f21151fe81d096a794"><span class="icon"></span>ca2d1b3</a></td><td><code>Fixing doctests due to bad rebase and some doc tweaks.</code>
</td></tr></table>
TicketgitTue, 18 Sep 2018 08:52:31 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:143
https://trac.sagemath.org/ticket/25477#comment:143
<ul>
<li><strong>commit</strong>
changed from <em>ca2d1b3bdecc3544afd400f21151fe81d096a794</em> to <em>1b00bf24882d4a3cf2e38380501c4d76a926fc93</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=1b00bf24882d4a3cf2e38380501c4d76a926fc93"><span class="icon"></span>1b00bf2</a></td><td><code>merged</code>
</td></tr></table>
Ticketstumpc5Tue, 18 Sep 2018 11:38:38 GMT
https://trac.sagemath.org/ticket/25477#comment:144
https://trac.sagemath.org/ticket/25477#comment:144
<p>
@tscrim: what to do with these doctest failures?
</p>
TicketgitTue, 18 Sep 2018 22:47:44 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:145
https://trac.sagemath.org/ticket/25477#comment:145
<ul>
<li><strong>commit</strong>
changed from <em>1b00bf24882d4a3cf2e38380501c4d76a926fc93</em> to <em>f226bc3953195da299e35f8b2b2bbb34264cb097</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=5af3439fea2d996e84ceb1190c863b5a58d82509"><span class="icon"></span>5af3439</a></td><td><code>Fix the erroneous fix of some corner cases</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=138f85b3c9ad61aab1116b5acac2062f175fd298"><span class="icon"></span>138f85b</a></td><td><code>Turn some functions of polynomial.hilbert to methods of ETuple</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=e900222fb9b43aa1470790f1e9d903bb0270dcb3"><span class="icon"></span>e900222</a></td><td><code>Hilbert series: Remove unnecessary bound checks, simplify code branches</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=f0e5c8585489cdf3a80e3ee161561184bb648408"><span class="icon"></span>f0e5c85</a></td><td><code>Add documentation to new ETuple methods</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=2d29b9b164fd1e429466c882ace499a238ecf02c"><span class="icon"></span>2d29b9b</a></td><td><code>Using slices, custom median, and formatting/P#P8 tweaks to Hilbert code.</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=07ff2e1627ea16a9921dde8ffea053e597630043"><span class="icon"></span>07ff2e1</a></td><td><code>Reverting use of get_exp for __getitem__.</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=7b2ed5054f9b88eb0da5f60da8894b7368b11519"><span class="icon"></span>7b2ed50</a></td><td><code>Merge branch 'u/tscrim/hilbert_functions26243' of git://trac.sagemath.org/sage into u/tscrim/hilbert_functions26243</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=5637e07941cab4d3c8ea35b0b35b94150ed0a58c"><span class="icon"></span>5637e07</a></td><td><code>Fixing INPUT:: to INPUT: in hilbert.pyx.</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=10f39217f8b56040b44e36962529112d9890acc0"><span class="icon"></span>10f3921</a></td><td><code>Merge branch 'public/group_theory/improve_iterator_perm_gps25477' of git://trac.sagemath.org/sage into public/group_theory/improve_iterator_perm_gps25477</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=f226bc3953195da299e35f8b2b2bbb34264cb097"><span class="icon"></span>f226bc3</a></td><td><code>Fixing trivial doctest failures.</code>
</td></tr></table>
TicketgitTue, 18 Sep 2018 22:51:15 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:146
https://trac.sagemath.org/ticket/25477#comment:146
<ul>
<li><strong>commit</strong>
changed from <em>f226bc3953195da299e35f8b2b2bbb34264cb097</em> to <em>dddbcf33c4e8113862e127b26ca5a9e6e6d62267</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=dddbcf33c4e8113862e127b26ca5a9e6e6d62267"><span class="icon"></span>dddbcf3</a></td><td><code>Fixing trivial doctest failures.</code>
</td></tr></table>
TickettscrimTue, 18 Sep 2018 22:52:13 GMT
https://trac.sagemath.org/ticket/25477#comment:147
https://trac.sagemath.org/ticket/25477#comment:147
<p>
Since <a class="closed ticket" href="https://trac.sagemath.org/ticket/26225" title="enhancement: py3: change the repr of Finite families (closed: fixed)">#26225</a> is now in Sage, those doctest should essentially be sorted (or given by a fixed ordering). So this should fix those. Also you were missing a blank line in one of the book tests.
</p>
<p>
(Sorry about the noise, I was not based on develop. Fixed in the last forced push.)
</p>
Ticketstumpc5Wed, 19 Sep 2018 06:19:24 GMT
https://trac.sagemath.org/ticket/25477#comment:148
https://trac.sagemath.org/ticket/25477#comment:148
<p>
Only
</p>
<pre class="wiki">File "src/sage/tests/books/judsonabstractalgebra/permutesage.py", line 268, in sage.tests.books.judsonabstractalgebra.permutesage
Failed example:
H.list()
Expected:
[(), (1,3), (4,5), (1,3)(4,5)]
Got:
[(), (4,5), (1,3), (1,3)(4,5)]
</pre><p>
seems to be left. What kind of sorting do you want there?
</p>
TicketgitWed, 19 Sep 2018 08:25:49 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:149
https://trac.sagemath.org/ticket/25477#comment:149
<ul>
<li><strong>commit</strong>
changed from <em>dddbcf33c4e8113862e127b26ca5a9e6e6d62267</em> to <em>1a3a69aab4d4f681c9e6237dc8bdfaa17fc93def</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=1a3a69aab4d4f681c9e6237dc8bdfaa17fc93def"><span class="icon"></span>1a3a69a</a></td><td><code>Fix the ordering of one more test.</code>
</td></tr></table>
TickettscrimWed, 19 Sep 2018 08:26:57 GMT
https://trac.sagemath.org/ticket/25477#comment:150
https://trac.sagemath.org/ticket/25477#comment:150
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:148" title="Comment 148">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
What kind of sorting do you want there?
</p>
</blockquote>
<p>
I suspect that is just a leftover from the test not being run. I doubt it is machinedependent, so the fix I just pushed should take care of it.
</p>
Ticketstumpc5Wed, 19 Sep 2018 12:06:49 GMT
https://trac.sagemath.org/ticket/25477#comment:151
https://trac.sagemath.org/ticket/25477#comment:151
<p>
okay, this seems to be ready to go!
</p>
TickettscrimWed, 19 Sep 2018 13:00:54 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:152
https://trac.sagemath.org/ticket/25477#comment:152
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketvbraunThu, 20 Sep 2018 21:28:19 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:153
https://trac.sagemath.org/ticket/25477#comment:153
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Can you have a look at the patchbot output: Python3 incompatible code inserted on 1 nonempty lines. Also, tests fail
</p>
<pre class="wiki">sage t long src/sage/geometry/polyhedron/ppl_lattice_polytope.py # 1 doctest failed
</pre>
TickettscrimThu, 20 Sep 2018 22:28:36 GMT
https://trac.sagemath.org/ticket/25477#comment:154
https://trac.sagemath.org/ticket/25477#comment:154
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:153" title="Comment 153">vbraun</a>:
</p>
<blockquote class="citation">
<p>
Can you have a look at the patchbot output: Python3 incompatible code inserted on 1 nonempty lines.
</p>
</blockquote>
<p>
That is libGAP code on that line (comes from the <code>libgap.function_factory("""</code>), so it is not Python3 incompatible.
</p>
<blockquote class="citation">
<p>
Also, tests fail
</p>
<pre class="wiki">sage t long src/sage/geometry/polyhedron/ppl_lattice_polytope.py # 1 doctest failed
</pre></blockquote>
<p>
I think I forgot to run the <code>long</code> when I checked this locally (and so I concluded that it was a spurious patchbot fault). However, I did confirm this locally. It seems like the group is too large to pass to libgap:
</p>
<pre class="wiki">sage: libgap(aut) # the group from the test in question
python2: libgap.c:184: libgap_get_input: Assertion `strlen(libGAP_stdin_buffer) < length' failed.
</pre><p>
It has 1152 generators! However <code>gap</code> handles this fine.
</p>
<p>
So I just reverted the first change on <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:115" title="Comment 115">comment:115</a>, and that seems to fix the problem. I can see how that is more safe as I am surprised <code>libgap</code> is passing things by strings. Which might account for the fact that @stumpc5 and me got different timing results.
</p>
TicketgitThu, 20 Sep 2018 22:28:44 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:155
https://trac.sagemath.org/ticket/25477#comment:155
<ul>
<li><strong>commit</strong>
changed from <em>1a3a69aab4d4f681c9e6237dc8bdfaa17fc93def</em> to <em>1a85742fa2577f9612fe1df3ac7faad52e2ee050</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=1a85742fa2577f9612fe1df3ac7faad52e2ee050"><span class="icon"></span>1a85742</a></td><td><code>Using libgap.Group(self.gens()) to avoid input string limits via libgap(self).</code>
</td></tr></table>
TickettscrimThu, 20 Sep 2018 22:28:54 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:156
https://trac.sagemath.org/ticket/25477#comment:156
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketvbraunThu, 20 Sep 2018 22:52:32 GMT
https://trac.sagemath.org/ticket/25477#comment:157
https://trac.sagemath.org/ticket/25477#comment:157
<p>
Its the Weyl group of F4...
</p>
<p>
libgap is passing by strings but there is an assumption that it fits into a certain buffer. This could be fixed...
</p>
TicketdimpaseThu, 20 Sep 2018 23:06:40 GMT
https://trac.sagemath.org/ticket/25477#comment:158
https://trac.sagemath.org/ticket/25477#comment:158
<p>
Why on Earth one generates all the 1152 elements of W(F_4)? This looks like something really weird in the implementation...
</p>
TickettscrimThu, 20 Sep 2018 23:12:20 GMT
https://trac.sagemath.org/ticket/25477#comment:159
https://trac.sagemath.org/ticket/25477#comment:159
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:157" title="Comment 157">vbraun</a>:
</p>
<blockquote class="citation">
<p>
Its the Weyl group of F4...
</p>
</blockquote>
<p>
Right, but the computation uses all of the elements as generators, which is what makes it blowout the buffer.
</p>
<blockquote class="citation">
<p>
libgap is passing by strings but there is an assumption that it fits into a certain buffer. This could be fixed...
</p>
</blockquote>
<p>
I agree, but this is the less invasive (and easier) change. Ideally a <code>PermutationGroup</code> and its elements would directly construct the object in libgap using the C data structures.
</p>
TickettscrimFri, 21 Sep 2018 01:37:55 GMT
https://trac.sagemath.org/ticket/25477#comment:160
https://trac.sagemath.org/ticket/25477#comment:160
<p>
That change annoyingly causes the output order to change... So, should we fix the output order (again) or revert 1a85742 and do a more proper fix of the libgap interface?
</p>
TicketdimpaseFri, 21 Sep 2018 06:57:12 GMT
https://trac.sagemath.org/ticket/25477#comment:161
https://trac.sagemath.org/ticket/25477#comment:161
<p>
What exactly is happening in the latest commit? Do you mean to say that before it
<code>libgap(bla)</code>, for <code>bla</code> a permutation group, caused all the elements of <code>bla</code> to be listed?! If so, this was certainly a bug.
</p>
TickettscrimFri, 21 Sep 2018 06:59:32 GMT
https://trac.sagemath.org/ticket/25477#comment:162
https://trac.sagemath.org/ticket/25477#comment:162
<p>
No, I am saying that <code>libgap(bla)</code> and <code>libgap.Group(bla.gens())</code> results in a different iteration order (at least in Sage) of the group elements.
</p>
TicketdimpaseFri, 21 Sep 2018 07:25:24 GMT
https://trac.sagemath.org/ticket/25477#comment:163
https://trac.sagemath.org/ticket/25477#comment:163
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:113" title="Comment 113">tscrim</a>:
</p>
<blockquote class="citation">
<p>
So I don't understand the comment about iterations. So I removed it. However, if SGS is not consistent across different computers, we have a problem with doctests. The RES is guaranteed to have a fixed iteration order, so I can only assume the SGS does not have such a guarantee. I changed the doctests to what I needed for them to pass, but I am guessing they will fail for you. If they pass for you and SGS is consistent, then the comment should have been removed anyways.
</p>
</blockquote>
<p>
SGS is often computed with a randomisation involved, and so one cannot guarantee the same chain of subgroups across different runs on the same machine.
If you fix the base to be used, you'd have less variance, but still there could be randomisation involved in choosing the ordering of the base elements.
</p>
<p>
We should not tweak algorithms in order to make testing easier, we should tweak tests, anyway.
</p>
<p>
What is RES?
</p>
TickettscrimFri, 21 Sep 2018 07:29:34 GMT
https://trac.sagemath.org/ticket/25477#comment:164
https://trac.sagemath.org/ticket/25477#comment:164
<p>
RES = <code>RecursivelyEnumeratedSet</code>.
</p>
TicketgitFri, 28 Sep 2018 00:25:41 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:165
https://trac.sagemath.org/ticket/25477#comment:165
<ul>
<li><strong>commit</strong>
changed from <em>1a85742fa2577f9612fe1df3ac7faad52e2ee050</em> to <em>916cea6571eb56c3c88d54cd3373476030ce501c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=b52770e1f67b39016493b64eb559b6142cca9277"><span class="icon"></span>b52770e</a></td><td><code>Merge branch 'public/group_theory/improve_iterator_perm_gps25477' of git://trac.sagemath.org/sage into public/group_theory/improve_iterator_perm_gps25477</code>
</td></tr><tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=916cea6571eb56c3c88d54cd3373476030ce501c"><span class="icon"></span>916cea6</a></td><td><code>Fixing doctests due to change in output order.</code>
</td></tr></table>
TickettscrimFri, 28 Sep 2018 00:27:41 GMT
https://trac.sagemath.org/ticket/25477#comment:166
https://trac.sagemath.org/ticket/25477#comment:166
<p>
I've just updated the doctests to reflect the change in ordering (or remove the dependence on the ordering). So if the patchbots come back green, I think we can set this back to a positive review (that should be reasonable enough confirmation that the doctest outputs are not machinedependent).
</p>
TickettscrimFri, 28 Sep 2018 04:55:03 GMT
https://trac.sagemath.org/ticket/25477#comment:167
https://trac.sagemath.org/ticket/25477#comment:167
<p>
One green patchbot and one almost green. I don't see how the error in computing the volume of a polytope could be caused by this ticket, so I suspect it is an unrelated failure.
</p>
TicketdimpaseFri, 28 Sep 2018 10:34:36 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:168
https://trac.sagemath.org/ticket/25477#comment:168
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Let us get this in. The polyhedral computation stuff done, as in the doctest in question, over RDF, is dodgy anyway (more so as it is done on PPC64, of all platforms), and I don't see how it can have anything to do with this ticket.
</p>
TicketvbraunFri, 28 Sep 2018 22:32:15 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:169
https://trac.sagemath.org/ticket/25477#comment:169
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Merge conflict
</p>
TicketgitMon, 01 Oct 2018 08:00:42 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:170
https://trac.sagemath.org/ticket/25477#comment:170
<ul>
<li><strong>commit</strong>
changed from <em>916cea6571eb56c3c88d54cd3373476030ce501c</em> to <em>ca255bbfb94ace207a6b87a4d364310786315dd1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=ca255bbfb94ace207a6b87a4d364310786315dd1"><span class="icon"></span>ca255bb</a></td><td><code>Merge branch 'develop' into public/group_theory/improve_iterator_perm_gps25477</code>
</td></tr></table>
TickettscrimMon, 01 Oct 2018 08:01:04 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:171
https://trac.sagemath.org/ticket/25477#comment:171
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Trivial merge conflict.
</p>
TicketvbraunTue, 02 Oct 2018 23:03:09 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:172
https://trac.sagemath.org/ticket/25477#comment:172
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<pre class="wiki">File "src/sage/rings/number_field/galois_group.py", line 137, in sage.rings.number_field.galois_group.GaloisGroup_v1.group
Failed example:
list(P) # optional  database_gap
Expected:
[(), (1,2), (1,2,3), (2,3), (1,3,2), (1,3)]
Got:
[(), (1,2,3), (1,3,2), (2,3), (1,2), (1,3)]
**********************************************************************
1 item had failures:
1 of 5 in sage.rings.number_field.galois_group.GaloisGroup_v1.group
[142 tests, 1 failure, 3.05 s]

sage t long src/sage/rings/number_field/galois_group.py # 1 doctest failed
</pre>
TicketdimpaseTue, 02 Oct 2018 23:13:52 GMT
https://trac.sagemath.org/ticket/25477#comment:173
https://trac.sagemath.org/ticket/25477#comment:173
<p>
Just sort these doctest results with something stable and platformindependent...
</p>
TicketgitTue, 02 Oct 2018 23:32:21 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:174
https://trac.sagemath.org/ticket/25477#comment:174
<ul>
<li><strong>commit</strong>
changed from <em>ca255bbfb94ace207a6b87a4d364310786315dd1</em> to <em>648e61cfc2a3e207d254631a055f006c8a847b8e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=648e61cfc2a3e207d254631a055f006c8a847b8e"><span class="icon"></span>648e61c</a></td><td><code>Fixing database_gap doctest.</code>
</td></tr></table>
TickettscrimTue, 02 Oct 2018 23:36:22 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:175
https://trac.sagemath.org/ticket/25477#comment:175
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
It actually is not machinedependent, it was just not tested by the patchbots because it is marked with an optional gap package to make sure there were no others (well, there was one also marked with magma, but I cannot test that one).
</p>
TicketdimpaseTue, 02 Oct 2018 23:49:34 GMT
https://trac.sagemath.org/ticket/25477#comment:176
https://trac.sagemath.org/ticket/25477#comment:176
<p>
I don't think this is a right fix. Any new version of GAP might mess this up...
How about
</p>
<pre class="wiki">sage: set(list(P))
{(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)}
</pre><p>
or
</p>
<pre class="wiki">sage: sorted(list(P))
[(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]
</pre>
TicketgitWed, 03 Oct 2018 00:45:16 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:177
https://trac.sagemath.org/ticket/25477#comment:177
<ul>
<li><strong>commit</strong>
changed from <em>648e61cfc2a3e207d254631a055f006c8a847b8e</em> to <em>6c634093d2d26be5837470c8325ff92cbfa3d9ca</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=6c634093d2d26be5837470c8325ff92cbfa3d9ca"><span class="icon"></span>6c63409</a></td><td><code>Using sorted on doctest.</code>
</td></tr></table>
TickettscrimWed, 03 Oct 2018 00:46:22 GMT
https://trac.sagemath.org/ticket/25477#comment:178
https://trac.sagemath.org/ticket/25477#comment:178
<p>
I'm not a fan of decorating doctests that don't really need it, but I've added it.
</p>
TicketdimpaseWed, 03 Oct 2018 13:22:48 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:179
https://trac.sagemath.org/ticket/25477#comment:179
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketvbraunThu, 04 Oct 2018 20:47:32 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:180
https://trac.sagemath.org/ticket/25477#comment:180
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
On 32bit:
</p>
<pre class="wiki">**********************************************************************
File "src/sage/geometry/polyhedron/library.py", line 360, in sage.geometry.polyhedron.library.Polytopes.icosahedron
Failed example:
ico.volume()
Expected:
2.1816949907715726
Got:
2.181694990771572
**********************************************************************
1 item had failures:
1 of 11 in sage.geometry.polyhedron.library.Polytopes.icosahedron
[211 tests, 1 failure, 118.70 s]

sage t long src/sage/geometry/polyhedron/library.py # 1 doctest failed
</pre>
TicketdimpaseThu, 04 Oct 2018 21:24:35 GMT
https://trac.sagemath.org/ticket/25477#comment:181
https://trac.sagemath.org/ticket/25477#comment:181
<p>
oh, and that's why: the icosahedron generator contains
</p>
<pre class="wiki"> verts = [p(v) for p in AlternatingGroup(3) for v in pts]
return Polyhedron(vertices=verts, base_ring=base_ring, backend=backend)
</pre><p>
how about we just add <code>...</code> to that doctest, like <code>2.18169499...</code> ?
</p>
TicketgitThu, 04 Oct 2018 22:34:46 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:182
https://trac.sagemath.org/ticket/25477#comment:182
<ul>
<li><strong>commit</strong>
changed from <em>6c634093d2d26be5837470c8325ff92cbfa3d9ca</em> to <em>693ada71485226cf82fa700c9a1c3d4201d3b404</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=693ada71485226cf82fa700c9a1c3d4201d3b404"><span class="icon"></span>693ada7</a></td><td><code>Adding rel tol to polyhedron/library.py test.</code>
</td></tr></table>
TickettscrimThu, 04 Oct 2018 22:36:19 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:183
https://trac.sagemath.org/ticket/25477#comment:183
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
I added a <code>rel tol</code> in case there ends up being other slight numerical differences in the future.
</p>
TicketdimpaseThu, 04 Oct 2018 22:47:31 GMT
https://trac.sagemath.org/ticket/25477#comment:184
https://trac.sagemath.org/ticket/25477#comment:184
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:183" title="Comment 183">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I added a <code>rel tol</code> in case there ends up being other slight numerical differences in the future.
</p>
</blockquote>
<p>
The digits after <code>2.18169499</code> are not right, for the exact evaluation gives
<code>2.18169499062...</code>.
</p>
<pre class="wiki">sage: (5/12*sqrt(5) + 5/4).n()
2.18169499062491
</pre><p>
That's why I'd prefer truncation as I suggested.
</p>
TickettscrimThu, 04 Oct 2018 22:52:55 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:185
https://trac.sagemath.org/ticket/25477#comment:185
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
</ul>
<p>
I think that is part of the point of the doctest, that it is different. If you insist, I will change it to truncation, but I also believe that suggests a much larger numerical instability than is actually present.
</p>
TicketdimpaseFri, 05 Oct 2018 06:41:39 GMT
https://trac.sagemath.org/ticket/25477#comment:186
https://trac.sagemath.org/ticket/25477#comment:186
<p>
IMHO it is not an instability, it is an artefact of naive computing with finite precision, i.e. accumulation of a rounding error.
</p>
TicketgitFri, 05 Oct 2018 07:44:31 GMTcommit changed
https://trac.sagemath.org/ticket/25477#comment:187
https://trac.sagemath.org/ticket/25477#comment:187
<ul>
<li><strong>commit</strong>
changed from <em>693ada71485226cf82fa700c9a1c3d4201d3b404</em> to <em>3ec5057ee13ac5450b3b7a2ddba09c2c4aa772c7</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="extlink" href="https://git.sagemath.org/sage.git/commit/?id=3ec5057ee13ac5450b3b7a2ddba09c2c4aa772c7"><span class="icon"></span>3ec5057</a></td><td><code>Changing to truncated version.</code>
</td></tr></table>
TickettscrimFri, 05 Oct 2018 07:45:36 GMTstatus changed
https://trac.sagemath.org/ticket/25477#comment:188
https://trac.sagemath.org/ticket/25477#comment:188
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Okay, that is not quite the right terminology. It still suggests that there is significantly more variation in the doctest than what it really has. However, I changed it because I want this to get in and don't want it cut from the next stable release.
</p>
TicketdimpaseFri, 05 Oct 2018 11:12:56 GMT
https://trac.sagemath.org/ticket/25477#comment:189
https://trac.sagemath.org/ticket/25477#comment:189
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/25477#comment:188" title="Comment 188">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Okay, that is not quite the right terminology. It still suggests that there is significantly more variation in the doctest than what it really has. However, I changed it because I want this to get in and don't want it cut from the next stable release.
</p>
</blockquote>
<p>
It rather illustrates that RDF is not a field, and that it isn't even commutative...
There could be more variation coming from a yet another CPU used. E.g. if you have a better FPU then you might get closer to the correct value, which would again break the doctest if it had too much numerical noise left.
</p>
TicketvbraunSat, 06 Oct 2018 17:13:13 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/25477#comment:190
https://trac.sagemath.org/ticket/25477#comment:190
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/group_theory/improve_iterator_perm_gps25477</em> to <em>3ec5057ee13ac5450b3b7a2ddba09c2c4aa772c7</em>
</li>
</ul>
Ticket