Function for faster evaluation of cyclotomic polynomials

[roed]

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.

[aapitzsch]

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

[roed]

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.

[aapitzsch]

I attached a patch to add a colon and to replace TAB characters. Everything else looks fine, so I give it a positive review.

[jdemeyer]

Please state clearly which patches have to be applied.

[aapitzsch]

Apply

1. 12109.2.patch
2. trac_12109_reviewer.patch.

[jdemeyer]

You really should add more tests: real numbers, complex numbers, finite field elements, number field elements...

[jdemeyer]

This is obviously wrong:

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

[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).

[jdemeyer]

Instead of doing many divisions, it would be more efficient to simply compute numerator and denominator and divide once.

[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

[roed]

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.

[davidloeffler]

Apply 12109.3.patch

(for patchbot)

[davidloeffler]

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]

[jdemeyer]

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

[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....

[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?

[jpflori]

Hum, I just saw you did not remove your additional code, so disregard my previous comment.

[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.

[roed]

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

[spice]

Minor documentation fixes in cyclotomic_value()

[spice]

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.

[spice]

Apply 12109.4.patch

(for patchbot)

[jdemeyer]

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

[roed]

Yeah, that's correct.