Opened 6 years ago
Closed 6 years ago
#21746 closed defect (fixed)
overflow for vector mod2 dense
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  linear algebra  Keywords:  
Cc:  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Jeroen Demeyer, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  428c88e (Commits, GitHub, GitLab)  Commit:  428c88e3e6869f508308c7395037977b3cd9e115 
Dependencies:  Stopgaps: 
Description
sage: VS = VectorSpace(GF(2),1) sage: VS([2**64]) Traceback (most recent call last): ... OverflowError: Python int too large to convert to C long
Change History (17)
comment:1 Changed 6 years ago by
 Branch set to u/vdelecroix/21746
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit set to 9a5227206b6a75f36cca0a82299666e158061c18
comment:3 Changed 6 years ago by
 Reviewers set to Jeroen Demeyer
 Status changed from needs_review to positive_review
comment:4 Changed 6 years ago by
 Commit changed from 9a5227206b6a75f36cca0a82299666e158061c18 to d1c54b1679d9f60b6612a98d6b1386d5ddb1b347
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
d1c54b1  21746: fix doctest in coding/

comment:5 Changed 6 years ago by
Fixed doctest failure in coding/
. Needs review again.
comment:6 Changed 6 years ago by
This branch does result in ~10% slowdown:
sage: V = VectorSpace(GF(2), 2^10) sage: %timeit V([1]*(2^10)) The slowest run took 5.95 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 49.8 µs per loop
Before:
sage: V = VectorSpace(GF(2), 2^10) sage: %timeit V([1]*(2^10)) The slowest run took 5.69 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 45.8 µs per loop
However, changing the for loop over enumerate
back to for i from 0 <= i < self._degree:
and setting xi = x[i]
doesn't have a noticeable impact. So I think we have to deal with this.
I do have one nitpick: change the ZeroDivisionError
to start with a lowercase. Once that is done, you can put this back to a positive review.
comment:7 Changed 6 years ago by
 Commit changed from d1c54b1679d9f60b6612a98d6b1386d5ddb1b347 to 428c2cd96d640a939424865a85660cf0813b3e1d
Branch pushed to git repo; I updated commit sha1. New commits:
428c2cd  21746: remove enumerate + cleaning

comment:8 Changed 6 years ago by
 Commit changed from 428c2cd96d640a939424865a85660cf0813b3e1d to 65894e56a7405309381db71dbe583d7b8f943388
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
65894e5  21746: remove enumerate + cleaning

comment:9 Changed 6 years ago by
Thanks for the timings!
I removed the enumerate and also did some cleaning in the case x = 0
. This code is completely useless
for i from 0 <= i < self._degree: mzd_set_ui(self._entries, 0)
comment:10 Changed 6 years ago by
The enumerate
is optimized by Cython, so no need to remove it!
comment:11 Changed 6 years ago by
 Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Travis Scrimshaw
 Status changed from needs_review to positive_review
I realize the phrasing in my comment was somewhat vague too; I meant we have to just live with the slowdown. I did come to the conclusion that enumerate
was likely optimized by Cython, but it is good to know. Anyways, removing it is a netzero change, so I'm setting this back to a positive review.
comment:12 Changed 6 years ago by
 Status changed from positive_review to needs_work
segfault galore... see patchbot
comment:13 Changed 6 years ago by
Indeed. I am able to reproduce it with the shorter
sage: (GF(2)**0).zero_vector()
comment:14 Changed 6 years ago by
 Commit changed from 65894e56a7405309381db71dbe583d7b8f943388 to 428c88e3e6869f508308c7395037977b3cd9e115
Branch pushed to git repo; I updated commit sha1. New commits:
428c88e  21746: fix segementation fault for 0dim spaces

comment:15 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:16 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:17 Changed 6 years ago by
 Branch changed from u/vdelecroix/21746 to 428c88e3e6869f508308c7395037977b3cd9e115
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
21746: fix overflow for dense vector mod 2