Karim Belabas on Sat, 10 Nov 2007 16:57:08 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: wishlist: evaluating polcyclo() and others |
* Jeroen Demeyer [2007-11-08 23:16]: > This is a long-time wishlist item of mine. It concerns the functions which > compute certain polynomials, for example polcyclo(), polchebyshev(), > pollegendre() and maybe others. These functions take an argument which is > the variable, but I would really like to put anything there, for example > polcyclo(10^6, 2) would compute the value of the 10^6-th cyclotomic > polynomial at the point 2. Or polchebyshev(10^4, x*Mod(1,3)) to get the > 10^4-th Chebyshev polynomial mod 3. Essentially polcyclo(n,a) should be > the same as subst(polcyclo(n),x,a). Done in CVS for polcyclo [ proof of concept first... ]. I started by improving the algorithms so that polcyclo(10^6) no longer requires about 5 minutes (---> 12ms, reducing to squarefree n helps a lot on this example...) Indeed, inline evaluation is usually faster: (15:16) gp > subst(polcyclo(2*3*5*7*11*13*19), x, 2); time = 1mn, 1,876 ms. (15:17) gp > polcyclo(2*3*5*7*11*13*19, 2); time = 1,568 ms. But I am using different formulas for the formal and "evaluated" computation, so that subst(polcyclo(n),x,a) MAY be faster than polcyclo(n, a) if a lives in a ring allowing coefficient explosion. The reason is that the 'subst' variant does not use divisions in the base ring (only over Z[X], with small operands), whereas the direct 'polcyclo(n,a)' does, possibly with huge operands. Native kernel: (first version) (15:18) gp > polcyclo(10^6,2); time = 2,416 ms. (15:18) gp > subst(polcyclo(10^6),x,2); time = 20 ms. GMP kernel: (15:18) gp > polcyclo(10^6,2); time = 212 ms. (15:18) gp > subst(polcyclo(10^6),x,2); time = 36 ms. I added a heuristic check in the code: if 'a' looks "huge", compute polcyclo(n, a) essentially as subst(polcyclo(n), x, a). And the above problem mostly disappears: Native kernel: (after patch) (15:18) gp > polcyclo(10^6,2); time = 4 ms. Still, inputs like polcyclo(n, Mod(1,2)*x) are a terrible idea compared to the old polcyclo(n) * Mod(1,2) [ 1) cyclotomics have tiny coeffs, so INTMODs don't help, 2) INTMODs are slow ] Cheers, K.B. -- Karim Belabas Tel: (+33) (0)5 40 00 26 17 Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP] `