Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Unoptimal memory complexity of sage.matrix.berlekamp #36172

Closed
2 tasks done
grhkm21 opened this issue Sep 1, 2023 · 0 comments · Fixed by #36173
Closed
2 tasks done

Unoptimal memory complexity of sage.matrix.berlekamp #36172

grhkm21 opened this issue Sep 1, 2023 · 0 comments · Fixed by #36173
Labels
t: bug
Milestone
sage-10.2

Comments

@grhkm21
Copy link
Contributor

grhkm21 commented Sep 1, 2023 •
edited
Loading

The code here is unoptimal:

sage/src/sage/matrix/berlekamp_massey.py

Lines 90 to 98 in 6695bec

f = {-1: R(a), 0: x**(2 * M)}
s = {-1: 1, 0: 0}
j = 0
while f[j].degree() >= M:
j += 1
qj, f[j] = f[j - 2].quo_rem(f[j - 1])
s[j] = s[j - 2] - qj * s[j - 1]
t = s[j].reverse()
return ~(t[t.degree()]) * t # make monic (~ is inverse in python)

For example, the following code uses a lot of memory:

sage: from sage.matrix.berlekamp_massey import berlekamp_massey
sage: p = next_prime(2**64)
sage: ls = [GF(p).random_element() for _ in range(20000)]
sage: berlekamp_massey(ls);

To be more specific, the dictionaries are not necessarily and only f[j - 2] and f[j - 1] are used every time, same for s. So they can be stored as temporary variables.

Additional Information

I am fixing it.

Checklist

  • I have searched the existing issues for a bug report that matches the one I want to file, without success.
  • I have read the documentation and troubleshoot guide
@grhkm21 grhkm21 added the t: bug label Sep 1, 2023
@grhkm21 grhkm21 mentioned this issue Sep 1, 2023
Merged
5 tasks
vbraun pushed a commit to vbraun/sage that referenced this issue Sep 4, 2023
sagemathgh-36173: Fix quadratic memory of berlekamp_massey
bc9f890 
    
Fix sagemath#36172.

Reduced berlekamp_massey memory consumption by replacing a dictionary
with temporary variables. The memory consumption of the line highlighted
below reduced from 42MB to 4MB (probably inaccurate, but significant
enough).

```python
from memory_profiler import profile
from sage.matrix.berlekamp_massey import berlekamp_massey
@Profile
def gen_data():
    p = random_prime(2**64)
    ls = [GF(p).random_element() for _ in range(20000)]
    berlekamp_massey(ls); # <--- this line
gen_data()
```

I am not sure if I have to include extra doctests or not, or how to test
memory consumptions, since the time complexity is also O(n^2).

### 📝 Checklist

- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.
    
URL: sagemath#36173
Reported by: grhkm21
Reviewer(s): grhkm21, Kwankyu Lee
vbraun pushed a commit to vbraun/sage that referenced this issue Sep 5, 2023
sagemathgh-36173: Fix quadratic memory of berlekamp_massey
66146e0 
    
Fix sagemath#36172.

Reduced berlekamp_massey memory consumption by replacing a dictionary
with temporary variables. The memory consumption of the line highlighted
below reduced from 42MB to 4MB (probably inaccurate, but significant
enough).

```python
from memory_profiler import profile
from sage.matrix.berlekamp_massey import berlekamp_massey
@Profile
def gen_data():
    p = random_prime(2**64)
    ls = [GF(p).random_element() for _ in range(20000)]
    berlekamp_massey(ls); # <--- this line
gen_data()
```

I am not sure if I have to include extra doctests or not, or how to test
memory consumptions, since the time complexity is also O(n^2).

### 📝 Checklist

- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.
    
URL: sagemath#36173
Reported by: grhkm21
Reviewer(s): grhkm21, Kwankyu Lee
vbraun pushed a commit to vbraun/sage that referenced this issue Sep 10, 2023
sagemathgh-36173: Fix quadratic memory of berlekamp_massey
f63a4d5 
    
Fix sagemath#36172.

Reduced berlekamp_massey memory consumption by replacing a dictionary
with temporary variables. The memory consumption of the line highlighted
below reduced from 42MB to 4MB (probably inaccurate, but significant
enough).

```python
from memory_profiler import profile
from sage.matrix.berlekamp_massey import berlekamp_massey
@Profile
def gen_data():
    p = random_prime(2**64)
    ls = [GF(p).random_element() for _ in range(20000)]
    berlekamp_massey(ls); # <--- this line
gen_data()
```

I am not sure if I have to include extra doctests or not, or how to test
memory consumptions, since the time complexity is also O(n^2).

### 📝 Checklist

- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.
    
URL: sagemath#36173
Reported by: grhkm21
Reviewer(s): grhkm21, Kwankyu Lee
@mkoeppe mkoeppe added this to the sage-10.2 milestone Sep 10, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
t: bug
Projects
None yet
Milestone
sage-10.2
Development

Successfully merging a pull request may close this issue.

Fix quadratic memory of berlekamp_massey grhkm21/sage
2 participants
@mkoeppe @grhkm21