Bug in vector reduction

[robertwb]

From sage-support:

On Mar 24, 2010, at 10:35 AM, mb wrote:

Hi,

The following seems like strange behavior to me.

In [1]: V=VectorSpace(GF(2),2)
In [2]: V([1,3])
Out[2]: (1, 1)
In [3]: V([1,-3])
Out[3]: (1, 0)

I would expect the last answer to be (1,1).

CC: @rbeezer

Component: linear algebra

Author: Jason Grout

Reviewer: Minh Van Nguyen

Merged: sage-4.4.2.rc0

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

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Description changed:

--- 
+++ 
@@ -1,3 +1,4 @@
+From [sage-support](http://groups.google.com/group/sage-support/browse_thread/thread/f18b1f77ea5d529f):

On Mar 24, 2010, at 10:35 AM, mb wrote:

[jasongrout]

comment:2

Narrowing this down:

sage: V=GF(2)^2                                   
sage: V.coordinate_vector([1,-3])
(1, 0)

[jasongrout]

comment:3

As a workaround:

sage: vector(GF(2),[1,-3])                                                     
(1, 1)

Note that the category seems autogenerated or something since I can't get the source:

sage: type(GF(2)^2)
<class 'sage.modules.free_module.FreeModule_ambient_field_with_category'>
sage: sage.modules.free_module.FreeModule_ambient_field_with_category??
Object `sage.modules.free_module.FreeModule_ambient_field_with_category` not found.

[jasongrout]

comment:4

It seems to only affect GF(2), and only when you pass in negative numbers:

sage: (GF(2)^10)(range(-5,5))
(0, 0, 0, 0, 0, 0, 1, 0, 1, 0)
sage: (GF(3)^10)(range(-5,5))
(1, 2, 0, 1, 2, 0, 1, 2, 0, 1)

[jasongrout]

comment:5

If after line 150 of vector_mod2_dense.pyx, you put the line:

print xi, type(xi), xi%2

you see that the problem happens because in the Cython file, -1%2 is -1, not 1. Apparently the C standard doesn't specify what happens if you mod with a negative number; some compilers return positive numbers, some return negative numbers.

Here is a patch which fixes the issue. I don't have time to formalize it and upload it right now.

diff -r c04df7b7f023 sage/modules/vector_mod2_dense.pyx
--- a/sage/modules/vector_mod2_dense.pyx    Thu Mar 18 01:56:14 2010 -0500
+++ b/sage/modules/vector_mod2_dense.pyx    Wed Mar 24 20:12:27 2010 -0500
@@ -137,6 +137,8 @@
             (0, 0, 1)
             sage: VS((0,0,GF(2)(1)))
             (0, 0, 1)
+            sage: VS((-1,-2,-3))
+            (1, 0, 1)
         """
         cdef Py_ssize_t i
         cdef int xi
@@ -146,7 +148,8 @@
             for i from 0 <= i < self._degree:
                 if PY_TYPE_CHECK(x[i],IntegerMod_int) or PY_TYPE_CHECK(x[i],int) or PY_TYPE_CHECK(x[i],Integer):
                     xi = x[i]
-                    mzd_write_bit(self._entries, 0, i, xi%2)
+                    # the if/else statement is because some in some compilers, (-1)%2 is -1
+                    mzd_write_bit(self._entries, 0, i, 0 if xi%2==0 else 1)
                 else:
                     mzd_write_bit(self._entries, 0, i, x[i]%2)
             return

[jasongrout]

comment:7

Attachment: trac-8601-vector-mod2-negative.patch.gz

This patch should be ready for review. Doctests pass in the modules/*.pyx files.

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Author: Jason Grout

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Reviewer: Minh Van Nguyen

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

comment:8

Attachment: trac_8601-reviewer.patch.gz

The patch trac-8601-vector-mod2-negative.patch is OK by me. But I would prefer referencing the ticket number in a doctest. My reviewer patch does that and it also fixes a typo. Anyone but myself is welcome to give a final sign off on this ticket.

[jasongrout]

comment:9

Your changes look good to me (and pass doctests).

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Merged: sage-4.4.2.rc0