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:

Status badges

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)

12109.4.patch (7.8 KB) - added by spice 9 years ago.
Minor documentation fixes in cyclotomic_value()

Download all attachments as: .zip

Change History (28)

comment:1 Changed 11 years ago by roed

  • Status changed from new to needs_review

comment:2 Changed 11 years ago by aapitzsch

  • Status changed from needs_review to needs_work

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) shows

System Message: WARNING/2 (\Phi_n(x) = \prod_{d \divides n} (x^d - 1)^{\mu(n / d)})

use \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

raise *Error, "..."

to

raise *Error("...")

http://www.python.org/dev/peps/pep-3109/#compatibility-issues

comment:3 Changed 11 years ago by roed

  • 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 aapitzsch

  • 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 jdemeyer

Please state clearly which patches have to be applied.

comment:7 Changed 11 years ago by jdemeyer

  • 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 jdemeyer

This is obviously wrong:

sage: cyclotomic_value(11, GF(5)(2))
2047

comment:9 Changed 11 years ago by jdemeyer

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 jdemeyer

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 jdemeyer

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 roed

  • 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 davidloeffler

Apply 12109.3.patch

(for patchbot)

comment:14 Changed 10 years ago by davidloeffler

  • 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: Changed 10 years ago by jdemeyer

Probably this whole patch would better be replaced anyway by a call to PARI.

comment:16 Changed 9 years ago by jpflori

  • Cc jpflori added

comment:17 in reply to: ↑ 15 ; follow-up: Changed 9 years ago by roed

  • 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 jpflori

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: Changed 9 years ago by jpflori

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 roed

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 roed

Just fixed a small problem in the TESTS (used x as the variable in the for loop).

Changed 9 years ago by spice

Minor documentation fixes in cyclotomic_value()

comment:22 Changed 9 years ago by spice

  • 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 spice

Apply 12109.4.patch

(for patchbot)

comment:24 Changed 9 years ago by spice

  • Reviewers changed from André Apitzsch to André Apitzsch, Simon Spicer

comment:25 Changed 9 years ago by jdemeyer

  • Work issues infinite loop deleted

I assume the "work issue" is no longer relevant?...

comment:26 Changed 9 years ago by roed

Yeah, that's correct.

comment:27 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.8.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.