Opened 11 years ago
Closed 9 years ago
#12109 closed enhancement (fixed)
Function for faster evaluation of cyclotomic polynomials
Reported by: | roed | Owned by: | was |
---|---|---|---|
Priority: | major | Milestone: | sage-5.8 |
Component: | number theory | Keywords: | |
Cc: | jpflori | Merged in: | sage-5.8.beta3 |
Authors: | David Roe | Reviewers: | André Apitzsch, Simon Spicer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
I've implemented a function for evaluating cyclotomic polynomials without having to explicitly create the polynomial: this gives both memory and speed savings for large n.
Attachments (1)
Change History (28)
comment:1 Changed 11 years ago by
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 11 years ago by
- Status changed from needs_work to needs_review
I changed comments and documentation to less than 79 characters, but left a couple of code snippets longer than that since they were less than 85 and I thought that introducing a line break would make it less clear. Let me know if you want me to change it.
Apply 12109.2.patch only.
comment:4 Changed 11 years ago by
- Reviewers set to André Apitzsch
- Status changed from needs_review to positive_review
I attached a patch to add a colon and to replace TAB characters. Everything else looks fine, so I give it a positive review.
comment:5 Changed 11 years ago by
Please state clearly which patches have to be applied.
comment:6 Changed 11 years ago by
comment:7 Changed 11 years ago by
- Status changed from positive_review to needs_work
You really should add more tests: real numbers, complex numbers, finite field elements, number field elements...
comment:8 Changed 11 years ago by
This is obviously wrong:
sage: cyclotomic_value(11, GF(5)(2)) 2047
comment:9 Changed 11 years ago by
You have a big Cython loop without any interrupt checks, you should implement http://sagemath.org/doc/developer/coding_in_cython.html#interrupt-and-signal-handling (and add a test for it for good measure).
comment:10 Changed 11 years ago by
Instead of doing many divisions, it would be more efficient to simply compute numerator and denominator and divide once.
comment:11 Changed 11 years ago by
This new code is actually quite a bit slower than PARI:
sage: timeit("cyclotomic_value(2*3*5*7*11*13*17, 10)") 5 loops, best of 3: 740 ms per loop sage: timeit("pari('polcyclo(2*3*5*7*11*13*17, 10)')") 5 loops, best of 3: 199 ms per loop
comment:12 Changed 11 years ago by
- Status changed from needs_work to needs_review
Thanks for catching those. I couldn't beat Pari, so the new patch uses pari for integers, rationals, and pari elements. I also incorporated the code for roots of unity and the tests from http://permalink.gmane.org/gmane.comp.mathematics.pari.devel/2930
Apply only 12109.3.patch.
comment:13 Changed 10 years ago by
Apply 12109.3.patch
(for patchbot)
comment:14 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to infinite loop
This patch seems to cause an infinite loop: both recent patchbot runs ended in timeout errors, including one with the timeout set to 1 hour:
sage -t -force_lib devel/sage-12109/sage/rings/polynomial/cyclotomic.pyx *** *** Error: TIMED OUT! PROCESS KILLED! *** *** [3600.2 s]
comment:15 follow-up: ↓ 17 Changed 10 years ago by
Probably this whole patch would better be replaced anyway by a call to PARI.
comment:16 Changed 9 years ago by
- Cc jpflori added
comment:17 in reply to: ↑ 15 ; follow-up: ↓ 18 Changed 9 years ago by
- Status changed from needs_work to needs_review
Replying to jdemeyer:
Probably this whole patch would better be replaced anyway by a call to PARI.
I've changed it so that it tries to just call PARI (and fixed the timeout problem). But that won't always work, since not every ring in Sage can convert to PARI.
I don't strongly object to just falling back on cyclotomic_polynomial
in this case, but the current code will provide a speedup in some cases. Of course those cases are probably rarely of interest....
comment:18 in reply to: ↑ 17 Changed 9 years ago by
Replying to roed:
Replying to jdemeyer:
Probably this whole patch would better be replaced anyway by a call to PARI.
I've changed it so that it tries to just call PARI (and fixed the timeout problem). But that won't always work, since not every ring in Sage can convert to PARI.
I don't strongly object to just falling back on
cyclotomic_polynomial
in this case, but the current code will provide a speedup in some cases. Of course those cases are probably rarely of interest....
I'd prefer to keep your generic code in if it really handles some corner cases better than going through cyclotomic_polynomial
.
Could provide an example of a ring where this additional code would be of interest?
comment:19 follow-up: ↓ 20 Changed 9 years ago by
Hum, I just saw you did not remove your additional code, so disregard my previous comment.
comment:20 in reply to: ↑ 19 Changed 9 years ago by
Replying to jpflori:
Hum, I just saw you did not remove your additional code, so disregard my previous comment.
It's still interesting to figure out when it's being used. Adding a print statement in the except StandardError
clause, I'm finding that most of the examples in the TESTS
block are using my implementation. I'm not sure why PARI is failing in these cases though.
comment:21 Changed 9 years ago by
Just fixed a small problem in the TESTS (used x
as the variable in the for loop).
comment:22 Changed 9 years ago by
- Status changed from needs_review to positive_review
Can't see any issues. Patch applies, tests work, code checks out with changes mentioned above added, values agree with evaluation of cyclotomic_polynomial()
for every test case I tried.
Fixed minor formatting errors in the documentation for cyclotomic_value()
. Added one or two lines too for further clarification of the algorithm.
comment:23 Changed 9 years ago by
Apply 12109.4.patch
(for patchbot)
comment:24 Changed 9 years ago by
- Reviewers changed from André Apitzsch to André Apitzsch, Simon Spicer
comment:25 Changed 9 years ago by
- Work issues infinite loop deleted
I assume the "work issue" is no longer relevant?...
comment:26 Changed 9 years ago by
Yeah, that's correct.
comment:27 Changed 9 years ago by
- Merged in set to sage-5.8.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
Some lines are to long. Maximum line length should be 79 characters.
`n`th
creates a bad rendered reference manual (HTML),`n`-th
should work.\divides
seems to be an unknown command. Reference manual (HTML) showsuse
\mid
instead.There is a double "that" in
parity_divisors()
.Please add an example for
_x = Integer(x)
fails.Not necessary for positive review but could you also change
to
http://www.python.org/dev/peps/pep-3109/#compatibility-issues