Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - ZX.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 24988-2584e74448) Lines: 576 669 86.1 %
Date: 2020-01-26 05:57:03 Functions: 79 87 90.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2007  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : /*******************************************************************/
      18             : /*                                                                 */
      19             : /*                                ZX                               */
      20             : /*                                                                 */
      21             : /*******************************************************************/
      22             : void
      23      228355 : RgX_check_QX(GEN x, const char *s)
      24      228355 : { if (!RgX_is_QX(x)) pari_err_TYPE(stack_strcat(s," [not in Q[X]]"), x); }
      25             : void
      26      686428 : RgX_check_ZX(GEN x, const char *s)
      27      686428 : { if (!RgX_is_ZX(x)) pari_err_TYPE(stack_strcat(s," [not in Z[X]]"), x); }
      28             : long
      29       15477 : ZX_max_lg(GEN x)
      30             : {
      31       15477 :   long i, prec = 0, lx = lg(x);
      32             : 
      33       15477 :   for (i=2; i<lx; i++) { long l = lgefint(gel(x,i)); if (l > prec) prec = l; }
      34       15477 :   return prec;
      35             : }
      36             : 
      37             : GEN
      38    13144511 : ZX_add(GEN x, GEN y)
      39             : {
      40             :   long lx,ly,i;
      41             :   GEN z;
      42    13144511 :   lx = lg(x); ly = lg(y); if (lx < ly) swapspec(x,y, lx,ly);
      43    13144511 :   z = cgetg(lx,t_POL); z[1] = x[1];
      44    13148965 :   for (i=2; i<ly; i++) gel(z,i) = addii(gel(x,i),gel(y,i));
      45    13142218 :   for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
      46    13144493 :   if (lx == ly) z = ZX_renormalize(z, lx);
      47    13144499 :   if (!lgpol(z)) { set_avma((pari_sp)(z + lx)); return pol_0(varn(x)); }
      48    11900294 :   return z;
      49             : }
      50             : 
      51             : GEN
      52     6276012 : ZX_sub(GEN x,GEN y)
      53             : {
      54     6276012 :   long i, lx = lg(x), ly = lg(y);
      55             :   GEN z;
      56     6276012 :   if (lx >= ly)
      57             :   {
      58     6202996 :     z = cgetg(lx,t_POL); z[1] = x[1];
      59     6203066 :     for (i=2; i<ly; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
      60     6202996 :     if (lx == ly)
      61             :     {
      62     5036996 :       z = ZX_renormalize(z, lx);
      63     5036996 :       if (!lgpol(z)) { set_avma((pari_sp)(z + lx)); z = pol_0(varn(x)); }
      64             :     }
      65             :     else
      66     1166000 :       for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
      67             :   }
      68             :   else
      69             :   {
      70       73016 :     z = cgetg(ly,t_POL); z[1] = y[1];
      71       73016 :     for (i=2; i<lx; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
      72       73016 :     for (   ; i<ly; i++) gel(z,i) = negi(gel(y,i));
      73             :   }
      74     6276012 :   return z;
      75             : }
      76             : 
      77             : GEN
      78      326898 : ZX_neg(GEN x)
      79             : {
      80      326898 :   long i, l = lg(x);
      81      326898 :   GEN y = cgetg(l,t_POL);
      82      326898 :   y[1] = x[1]; for(i=2; i<l; i++) gel(y,i) = negi(gel(x,i));
      83      326898 :   return y;
      84             : }
      85             : GEN
      86     5456510 : ZX_copy(GEN x)
      87             : {
      88     5456510 :   long i, l = lg(x);
      89     5456510 :   GEN y = cgetg(l, t_POL);
      90     5456517 :   y[1] = x[1];
      91    21473145 :   for (i=2; i<l; i++)
      92             :   {
      93    16016631 :     GEN c = gel(x,i);
      94    16016631 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
      95             :   }
      96     5456514 :   return y;
      97             : }
      98             : 
      99             : GEN
     100       55542 : scalar_ZX(GEN x, long v)
     101             : {
     102             :   GEN z;
     103       55542 :   if (!signe(x)) return pol_0(v);
     104        4336 :   z = cgetg(3, t_POL);
     105        4336 :   z[1] = evalsigne(1) | evalvarn(v);
     106        4336 :   gel(z,2) = icopy(x); return z;
     107             : }
     108             : 
     109             : GEN
     110       19059 : scalar_ZX_shallow(GEN x, long v)
     111             : {
     112             :   GEN z;
     113       19059 :   if (!signe(x)) return pol_0(v);
     114       18890 :   z = cgetg(3, t_POL);
     115       18890 :   z[1] = evalsigne(1) | evalvarn(v);
     116       18890 :   gel(z,2) = x; return z;
     117             : }
     118             : 
     119             : GEN
     120       83700 : ZX_Z_add(GEN y, GEN x)
     121             : {
     122             :   long lz, i;
     123       83700 :   GEN z = cgetg_copy(y, &lz);
     124       83700 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX(x,varn(y)); }
     125       73032 :   z[1] = y[1];
     126       73032 :   gel(z,2) = addii(gel(y,2),x);
     127       71799 :   for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
     128       73035 :   if (lz==3) z = ZX_renormalize(z,lz);
     129       73035 :   return z;
     130             : }
     131             : GEN
     132       11159 : ZX_Z_add_shallow(GEN y, GEN x)
     133             : {
     134             :   long lz, i;
     135       11159 :   GEN z = cgetg_copy(y, &lz);
     136       11159 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX_shallow(x,varn(y)); }
     137       10949 :   z[1] = y[1];
     138       10949 :   gel(z,2) = addii(gel(y,2),x);
     139       10949 :   for(i=3; i<lz; i++) gel(z,i) = gel(y,i);
     140       10949 :   if (lz==3) z = ZX_renormalize(z,lz);
     141       10949 :   return z;
     142             : }
     143             : 
     144             : GEN
     145       61513 : ZX_Z_sub(GEN y, GEN x)
     146             : {
     147             :   long lz, i;
     148       61513 :   GEN z = cgetg_copy(y, &lz);
     149       61513 :   if (lz == 2)
     150             :   { /* scalarpol(negi(x), v) */
     151           0 :     long v = varn(y);
     152           0 :     set_avma((pari_sp)(z + 2));
     153           0 :     if (!signe(x)) return pol_0(v);
     154           0 :     z = cgetg(3,t_POL);
     155           0 :     z[1] = evalvarn(v) | evalsigne(1);
     156           0 :     gel(z,2) = negi(x); return z;
     157             :   }
     158       61513 :   z[1] = y[1];
     159       61513 :   gel(z,2) = subii(gel(y,2),x);
     160       61513 :   for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
     161       61513 :   if (lz==3) z = ZX_renormalize(z,lz);
     162       61513 :   return z;
     163             : }
     164             : 
     165             : GEN
     166      502596 : Z_ZX_sub(GEN x, GEN y)
     167             : {
     168             :   long lz, i;
     169      502596 :   GEN z = cgetg_copy(y, &lz);
     170      502596 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX(x,varn(y)); }
     171      502596 :   z[1] = y[1];
     172      502596 :   gel(z,2) = subii(x, gel(y,2));
     173      502596 :   for(i=3; i<lz; i++) gel(z,i) = negi(gel(y,i));
     174      502596 :   if (lz==3) z = ZX_renormalize(z,lz);
     175      502596 :   return z;
     176             : }
     177             : 
     178             : GEN
     179     2991051 : ZX_Z_divexact(GEN y,GEN x)
     180             : {
     181     2991051 :   long i, l = lg(y);
     182     2991051 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
     183     2991720 :   for(i=2; i<l; i++) gel(z,i) = diviiexact(gel(y,i),x);
     184     2991039 :   return z;
     185             : }
     186             : 
     187             : GEN
     188           0 : zx_z_divexact(GEN y, long x)
     189             : {
     190           0 :   long i, l = lg(y);
     191           0 :   GEN z = cgetg(l,t_VECSMALL); z[1] = y[1];
     192           0 :   for (i=2; i<l; i++) z[i] = y[i]/x;
     193           0 :   return z;
     194             : }
     195             : 
     196             : GEN
     197     9213647 : ZX_Z_mul(GEN y,GEN x)
     198             : {
     199             :   GEN z;
     200             :   long i, l;
     201     9213647 :   if (!signe(x)) return pol_0(varn(y));
     202     6489351 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     203     6490553 :   for(i=2; i<l; i++) gel(z,i) = mulii(gel(y,i),x);
     204     6489332 :   return z;
     205             : }
     206             : 
     207             : GEN
     208      120491 : ZX_mulu(GEN y, ulong x)
     209             : {
     210             :   GEN z;
     211             :   long i, l;
     212      120491 :   if (!x) return pol_0(varn(y));
     213      120491 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     214      120491 :   for(i=2; i<l; i++) gel(z,i) = mului(x,gel(y,i));
     215      120491 :   return z;
     216             : }
     217             : 
     218             : GEN
     219     1373898 : ZX_shifti(GEN y, long n)
     220             : {
     221             :   GEN z;
     222             :   long i, l;
     223     1373898 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     224     1392431 :   for(i=2; i<l; i++) gel(z,i) = shifti(gel(y,i),n);
     225     1373775 :   return ZX_renormalize(z,l);
     226             : }
     227             : 
     228             : GEN
     229       97825 : ZX_remi2n(GEN y, long n)
     230             : {
     231             :   GEN z;
     232             :   long i, l;
     233       97825 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     234      102485 :   for(i=2; i<l; i++) gel(z,i) = remi2n(gel(y,i),n);
     235       97754 :   return ZX_renormalize(z,l);
     236             : }
     237             : 
     238             : GEN
     239       39362 : ZXT_remi2n(GEN z, long n)
     240             : {
     241       39362 :   if (typ(z) == t_POL)
     242       35311 :     return ZX_remi2n(z, n);
     243             :   else
     244             :   {
     245        4051 :     long i,l = lg(z);
     246        4051 :     GEN x = cgetg(l, t_VEC);
     247        4050 :     for (i=1; i<l; i++) gel(x,i) = ZXT_remi2n(gel(z,i), n);
     248        4050 :     return x;
     249             :   }
     250             : }
     251             : 
     252             : GEN
     253         294 : zx_to_ZX(GEN z)
     254             : {
     255         294 :   long i, l = lg(z);
     256         294 :   GEN x = cgetg(l,t_POL);
     257         294 :   for (i=2; i<l; i++) gel(x,i) = stoi(z[i]);
     258         294 :   x[1] = evalsigne(l-2!=0)| z[1]; return x;
     259             : }
     260             : 
     261             : GEN
     262     2400923 : ZX_deriv(GEN x)
     263             : {
     264     2400923 :   long i,lx = lg(x)-1;
     265             :   GEN y;
     266             : 
     267     2400923 :   if (lx<3) return pol_0(varn(x));
     268     2394895 :   y = cgetg(lx,t_POL);
     269     2394904 :   for (i=2; i<lx ; i++) gel(y,i) = mului(i-1,gel(x,i+1));
     270     2394895 :   y[1] = x[1]; return y;
     271             : }
     272             : 
     273             : int
     274     1498741 : ZX_equal(GEN V, GEN W)
     275             : {
     276     1498741 :   long i, l = lg(V);
     277     1498741 :   if (lg(W) != l) return 0;
     278     5142509 :   for (i = 2; i < l; i++)
     279     3867656 :     if (!equalii(gel(V,i), gel(W,i))) return 0;
     280     1274853 :   return 1;
     281             : }
     282             : 
     283             : static long
     284   119797454 : ZX_valspec(GEN x, long nx)
     285             : {
     286             :   long vx;
     287   182545671 :   for (vx = 0; vx<nx ; vx++)
     288   182545549 :     if (signe(gel(x,vx))) break;
     289   119797454 :   return vx;
     290             : }
     291             : 
     292             : long
     293       35910 : ZX_val(GEN x)
     294             : {
     295             :   long vx;
     296       35910 :   if (!signe(x)) return LONG_MAX;
     297       37478 :   for (vx = 0;; vx++)
     298       39046 :     if (signe(gel(x,2+vx))) break;
     299       35910 :   return vx;
     300             : }
     301             : long
     302    21283707 : ZX_valrem(GEN x, GEN *Z)
     303             : {
     304             :   long vx;
     305    21283707 :   if (!signe(x)) { *Z = pol_0(varn(x)); return LONG_MAX; }
     306    41221837 :   for (vx = 0;; vx++)
     307    61159967 :     if (signe(gel(x,2+vx))) break;
     308    21283707 :   *Z = RgX_shift_shallow(x, -vx);
     309    21283707 :   return vx;
     310             : }
     311             : 
     312             : GEN
     313          21 : ZX_div_by_X_1(GEN a, GEN *r)
     314             : {
     315          21 :   long l = lg(a), i;
     316          21 :   GEN a0, z0, z = cgetg(l-1, t_POL);
     317          21 :   z[1] = a[1];
     318          21 :   a0 = a + l-1;
     319          21 :   z0 = z + l-2; *z0 = *a0--;
     320        4732 :   for (i=l-3; i>1; i--) /* z[i] = a[i+1] + z[i+1] */
     321             :   {
     322        4711 :     GEN t = addii(gel(a0--,0), gel(z0--,0));
     323        4711 :     gel(z0,0) = t;
     324             :   }
     325          21 :   if (r) *r = addii(gel(a0,0), gel(z0,0));
     326          21 :   return z;
     327             : }
     328             : 
     329             : /* return P(X + c) using destructive Horner, optimize for c = 1,-1 */
     330             : static GEN
     331      393714 : ZX_translate_basecase(GEN P, GEN c)
     332             : {
     333      393714 :   pari_sp av = avma;
     334             :   GEN Q, R;
     335             :   long i, k, n;
     336             : 
     337      393714 :   if (!signe(P) || !signe(c)) return ZX_copy(P);
     338      393693 :   Q = leafcopy(P);
     339      393693 :   R = Q+2; n = degpol(P);
     340      393693 :   if (equali1(c))
     341             :   {
     342     2483851 :     for (i=1; i<=n; i++)
     343             :     {
     344     2195772 :       for (k=n-i; k<n; k++) gel(R,k) = addii(gel(R,k), gel(R,k+1));
     345     2195772 :       if (gc_needed(av,2))
     346             :       {
     347           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate(1), i = %ld/%ld", i,n);
     348           0 :         Q = gerepilecopy(av, Q); R = Q+2;
     349             :       }
     350             :     }
     351             :   }
     352      105614 :   else if (equalim1(c))
     353             :   {
     354           0 :     for (i=1; i<=n; i++)
     355             :     {
     356           0 :       for (k=n-i; k<n; k++) gel(R,k) = subii(gel(R,k), gel(R,k+1));
     357           0 :       if (gc_needed(av,2))
     358             :       {
     359           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate(-1), i = %ld/%ld", i,n);
     360           0 :         Q = gerepilecopy(av, Q); R = Q+2;
     361             :       }
     362             :     }
     363             :   }
     364             :   else
     365             :   {
     366      798506 :     for (i=1; i<=n; i++)
     367             :     {
     368      692892 :       for (k=n-i; k<n; k++) gel(R,k) = addmulii_inplace(gel(R,k), c, gel(R,k+1));
     369      692892 :       if (gc_needed(av,2))
     370             :       {
     371           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate, i = %ld/%ld", i,n);
     372           0 :         Q = gerepilecopy(av, Q); R = Q+2;
     373             :       }
     374             :     }
     375             :   }
     376      393693 :   return gerepilecopy(av, Q);
     377             : }
     378             : 
     379             : static GEN
     380           0 : Z_Xpm1_powu(long n, long s, long v)
     381             : {
     382             :   long d, k;
     383             :   GEN C;
     384           0 :   if (!n) return pol_1(v);
     385           0 :   d = (n + 1) >> 1;
     386           0 :   C = cgetg(n+3, t_POL);
     387           0 :   C[1] = evalsigne(1)| evalvarn(v);
     388           0 :   gel(C,2) = gen_1;
     389           0 :   gel(C,3) = utoipos(n);
     390           0 :   for (k=2; k <= d; k++)
     391           0 :     gel(C,k+2) = diviuexact(mului(n-k+1, gel(C,k+1)), k);
     392           0 :   if (s < 0)
     393           0 :     for (k = odd(n)? 0: 1; k <= d; k += 2)
     394           0 :       togglesign_safe(&gel(C,k+2));
     395           0 :   if (s > 0 || !odd(n))
     396           0 :     for (k = d+1; k <= n; k++) gel(C,k+2) = gel(C,n-k+2);
     397             :   else
     398           0 :     for (k = d+1; k <= n; k++) gel(C,k+2) = negi(gel(C,n-k+2));
     399           0 :   return C;
     400             : }
     401             : /* return (x+u)^n */
     402             : static GEN
     403           0 : Z_XpN_powu(GEN u, long n, long v)
     404             : {
     405             :   pari_sp av;
     406             :   long k;
     407             :   GEN B, C, V;
     408           0 :   if (!n) return pol_1(v);
     409           0 :   if (is_pm1(u))
     410           0 :     return Z_Xpm1_powu(n, signe(u), v);
     411           0 :   av = avma;
     412           0 :   V = gpowers(u, n);
     413           0 :   B = vecbinomial(n);
     414           0 :   C = cgetg(n+3, t_POL);
     415           0 :   C[1] = evalsigne(1)| evalvarn(v);
     416           0 :   for (k=1; k <= n+1; k++)
     417           0 :     gel(C,k+1) = mulii(gel(V,n+2-k), gel(B,k));
     418           0 :   return gerepileupto(av, C);
     419             : }
     420             : 
     421             : GEN
     422      393714 : ZX_translate(GEN P, GEN c)
     423             : {
     424      393714 :   pari_sp av = avma;
     425      393714 :   long n = degpol(P);
     426      393714 :   if (n < 220)
     427      393714 :     return ZX_translate_basecase(P, c);
     428             :   else
     429             :   {
     430           0 :     long d = n >> 1;
     431           0 :     GEN Q = ZX_translate(RgX_shift_shallow(P, -d), c);
     432           0 :     GEN R = ZX_translate(RgXn_red_shallow(P, d), c);
     433           0 :     GEN S = Z_XpN_powu(c, d, varn(P));
     434           0 :     return gerepileupto(av, ZX_add(ZX_mul(Q, S), R));
     435             :   }
     436             : }
     437             : 
     438             : /* Return 2^(n degpol(P))  P(x >> n) */
     439             : GEN
     440           0 : ZX_rescale2n(GEN P, long n)
     441             : {
     442           0 :   long i, l = lg(P), ni = n;
     443             :   GEN Q;
     444           0 :   if (l==2) return pol_0(varn(P));
     445           0 :   Q = cgetg(l,t_POL);
     446           0 :   gel(Q,l-1) = icopy(gel(P,l-1));
     447           0 :   for (i=l-2; i>=2; i--)
     448             :   {
     449           0 :     gel(Q,i) = shifti(gel(P,i), ni);
     450           0 :     ni += n;
     451             :   }
     452           0 :   Q[1] = P[1]; return Q;
     453             : }
     454             : 
     455             : /* Return h^deg(P) P(x / h), not memory clean. h integer, P ZX */
     456             : GEN
     457       12317 : ZX_rescale(GEN P, GEN h)
     458             : {
     459       12317 :   long l = lg(P);
     460       12317 :   GEN Q = cgetg(l,t_POL);
     461       12317 :   if (l != 2)
     462             :   {
     463       12317 :     long i = l-1;
     464       12317 :     GEN hi = h;
     465       12317 :     gel(Q,i) = gel(P,i);
     466       12317 :     if (l != 3) { i--; gel(Q,i) = mulii(gel(P,i), h); }
     467       12317 :     for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
     468             :   }
     469       12317 :   Q[1] = P[1]; return Q;
     470             : }
     471             : /* Return h^(deg(P)-1) P(x / h), P!=0, h=lt(P), memory unclean; monic result */
     472             : GEN
     473           0 : ZX_rescale_lt(GEN P)
     474             : {
     475           0 :   long l = lg(P);
     476           0 :   GEN Q = cgetg(l,t_POL);
     477           0 :   gel(Q,l-1) = gen_1;
     478           0 :   if (l != 3)
     479             :   {
     480           0 :     long i = l-1;
     481           0 :     GEN h = gel(P,i), hi = h;
     482           0 :     i--; gel(Q,i) = gel(P,i);
     483           0 :     if (l != 4) { i--; gel(Q,i) = mulii(gel(P,i), h); }
     484           0 :     for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
     485             :   }
     486           0 :   Q[1] = P[1]; return Q;
     487             : }
     488             : 
     489             : 
     490             : /*Eval x in 2^(k*BIL) in linear time*/
     491             : static GEN
     492    48709865 : ZX_eval2BILspec(GEN x, long k, long nx)
     493             : {
     494    48709865 :   pari_sp av = avma;
     495    48709865 :   long i,j, lz = k*nx, ki;
     496    48709865 :   GEN pz = cgetipos(2+lz);
     497    48709270 :   GEN nz = cgetipos(2+lz);
     498  1620468131 :   for(i=0; i < lz; i++)
     499             :   {
     500  1571755627 :     *int_W(pz,i) = 0UL;
     501  1571755627 :     *int_W(nz,i) = 0UL;
     502             :   }
     503   485272938 :   for(i=0, ki=0; i<nx; i++, ki+=k)
     504             :   {
     505   436560434 :     GEN c = gel(x,i);
     506   436560434 :     long lc = lgefint(c)-2;
     507   436560434 :     if (signe(c)==0) continue;
     508   329909447 :     if (signe(c) > 0)
     509   272941402 :       for (j=0; j<lc; j++) *int_W(pz,j+ki) = *int_W(c,j);
     510             :     else
     511    56968045 :       for (j=0; j<lc; j++) *int_W(nz,j+ki) = *int_W(c,j);
     512             :   }
     513    48712504 :   pz = int_normalize(pz,0);
     514    48712117 :   nz = int_normalize(nz,0); return gerepileuptoint(av, subii(pz,nz));
     515             : }
     516             : 
     517             : static long
     518    62225064 : ZX_expispec(GEN x, long nx)
     519             : {
     520    62225064 :   long i, m = 0;
     521   544888692 :   for(i = 0; i < nx; i++)
     522             :   {
     523   482667072 :     long e = expi(gel(x,i));
     524   482663628 :     if (e > m) m = e;
     525             :   }
     526    62221620 :   return m;
     527             : }
     528             : 
     529             : static GEN
     530    27549837 : Z_mod2BIL_ZX(GEN x, long bs, long d, long vx)
     531             : {
     532    27549837 :   long i, offset, lm = lgefint(x)-2, l = d+vx+3, sx = signe(x);
     533    27549837 :   GEN s1 = int2n(bs*BITS_IN_LONG), pol = cgetg(l, t_POL);
     534    27659968 :   int carry = 0;
     535    27659968 :   pol[1] = evalsigne(1);
     536    27659968 :   for (i=0; i<vx; i++) gel(pol,i+2) = gen_0;
     537   475814211 :   for (offset=0; i <= d+vx; i++, offset += bs)
     538             :   {
     539   448269197 :     pari_sp av = avma;
     540   448269197 :     long lz = minss(bs, lm-offset);
     541   449466874 :     GEN z = lz > 0 ?adduispec_offset(carry, x, offset, lz): utoi(carry);
     542   448247480 :     if (lgefint(z) == 3+bs) { carry = 1; z = gen_0;}
     543             :     else
     544             :     {
     545   436690385 :       carry = (lgefint(z) == 2+bs && (HIGHBIT & *int_W(z,bs-1)));
     546   436690385 :       if (carry)
     547    34390521 :         z = gerepileuptoint(av, (sx==-1)? subii(s1,z): subii(z,s1));
     548   402299864 :       else if (sx==-1) togglesign(z);
     549             :     }
     550   448154243 :     gel(pol,i+2) = z;
     551             :   }
     552    27545014 :   return ZX_renormalize(pol,l);
     553             : }
     554             : 
     555             : static GEN
     556     4727569 : ZX_sqrspec_sqri(GEN x, long nx, long ex, long v)
     557             : {
     558     4727569 :   long e = 2*ex + expu(nx) + 3;
     559     4727542 :   long N = divsBIL(e)+1;
     560     4727495 :   GEN  z = sqri(ZX_eval2BILspec(x,N,nx));
     561     4728452 :   return Z_mod2BIL_ZX(z, N, nx*2-2, v);
     562             : }
     563             : 
     564             : static GEN
     565    21150282 : ZX_mulspec_mulii(GEN x, GEN y, long nx, long ny, long ex, long ey, long v)
     566             : {
     567    21150282 :   long e = ex + ey + expu(minss(nx,ny)) + 3;
     568    21150195 :   long N = divsBIL(e)+1;
     569    21150161 :   GEN  z = mulii(ZX_eval2BILspec(x,N,nx), ZX_eval2BILspec(y,N,ny));
     570    21150281 :   return Z_mod2BIL_ZX(z, N, nx+ny-2, v);
     571             : }
     572             : 
     573             : INLINE GEN
     574    78979899 : ZX_sqrspec_basecase_limb(GEN x, long a, long i)
     575             : {
     576    78979899 :   pari_sp av = avma;
     577    78979899 :   GEN s = gen_0;
     578    78979899 :   long j, l = (i+1)>>1;
     579   222003342 :   for (j=a; j<l; j++)
     580             :   {
     581   143592513 :     GEN xj = gel(x,j), xx = gel(x,i-j);
     582   143592513 :     if (signe(xj) && signe(xx))
     583   141462167 :       s = addii(s, mulii(xj, xx));
     584             :   }
     585    78410829 :   s = shifti(s,1);
     586    78331845 :   if ((i&1) == 0)
     587             :   {
     588    46044693 :     GEN t = gel(x, i>>1);
     589    46044693 :     if (signe(t))
     590    45907610 :       s = addii(s, sqri(t));
     591             :   }
     592    78316332 :   return gerepileuptoint(av,s);
     593             : }
     594             : 
     595             : static GEN
     596    13512588 : ZX_sqrspec_basecase(GEN x, long nx, long v)
     597             : {
     598             :   long i, lz, nz;
     599             :   GEN z;
     600             : 
     601    13512588 :   lz = (nx << 1) + 1; nz = lz-2;
     602    13512588 :   lz += v;
     603    13512588 :   z = cgetg(lz,t_POL); z[1] = evalsigne(1); z += 2;
     604    13514170 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
     605    59583740 :   for (i=0; i<nx; i++)
     606    46077561 :     gel(z,i) = ZX_sqrspec_basecase_limb(x, 0, i);
     607    13506179 :   for (  ; i<nz; i++) gel(z,i) = ZX_sqrspec_basecase_limb(x, i-nx+1, i);
     608    13511918 :   z -= v+2; return z;
     609             : }
     610             : 
     611             : static GEN
     612     6054679 : Z_sqrshiftspec_ZX(GEN x, long vx)
     613             : {
     614     6054679 :   long i, nz = 2*vx+1;
     615     6054679 :   GEN z = cgetg(2+nz, t_POL);
     616     6054679 :   z[1] = evalsigne(1);
     617     6054679 :   for(i=2;i<nz+1;i++) gel(z,i) = gen_0;
     618     6054679 :   gel(z,nz+1) = sqri(x);
     619     6054679 :   return z;
     620             : }
     621             : 
     622             : static GEN
     623    26601379 : Z_ZX_mulshiftspec(GEN x, GEN y, long ny, long vz)
     624             : {
     625    26601379 :   long i, nz = vz+ny;
     626    26601379 :   GEN z = cgetg(2+nz, t_POL);
     627    26601410 :   z[1] = evalsigne(1);
     628    26601410 :   for (i=0; i<vz; i++)   gel(z,i+2)    = gen_0;
     629    26601410 :   for (i=0; i<ny; i++) gel(z,i+vz+2) = mulii(x, gel(y,i));
     630    26601374 :   return z;
     631             : }
     632             : 
     633             : GEN
     634    24375370 : ZX_sqrspec(GEN x, long nx)
     635             : {
     636             : #ifdef PARI_KERNEL_GMP
     637    14167498 :   const long low[]={ 17, 32, 96, 112, 160, 128, 128, 160, 160, 160, 160, 160, 176, 192, 192, 192, 192, 192, 224, 224, 224, 240, 240, 240, 272, 288, 288, 240, 288, 304, 304, 304, 304, 304, 304, 352, 352, 368, 352, 352, 352, 368, 368, 432, 432, 496, 432, 496, 496};
     638    14167498 :   const long high[]={ 102860, 70254, 52783, 27086, 24623, 18500, 15289, 13899, 12635, 11487, 10442, 9493, 8630, 7845, 7132, 7132, 6484, 6484, 5894, 5894, 4428, 4428, 3660, 4428, 3660, 3660, 2749, 2499, 2272, 2066, 1282, 1282, 1166, 1166, 1166, 1166, 1166, 1166, 1166, 963, 963, 724, 658, 658, 658, 528, 528, 528, 528};
     639             : #else
     640    10207872 :   const long low[]={ 17, 17, 32, 32, 96, 96, 96, 96, 96, 96, 96, 96, 96, 96, 112, 112, 128, 112, 112, 112, 112, 112, 128, 128, 160, 160, 112, 128, 128, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 176, 160, 160, 176, 160, 160, 176, 176, 208, 176, 176, 176, 192, 192, 176, 176, 224, 176, 224, 224, 176, 224, 224, 224, 176, 176, 176, 176, 176, 176, 176, 176, 224, 176, 176, 224, 224, 224, 224, 224, 224, 224, 240, 288, 240, 288, 288, 240, 288, 288, 240, 240, 304, 304};
     641    10207872 :   const long high[]={ 165657, 85008, 52783, 43622, 32774, 27086, 22385, 15289, 13899, 12635, 11487, 10442, 9493, 7845, 6484, 6484, 5894, 5894, 4871, 4871, 4428, 4026, 3660, 3660, 3660, 3327, 3327, 3024, 2749, 2749, 2272, 2749, 2499, 2499, 2272, 1878, 1878, 1878, 1707, 1552, 1552, 1552, 1552, 1552, 1411, 1411, 1411, 1282, 1282, 1282, 1282, 1282, 1166, 1166, 1166, 1166, 1166, 1166, 1166, 1166, 1060, 1060, 963, 963, 963, 963, 963, 963, 963, 963, 963, 963, 963, 876, 876, 876, 876, 796, 658, 724, 658, 724, 658, 658, 658, 658, 658, 658, 658, 658, 658, 658, 658, 658, 336, 658, 658, 592, 336, 336};
     642             : #endif
     643    24375370 :   const long nblow = numberof(low);
     644             :   pari_sp av;
     645             :   long ex, vx;
     646             :   GEN z;
     647    24375370 :   if (!nx) return pol_0(0);
     648    24295938 :   vx = ZX_valspec(x,nx); nx-=vx; x+=vx;
     649    24296069 :   if (nx==1) return Z_sqrshiftspec_ZX(gel(x, 0), vx);
     650    18241390 :   av = avma;
     651    18241390 :   ex = ZX_expispec(x,nx);
     652    18240048 :   if (nx-2 < nblow && low[nx-2]<=ex && ex<=high[nx-2])
     653    13512603 :     z = ZX_sqrspec_basecase(x, nx, 2*vx);
     654             :   else
     655     4727445 :     z = ZX_sqrspec_sqri(x, nx, ex, 2*vx);
     656    18238583 :   return gerepileupto(av, z);
     657             : }
     658             : 
     659             : GEN
     660    24373277 : ZX_sqr(GEN x)
     661             : {
     662    24373277 :   GEN z = ZX_sqrspec(x+2, lgpol(x));
     663    24373142 :   z[1] = x[1];
     664    24373142 :   return z;
     665             : }
     666             : 
     667             : GEN
     668    56448639 : ZX_mulspec(GEN x, GEN y, long nx, long ny)
     669             : {
     670             :   pari_sp av;
     671             :   long ex, ey, vx, vy;
     672             :   GEN z;
     673    56448639 :   if (!nx || !ny) return pol_0(0);
     674    47751394 :   vx = ZX_valspec(x,nx); nx-=vx; x += vx;
     675    47751382 :   vy = ZX_valspec(y,ny); ny-=vy; y += vy;
     676    47751434 :   if (nx==1) return Z_ZX_mulshiftspec(gel(x,0), y, ny, vx+vy);
     677    27557227 :   if (ny==1) return Z_ZX_mulshiftspec(gel(y,0), x, nx, vy+vx);
     678    21150055 :   av = avma;
     679    21150055 :   ex = ZX_expispec(x, nx); ey = ZX_expispec(y, ny);
     680    21150221 :   z  = ZX_mulspec_mulii(x,y,nx,ny,ex,ey,vx+vy);
     681    21149620 :   return gerepileupto(av, z);
     682             : }
     683             : GEN
     684    55207953 : ZX_mul(GEN x, GEN y)
     685             : {
     686             :   GEN z;
     687    55207953 :   if (x == y) return ZX_sqr(x);
     688    54482239 :   z = ZX_mulspec(x+2,y+2,lgpol(x),lgpol(y));
     689    54482489 :   z[1] = x[1];
     690    54482489 :   if (!signe(y)) z[1] &= VARNBITS;
     691    54482489 :   return z;
     692             : }
     693             : 
     694             : /* x,y two ZX in the same variable; assume y is monic */
     695             : GEN
     696     8466508 : ZX_rem(GEN x, GEN y)
     697             : {
     698             :   long vx, dx, dy, dz, i, j, sx, lr;
     699             :   pari_sp av0, av;
     700             :   GEN z,p1,rem;
     701             : 
     702     8466508 :   vx = varn(x);
     703     8466508 :   dy = degpol(y);
     704     8466443 :   dx = degpol(x);
     705     8466360 :   if (dx < dy) return ZX_copy(x);
     706     3209001 :   if (!dy) return pol_0(vx); /* y is constant */
     707     3208966 :   av0 = avma; dz = dx-dy;
     708     3208966 :   z=cgetg(dz+3,t_POL); z[1] = x[1];
     709     3208946 :   x += 2; y += 2; z += 2;
     710             : 
     711     3208946 :   p1 = gel(x,dx);
     712     3208946 :   gel(z,dz) = icopy(p1);
     713    15672373 :   for (i=dx-1; i>=dy; i--)
     714             :   {
     715    12463593 :     av=avma; p1=gel(x,i);
     716   129210056 :     for (j=i-dy+1; j<=i && j<=dz; j++)
     717   116760337 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     718    12449719 :     gel(z,i-dy) = avma == av? icopy(p1): gerepileuptoint(av, p1);
     719             :   }
     720     3208780 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     721     4660355 :   for (sx=0; ; i--)
     722             :   {
     723     6107344 :     p1 = gel(x,i);
     724    31992182 :     for (j=0; j<=i && j<=dz; j++)
     725    27336769 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     726     4655413 :     if (signe(p1)) { sx = 1; break; }
     727     1654073 :     if (!i) break;
     728     1446989 :     set_avma(av);
     729             :   }
     730     3208424 :   lr=i+3; rem -= lr;
     731     3208424 :   rem[0] = evaltyp(t_POL) | evallg(lr);
     732     3208374 :   rem[1] = z[-1];
     733     3208374 :   p1 = gerepileuptoint((pari_sp)rem, p1);
     734     3210126 :   rem += 2; gel(rem,i) = p1;
     735    18533730 :   for (i--; i>=0; i--)
     736             :   {
     737    15324906 :     av=avma; p1 = gel(x,i);
     738   147036502 :     for (j=0; j<=i && j<=dz; j++)
     739   131745726 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     740    15290776 :     gel(rem,i) = avma == av? icopy(p1): gerepileuptoint(av, p1);
     741             :   }
     742     3208824 :   rem -= 2;
     743     3208824 :   if (!sx) (void)ZX_renormalize(rem, lr);
     744     3208824 :   return gerepileupto(av0,rem);
     745             : }
     746             : 
     747             : /* return x(1) */
     748             : GEN
     749        4718 : ZX_eval1(GEN x)
     750             : {
     751        4718 :   pari_sp av = avma;
     752        4718 :   long i = lg(x)-1;
     753             :   GEN s;
     754        4718 :   if (i < 2) return gen_0;
     755        4193 :   s = gel(x,i); i--;
     756        4193 :   if (i == 1) return icopy(s);
     757       34608 :   for ( ; i>=2; i--)
     758             :   {
     759       31423 :     GEN c = gel(x,i);
     760       31423 :     if (signe(c)) s = addii(s, c);
     761             :   }
     762        3185 :   return gerepileuptoint(av,s);
     763             : }
     764             : 
     765             : /* reduce T mod X^n - 1. Shallow function */
     766             : GEN
     767     1481507 : ZX_mod_Xnm1(GEN T, ulong n)
     768             : {
     769     1481507 :   long i, j, L = lg(T), l = n+2;
     770             :   GEN S;
     771     1481507 :   if (L <= l) return T;
     772     1315131 :   S = cgetg(l, t_POL);
     773     1318842 :   S[1] = T[1];
     774     1318842 :   for (i = 2; i < l; i++) gel(S,i) = gel(T,i);
     775     5990297 :   for (j = 2; i < L; i++) {
     776     4677143 :     gel(S,j) = addii(gel(S,j), gel(T,i));
     777     4671455 :     if (++j == l) j = 2;
     778             :   }
     779     1313154 :   return normalizepol_lg(S, l);
     780             : }
     781             : 
     782             : /*******************************************************************/
     783             : /*                                                                 */
     784             : /*                                ZXV                              */
     785             : /*                                                                 */
     786             : /*******************************************************************/
     787             : 
     788             : int
     789          35 : ZXV_equal(GEN V, GEN W)
     790             : {
     791          35 :   long l = lg(V);
     792          35 :   if (l!=lg(W)) return 0;
     793          70 :   while (--l > 0)
     794          35 :     if (!ZX_equal(gel(V,l), gel(W,l))) return 0;
     795           0 :   return 1;
     796             : }
     797             : 
     798             : GEN
     799        7476 : ZXV_Z_mul(GEN x, GEN y)
     800        7476 : { pari_APPLY_same(ZX_Z_mul(gel(x,i), y)) }
     801             : 
     802             : GEN
     803           0 : ZXV_remi2n(GEN x, long N)
     804           0 : { pari_APPLY_same(ZX_remi2n(gel(x,i), N)) }
     805             : 
     806             : GEN
     807       82873 : ZXV_dotproduct(GEN x, GEN y)
     808             : {
     809       82873 :   pari_sp av = avma;
     810       82873 :   long i, lx = lg(x);
     811             :   GEN c;
     812       82873 :   if (lx == 1) return pol_0(varn(x));
     813       82873 :   c = ZX_mul(gel(x,1), gel(y,1));
     814      391629 :   for (i = 2; i < lx; i++)
     815             :   {
     816      308756 :     GEN t = ZX_mul(gel(x,i), gel(y,i));
     817      308756 :     if (signe(t)) c = ZX_add(c, t);
     818             :   }
     819       82873 :   return gerepileupto(av, c);
     820             : }
     821             : 
     822             : /*******************************************************************/
     823             : /*                                                                 */
     824             : /*                                ZXQM                             */
     825             : /*                                                                 */
     826             : /*******************************************************************/
     827             : 
     828             : GEN
     829     2089644 : ZXn_mul(GEN x, GEN y, long n)
     830     2089644 : { return RgXn_red_shallow(ZX_mul(x, y), n); }
     831             : 
     832             : GEN
     833        1386 : ZXn_sqr(GEN x, long n)
     834        1386 : { return RgXn_red_shallow(ZX_sqr(x), n); }
     835             : 
     836             : /*******************************************************************/
     837             : /*                                                                 */
     838             : /*                                ZXQM                             */
     839             : /*                                                                 */
     840             : /*******************************************************************/
     841             : 
     842             : static long
     843     5058119 : ZX_expi(GEN x)
     844             : {
     845     5058119 :   if (signe(x)==0) return 0;
     846     2329816 :   if (typ(x)==t_INT) return expi(x);
     847     1683891 :   return ZX_expispec(x+2, lgpol(x));
     848             : }
     849             : 
     850             : static long
     851      773753 : ZXC_expi(GEN x)
     852             : {
     853      773753 :   long i, l = lg(x), m=0;
     854     5831872 :   for(i = 1; i < l; i++)
     855             :   {
     856     5058119 :     long e = ZX_expi(gel(x,i));
     857     5058119 :     if (e > m) m = e;
     858             :   }
     859      773753 :   return m;
     860             : }
     861             : 
     862             : static long
     863      142398 : ZXM_expi(GEN x)
     864             : {
     865      142398 :   long i, l = lg(x), m=0;
     866      916151 :   for(i = 1; i < l; i++)
     867             :   {
     868      773753 :     long e = ZXC_expi(gel(x,i));
     869      773753 :     if (e > m) m = e;
     870             :   }
     871      142398 :   return m;
     872             : }
     873             : 
     874             : static GEN
     875     5058119 : ZX_eval2BIL(GEN x, long k)
     876             : {
     877     5058119 :   if (signe(x)==0) return gen_0;
     878     2329816 :   if (typ(x)==t_INT) return x;
     879     1683891 :   return ZX_eval2BILspec(x+2, k, lgpol(x));
     880             : }
     881             : 
     882             : /*Eval x in 2^(k*BIL) in linear time*/
     883             : static GEN
     884      773753 : ZXC_eval2BIL(GEN x, long k)
     885             : {
     886      773753 :   long i, lx = lg(x);
     887      773753 :   GEN A = cgetg(lx, t_COL);
     888      773753 :   for (i=1; i<lx; i++) gel(A,i) = ZX_eval2BIL(gel(x,i), k);
     889      773753 :   return A;
     890             : }
     891             : 
     892             : static GEN
     893      142398 : ZXM_eval2BIL(GEN x, long k)
     894             : {
     895      142398 :   long i, lx = lg(x);
     896      142398 :   GEN A = cgetg(lx, t_MAT);
     897      142398 :   for (i=1; i<lx; i++) gel(A,i) = ZXC_eval2BIL(gel(x,i), k);
     898      142398 :   return A;
     899             : }
     900             : 
     901             : static GEN
     902      666597 : Z_mod2BIL_ZXQ(GEN x, long bs, GEN T)
     903             : {
     904      666597 :   pari_sp av = avma;
     905      666597 :   long v = varn(T), d = 2*(degpol(T)-1);
     906      666597 :   GEN z = Z_mod2BIL_ZX(x, bs, d, 0);
     907      666597 :   setvarn(z, v);
     908      666597 :   return gerepileupto(av, ZX_rem(z, T));
     909             : }
     910             : 
     911             : static GEN
     912       28437 : ZC_mod2BIL_ZXQC(GEN x, long bs, GEN T)
     913             : {
     914       28437 :   long i, lx = lg(x);
     915       28437 :   GEN A = cgetg(lx, t_COL);
     916       28437 :   for (i=1; i<lx; i++) gel(A,i) = Z_mod2BIL_ZXQ(gel(x,i), bs, T);
     917       28437 :   return A;
     918             : }
     919             : 
     920             : static GEN
     921        8465 : ZM_mod2BIL_ZXQM(GEN x, long bs, GEN T)
     922             : {
     923        8465 :   long i, lx = lg(x);
     924        8465 :   GEN A = cgetg(lx, t_MAT);
     925        8465 :   for (i=1; i<lx; i++) gel(A,i) = ZC_mod2BIL_ZXQC(gel(x,i), bs, T);
     926        8465 :   return A;
     927             : }
     928             : 
     929             : GEN
     930        8325 : ZXQM_mul(GEN x, GEN y, GEN T)
     931             : {
     932        8325 :   long d = degpol(T);
     933             :   GEN z;
     934        8325 :   pari_sp av = avma;
     935        8325 :   if (d == 0)
     936           0 :     z = ZM_mul(simplify_shallow(x),simplify_shallow(y));
     937             :   else
     938             :   {
     939        8325 :     long ex = ZXM_expi(x), ey = ZXM_expi(y), d= degpol(T), n = lg(x)-1;
     940        8325 :     long e = ex + ey + expu(d) + expu(n) + 4;
     941        8325 :     long N = divsBIL(e)+1;
     942        8325 :     z = ZM_mul(ZXM_eval2BIL(x,N), ZXM_eval2BIL(y,N));
     943        8325 :     z = ZM_mod2BIL_ZXQM(z, N, T);
     944             :   }
     945        8325 :   return gerepileupto(av, z);
     946             : }
     947             : 
     948             : GEN
     949         140 : ZXQM_sqr(GEN x, GEN T)
     950             : {
     951         140 :   long d = degpol(T);
     952             :   GEN z;
     953         140 :   pari_sp av = avma;
     954         140 :   if (d == 0)
     955           0 :     z = ZM_sqr(simplify_shallow(x));
     956             :   else
     957             :   {
     958         140 :     long ex = ZXM_expi(x), d = degpol(T), n = lg(x)-1;
     959         140 :     long e = 2*ex + expu(d) + expu(n) + 4;
     960         140 :     long N = divsBIL(e)+1;
     961         140 :     z = ZM_sqr(ZXM_eval2BIL(x,N));
     962         140 :     z = ZM_mod2BIL_ZXQM(z, N, T);
     963             :   }
     964         140 :   return gerepileupto(av, z);
     965             : }
     966             : 
     967             : GEN
     968        4571 : QXQM_mul(GEN x, GEN y, GEN T)
     969             : {
     970        4571 :   GEN dx, nx = Q_primitive_part(x, &dx);
     971        4571 :   GEN dy, ny = Q_primitive_part(y, &dy);
     972        4571 :   GEN z = ZXQM_mul(nx, ny, T);
     973        4571 :   if (dx || dy)
     974             :   {
     975        4571 :     GEN d = dx ? dy ? gmul(dx, dy): dx : dy;
     976        4571 :     if (!gequal1(d)) z = RgM_Rg_mul(z, d);
     977             :   }
     978        4571 :   return z;
     979             : }
     980             : 
     981             : GEN
     982           7 : QXQM_sqr(GEN x, GEN T)
     983             : {
     984           7 :   GEN dx, nx = Q_primitive_part(x, &dx);
     985           7 :   GEN z = ZXQM_sqr(nx, T);
     986           7 :   if (dx) z = RgM_Rg_mul(z, gsqr(dx));
     987           7 :   return z;
     988             : }
     989             : 
     990             : static GEN
     991     1004988 : Z_mod2BIL_Fq(GEN x, long bs, GEN T, GEN p)
     992             : {
     993     1004988 :   pari_sp av = avma;
     994     1004988 :   long v = get_FpX_var(T), d = 2*(get_FpX_degree(T)-1);
     995     1004988 :   GEN z = Z_mod2BIL_ZX(x, bs, d, 0);
     996     1004988 :   setvarn(z, v);
     997     1004988 :   return gerepileupto(av, FpX_rem(z, T, p));
     998             : }
     999             : 
    1000             : static GEN
    1001      240757 : ZC_mod2BIL_FqC(GEN x, long bs, GEN T, GEN p)
    1002             : {
    1003      240757 :   long i, lx = lg(x);
    1004      240757 :   GEN A = cgetg(lx, t_COL);
    1005      240757 :   for (i=1; i<lx; i++) gel(A,i) = Z_mod2BIL_Fq(gel(x,i), bs, T, p);
    1006      240757 :   return A;
    1007             : }
    1008             : 
    1009             : static GEN
    1010       62804 : ZM_mod2BIL_FqM(GEN x, long bs, GEN T, GEN p)
    1011             : {
    1012       62804 :   long i, lx = lg(x);
    1013       62804 :   GEN A = cgetg(lx, t_MAT);
    1014       62804 :   for (i=1; i<lx; i++) gel(A,i) = ZC_mod2BIL_FqC(gel(x,i), bs, T, p);
    1015       62804 :   return A;
    1016             : }
    1017             : 
    1018             : GEN
    1019       62804 : FqM_mul_Kronecker(GEN x, GEN y, GEN T, GEN p)
    1020             : {
    1021       62804 :   pari_sp av = avma;
    1022       62804 :   long ex = ZXM_expi(x), ey = ZXM_expi(y), d= degpol(T), n = lg(x)-1;
    1023       62804 :   long e = ex + ey + expu(d) + expu(n) + 4;
    1024       62804 :   long N = divsBIL(e)+1;
    1025       62804 :   GEN  z = ZM_mul(ZXM_eval2BIL(x,N), ZXM_eval2BIL(y,N));
    1026       62804 :   return gerepileupto(av, ZM_mod2BIL_FqM(z, N, T, p));
    1027             : }
    1028             : 
    1029             : /*******************************************************************/
    1030             : /*                                                                 */
    1031             : /*                                ZXX                              */
    1032             : /*                                                                 */
    1033             : /*******************************************************************/
    1034             : 
    1035             : void
    1036         826 : RgX_check_ZXX(GEN x, const char *s)
    1037             : {
    1038         826 :   long k = lg(x)-1;
    1039        8946 :   for ( ; k>1; k--) {
    1040        8120 :     GEN t = gel(x,k);
    1041        8120 :     switch(typ(t)) {
    1042        7329 :       case t_INT: break;
    1043         791 :       case t_POL: if (RgX_is_ZX(t)) break;
    1044             :       /* fall through */
    1045           0 :       default: pari_err_TYPE(stack_strcat(s, " not in Z[X,Y]"),x);
    1046             :     }
    1047             :   }
    1048         826 : }
    1049             : 
    1050             : /*Renormalize (in place) polynomial with t_INT or ZX coefficients.*/
    1051             : GEN
    1052   136324792 : ZXX_renormalize(GEN x, long lx)
    1053             : {
    1054             :   long i;
    1055   174785885 :   for (i = lx-1; i>1; i--)
    1056   164954881 :     if (signe(gel(x,i))) break;
    1057   136324792 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + (i+1)));
    1058   136325518 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    1059             : }
    1060             : 
    1061             : GEN
    1062       20629 : ZXX_evalx0(GEN y)
    1063             : {
    1064       20629 :   long i, l = lg(y);
    1065       20629 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1066      400260 :   for(i=2; i<l; i++)
    1067             :   {
    1068      379631 :     GEN yi = gel(y,i);
    1069      379631 :     gel(z,i) = typ(yi)==t_INT? yi: constant_coeff(yi);
    1070             :   }
    1071       20629 :   return ZX_renormalize(z,l);
    1072             : }
    1073             : 
    1074             : long
    1075        2289 : ZXX_max_lg(GEN x)
    1076             : {
    1077        2289 :   long i, prec = 0, lx = lg(x);
    1078       13384 :   for (i=2; i<lx; i++)
    1079             :   {
    1080       11095 :     GEN p = gel(x,i);
    1081       11095 :     long l = (typ(p) == t_INT)? lgefint(p): ZX_max_lg(p);
    1082       11095 :     if (l > prec) prec = l;
    1083             :   }
    1084        2289 :   return prec;
    1085             : }
    1086             : 
    1087             : GEN
    1088        3367 : ZXX_Z_mul(GEN y, GEN x)
    1089             : {
    1090        3367 :   long i, l = lg(y);
    1091        3367 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1092      206528 :   for(i=2; i<l; i++)
    1093      203161 :     if(typ(gel(y,i))==t_INT)
    1094           0 :       gel(z,i) = mulii(gel(y,i),x);
    1095             :     else
    1096      203161 :       gel(z,i) = ZX_Z_mul(gel(y,i),x);
    1097        3367 :   return z;
    1098             : }
    1099             : 
    1100             : GEN
    1101          56 : ZXX_Z_add_shallow(GEN x, GEN y)
    1102             : {
    1103          56 :   long i, l = lg(x);
    1104             :   GEN z, a;
    1105          56 :   if (signe(x)==0) return scalarpol(y,varn(x));
    1106          56 :   z = cgetg(l,t_POL); z[1] = x[1];
    1107          56 :   a = gel(x,2);
    1108          56 :   gel(z, 2) = typ(a)==t_INT? addii(a,y): ZX_Z_add(a,y);
    1109         280 :   for(i=3; i<l; i++)
    1110         224 :     gel(z,i) = gel(x,i);
    1111          56 :   return z;
    1112             : }
    1113             : 
    1114             : GEN
    1115       55363 : ZXX_Z_divexact(GEN y, GEN x)
    1116             : {
    1117       55363 :   long i, l = lg(y);
    1118       55363 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1119      465073 :   for(i=2; i<l; i++)
    1120      409710 :     if(typ(gel(y,i))==t_INT)
    1121        3031 :       gel(z,i) = diviiexact(gel(y,i),x);
    1122             :     else
    1123      406679 :       gel(z,i) = ZX_Z_divexact(gel(y,i),x);
    1124       55363 :   return z;
    1125             : }
    1126             : 
    1127             : /* Kronecker substitution, ZXX -> ZX:
    1128             :  * P(X,Y) = sum_{0<=i<lP} P_i(X) * Y^i, where deg P_i < n.
    1129             :  * Returns P(X,X^(2n-1)) */
    1130             : GEN
    1131     2215737 : ZXX_to_Kronecker_spec(GEN P, long lP, long n)
    1132             : {
    1133     2215737 :   long i, k, N = (n<<1) + 1;
    1134             :   GEN y;
    1135     2215737 :   if (!lP) return pol_0(0);
    1136     2202269 :   y = cgetg((N-2)*lP + 2, t_POL) + 2;
    1137    18810602 :   for (k=i=0; i<lP; i++)
    1138             :   {
    1139             :     long j;
    1140    18810602 :     GEN c = gel(P,i);
    1141    18810602 :     if (typ(c)!=t_POL)
    1142             :     {
    1143     1326831 :       gel(y,k++) = c;
    1144     1326831 :       j = 3;
    1145             :     }
    1146             :     else
    1147             :     {
    1148    17483771 :       long l = lg(c);
    1149    17483771 :       if (l-3 >= n)
    1150           0 :         pari_err_BUG("ZXX_to_Kronecker, P is not reduced mod Q");
    1151    17483771 :       for (j=2; j < l; j++) gel(y,k++) = gel(c,j);
    1152             :     }
    1153    18810602 :     if (i == lP-1) break;
    1154    16608333 :     for (   ; j < N; j++) gel(y,k++) = gen_0;
    1155             :   }
    1156     2202269 :   y-=2; setlg(y, k+2); y[1] = evalsigne(1); return y;
    1157             : }
    1158             : 
    1159             : GEN
    1160      994377 : ZXX_to_Kronecker(GEN P, long n)
    1161             : {
    1162      994377 :   GEN z = ZXX_to_Kronecker_spec(P+2, lgpol(P), n);
    1163      994377 :   setvarn(z,varn(P)); return z;
    1164             : }
    1165             : 
    1166             : GEN
    1167           0 : ZXQX_sqr(GEN x, GEN T)
    1168             : {
    1169           0 :   pari_sp av = avma;
    1170           0 :   long n = degpol(T);
    1171           0 :   GEN z = ZXX_sqr_Kronecker(x, n);
    1172           0 :   z = Kronecker_to_ZXX(z, n, varn(T));
    1173           0 :   return gerepileupto(av, z);
    1174             : }
    1175             : 
    1176             : GEN
    1177           0 : ZXQX_mul(GEN x, GEN y, GEN T)
    1178             : {
    1179           0 :   pari_sp av = avma;
    1180           0 :   long n = degpol(T);
    1181           0 :   GEN z = ZXX_mul_Kronecker(x, y, n);
    1182           0 :   z = Kronecker_to_ZXX(z, n, varn(T));
    1183           0 :   return gerepileupto(av, z);
    1184             : }
    1185             : 
    1186             : GEN
    1187     2802218 : QX_mul(GEN x, GEN y)
    1188             : {
    1189     2802218 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1190     2802218 :   GEN dy, ny = Q_primitive_part(y, &dy);
    1191     2802218 :   GEN z = ZX_mul(nx, ny);
    1192     2802218 :   if (dx || dy)
    1193             :   {
    1194     2705593 :     GEN d = dx ? dy ? gmul(dx, dy): dx : dy;
    1195     2705593 :     return ZX_Q_mul(z, d);
    1196             :   } else
    1197       96625 :     return z;
    1198             : }
    1199             : 
    1200             : GEN
    1201       23724 : QX_sqr(GEN x)
    1202             : {
    1203       23724 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1204       23724 :   GEN z = ZX_sqr(nx);
    1205       23724 :   if (dx)
    1206       13693 :     return ZX_Q_mul(z, gsqr(dx));
    1207             :   else
    1208       10031 :     return z;
    1209             : }
    1210             : 
    1211             : GEN
    1212     1610457 : QX_ZX_rem(GEN x, GEN y)
    1213             : {
    1214     1610457 :   pari_sp av = avma;
    1215     1610457 :   GEN d, nx = Q_primitive_part(x, &d);
    1216     1610457 :   GEN r = ZX_rem(nx, y);
    1217     1610457 :   if (d) r = ZX_Q_mul(r, d);
    1218     1610457 :   return gerepileupto(av, r);
    1219             : }

Generated by: LCOV version 1.13