Sage: Ticket #3112: [with patch, positive review] Generate self-orthogonal binary codes
https://trac.sagemath.org/ticket/3112
<pre class="wiki">sage: for B in self_orthogonal_binary_codes(8,3):
....: print B.gen_mat()
....: print
....:
[1 1]
[1 1 0 0]
[0 0 1 1]
[1 0 1 0 0 0]
[0 1 0 1 0 0]
[0 0 0 0 1 1]
[1 1 1 1]
[1 1 1 1 0 0]
[0 0 0 0 1 1]
[1 0 1 1 1 0 0 0]
[0 1 0 0 0 1 0 0]
[0 0 0 0 0 0 1 1]
[1 0 1 1 1 0 0 0]
[0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 1 1]
[1 1 1 1 0 0]
[0 1 0 1 1 1]
[1 0 1 1 0 1 0]
[0 1 0 1 1 1 0]
[0 0 1 0 1 1 1]
[1 0 1 1 0 1 0 0]
[0 1 0 1 1 1 0 0]
[0 0 0 1 0 1 1 1]
[1 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1 0 0]
[0 0 0 0 0 0 1 1]
[1 1 1 1 1 1 0 0]
[0 1 0 0 0 1 1 1]
[1 1 1 1 1 1 1 1]
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/3112
Trac 1.1.6mabshoffTue, 06 May 2008 20:03:48 GMT
https://trac.sagemath.org/ticket/3112#comment:1
https://trac.sagemath.org/ticket/3112#comment:1
<p>
Hi rlm,
</p>
<p>
I didn't look at the patch too closely, but I noticed that you added a lot of code with sparse documentation and also some [internal] function that are not doctested. Is there more coming?
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketrlmTue, 06 May 2008 20:45:06 GMT
https://trac.sagemath.org/ticket/3112#comment:2
https://trac.sagemath.org/ticket/3112#comment:2
<p>
The only new external function is <code>self_orthogonal_binary_codes</code>, which does have doctests. Most of the internal functions are cdef, and they are only there for the self orthogonal code generator.
</p>
<p>
Perhaps you'd like more doctests for <code>self_orthogonal_binary_codes</code>?
</p>
TicketmhansenTue, 06 May 2008 22:11:03 GMTcc changed
https://trac.sagemath.org/ticket/3112#comment:3
https://trac.sagemath.org/ticket/3112#comment:3
<ul>
<li><strong>cc</strong>
<em>mhansen</em> added
</li>
</ul>
TicketwdjWed, 07 May 2008 18:12:03 GMT
https://trac.sagemath.org/ticket/3112#comment:4
https://trac.sagemath.org/ticket/3112#comment:4
<p>
This passes sage -testall.
</p>
<p>
Some questions.
</p>
<ol><li>Does the command
</li></ol><blockquote>
<p>
517 def matrix(self):
</p>
</blockquote>
<p>
return a generator matrix or the so-called syndrome table or ...?
Does the name matrix seem too ambiguous to you?
</p>
<ol start="2"><li>Should the docstring for self_orthogonal_binary_codes
</li></ol><p>
explain that you are actually computing a complete set of representatives
of equivalence clasees of such codes up to a given length and dim?
</p>
<ol start="3"><li>When you run self_orthogonal_binary_codes, are you actually
</li></ol><p>
computing all the (equiv classes of) [n,k]-codes, then adding up those
to get the codes up to a given length and dim? Or, are you somehow
getting all of them at once? In either case, it would obviously be
useful to have a function which only returns those of a given
length. It would be easy enough to simply simply filter out the
"bad" ones from the output of self_orthogonal_binary_codes. However,
I wonder if there was a slicker way to do this using Cython?
</p>
<ol start="4"><li>I'm not competent enough to review the cython code. Mike Hansen,
</li></ol><p>
can you do this?
</p>
TicketrlmWed, 07 May 2008 18:39:06 GMT
https://trac.sagemath.org/ticket/3112#comment:5
https://trac.sagemath.org/ticket/3112#comment:5
<p>
Regarding 1, 2, and 4, there is a second patch on the way.
</p>
<p>
Regarding 3, the codes are built up recursively, so the program is naturally computing up to some n and k, but I guess I could put in an option for the filtering so you didn't have to do it each time.
</p>
TicketwdjWed, 07 May 2008 18:58:14 GMT
https://trac.sagemath.org/ticket/3112#comment:6
https://trac.sagemath.org/ticket/3112#comment:6
<ol><li>This seems to be a bug:
</li></ol><pre class="wiki">sage: B = self_orthogonal_binary_codes(8,4,4)
sage: for C in B: print C.gen_mat()
....:
[1 1 1 1]
[1 1 1 1 0 0]
[0 1 0 1 1 1]
[1 0 1 1 0 1 0]
[0 1 0 1 1 1 0]
[0 0 1 0 1 1 1]
[1 0 0 1 1 0 1 0]
[0 1 0 1 1 1 0 0]
[0 0 1 0 1 1 1 0]
[0 0 0 1 0 1 1 1]
[1 0 1 1 0 1 0 0]
[0 1 0 1 1 1 0 0]
[0 0 0 1 0 1 1 1]
[1 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 1]
[1 1 1 1 1 1 1 1]
sage: for C in B: print C.gen_mat()
....:
sage:
</pre><p>
It appears B cannot be re-used!??
</p>
<ol start="2"><li>Can the docstring for this command explain what kind of object the output is?
</li></ol><p>
A natural thing for a user to try is to pick off the first element:
</p>
<pre class="wiki">sage: B = self_orthogonal_binary_codes(8,4,4)
sage: B[0]
---------------------------------------------------------------------------
<type 'exceptions.TypeError'> Traceback (most recent call last)
/mnt/drive_hda1/sagefiles/sage-3.0.1/<ipython console> in <module>()
<type 'exceptions.TypeError'>: 'generator' object is unsubscriptable
</pre><p>
But as you see, a type error is raised.
</p>
<ol start="3"><li>Check this out:
</li></ol><pre class="wiki">sage: C = QuasiQuadraticResidueCode(11)
sage: G = C.automorphism_group_binary_code()
sage: G.order()/MathieuGroup(22).order()
2
</pre><p>
This is very interesting!
</p>
TicketrlmWed, 07 May 2008 22:00:51 GMT
https://trac.sagemath.org/ticket/3112#comment:7
https://trac.sagemath.org/ticket/3112#comment:7
<p>
David,
</p>
<p>
Both 1 and 2 are generally properties of iterators. What you want might be <code>list(self_orthogonal_binary_codes(8,4,4))</code>.
</p>
TicketwdjThu, 08 May 2008 01:45:50 GMT
https://trac.sagemath.org/ticket/3112#comment:8
https://trac.sagemath.org/ticket/3112#comment:8
<p>
Okay, thanks. Could you toss in an example to that effect in the docstring?
</p>
TicketrlmSat, 10 May 2008 22:05:43 GMT
https://trac.sagemath.org/ticket/3112#comment:9
https://trac.sagemath.org/ticket/3112#comment:9
<p>
What this patch provides is a Python iterator. If someone wants to make a nicer interface, that's great, but that should be the subject of a separate ticket.
</p>
TicketwdjSun, 11 May 2008 16:21:49 GMT
https://trac.sagemath.org/ticket/3112#comment:10
https://trac.sagemath.org/ticket/3112#comment:10
<p>
The 2 patches apply cleanly to 3.0.1 and pass sage -testall.
</p>
<ol><li>This segfault is a problem:
</li></ol><p>
sage: len(list(self_orthogonal_binary_codes(8, 4, d=1, equal=True)))
</p>
<hr />
<p>
Unhandled SIGSEGV: A segmentation fault occured in SAGE.
This probably occured because a *compiled* component
of SAGE has a bug in it (typically accessing invalid memory)
or is not properly wrapped with _sig_on, _sig_off.
You might want to run SAGE under gdb with 'sage -gdb' to debug this.
SAGE will now terminate (sorry).
</p>
<hr />
<p>
This is a rather nasty segfault which does not return the command line
in the terminal window....
</p>
<p>
Once this is fixed, it would be useful for doctesting (and user's understanding)
to include something like this in the docstring.
</p>
<ol start="2"><li>Minor issue: instead of
</li></ol><pre class="wiki"> Generates all (permutation equivalence classes of) self-orthogonal binary
linear codes of length in [1..n] and dimension in [1..k].
NOTE:
Technically, what is returned is a set of representatives of these classes.
</pre><p>
I would say something like
</p>
<pre class="wiki"> Returns a Python iterator which generates a complete set of representatives of
all permutation equivalence classes of self-orthogonal binary linear codes of
length in [1..n] and dimension in [1..k].
</pre><ol start="3"><li>Other than these, looks good to me.
</li></ol>
TicketwdjSun, 11 May 2008 16:25:00 GMT
https://trac.sagemath.org/ticket/3112#comment:11
https://trac.sagemath.org/ticket/3112#comment:11
<p>
One more (minor notational) thing: I think the use of the parameter d in the function
</p>
<pre class="wiki">self_orthogonal_binary_codes(8, 4, d=2,...
</pre><p>
goes against standard notation. Usually, d represents the minimum distance and either b or c represent the divisibility factor. Probably b is preferable here since c is somethings used for codewords.
</p>
TicketrlmSun, 11 May 2008 18:00:58 GMT
https://trac.sagemath.org/ticket/3112#comment:12
https://trac.sagemath.org/ticket/3112#comment:12
<p>
David,
</p>
<p>
That's a nasty segfault there. Also, I agree with all your comments. Expect a new patch soon.
</p>
TicketrlmSun, 11 May 2008 20:20:03 GMT
https://trac.sagemath.org/ticket/3112#comment:13
https://trac.sagemath.org/ticket/3112#comment:13
<p>
The new patch fixes both your problems. Thanks!
</p>
TicketwdjMon, 12 May 2008 00:42:57 GMTsummary changed
https://trac.sagemath.org/ticket/3112#comment:14
https://trac.sagemath.org/ticket/3112#comment:14
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Generate self-orthogonal binary codes</em> to <em>[with patch, positive review] Generate self-orthogonal binary codes</em>
</li>
</ul>
<p>
These three patches apply cleanly to 3.0.1 and pass sage -testall. I think this is a very significant contribution and hope it can be applied before 3.0.2 comes out.
</p>
TicketrlmMon, 19 May 2008 18:26:54 GMTattachment set
https://trac.sagemath.org/ticket/3112
https://trac.sagemath.org/ticket/3112
<ul>
<li><strong>attachment</strong>
set to <em>trac-3112-socodes.patch</em>
</li>
</ul>
<p>
This is a flat version of the previous three.
</p>
TicketmabshoffThu, 22 May 2008 02:22:07 GMT
https://trac.sagemath.org/ticket/3112#comment:15
https://trac.sagemath.org/ticket/3112#comment:15
<p>
Hi rlm.
</p>
<p>
assuming 100% doctest coverage this patch will be merged in 3.0.2.rc0.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketrlmThu, 22 May 2008 05:02:31 GMTattachment set
https://trac.sagemath.org/ticket/3112
https://trac.sagemath.org/ticket/3112
<ul>
<li><strong>attachment</strong>
set to <em>trac-3112-doc.patch</em>
</li>
</ul>
<p>
That should do it.
</p>
TicketmabshoffThu, 22 May 2008 20:36:09 GMTsummary changed
https://trac.sagemath.org/ticket/3112#comment:16
https://trac.sagemath.org/ticket/3112#comment:16
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, positive review] Generate self-orthogonal binary codes</em> to <em>[with patch, positive review, needs rebase] Generate self-orthogonal binary codes</em>
</li>
</ul>
<p>
Oops, the patch no longer applies cleanly:
</p>
<pre class="wiki">mabshoff@sage:/scratch/mabshoff/release-cycle/sage-3.0.2.rc0/devel/sage$ patch -p1 < trac_3112-socodes.patch
patching file sage/coding/all.py
patching file sage/coding/binary_code.pxd
patching file sage/coding/binary_code.pyx
Hunk #2 FAILED at 34.
Hunk #3 succeeded at 72 (offset 2 lines).
Hunk #4 succeeded at 534 (offset 2 lines).
Hunk #5 succeeded at 549 (offset 2 lines).
Hunk #6 succeeded at 570 (offset 2 lines).
Hunk #7 succeeded at 588 (offset 2 lines).
Hunk #8 succeeded at 615 (offset 2 lines).
Hunk #9 succeeded at 833 (offset 2 lines).
Hunk #10 succeeded at 847 (offset 2 lines).
Hunk #11 succeeded at 940 (offset 2 lines).
Hunk #12 succeeded at 954 (offset 2 lines).
Hunk #13 succeeded at 1202 (offset 2 lines).
Hunk #14 succeeded at 1249 (offset 2 lines).
Hunk #15 succeeded at 1275 (offset 2 lines).
Hunk #16 succeeded at 1810 (offset 2 lines).
Hunk #17 succeeded at 1818 (offset 2 lines).
Hunk #18 succeeded at 1838 (offset 2 lines).
Hunk #19 succeeded at 1848 (offset 2 lines).
Hunk #20 succeeded at 2110 (offset 2 lines).
Hunk #21 succeeded at 2347 (offset 2 lines).
Hunk #22 succeeded at 2377 (offset 2 lines).
Hunk #23 succeeded at 2397 (offset 2 lines).
Hunk #24 succeeded at 2414 (offset 2 lines).
Hunk #25 succeeded at 2434 (offset 2 lines).
Hunk #26 succeeded at 2445 (offset 2 lines).
Hunk #27 succeeded at 2533 (offset 2 lines).
Hunk #28 succeeded at 2603 (offset 2 lines).
Hunk #29 succeeded at 2621 (offset 2 lines).
Hunk #30 succeeded at 2665 (offset 2 lines).
Hunk #31 succeeded at 2691 (offset 2 lines).
Hunk #32 succeeded at 2706 (offset 2 lines).
Hunk #33 succeeded at 2774 (offset 2 lines).
Hunk #34 succeeded at 2795 (offset 2 lines).
Hunk #35 succeeded at 2809 (offset 2 lines).
Hunk #36 succeeded at 2827 (offset 2 lines).
Hunk #37 succeeded at 2848 (offset 2 lines).
Hunk #38 succeeded at 2858 (offset 2 lines).
Hunk #39 succeeded at 2920 (offset 2 lines).
Hunk #40 succeeded at 2992 (offset 2 lines).
Hunk #41 succeeded at 3093 (offset 2 lines).
Hunk #42 succeeded at 3168 (offset 2 lines).
Hunk #43 succeeded at 3195 (offset 2 lines).
Hunk #44 succeeded at 3221 (offset 2 lines).
Hunk #45 succeeded at 3303 (offset 2 lines).
Hunk #46 succeeded at 3499 (offset 2 lines).
Hunk #47 succeeded at 3518 (offset 2 lines).
1 out of 47 hunks FAILED -- saving rejects to file sage/coding/binary_code.pyx.rej
patching file sage/coding/linear_code.py
Hunk #5 succeeded at 1491 (offset 9 lines).
</pre><p>
Feel free to rebase it against my tree on sage.math with the above path. There are still some doctests missing, but let's get this merged and open a follow up ticket.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketrlmThu, 22 May 2008 22:42:12 GMTattachment set
https://trac.sagemath.org/ticket/3112
https://trac.sagemath.org/ticket/3112
<ul>
<li><strong>attachment</strong>
set to <em>trac-3112-rebased.patch</em>
</li>
</ul>
<p>
This should replace the previous two.
</p>
TicketmabshoffThu, 22 May 2008 22:59:03 GMTsummary changed
https://trac.sagemath.org/ticket/3112#comment:17
https://trac.sagemath.org/ticket/3112#comment:17
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, positive review, needs rebase] Generate self-orthogonal binary codes</em> to <em>[with patch, positive review] Generate self-orthogonal binary codes</em>
</li>
</ul>
<p>
The new patch applies cleanly. In the process of rebasing rlm also found an issue in <a class="closed ticket" href="https://trac.sagemath.org/ticket/3269" title="defect: [with patch, positive review] Improved documentation to ... (closed: fixed)">#3269</a>'s docstring.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketmabshoffThu, 22 May 2008 23:12:40 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/3112#comment:18
https://trac.sagemath.org/ticket/3112#comment:18
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Merged in Sage 3.0.2.rc0
</p>
TicketmabshoffThu, 22 May 2008 23:19:50 GMTmilestone changed
https://trac.sagemath.org/ticket/3112#comment:19
https://trac.sagemath.org/ticket/3112#comment:19
<ul>
<li><strong>milestone</strong>
changed from <em>sage-3.0.3</em> to <em>sage-3.0.2</em>
</li>
</ul>
Ticket