CoCalc -- vector_mod2

GitHub Repository: sagemath/sagesmc
Path: blob/master/src/sage/modules/vector_mod2_dense.pyx
⁸⁸¹⁵ views
1
"""
2
Vectors with elements in GF(2).
3

4
AUTHOR:
5

6
- Martin Albrecht (2009-12): initial implementation
7

8
- Thomas Feulner (2012-11): added :meth:`Vector_mod2_dense.hamming_weight`
9

10
EXAMPLES::
11

12
    sage: VS = GF(2)^3
13
    sage: e = VS.random_element(); e
14
    (1, 0, 0)
15
    sage: f = VS.random_element(); f
16
    (0, 1, 1)
17
    sage: e + f
18
    (1, 1, 1)
19
"""
20

21
##############################################################################
22
#       Copyright (C) 2009 Martin Albrecht <[email protected]>
23
#  Distributed under the terms of the GNU General Public License (GPL)
24
#  The full text of the GPL is available at:
25
#                  http://www.gnu.org/licenses/
26
##############################################################################
27

28
include 'sage/ext/interrupt.pxi'
29
include 'sage/ext/stdsage.pxi'
30

31
from sage.rings.finite_rings.integer_mod cimport IntegerMod_int, IntegerMod_abstract
32
from sage.rings.integer cimport Integer
33
from sage.structure.element cimport Element, ModuleElement, RingElement, Vector
34

35
cimport free_module_element
36
from free_module_element import vector
37

38
from sage.libs.m4ri cimport *
39

40
cdef class Vector_mod2_dense(free_module_element.FreeModuleElement):
41
    cdef _new_c(self):
42
        """
43
        EXAMPLE::
44

45
            sage: VS = VectorSpace(GF(2),3)
46
            sage: VS([0,0,1])
47
            (0, 0, 1)
48
            sage: type(_)
49
            <type 'sage.modules.vector_mod2_dense.Vector_mod2_dense'>
50
        """
51
        cdef Vector_mod2_dense y
52
        y = PY_NEW(Vector_mod2_dense)
53
        y._init(self._degree, self._parent)
54
        return y
55

56
    cdef bint is_dense_c(self):
57
        """
58
        EXAMPLE::
59

60
            sage: VS = VectorSpace(GF(2),3)
61
            sage: VS([0,0,1]).is_dense()
62
            True
63
        """
64
        return 1
65

66
    cdef bint is_sparse_c(self):
67
        """
68
        EXAMPLE::
69

70
            sage: VS = VectorSpace(GF(2),3)
71
            sage: VS([0,0,1]).is_sparse()
72
            False
73
        """
74
        return 0
75

76
    def __copy__(self):
77
        """
78
        EXAMPLE::
79

80
            sage: VS = VectorSpace(GF(2),10^4)
81
            sage: v = VS.random_element()
82
            sage: w = copy(v)
83
            sage: w == v
84
            True
85
            sage: v[:10]
86
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1)
87
            sage: w[:10]
88
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1)
89
        """
90
        cdef Vector_mod2_dense y = self._new_c()
91
        if self._degree:
92
            mzd_copy(y._entries, self._entries)
93
        return y
94

95
    cdef _init(self, Py_ssize_t degree, parent):
96
        """
97
        EXAMPLE::
98

99
            sage: VS = VectorSpace(GF(2),3)
100
            sage: VS([0,0,1])
101
            (0, 0, 1)
102
            sage: type(_)
103
            <type 'sage.modules.vector_mod2_dense.Vector_mod2_dense'>
104
        """
105
        self._degree = degree
106
        self._parent = parent
107
        self._base_ring = parent.base_ring()
108
        self._entries = mzd_init(1, degree)
109
        if self._entries == NULL:
110
            raise MemoryError("Allocation of Vector_mod2_dense failed.")
111

112
    def __cinit__(self, parent=None, x=None, coerce=True, copy=True):
113
        """
114
        EXAMPLE::
115

116
            sage: VS = VectorSpace(GF(2),3)
117
            sage: VS((0,0,1/3))
118
            (0, 0, 1)
119
            sage: type(_)
120
            <type 'sage.modules.vector_mod2_dense.Vector_mod2_dense'>
121
        """
122
        self._entries = NULL
123
        self._is_mutable = 1
124
        if not parent is None:
125
            self._init(parent.degree(), parent)
126

127
    def __init__(self, parent, x, coerce=True, copy=True):
128
        """
129
        EXAMPLE::
130

131
            sage: VS = VectorSpace(GF(2),3)
132
            sage: VS((0,0,1/3))
133
            (0, 0, 1)
134
            sage: type(_)
135
            <type 'sage.modules.vector_mod2_dense.Vector_mod2_dense'>
136
            sage: VS((0,0,int(3)))
137
            (0, 0, 1)
138
            sage: VS((0,0,3))
139
            (0, 0, 1)
140
            sage: VS((0,0,GF(2)(1)))
141
            (0, 0, 1)
142

143
        TESTS:
144

145
        Check that ticket #8601 is fixed::
146

147
            sage: VS = VectorSpace(GF(2), 3)
148
            sage: VS((-1,-2,-3))
149
            (1, 0, 1)
150
            sage: V = VectorSpace(GF(2), 2)
151
            sage: V([1,3])
152
            (1, 1)
153
            sage: V([1,-3])
154
            (1, 1)
155
        """
156
        cdef Py_ssize_t i
157
        cdef int xi
158
        if isinstance(x, (list, tuple)):
159
            if len(x) != self._degree:
160
                raise TypeError("x must be a list of the right length")
161
            for i from 0 <= i < self._degree:
162
                if PY_TYPE_CHECK(x[i],IntegerMod_int) or PY_TYPE_CHECK(x[i],int) or PY_TYPE_CHECK(x[i],Integer):
163
                    xi = x[i]
164
                    # the if/else statement is because in some compilers, (-1)%2 is -1
165
                    mzd_write_bit(self._entries, 0, i, 0 if xi%2==0 else 1)
166
                else:
167
                    mzd_write_bit(self._entries, 0, i, x[i]%2)
168
            return
169
        if x != 0:
170
            raise TypeError("can't initialize vector from nonzero non-list")
171
        else:
172
            for i from 0 <= i < self._degree:
173
                mzd_set_ui(self._entries, 0)
174

175
    def __dealloc__(self):
176
        """
177
        EXAMPLE::
178

179
        sage: VS = VectorSpace(GF(2),10^3)
180
        sage: import gc
181
        sage: for i in range(10):
182
        ...      v = VS.random_element()
183
        ...      del v
184
        ...      _ = gc.collect()
185
        """
186
        if self._entries:
187
            mzd_free(self._entries)
188

189
    cdef int _cmp_c_impl(left, Element right) except -2:
190
        """
191
        EXAMPLES::
192
            sage: v = vector(GF(2), [0,0,0,0])
193
            sage: v == 0
194
            True
195
            sage: v == 1
196
            False
197
            sage: v == v
198
            True
199
            sage: w = vector(GF(2), [1,0,0,0])
200
            sage: w < v
201
            False
202
            sage: w > v
203
            True
204
        """
205
        if left._degree == 0:
206
            return 0
207
        return mzd_cmp(left._entries, (<Vector_mod2_dense>right)._entries)
208

209
    # see sage/structure/element.pyx
210
    def __richcmp__(left, right, int op):
211
        """
212
        TEST::
213

214
            sage: w = vector(GF(2), [-1,0,0,0])
215
            sage: w == w
216
            True
217
        """
218
        return (<Element>left)._richcmp(right, op)
219

220
    # __hash__ is not properly inherited if comparison is changed
221
    def __hash__(self):
222
        """
223
        TEST::
224

225
            sage: w = vector(GF(2), [-1,0,0,0])
226
            sage: w.set_immutable()
227
            sage: isinstance(hash(w), int)
228
            True
229
        """
230
        return free_module_element.FreeModuleElement.__hash__(self)
231

232
    def __len__(self):
233
        """
234
        EXAMPLES::
235

236
            sage: len(vector(GF(2),[0,0,1,1,1]))
237
            5
238
        """
239
        return self._degree
240

241
    def __setitem__(self, i, value):
242
        """
243
        EXAMPLES::
244

245
            sage: VS = VectorSpace(GF(2),4)
246
            sage: v = VS.random_element(); v
247
            (1, 0, 0, 0)
248
            sage: v[0] = 0; v
249
            (0, 0, 0, 0)
250
            sage: v[1:3] = [1, 1]; v
251
            (0, 1, 1, 0)
252
            sage: v[4] = 0
253
            Traceback (most recent call last):
254
            ...
255
            IndexError: Index '4' out of bound.
256
        """
257
        if not self._is_mutable:
258
            raise ValueError("vector is immutable; please change a copy instead (use copy())")
259
        cdef IntegerMod_int m
260
        cdef Py_ssize_t k, d, n
261
        if isinstance(i, slice):
262
            start, stop = i.start, i.stop
263
            d = self.degree()
264
            R = self.base_ring()
265
            n = 0
266
            for k from start <= k < stop:
267
                if k >= d:
268
                    return
269
                if k >= 0:
270
                    self[k] = R(value[n])
271
                    n = n + 1
272
        else:
273
            m = self.base_ring()(value)
274
            if i < 0 or i >= self._degree:
275
                raise IndexError("Index '%s' out of bound."%(i))
276
            else:
277
                mzd_write_bit(self._entries, 0, i, m)
278

279
    def __getitem__(self, i):
280
        """
281
        Returns `i`-th entry or slice of self.
282

283
        EXAMPLES::
284

285
            sage: v = vector(GF(2), [1,2,3]); v
286
            (1, 0, 1)
287
            sage: v[0]
288
            1
289
            sage: v[2]
290
            1
291
            sage: v[-2]
292
            0
293
            sage: v[0:2]
294
            (1, 0)
295
            sage: v[5]
296
            Traceback (most recent call last):
297
            ...
298
            IndexError: index '5' out of range
299

300
            sage: v[-5]
301
            Traceback (most recent call last):
302
            ...
303
            IndexError: index '-2' out of range
304
        """
305
        if isinstance(i, slice):
306
            start, stop, step = i.indices(len(self))
307
            return vector(self.base_ring(), self.list()[start:stop])
308
        else:
309
            if i < 0:
310
                i += self._degree
311
            if i < 0 or i >= self._degree:
312
                raise IndexError("index '%s' out of range"%(i,))
313
            return self._base_ring(mzd_read_bit(self._entries, 0, i))
314

315
    def __reduce__(self):
316
        """
317
        EXAMPLE::
318

319
            sage: VS = VectorSpace(GF(2),10^4)
320
            sage: e = VS.random_element()
321
            sage: loads(dumps(e)) == e
322
            True
323
        """
324
        return unpickle_v0, (self._parent, self.list(), self._degree, self._is_mutable)
325

326
    cpdef ModuleElement _add_(self, ModuleElement right):
327
        """
328
        EXAMPLE::
329

330
            sage: VS = VectorSpace(GF(2),10)
331
            sage: e = VS([0,0,1,1,0,0,1,1,0,0])
332
            sage: f = VS([0,1,0,1,0,1,0,1,0,1])
333
            sage: e + f #indirect doctest
334
            (0, 1, 1, 0, 0, 1, 1, 0, 0, 1)
335
        """
336
        cdef Vector_mod2_dense z = self._new_c()
337
        if self._degree:
338
            mzd_add(z._entries, self._entries, (<Vector_mod2_dense>right)._entries)
339
        return z
340

341
    cpdef ModuleElement _sub_(self, ModuleElement right):
342
        """
343
        EXAMPLE::
344

345
            sage: VS = VectorSpace(GF(2),10)
346
            sage: e = VS([0,0,1,1,0,0,1,1,0,0])
347
            sage: f = VS([0,1,0,1,0,1,0,1,0,1])
348
            sage: e - f #indirect doctest
349
            (0, 1, 1, 0, 0, 1, 1, 0, 0, 1)
350
        """
351
        cdef Vector_mod2_dense z = self._new_c()
352
        if self._degree:
353
            mzd_add(z._entries, self._entries, (<Vector_mod2_dense>right)._entries)
354
        return z
355

356
    cpdef int hamming_weight(self):
357
        """
358
        Return the number of positions ``i`` such that ``self[i] != 0``.
359

360
        EXAMPLES::
361

362
            sage: vector(GF(2), [1,1,0]).hamming_weight()
363
            2
364
        """
365
        cdef int i
366
        cdef int res = 0
367
        for i from 0 <= i < self._entries.width:
368
            res += Integer(self._entries.rows[0][i]).popcount()
369
        return res
370

371

372
    cpdef Element _dot_product_(self, Vector right):
373
        """
374
        EXAMPLES::
375
           sage: VS = VectorSpace(GF(2),3)
376
           sage: v = VS([1,1,1]); w = VS([0,0,0])
377
           sage: v * w, w * v #indirect doctest
378
           (0, 0)
379
           sage: v = VS([1,1,1]); w = VS([0,1,0])
380
           sage: v * w, w * v
381
           (1, 1)
382
           sage: v = VS([1,1,1]); w = VS([0,1,1])
383
           sage: v * w, w * v
384
           (0, 0)
385
           sage: v = VS([1,1,1]); w = VS([1,1,1])
386
           sage: v * w, w * v
387
           (1, 1)
388

389
           sage: VS = VectorSpace(GF(2),10^4)
390
           sage: v = VS(0); w = VS(0)
391
           sage: v[1337] = 1; w[1337] = 1
392
           sage: v * w, w * v
393
           (1, 1)
394
           sage: v[9881] = 1; w[9881] = 1
395
           sage: v * w, w * v
396
           (0, 0)
397
           sage: v[5172] = 1; w[6178] = 1
398
           sage: v * w, w * v
399
           (0, 0)
400
        """
401
        cdef Py_ssize_t i
402
        cdef IntegerMod_int n
403
        cdef Vector_mod2_dense r = right
404
        cdef m4ri_word tmp = 0
405
        n =  IntegerMod_int.__new__(IntegerMod_int)
406
        IntegerMod_abstract.__init__(n, self.base_ring())
407
        n.ivalue = 0
408

409
        for i from 0 <= i < self._entries.width:
410
            tmp ^= self._entries.rows[0][i] & r._entries.rows[0][i]
411

412
        for i in range(64):
413
            n.ivalue ^= <int>(tmp & 1)
414
            tmp = tmp >> 1
415

416
        return n
417

418
    cpdef Vector _pairwise_product_(self, Vector right):
419
        """
420
        EXAMPLE::
421

422
            sage: VS = VectorSpace(GF(2),10)
423
            sage: e = VS.random_element(); e
424
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1)
425
            sage: f = VS.random_element(); f
426
            (1, 1, 0, 1, 1, 1, 0, 0, 0, 1)
427
            sage: e.pairwise_product(f) #indirect doctest
428
            (1, 0, 0, 0, 1, 1, 0, 0, 0, 1)
429
        """
430
        cdef Vector_mod2_dense z, r
431
        r = right
432
        z = self._new_c()
433
        cdef Py_ssize_t i
434
        for i from 0 <= i < self._entries.width:
435
            z._entries.rows[0][i] = (self._entries.rows[0][i] & r._entries.rows[0][i])
436
        return z
437

438
    cpdef ModuleElement _rmul_(self, RingElement left):
439
        """
440
        EXAMPLE::
441

442
            sage: VS = VectorSpace(GF(2),10)
443
            sage: e = VS.random_element(); e
444
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1)
445
            sage: 0 * e
446
            (0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
447
            sage: 1 * e
448
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1)
449
            sage: 2 * e #indirect doctest
450
            (0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
451
        """
452
        cdef IntegerMod_int a
453

454
        if left:
455
            return self.__copy__()
456
        else:
457
            return self._new_c()
458

459

460
    cpdef ModuleElement _lmul_(self, RingElement right):
461
        """
462
        EXAMPLE::
463

464
            sage: VS = VectorSpace(GF(2),10)
465
            sage: e = VS.random_element(); e
466
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1)
467
            sage: e * 0 #indirect doctest
468
            (0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
469
            sage: e * 1
470
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1)
471
            sage: e * 2
472
            (0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
473
        """
474
        return self._rmul_(right)
475

476
    cpdef ModuleElement _neg_(self):
477
        """
478
        EXAMPLE::
479

480
            sage: VS = VectorSpace(GF(2),10)
481
            sage: e = VS.random_element()
482
            sage: -e == e
483
            True
484
        """
485
        return self.__copy__()
486

487
    def n(self, *args, **kwargs):
488
        """
489
        Returns a numerical approximation of ``self`` by calling the
490
        :meth:`n()` method on all of its entries.
491

492
        EXAMPLES::
493

494
            sage: v = vector(GF(2), [1,2,3])
495
            sage: v.n()
496
            (1.00000000000000, 0.000000000000000, 1.00000000000000)
497
            sage: _.parent()
498
            Vector space of dimension 3 over Real Field with 53 bits of precision
499
            sage: v.n(prec=75)
500
            (1.000000000000000000000, 0.0000000000000000000000, 1.000000000000000000000)
501
            sage: _.parent()
502
            Vector space of dimension 3 over Real Field with 75 bits of precision
503
        """
504
        return vector( [e.n(*args, **kwargs) for e in self] )
505

506
    def list(self, copy=True):
507
        """
508
        Return a list of entries in ``self``.
509

510
        INPUT:
511

512
        - ``copy`` - always ``True
513

514
        EXAMPLE::
515

516
            sage: VS = VectorSpace(GF(2),10)
517
            sage: e = VS.random_element(); e
518
            (1, 0, 0, 0, 1, 1, 1, 0, 0, 1)
519
            sage: e.list()
520
            [1, 0, 0, 0, 1, 1, 1, 0, 0, 1]
521
        """
522
        cdef Py_ssize_t d = self._degree
523
        cdef Py_ssize_t i
524
        cdef list v = [0]*d
525
        K = self.base_ring()
526
        z = K.zero_element()
527
        o = K.one_element()
528
        cdef list switch = [z,o]
529
        for i in range(d):
530
            v[i] = switch[mzd_read_bit(self._entries, 0, i)]
531
        return v
532

533
def unpickle_v0(parent, entries, degree, is_mutable):
534
    """
535
    EXAMPLE::
536

537
        sage: from sage.modules.vector_mod2_dense import unpickle_v0
538
        sage: VS = VectorSpace(GF(2),10)
539
        sage: unpickle_v0(VS, [0,1,2,3,4,5,6,7,8,9], 10, 0)
540
        (0, 1, 0, 1, 0, 1, 0, 1, 0, 1)
541
    """
542
    # If you think you want to change this function, don't.
543
    cdef Vector_mod2_dense v
544
    v = PY_NEW(Vector_mod2_dense)
545
    v._init(degree, parent)
546
    cdef int xi
547

548
    for i from 0 <= i < degree:
549
        if PY_TYPE_CHECK(entries[i],IntegerMod_int) or PY_TYPE_CHECK(entries[i],int) or PY_TYPE_CHECK(entries[i],Integer):
550
            xi = entries[i]
551
            mzd_write_bit(v._entries, 0, i, xi%2)
552
        else:
553
            mzd_write_bit(v._entries, 0, i, entries[i]%2)
554
    v._is_mutable = int(is_mutable)
555
    return v
556

557

558
Product

Resources

Company
