Karim Belabas on Wed, 09 May 2012 18:28:43 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Errors in poliscycloprod


* Charles Greathouse [2012-05-09 14:48]:
> poliscycloprod(polcyclo(1)^2) returns 0 instead of 1.  More generally,
> it seems that poliscycloprod(polcyclo(m)^n) is 0 for any m >= 1 and n
> >= 2.  This does not follow the documentation, which says, properly in
> my opinion,
> 
> poliscycloprod(f): returns 1 if f is a product of cyclotomic
> polynonials, and 0 otherwise.
> 
> One thing I'd like to do with the function is to detect periodic
> sequences by the denominator of their g.f., and in that case repeated
> factors -- especially of x-1 -- are very common.

Sorry, I currently can't access the git repository ( behind a stupid
firewall and the 'workaround' proxy I had set up on my home machine died 
yesterday )

But the following patch should fix the (trivial) problem:

diff --git a/src/basemath/QX_factor.c b/src/basemath/QX_factor.c
index 4c666b7..7a1db54 100644
--- a/src/basemath/QX_factor.c
+++ b/src/basemath/QX_factor.c
@@ -1414,7 +1414,11 @@ poliscycloprod(GEN f)
   if (!RgX_is_ZX(f)) return 0;
   if (!equali1(leading_term(f)) || !is_pm1(constant_term(f))) return 0;
   if (d < 2) return (d == 1);
-  (void)ZX_gcd_all(f, ZX_deriv(f), &f);
+  if ( degpol(ZX_gcd_all(f, ZX_deriv(f), &f)) )
+  {
+    d = degpol(f);
+    if (d == 1) return 1;
+  }
   f = BD(f); if (!f) return 0;
   for (i = lg(f)-1; i; i--) d -= degpol(gel(f,i));
   avma = av; return d == 0;


> Further, on the Windows git version,
> 
> ? poliscycloprod(x^3-1)
>   ***   at top-level: poliscycloprod(x^3-1
>   ***                 ^--------------------
>   *** poliscycloprod: the PARI stack overflows !
>   current stack size: 157286400 (150.000 Mbytes)
>   [hint] you can increase GP stack with allocatemem()
> 
> which seems to happen for x^k - 1 for all k not a power of 2.

I can't reproduce that one. I get no compiler warning and valgrind doesn't
show anything suspect.

Can you try to investigate ?

Cheers,

    K.B.
-- 
Karim Belabas, IMB (UMR 5251)  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-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`