Skip to content

Comments

Bind to FLINT/NTL API for polynomial modular exponentiation (new version)#37441

Merged
vbraun merged 17 commits intosagemath:developfrom
GiacomoPope:faster_poly_pow_mod
Apr 27, 2024
Merged

Bind to FLINT/NTL API for polynomial modular exponentiation (new version)#37441
vbraun merged 17 commits intosagemath:developfrom
GiacomoPope:faster_poly_pow_mod

Conversation

@GiacomoPope
Copy link
Contributor

@GiacomoPope GiacomoPope commented Feb 23, 2024 •
edited
Loading

This is a rejuvenation of the pull request by @remyoudompheng #35320.

All I have done is rebase with develop and modify a few lines to fit with the current structuring of SageMath. I have also added a few additional docstrings.

As an example of the performance gain:

Flint polynomials over prime fields

Old timings:

About 5x faster for flint using nmod_poly

sage: R.<x> = GF(5)[]
sage: %time pow(x+1, 5**100, x^5 + 4*x + 3)
CPU times: user 551 µs, sys: 1e+03 ns, total: 552 µs
Wall time: 555 µs
x + 1

New timings:

sage: R.<x> = GF(5)[]
sage:  %time pow(x+1, 5**100, x^5 + 4*x + 3)
CPU times: user 175 µs, sys: 1e+03 ns, total: 176 µs
Wall time: 179 µs
x + 1

NTL polynomials over prime fields

About 1000x faster for NTL $\textrm{GF}(p)$
Old timings:

sage: set_random_seed(0)
....: p = 2**255 - 19
....: R.<x> = F[]
....: f = R.random_element(degree=12)
....: g = R.random_element(degree=12)
....: %timeit pow(f, 2**33, g)
92.3 ms ± 947 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit pow(f, 2**64, g)
1.29 s ± 35.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

New timings:

sage: set_random_seed(0)
....: p = 2**255 - 19
....: R.<x> = F[]
....: f = R.random_element(degree=12)
....: g = R.random_element(degree=12)
....: %timeit pow(f, 2**33, g)
651 µs ± 28.9 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage:  %timeit pow(f, 2**64, g)
1.17 ms ± 10.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

NTL polynomials over extension fields

About 10x faster for NTL polynomial rings over $\textrm{GF}(p^k)$
Old timings:

sage: set_random_seed(0)
....: 
....: p = 2**255 - 19
....: F.<a> = GF(p^3)
....: q = F.order()
....: R.<x> = F[]
....: 
....: f = R.random_element(degree=12)
....: g = R.random_element(degree=12)
....: 
....: %time _ = pow(f, q, g)
....: 
....: p = 29
....: F.<a> = GF(p^100)
....: q = F.order()
....: R.<x> = F[]
....: 
....: f = R.random_element(degree=12)
....: g = R.random_element(degree=12)
....: 
....: %time _ = pow(f, q, g)
CPU times: user 409 ms, sys: 1.45 ms, total: 410 ms
Wall time: 411 ms
CPU times: user 14.6 s, sys: 202 ms, total: 14.8 s
Wall time: 14.9 s

New timings:

sage: set_random_seed(0)
....: 
....: p = 2**255 - 19
....: F.<a> = GF(p^3)
....: q = F.order()
....: R.<x> = F[]
....: 
....: f = R.random_element(degree=12)
....: g = R.random_element(degree=12)
....: 
....: %time _ = pow(f, q, g)
....: 
....: p = 29
....: F.<a> = GF(p^100)
....: q = F.order()
....: R.<x> = F[]
....: 
....: f = R.random_element(degree=12)
....: g = R.random_element(degree=12)
....: 
....: %time _ = pow(f, q, g)
CPU times: user 371 ms, sys: 761 µs, total: 371 ms
Wall time: 371 ms
CPU times: user 1.54 s, sys: 10.5 ms, total: 1.55 s
Wall time: 1.55 s

Closes #35320

@GiacomoPope GiacomoPope requested a review from tscrim February 23, 2024 15:51
tscrim
tscrim requested changes Feb 24, 2024
View reviewed changes
Copy link
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Just a bunch of details basically.

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Feb 24, 2024

Thanks for the comments, I have pushed your suggestions and then made the necessary changes for cython compilation. ./sage -t --new is fine, but I will let the CI run randomised testing for --all.

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Feb 24, 2024

On mobile so cannot search and fix what this failed doctest is. Will fix this ASAP

@grhkm21 grhkm21 mentioned this pull request Feb 24, 2024
Closed
2 tasks
@grhkm21
Copy link
Contributor

grhkm21 commented Feb 24, 2024

It's unrelated (exists since 10.2 release), I have reported it in #37454

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Feb 24, 2024

Thanks! Is there an easy way to trigger the CI to run again here? I could do a dumb commit but maybe there's something else I can do?

@grhkm21
Copy link
Contributor

grhkm21 commented Feb 24, 2024 •
edited
Loading

Don't think so, CI/workflow is triggered on push commit

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Feb 24, 2024

OK. Well either @tscrim will be OK with the current status after implementing his changes or I can do something silly to retrigger the CI.

@grhkm21 grhkm21 mentioned this pull request Feb 24, 2024
Open
2 tasks
@grhkm21
Copy link
Contributor

grhkm21 commented Feb 24, 2024

Sorry, I take the comment back. I do not fully understand the CI failure yet. I'm currently tracing it in #37454 ("fake failure") and #37455 (true cause).

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Feb 24, 2024 

Doctesting 1 file.
sage -t --long --random-seed=286735480429121101562228604801325644303 src/sage/rings/tests.py
    [62 tests, 16.37 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 17.2 seconds
    cpu time: 16.3 seconds
    cumulative wall time: 16.4 seconds
Features detected for doctesting: sage.modules,sage.rings.finite_rings,sage.rings.number_field,sage.rings.padics,sage.symbolic
pytest is not installed in the venv, skip checking tests that rely on it

I can't even reproduce the error locally???

@grhkm21 grhkm21 mentioned this pull request Feb 25, 2024
Merged
tscrim
tscrim approved these changes Feb 25, 2024
View reviewed changes
Copy link
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you. LGTM.

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Feb 25, 2024 •
edited
Loading

Note that the test failure here has been identified in #37471 and fixed in #37443 and is unrelated to this PR

@grhkm21
Copy link
Contributor

grhkm21 commented Feb 26, 2024

Can you add "closes #35320" in the PR description? :D

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Feb 26, 2024

@tscrim Sorry for the ping. I noticed a missing backtick in one of the docstrings so I fixed this. I don't know if officially this needs "reapproval"?

@tscrim
Copy link
Collaborator

tscrim commented Feb 26, 2024

I don't think so, but it is still good for someone to take a look over the changes. All is good.

@vbraun
Copy link
Member

vbraun commented Mar 26, 2024

merge conflict

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Mar 31, 2024

Conflict resolved.

@GiacomoPope GiacomoPope mentioned this pull request Apr 1, 2024
Closed
2 tasks
@GiacomoPope GiacomoPope mentioned this pull request Apr 3, 2024
Closed
2 tasks
@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Apr 8, 2024

@vbraun Can you take a look to whether this needs work still? Trying to clean up some of my PR

@github-actions
Copy link

github-actions bot commented Apr 9, 2024 •
edited
Loading

Documentation preview for this PR (built with commit eb80a09; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Apr 10, 2024

Doctest failure:

sage: from sage.rings.tests import test_karatsuba_multiplication ## line 429 ##
sage: test_karatsuba_multiplication(ZZ, 6, 5, verbose=True, seed=42) ## line 430 ##
test_karatsuba_multiplication: ring=Univariate Polynomial Ring in x over Integer Ring, threshold=2
  (x^6 + 4*x^5 + 4*x^4 - 3*x^3 - x^2 - x)*(2*x^4 + 3*x^3 - 20*x^2 - 2*x + 1)
  (4*x^5 + 16*x^2 + x - 41)*(x^2 + x - 1)
  (8*x^2 + 2*x + 1)*(3)
  (-4*x - 1)*(-8*x^2 - x)
  (-x^6 - x^3 - x^2 + x + 1)*(2*x^3 - x + 3)
  (-x^2 + x + 1)*(x^4 + x^3 - x^2 - x + 76)
  (4*x^3 + x^2 + 6)*(-x^2 - 5*x)
  (x + 4)*(-x + 5)
  (-2*x)*(3*x^2 - x)
  (x^6 + 21*x^5 + x^4 + 4*x^3 - x^2)*(14*x^4 + x^3 + 2*x^2 - 12*x)
sage: rings = [QQ] ## line 445 ##
sage: rings += [ZZ[I], ZZ[I, sqrt(2)]]                                          # needs sage.rings.number_field sage.symbolic ## line 446 ##
sage: rings += [GF(49, 'a')]                                                    # needs sage.rings.finite_rings ## line 447 ##
sage: rings += [MatrixSpace(GF(17), 3)]                                         # needs sage.modules ## line 448 ##
sage: for C in rings:                                                           # needs sage.modules
    test_karatsuba_multiplication(C, 10, 10) ## line 449 ##
sage: test_karatsuba_multiplication(QQbar, 3, 3, numtests=2)    # long time, needs sage.rings.number_field ## line 454 ##

Is unrelated, and to do with: #37455

@GiacomoPope GiacomoPope mentioned this pull request Apr 10, 2024
Open
2 tasks
@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Apr 19, 2024

Sorry for the ping, @vbraun but wanted to follow up on the needs work tag.

@tscrim
Copy link
Collaborator

tscrim commented Apr 21, 2024

I think its fine to just remove the needs work tag once the merge conflict is resolved assuming it was trivial (if it was not, just request a re-review by the reviewer(s)). Now just to wait for it to be merged.

@GiacomoPope
Copy link
Contributor Author

GiacomoPope commented Apr 21, 2024

Oh ok. I was under the impression that the PR owner should never add the positive review or remove the needs work tags.

@vbraun vbraun merged commit b704d41 into sagemath:develop Apr 27, 2024
@GiacomoPope GiacomoPope deleted the faster_poly_pow_mod branch August 21, 2024 14:35
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@tscrim tscrim tscrim approved these changes

Assignees

No one assigned

Labels

c: algebra p: major / 3 t: performance

Projects

None yet

Milestone

sage-10.4

Development

Successfully merging this pull request may close these issues.

5 participants

@GiacomoPope @grhkm21 @tscrim @vbraun @mkoeppe