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 25819-e703fe1174) Lines: 660 741 89.1 %
Date: 2020-09-18 06:10:04 Functions: 91 97 93.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      230262 : RgX_check_QX(GEN x, const char *s)
      24      230262 : { if (!RgX_is_QX(x)) pari_err_TYPE(stack_strcat(s," [not in Q[X]]"), x); }
      25             : void
      26      700144 : RgX_check_ZX(GEN x, const char *s)
      27      700144 : { if (!RgX_is_ZX(x)) pari_err_TYPE(stack_strcat(s," [not in Z[X]]"), x); }
      28             : long
      29       18826 : ZX_max_lg(GEN x)
      30             : {
      31       18826 :   long i, prec = 0, lx = lg(x);
      32             : 
      33      109475 :   for (i=2; i<lx; i++) { long l = lgefint(gel(x,i)); if (l > prec) prec = l; }
      34       18826 :   return prec;
      35             : }
      36             : 
      37             : GEN
      38    14939359 : ZX_add(GEN x, GEN y)
      39             : {
      40             :   long lx,ly,i;
      41             :   GEN z;
      42    14939359 :   lx = lg(x); ly = lg(y); if (lx < ly) swapspec(x,y, lx,ly);
      43    14939359 :   z = cgetg(lx,t_POL); z[1] = x[1];
      44   110496623 :   for (i=2; i<ly; i++) gel(z,i) = addii(gel(x,i),gel(y,i));
      45    43223241 :   for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
      46    14931990 :   if (lx == ly) z = ZX_renormalize(z, lx);
      47    14932006 :   if (!lgpol(z)) { set_avma((pari_sp)(z + lx)); return pol_0(varn(x)); }
      48    13694859 :   return z;
      49             : }
      50             : 
      51             : GEN
      52     7550729 : ZX_sub(GEN x,GEN y)
      53             : {
      54     7550729 :   long i, lx = lg(x), ly = lg(y);
      55             :   GEN z;
      56     7550729 :   if (lx >= ly)
      57             :   {
      58     7464804 :     z = cgetg(lx,t_POL); z[1] = x[1];
      59    32718147 :     for (i=2; i<ly; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
      60     7464636 :     if (lx == ly)
      61             :     {
      62     6055520 :       z = ZX_renormalize(z, lx);
      63     6055522 :       if (!lgpol(z)) { set_avma((pari_sp)(z + lx)); z = pol_0(varn(x)); }
      64             :     }
      65             :     else
      66     4901525 :       for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
      67             :   }
      68             :   else
      69             :   {
      70       85925 :     z = cgetg(ly,t_POL); z[1] = y[1];
      71      289588 :     for (i=2; i<lx; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
      72      245391 :     for (   ; i<ly; i++) gel(z,i) = negi(gel(y,i));
      73             :   }
      74     7550563 :   return z;
      75             : }
      76             : 
      77             : GEN
      78      330250 : ZX_neg(GEN x)
      79             : {
      80      330250 :   long i, l = lg(x);
      81      330250 :   GEN y = cgetg(l,t_POL);
      82     1142491 :   y[1] = x[1]; for(i=2; i<l; i++) gel(y,i) = negi(gel(x,i));
      83      330250 :   return y;
      84             : }
      85             : GEN
      86     5379952 : ZX_copy(GEN x)
      87             : {
      88     5379952 :   long i, l = lg(x);
      89     5379952 :   GEN y = cgetg(l, t_POL);
      90     5379959 :   y[1] = x[1];
      91    18476532 :   for (i=2; i<l; i++)
      92             :   {
      93    13096578 :     GEN c = gel(x,i);
      94    13096578 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
      95             :   }
      96     5379954 :   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       22013 : scalar_ZX_shallow(GEN x, long v)
     111             : {
     112             :   GEN z;
     113       22013 :   if (!signe(x)) return pol_0(v);
     114       18987 :   z = cgetg(3, t_POL);
     115       18987 :   z[1] = evalsigne(1) | evalvarn(v);
     116       18987 :   gel(z,2) = x; return z;
     117             : }
     118             : 
     119             : GEN
     120       88206 : ZX_Z_add(GEN y, GEN x)
     121             : {
     122             :   long lz, i;
     123       88206 :   GEN z = cgetg_copy(y, &lz);
     124       88206 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX(x,varn(y)); }
     125       77538 :   z[1] = y[1];
     126       77538 :   gel(z,2) = addii(gel(y,2),x);
     127     1987615 :   for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
     128       78768 :   if (lz==3) z = ZX_renormalize(z,lz);
     129       77539 :   return z;
     130             : }
     131             : GEN
     132       12194 : ZX_Z_add_shallow(GEN y, GEN x)
     133             : {
     134             :   long lz, i;
     135       12194 :   GEN z = cgetg_copy(y, &lz);
     136       12194 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX_shallow(x,varn(y)); }
     137       11984 :   z[1] = y[1];
     138       11984 :   gel(z,2) = addii(gel(y,2),x);
     139      189315 :   for(i=3; i<lz; i++) gel(z,i) = gel(y,i);
     140       11984 :   if (lz==3) z = ZX_renormalize(z,lz);
     141       11984 :   return z;
     142             : }
     143             : 
     144             : GEN
     145       62197 : ZX_Z_sub(GEN y, GEN x)
     146             : {
     147             :   long lz, i;
     148       62197 :   GEN z = cgetg_copy(y, &lz);
     149       62197 :   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       62197 :   z[1] = y[1];
     159       62197 :   gel(z,2) = subii(gel(y,2),x);
     160      403497 :   for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
     161       62197 :   if (lz==3) z = ZX_renormalize(z,lz);
     162       62197 :   return z;
     163             : }
     164             : 
     165             : GEN
     166      546337 : Z_ZX_sub(GEN x, GEN y)
     167             : {
     168             :   long lz, i;
     169      546337 :   GEN z = cgetg_copy(y, &lz);
     170      546338 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX(x,varn(y)); }
     171      546338 :   z[1] = y[1];
     172      546338 :   gel(z,2) = subii(x, gel(y,2));
     173     3956323 :   for(i=3; i<lz; i++) gel(z,i) = negi(gel(y,i));
     174      546340 :   if (lz==3) z = ZX_renormalize(z,lz);
     175      546338 :   return z;
     176             : }
     177             : 
     178             : GEN
     179     2084982 : ZX_Z_divexact(GEN y,GEN x)
     180             : {
     181     2084982 :   long i, l = lg(y);
     182     2084982 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
     183    13552008 :   for(i=2; i<l; i++) gel(z,i) = diviiexact(gel(y,i),x);
     184     2084225 :   return z;
     185             : }
     186             : 
     187             : GEN
     188      977753 : ZX_divuexact(GEN y, ulong x)
     189             : {
     190      977753 :   long i, l = lg(y);
     191      977753 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
     192     9684031 :   for(i=2; i<l; i++) gel(z,i) = diviuexact(gel(y,i),x);
     193      977753 :   return z;
     194             : }
     195             : 
     196             : GEN
     197           0 : zx_z_divexact(GEN y, long x)
     198             : {
     199           0 :   long i, l = lg(y);
     200           0 :   GEN z = cgetg(l,t_VECSMALL); z[1] = y[1];
     201           0 :   for (i=2; i<l; i++) z[i] = y[i]/x;
     202           0 :   return z;
     203             : }
     204             : 
     205             : GEN
     206     9728971 : ZX_Z_mul(GEN y,GEN x)
     207             : {
     208             :   GEN z;
     209             :   long i, l;
     210     9728971 :   if (!signe(x)) return pol_0(varn(y));
     211     6940959 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     212    62896090 :   for(i=2; i<l; i++) gel(z,i) = mulii(gel(y,i),x);
     213     6939263 :   return z;
     214             : }
     215             : 
     216             : GEN
     217      120491 : ZX_mulu(GEN y, ulong x)
     218             : {
     219             :   GEN z;
     220             :   long i, l;
     221      120491 :   if (!x) return pol_0(varn(y));
     222      120491 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     223      705250 :   for(i=2; i<l; i++) gel(z,i) = mului(x,gel(y,i));
     224      120491 :   return z;
     225             : }
     226             : 
     227             : GEN
     228     1641496 : ZX_shifti(GEN y, long n)
     229             : {
     230             :   GEN z;
     231             :   long i, l;
     232     1641496 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     233    10265456 :   for(i=2; i<l; i++) gel(z,i) = shifti(gel(y,i),n);
     234     1618270 :   return ZX_renormalize(z,l);
     235             : }
     236             : 
     237             : GEN
     238      109203 : ZX_remi2n(GEN y, long n)
     239             : {
     240             :   GEN z;
     241             :   long i, l;
     242      109203 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     243     4917793 :   for(i=2; i<l; i++) gel(z,i) = remi2n(gel(y,i),n);
     244      103402 :   return ZX_renormalize(z,l);
     245             : }
     246             : 
     247             : GEN
     248       47894 : ZXT_remi2n(GEN z, long n)
     249             : {
     250       47894 :   if (typ(z) == t_POL)
     251       41001 :     return ZX_remi2n(z, n);
     252             :   else
     253             :   {
     254        6893 :     long i,l = lg(z);
     255        6893 :     GEN x = cgetg(l, t_VEC);
     256       20694 :     for (i=1; i<l; i++) gel(x,i) = ZXT_remi2n(gel(z,i), n);
     257        6893 :     return x;
     258             :   }
     259             : }
     260             : 
     261             : GEN
     262         294 : zx_to_ZX(GEN z)
     263             : {
     264         294 :   long i, l = lg(z);
     265         294 :   GEN x = cgetg(l,t_POL);
     266        1764 :   for (i=2; i<l; i++) gel(x,i) = stoi(z[i]);
     267         294 :   x[1] = evalsigne(l-2!=0)| z[1]; return x;
     268             : }
     269             : 
     270             : GEN
     271     2444247 : ZX_deriv(GEN x)
     272             : {
     273     2444247 :   long i,lx = lg(x)-1;
     274             :   GEN y;
     275             : 
     276     2444247 :   if (lx<3) return pol_0(varn(x));
     277     2438197 :   y = cgetg(lx,t_POL);
     278    18351942 :   for (i=2; i<lx ; i++) gel(y,i) = mului(i-1,gel(x,i+1));
     279     2438188 :   y[1] = x[1]; return y;
     280             : }
     281             : 
     282             : int
     283     1638517 : ZX_equal(GEN V, GEN W)
     284             : {
     285     1638517 :   long i, l = lg(V);
     286     1638517 :   if (lg(W) != l) return 0;
     287     5287574 :   for (i = 2; i < l; i++)
     288     4013351 :     if (!equalii(gel(V,i), gel(W,i))) return 0;
     289     1274223 :   return 1;
     290             : }
     291             : 
     292             : static long
     293   127150993 : ZX_valspec(GEN x, long nx)
     294             : {
     295             :   long vx;
     296   190285763 :   for (vx = 0; vx<nx ; vx++)
     297   190285824 :     if (signe(gel(x,vx))) break;
     298   127150993 :   return vx;
     299             : }
     300             : 
     301             : long
     302       37362 : ZX_val(GEN x)
     303             : {
     304             :   long vx;
     305       37362 :   if (!signe(x)) return LONG_MAX;
     306       37362 :   for (vx = 0;; vx++)
     307       38930 :     if (signe(gel(x,2+vx))) break;
     308       37362 :   return vx;
     309             : }
     310             : long
     311    21307816 : ZX_valrem(GEN x, GEN *Z)
     312             : {
     313             :   long vx;
     314    21307816 :   if (!signe(x)) { *Z = pol_0(varn(x)); return LONG_MAX; }
     315    21307816 :   for (vx = 0;; vx++)
     316    41250990 :     if (signe(gel(x,2+vx))) break;
     317    21307816 :   *Z = RgX_shift_shallow(x, -vx);
     318    21307816 :   return vx;
     319             : }
     320             : 
     321             : GEN
     322          21 : ZX_div_by_X_1(GEN a, GEN *r)
     323             : {
     324          21 :   long l = lg(a), i;
     325          21 :   GEN a0, z0, z = cgetg(l-1, t_POL);
     326          21 :   z[1] = a[1];
     327          21 :   a0 = a + l-1;
     328          21 :   z0 = z + l-2; *z0 = *a0--;
     329        4732 :   for (i=l-3; i>1; i--) /* z[i] = a[i+1] + z[i+1] */
     330             :   {
     331        4711 :     GEN t = addii(gel(a0--,0), gel(z0--,0));
     332        4711 :     gel(z0,0) = t;
     333             :   }
     334          21 :   if (r) *r = addii(gel(a0,0), gel(z0,0));
     335          21 :   return z;
     336             : }
     337             : 
     338             : /* return P(X + c) using destructive Horner, optimize for c = 1,-1 */
     339             : static GEN
     340      407651 : ZX_translate_basecase(GEN P, GEN c)
     341             : {
     342      407651 :   pari_sp av = avma;
     343             :   GEN Q, R;
     344             :   long i, k, n;
     345             : 
     346      407651 :   if (!signe(P) || !signe(c)) return ZX_copy(P);
     347      407630 :   Q = leafcopy(P);
     348      407630 :   R = Q+2; n = degpol(P);
     349      407630 :   if (equali1(c))
     350             :   {
     351     2658018 :     for (i=1; i<=n; i++)
     352             :     {
     353    25373204 :       for (k=n-i; k<n; k++) gel(R,k) = addii(gel(R,k), gel(R,k+1));
     354     2356943 :       if (gc_needed(av,2))
     355             :       {
     356           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate(1), i = %ld/%ld", i,n);
     357           0 :         Q = gerepilecopy(av, Q); R = Q+2;
     358             :       }
     359             :     }
     360             :   }
     361      106555 :   else if (equalim1(c))
     362             :   {
     363           0 :     for (i=1; i<=n; i++)
     364             :     {
     365           0 :       for (k=n-i; k<n; k++) gel(R,k) = subii(gel(R,k), gel(R,k+1));
     366           0 :       if (gc_needed(av,2))
     367             :       {
     368           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate(-1), i = %ld/%ld", i,n);
     369           0 :         Q = gerepilecopy(av, Q); R = Q+2;
     370             :       }
     371             :     }
     372             :   }
     373             :   else
     374             :   {
     375      814114 :     for (i=1; i<=n; i++)
     376             :     {
     377     4728930 :       for (k=n-i; k<n; k++) gel(R,k) = addmulii_inplace(gel(R,k), c, gel(R,k+1));
     378      707559 :       if (gc_needed(av,2))
     379             :       {
     380           0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate, i = %ld/%ld", i,n);
     381           0 :         Q = gerepilecopy(av, Q); R = Q+2;
     382             :       }
     383             :     }
     384             :   }
     385      407630 :   return gerepilecopy(av, Q);
     386             : }
     387             : 
     388             : static GEN
     389           0 : Z_Xpm1_powu(long n, long s, long v)
     390             : {
     391             :   long d, k;
     392             :   GEN C;
     393           0 :   if (!n) return pol_1(v);
     394           0 :   d = (n + 1) >> 1;
     395           0 :   C = cgetg(n+3, t_POL);
     396           0 :   C[1] = evalsigne(1)| evalvarn(v);
     397           0 :   gel(C,2) = gen_1;
     398           0 :   gel(C,3) = utoipos(n);
     399           0 :   for (k=2; k <= d; k++)
     400           0 :     gel(C,k+2) = diviuexact(mului(n-k+1, gel(C,k+1)), k);
     401           0 :   if (s < 0)
     402           0 :     for (k = odd(n)? 0: 1; k <= d; k += 2)
     403           0 :       togglesign_safe(&gel(C,k+2));
     404           0 :   if (s > 0 || !odd(n))
     405           0 :     for (k = d+1; k <= n; k++) gel(C,k+2) = gel(C,n-k+2);
     406             :   else
     407           0 :     for (k = d+1; k <= n; k++) gel(C,k+2) = negi(gel(C,n-k+2));
     408           0 :   return C;
     409             : }
     410             : /* return (x+u)^n */
     411             : static GEN
     412           0 : Z_XpN_powu(GEN u, long n, long v)
     413             : {
     414             :   pari_sp av;
     415             :   long k;
     416             :   GEN B, C, V;
     417           0 :   if (!n) return pol_1(v);
     418           0 :   if (is_pm1(u))
     419           0 :     return Z_Xpm1_powu(n, signe(u), v);
     420           0 :   av = avma;
     421           0 :   V = gpowers(u, n);
     422           0 :   B = vecbinomial(n);
     423           0 :   C = cgetg(n+3, t_POL);
     424           0 :   C[1] = evalsigne(1)| evalvarn(v);
     425           0 :   for (k=1; k <= n+1; k++)
     426           0 :     gel(C,k+1) = mulii(gel(V,n+2-k), gel(B,k));
     427           0 :   return gerepileupto(av, C);
     428             : }
     429             : 
     430             : GEN
     431      407651 : ZX_translate(GEN P, GEN c)
     432             : {
     433      407651 :   pari_sp av = avma;
     434      407651 :   long n = degpol(P);
     435      407651 :   if (n < 220)
     436      407651 :     return ZX_translate_basecase(P, c);
     437             :   else
     438             :   {
     439           0 :     long d = n >> 1;
     440           0 :     GEN Q = ZX_translate(RgX_shift_shallow(P, -d), c);
     441           0 :     GEN R = ZX_translate(RgXn_red_shallow(P, d), c);
     442           0 :     GEN S = Z_XpN_powu(c, d, varn(P));
     443           0 :     return gerepileupto(av, ZX_add(ZX_mul(Q, S), R));
     444             :   }
     445             : }
     446             : 
     447             : /* Return 2^(n degpol(P))  P(x >> n) */
     448             : GEN
     449           0 : ZX_rescale2n(GEN P, long n)
     450             : {
     451           0 :   long i, l = lg(P), ni = n;
     452             :   GEN Q;
     453           0 :   if (l==2) return pol_0(varn(P));
     454           0 :   Q = cgetg(l,t_POL);
     455           0 :   gel(Q,l-1) = icopy(gel(P,l-1));
     456           0 :   for (i=l-2; i>=2; i--)
     457             :   {
     458           0 :     gel(Q,i) = shifti(gel(P,i), ni);
     459           0 :     ni += n;
     460             :   }
     461           0 :   Q[1] = P[1]; return Q;
     462             : }
     463             : 
     464             : /* Return h^deg(P) P(x / h), not memory clean. h integer, P ZX */
     465             : GEN
     466       12366 : ZX_rescale(GEN P, GEN h)
     467             : {
     468       12366 :   long l = lg(P);
     469       12366 :   GEN Q = cgetg(l,t_POL);
     470       12366 :   if (l != 2)
     471             :   {
     472       12366 :     long i = l-1;
     473       12366 :     GEN hi = h;
     474       12366 :     gel(Q,i) = gel(P,i);
     475       12366 :     if (l != 3) { i--; gel(Q,i) = mulii(gel(P,i), h); }
     476       41095 :     for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
     477             :   }
     478       12366 :   Q[1] = P[1]; return Q;
     479             : }
     480             : /* Return h^(deg(P)-1) P(x / h), P!=0, h=lt(P), memory unclean; monic result */
     481             : GEN
     482           0 : ZX_rescale_lt(GEN P)
     483             : {
     484           0 :   long l = lg(P);
     485           0 :   GEN Q = cgetg(l,t_POL);
     486           0 :   gel(Q,l-1) = gen_1;
     487           0 :   if (l != 3)
     488             :   {
     489           0 :     long i = l-1;
     490           0 :     GEN h = gel(P,i), hi = h;
     491           0 :     i--; gel(Q,i) = gel(P,i);
     492           0 :     if (l != 4) { i--; gel(Q,i) = mulii(gel(P,i), h); }
     493           0 :     for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
     494             :   }
     495           0 :   Q[1] = P[1]; return Q;
     496             : }
     497             : 
     498             : /*Eval x in 2^(k*BIL) in linear time*/
     499             : static GEN
     500    51286284 : ZX_eval2BILspec(GEN x, long k, long nx)
     501             : {
     502    51286284 :   pari_sp av = avma;
     503    51286284 :   long i,j, lz = k*nx, ki;
     504    51286284 :   GEN pz = cgetipos(2+lz);
     505    51285792 :   GEN nz = cgetipos(2+lz);
     506  1869348840 :   for(i=0; i < lz; i++)
     507             :   {
     508  1818059777 :     *int_W(pz,i) = 0UL;
     509  1818059777 :     *int_W(nz,i) = 0UL;
     510             :   }
     511   522865359 :   for(i=0, ki=0; i<nx; i++, ki+=k)
     512             :   {
     513   471576296 :     GEN c = gel(x,i);
     514   471576296 :     long lc = lgefint(c)-2;
     515   471576296 :     if (signe(c)==0) continue;
     516   355597708 :     if (signe(c) > 0)
     517   959207576 :       for (j=0; j<lc; j++) *int_W(pz,j+ki) = *int_W(c,j);
     518             :     else
     519   230228590 :       for (j=0; j<lc; j++) *int_W(nz,j+ki) = *int_W(c,j);
     520             :   }
     521    51289063 :   pz = int_normalize(pz,0);
     522    51288475 :   nz = int_normalize(nz,0); return gerepileuptoint(av, subii(pz,nz));
     523             : }
     524             : 
     525             : static long
     526    67485363 : ZX_expispec(GEN x, long nx)
     527             : {
     528    67485363 :   long i, m = 0;
     529   598316193 :   for(i = 0; i < nx; i++)
     530             :   {
     531   530833644 :     long e = expi(gel(x,i));
     532   530830830 :     if (e > m) m = e;
     533             :   }
     534    67482549 :   return m;
     535             : }
     536             : 
     537             : static GEN
     538    29056146 : Z_mod2BIL_ZX(GEN x, long bs, long d, long vx)
     539             : {
     540    29056146 :   long i, offset, lm = lgefint(x)-2, l = d+vx+3, sx = signe(x);
     541    29056146 :   GEN s1 = int2n(bs*BITS_IN_LONG), pol = cgetg(l, t_POL);
     542    29053122 :   int carry = 0;
     543    29053122 :   pol[1] = evalsigne(1);
     544    46331536 :   for (i=0; i<vx; i++) gel(pol,i+2) = gen_0;
     545   513774066 :   for (offset=0; i <= d+vx; i++, offset += bs)
     546             :   {
     547   484771326 :     pari_sp av = avma;
     548   484771326 :     long lz = minss(bs, lm-offset);
     549   485462592 :     GEN z = lz > 0 ?adduispec_offset(carry, x, offset, lz): utoi(carry);
     550   484656431 :     if (lgefint(z) == 3+bs) { carry = 1; z = gen_0;}
     551             :     else
     552             :     {
     553   472931079 :       carry = (lgefint(z) == 2+bs && (HIGHBIT & *int_W(z,bs-1)));
     554   472931079 :       if (carry)
     555    38697065 :         z = gerepileuptoint(av, (sx==-1)? subii(s1,z): subii(z,s1));
     556   434234014 :       else if (sx==-1) togglesign(z);
     557             :     }
     558   484720944 :     gel(pol,i+2) = z;
     559             :   }
     560    29002740 :   return ZX_renormalize(pol,l);
     561             : }
     562             : 
     563             : static GEN
     564     5173962 : ZX_sqrspec_sqri(GEN x, long nx, long ex, long v)
     565             : {
     566     5173962 :   long e = 2*ex + expu(nx) + 3;
     567     5173941 :   long N = divsBIL(e)+1;
     568     5173912 :   GEN  z = sqri(ZX_eval2BILspec(x,N,nx));
     569     5175353 :   return Z_mod2BIL_ZX(z, N, nx*2-2, v);
     570             : }
     571             : 
     572             : static GEN
     573    22211605 : ZX_mulspec_mulii(GEN x, GEN y, long nx, long ny, long ex, long ey, long v)
     574             : {
     575    22211605 :   long e = ex + ey + expu(minss(nx,ny)) + 3;
     576    22211561 :   long N = divsBIL(e)+1;
     577    22211533 :   GEN  z = mulii(ZX_eval2BILspec(x,N,nx), ZX_eval2BILspec(y,N,ny));
     578    22211451 :   return Z_mod2BIL_ZX(z, N, nx+ny-2, v);
     579             : }
     580             : 
     581             : INLINE GEN
     582   102109027 : ZX_sqrspec_basecase_limb(GEN x, long a, long i)
     583             : {
     584   102109027 :   pari_sp av = avma;
     585   102109027 :   GEN s = gen_0;
     586   102109027 :   long j, l = (i+1)>>1;
     587   305317046 :   for (j=a; j<l; j++)
     588             :   {
     589   203928819 :     GEN xj = gel(x,j), xx = gel(x,i-j);
     590   203928819 :     if (signe(xj) && signe(xx))
     591   200302864 :       s = addii(s, mulii(xj, xx));
     592             :   }
     593   101388227 :   s = shifti(s,1);
     594   101979443 :   if ((i&1) == 0)
     595             :   {
     596    59213919 :     GEN t = gel(x, i>>1);
     597    59213919 :     if (signe(t))
     598    59011191 :       s = addii(s, sqri(t));
     599             :   }
     600   101959646 :   return gerepileuptoint(av,s);
     601             : }
     602             : 
     603             : static GEN
     604    16198420 : ZX_sqrspec_basecase(GEN x, long nx, long v)
     605             : {
     606             :   long i, lz, nz;
     607             :   GEN z;
     608             : 
     609    16198420 :   lz = (nx << 1) + 1; nz = lz-2;
     610    16198420 :   lz += v;
     611    16198420 :   z = cgetg(lz,t_POL); z[1] = evalsigne(1); z += 2;
     612    16296795 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
     613    75433826 :   for (i=0; i<nx; i++)
     614    59237649 :     gel(z,i) = ZX_sqrspec_basecase_limb(x, 0, i);
     615    59250514 :   for (  ; i<nz; i++) gel(z,i) = ZX_sqrspec_basecase_limb(x, i-nx+1, i);
     616    16202912 :   z -= v+2; return z;
     617             : }
     618             : 
     619             : static GEN
     620     7053343 : Z_sqrshiftspec_ZX(GEN x, long vx)
     621             : {
     622     7053343 :   long i, nz = 2*vx+1;
     623     7053343 :   GEN z = cgetg(2+nz, t_POL);
     624     7053343 :   z[1] = evalsigne(1);
     625     8533585 :   for(i=2;i<nz+1;i++) gel(z,i) = gen_0;
     626     7053343 :   gel(z,nz+1) = sqri(x);
     627     7053336 :   return z;
     628             : }
     629             : 
     630             : static GEN
     631    27151881 : Z_ZX_mulshiftspec(GEN x, GEN y, long ny, long vz)
     632             : {
     633    27151881 :   long i, nz = vz+ny;
     634    27151881 :   GEN z = cgetg(2+nz, t_POL);
     635    27151881 :   z[1] = evalsigne(1);
     636    72319558 :   for (i=0; i<vz; i++)   gel(z,i+2)    = gen_0;
     637    79370248 :   for (i=0; i<ny; i++) gel(z,i+vz+2) = mulii(x, gel(y,i));
     638    27151816 :   return z;
     639             : }
     640             : 
     641             : GEN
     642    28512470 : ZX_sqrspec(GEN x, long nx)
     643             : {
     644             : #ifdef PARI_KERNEL_GMP
     645    16969628 :   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};
     646    16969628 :   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};
     647             : #else
     648    11542842 :   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};
     649    11542842 :   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};
     650             : #endif
     651    28512470 :   const long nblow = numberof(low);
     652             :   pari_sp av;
     653             :   long ex, vx;
     654             :   GEN z;
     655    28512470 :   if (!nx) return pol_0(0);
     656    28424562 :   vx = ZX_valspec(x,nx); nx-=vx; x+=vx;
     657    28426434 :   if (nx==1) return Z_sqrshiftspec_ZX(gel(x, 0), vx);
     658    21373091 :   av = avma;
     659    21373091 :   ex = ZX_expispec(x,nx);
     660    21372252 :   if (nx-2 < nblow && low[nx-2]<=ex && ex<=high[nx-2])
     661    16198396 :     z = ZX_sqrspec_basecase(x, nx, 2*vx);
     662             :   else
     663     5173856 :     z = ZX_sqrspec_sqri(x, nx, ex, 2*vx);
     664    21370738 :   return gerepileupto(av, z);
     665             : }
     666             : 
     667             : GEN
     668    28512673 : ZX_sqr(GEN x)
     669             : {
     670    28512673 :   GEN z = ZX_sqrspec(x+2, lgpol(x));
     671    28512507 :   z[1] = x[1];
     672    28512507 :   return z;
     673             : }
     674             : 
     675             : GEN
     676    58150171 : ZX_mulspec(GEN x, GEN y, long nx, long ny)
     677             : {
     678             :   pari_sp av;
     679             :   long ex, ey, vx, vy;
     680             :   GEN z;
     681    58150171 :   if (!nx || !ny) return pol_0(0);
     682    49363321 :   vx = ZX_valspec(x,nx); nx-=vx; x += vx;
     683    49363314 :   vy = ZX_valspec(y,ny); ny-=vy; y += vy;
     684    49363407 :   if (nx==1) return Z_ZX_mulshiftspec(gel(x,0), y, ny, vx+vy);
     685    28944572 :   if (ny==1) return Z_ZX_mulshiftspec(gel(y,0), x, nx, vy+vx);
     686    22211526 :   av = avma;
     687    22211526 :   ex = ZX_expispec(x, nx); ey = ZX_expispec(y, ny);
     688    22211513 :   z  = ZX_mulspec_mulii(x,y,nx,ny,ex,ey,vx+vy);
     689    22210831 :   return gerepileupto(av, z);
     690             : }
     691             : GEN
     692    56846652 : ZX_mul(GEN x, GEN y)
     693             : {
     694             :   GEN z;
     695    56846652 :   if (x == y) return ZX_sqr(x);
     696    56121660 :   z = ZX_mulspec(x+2,y+2,lgpol(x),lgpol(y));
     697    56121750 :   z[1] = x[1];
     698    56121750 :   if (!signe(y)) z[1] &= VARNBITS;
     699    56121750 :   return z;
     700             : }
     701             : 
     702             : /* x,y two ZX in the same variable; assume y is monic */
     703             : GEN
     704     8874040 : ZX_rem(GEN x, GEN y)
     705             : {
     706             :   long vx, dx, dy, dz, i, j, sx, lr;
     707             :   pari_sp av0, av;
     708             :   GEN z,p1,rem;
     709             : 
     710     8874040 :   vx = varn(x);
     711     8874040 :   dy = degpol(y);
     712     8874015 :   dx = degpol(x);
     713     8873994 :   if (dx < dy) return ZX_copy(x);
     714     3693877 :   if (!dy) return pol_0(vx); /* y is constant */
     715     3693842 :   av0 = avma; dz = dx-dy;
     716     3693842 :   z=cgetg(dz+3,t_POL); z[1] = x[1];
     717     3693824 :   x += 2; y += 2; z += 2;
     718             : 
     719     3693824 :   p1 = gel(x,dx);
     720     3693824 :   gel(z,dz) = icopy(p1);
     721    22138419 :   for (i=dx-1; i>=dy; i--)
     722             :   {
     723    18444661 :     av=avma; p1=gel(x,i);
     724   193613597 :     for (j=i-dy+1; j<=i && j<=dz; j++)
     725   175173711 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     726    18439886 :     gel(z,i-dy) = avma == av? icopy(p1): gerepileuptoint(av, p1);
     727             :   }
     728     3693758 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     729     3693799 :   for (sx=0; ; i--)
     730             :   {
     731     1552168 :     p1 = gel(x,i);
     732    39640588 :     for (j=0; j<=i && j<=dz; j++)
     733    34394899 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     734     5245689 :     if (signe(p1)) { sx = 1; break; }
     735     1764877 :     if (!i) break;
     736     1552167 :     set_avma(av);
     737             :   }
     738     3693522 :   lr=i+3; rem -= lr;
     739     3693522 :   rem[0] = evaltyp(t_POL) | evallg(lr);
     740     3693467 :   rem[1] = z[-1];
     741     3693467 :   p1 = gerepileuptoint((pari_sp)rem, p1);
     742     3694692 :   rem += 2; gel(rem,i) = p1;
     743    25314218 :   for (i--; i>=0; i--)
     744             :   {
     745    21620504 :     av=avma; p1 = gel(x,i);
     746   213937941 :     for (j=0; j<=i && j<=dz; j++)
     747   192340973 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     748    21596968 :     gel(rem,i) = avma == av? icopy(p1): gerepileuptoint(av, p1);
     749             :   }
     750     3693714 :   rem -= 2;
     751     3693714 :   if (!sx) (void)ZX_renormalize(rem, lr);
     752     3693714 :   return gerepileupto(av0,rem);
     753             : }
     754             : 
     755             : /* return x(1) */
     756             : GEN
     757        4718 : ZX_eval1(GEN x)
     758             : {
     759        4718 :   pari_sp av = avma;
     760        4718 :   long i = lg(x)-1;
     761             :   GEN s;
     762        4718 :   if (i < 2) return gen_0;
     763        4193 :   s = gel(x,i); i--;
     764        4193 :   if (i == 1) return icopy(s);
     765       34608 :   for ( ; i>=2; i--)
     766             :   {
     767       31423 :     GEN c = gel(x,i);
     768       31423 :     if (signe(c)) s = addii(s, c);
     769             :   }
     770        3185 :   return gerepileuptoint(av,s);
     771             : }
     772             : 
     773             : /* reduce T mod X^n - 1. Shallow function */
     774             : GEN
     775     1800801 : ZX_mod_Xnm1(GEN T, ulong n)
     776             : {
     777     1800801 :   long i, j, L = lg(T), l = n+2;
     778             :   GEN S;
     779     1800801 :   if (L <= l) return T;
     780     1609744 :   S = cgetg(l, t_POL);
     781     1609318 :   S[1] = T[1];
     782    12255512 :   for (i = 2; i < l; i++) gel(S,i) = gel(T,i);
     783     7396736 :   for (j = 2; i < L; i++) {
     784     5794032 :     gel(S,j) = addii(gel(S,j), gel(T,i));
     785     5787418 :     if (++j == l) j = 2;
     786             :   }
     787     1602704 :   return normalizepol_lg(S, l);
     788             : }
     789             : 
     790             : /*******************************************************************/
     791             : /*                                                                 */
     792             : /*                                ZXV                              */
     793             : /*                                                                 */
     794             : /*******************************************************************/
     795             : 
     796             : int
     797          35 : ZXV_equal(GEN V, GEN W)
     798             : {
     799          35 :   long l = lg(V);
     800          35 :   if (l!=lg(W)) return 0;
     801          35 :   while (--l > 0)
     802          35 :     if (!ZX_equal(gel(V,l), gel(W,l))) return 0;
     803           0 :   return 1;
     804             : }
     805             : 
     806             : GEN
     807        7476 : ZXV_Z_mul(GEN x, GEN y)
     808       29904 : { pari_APPLY_same(ZX_Z_mul(gel(x,i), y)) }
     809             : 
     810             : GEN
     811           0 : ZXV_remi2n(GEN x, long N)
     812           0 : { pari_APPLY_same(ZX_remi2n(gel(x,i), N)) }
     813             : 
     814             : GEN
     815       82873 : ZXV_dotproduct(GEN x, GEN y)
     816             : {
     817       82873 :   pari_sp av = avma;
     818       82873 :   long i, lx = lg(x);
     819             :   GEN c;
     820       82873 :   if (lx == 1) return pol_0(varn(x));
     821       82873 :   c = ZX_mul(gel(x,1), gel(y,1));
     822      391629 :   for (i = 2; i < lx; i++)
     823             :   {
     824      308756 :     GEN t = ZX_mul(gel(x,i), gel(y,i));
     825      308756 :     if (signe(t)) c = ZX_add(c, t);
     826             :   }
     827       82873 :   return gerepileupto(av, c);
     828             : }
     829             : 
     830             : /*******************************************************************/
     831             : /*                                                                 */
     832             : /*                                ZXQM                             */
     833             : /*                                                                 */
     834             : /*******************************************************************/
     835             : 
     836             : GEN
     837     2469639 : ZXn_mul(GEN x, GEN y, long n)
     838     2469639 : { return RgXn_red_shallow(ZX_mul(x, y), n); }
     839             : 
     840             : GEN
     841        1386 : ZXn_sqr(GEN x, long n)
     842        1386 : { return RgXn_red_shallow(ZX_sqr(x), n); }
     843             : 
     844             : /*******************************************************************/
     845             : /*                                                                 */
     846             : /*                                ZXQM                             */
     847             : /*                                                                 */
     848             : /*******************************************************************/
     849             : 
     850             : static long
     851     5093323 : ZX_expi(GEN x)
     852             : {
     853     5093323 :   if (signe(x)==0) return 0;
     854     2345868 :   if (typ(x)==t_INT) return expi(x);
     855     1691144 :   return ZX_expispec(x+2, lgpol(x));
     856             : }
     857             : 
     858             : static long
     859      772495 : ZXC_expi(GEN x)
     860             : {
     861      772495 :   long i, l = lg(x), m=0;
     862     5865818 :   for(i = 1; i < l; i++)
     863             :   {
     864     5093323 :     long e = ZX_expi(gel(x,i));
     865     5093323 :     if (e > m) m = e;
     866             :   }
     867      772495 :   return m;
     868             : }
     869             : 
     870             : static long
     871      142392 : ZXM_expi(GEN x)
     872             : {
     873      142392 :   long i, l = lg(x), m=0;
     874      914887 :   for(i = 1; i < l; i++)
     875             :   {
     876      772495 :     long e = ZXC_expi(gel(x,i));
     877      772495 :     if (e > m) m = e;
     878             :   }
     879      142392 :   return m;
     880             : }
     881             : 
     882             : static GEN
     883     5093323 : ZX_eval2BIL(GEN x, long k)
     884             : {
     885     5093323 :   if (signe(x)==0) return gen_0;
     886     2345868 :   if (typ(x)==t_INT) return x;
     887     1691144 :   return ZX_eval2BILspec(x+2, k, lgpol(x));
     888             : }
     889             : 
     890             : /*Eval x in 2^(k*BIL) in linear time*/
     891             : static GEN
     892      772495 : ZXC_eval2BIL(GEN x, long k)
     893             : {
     894      772495 :   long i, lx = lg(x);
     895      772495 :   GEN A = cgetg(lx, t_COL);
     896     5865818 :   for (i=1; i<lx; i++) gel(A,i) = ZX_eval2BIL(gel(x,i), k);
     897      772495 :   return A;
     898             : }
     899             : 
     900             : static GEN
     901      142392 : ZXM_eval2BIL(GEN x, long k)
     902             : {
     903      142392 :   long i, lx = lg(x);
     904      142392 :   GEN A = cgetg(lx, t_MAT);
     905      914887 :   for (i=1; i<lx; i++) gel(A,i) = ZXC_eval2BIL(gel(x,i), k);
     906      142392 :   return A;
     907             : }
     908             : 
     909             : static GEN
     910      664898 : Z_mod2BIL_ZXQ(GEN x, long bs, GEN T)
     911             : {
     912      664898 :   pari_sp av = avma;
     913      664898 :   long v = varn(T), d = 2*(degpol(T)-1);
     914      664898 :   GEN z = Z_mod2BIL_ZX(x, bs, d, 0);
     915      664898 :   setvarn(z, v);
     916      664898 :   return gerepileupto(av, ZX_rem(z, T));
     917             : }
     918             : 
     919             : static GEN
     920       27448 : ZC_mod2BIL_ZXQC(GEN x, long bs, GEN T)
     921             : {
     922       27448 :   long i, lx = lg(x);
     923       27448 :   GEN A = cgetg(lx, t_COL);
     924      692346 :   for (i=1; i<lx; i++) gel(A,i) = Z_mod2BIL_ZXQ(gel(x,i), bs, T);
     925       27448 :   return A;
     926             : }
     927             : 
     928             : static GEN
     929        8462 : ZM_mod2BIL_ZXQM(GEN x, long bs, GEN T)
     930             : {
     931        8462 :   long i, lx = lg(x);
     932        8462 :   GEN A = cgetg(lx, t_MAT);
     933       35910 :   for (i=1; i<lx; i++) gel(A,i) = ZC_mod2BIL_ZXQC(gel(x,i), bs, T);
     934        8462 :   return A;
     935             : }
     936             : 
     937             : GEN
     938        8322 : ZXQM_mul(GEN x, GEN y, GEN T)
     939             : {
     940        8322 :   long d = degpol(T);
     941             :   GEN z;
     942        8322 :   pari_sp av = avma;
     943        8322 :   if (d == 0)
     944           0 :     z = ZM_mul(simplify_shallow(x),simplify_shallow(y));
     945             :   else
     946             :   {
     947        8322 :     long ex = ZXM_expi(x), ey = ZXM_expi(y), d= degpol(T), n = lg(x)-1;
     948        8322 :     long e = ex + ey + expu(d) + expu(n) + 4;
     949        8322 :     long N = divsBIL(e)+1;
     950        8322 :     z = ZM_mul(ZXM_eval2BIL(x,N), ZXM_eval2BIL(y,N));
     951        8322 :     z = ZM_mod2BIL_ZXQM(z, N, T);
     952             :   }
     953        8322 :   return gerepileupto(av, z);
     954             : }
     955             : 
     956             : GEN
     957         140 : ZXQM_sqr(GEN x, GEN T)
     958             : {
     959         140 :   long d = degpol(T);
     960             :   GEN z;
     961         140 :   pari_sp av = avma;
     962         140 :   if (d == 0)
     963           0 :     z = ZM_sqr(simplify_shallow(x));
     964             :   else
     965             :   {
     966         140 :     long ex = ZXM_expi(x), d = degpol(T), n = lg(x)-1;
     967         140 :     long e = 2*ex + expu(d) + expu(n) + 4;
     968         140 :     long N = divsBIL(e)+1;
     969         140 :     z = ZM_sqr(ZXM_eval2BIL(x,N));
     970         140 :     z = ZM_mod2BIL_ZXQM(z, N, T);
     971             :   }
     972         140 :   return gerepileupto(av, z);
     973             : }
     974             : 
     975             : GEN
     976        4571 : QXQM_mul(GEN x, GEN y, GEN T)
     977             : {
     978        4571 :   GEN dx, nx = Q_primitive_part(x, &dx);
     979        4571 :   GEN dy, ny = Q_primitive_part(y, &dy);
     980        4571 :   GEN z = ZXQM_mul(nx, ny, T);
     981        4571 :   if (dx || dy)
     982             :   {
     983        4571 :     GEN d = dx ? dy ? gmul(dx, dy): dx : dy;
     984        4571 :     if (!gequal1(d)) z = RgM_Rg_mul(z, d);
     985             :   }
     986        4571 :   return z;
     987             : }
     988             : 
     989             : GEN
     990           7 : QXQM_sqr(GEN x, GEN T)
     991             : {
     992           7 :   GEN dx, nx = Q_primitive_part(x, &dx);
     993           7 :   GEN z = ZXQM_sqr(nx, T);
     994           7 :   if (dx) z = RgM_Rg_mul(z, gsqr(dx));
     995           7 :   return z;
     996             : }
     997             : 
     998             : static GEN
     999     1004988 : Z_mod2BIL_Fq(GEN x, long bs, GEN T, GEN p)
    1000             : {
    1001     1004988 :   pari_sp av = avma;
    1002     1004988 :   long v = get_FpX_var(T), d = 2*(get_FpX_degree(T)-1);
    1003     1004988 :   GEN z = Z_mod2BIL_ZX(x, bs, d, 0);
    1004     1004988 :   setvarn(z, v);
    1005     1004988 :   return gerepileupto(av, FpX_rem(z, T, p));
    1006             : }
    1007             : 
    1008             : static GEN
    1009      240757 : ZC_mod2BIL_FqC(GEN x, long bs, GEN T, GEN p)
    1010             : {
    1011      240757 :   long i, lx = lg(x);
    1012      240757 :   GEN A = cgetg(lx, t_COL);
    1013     1245745 :   for (i=1; i<lx; i++) gel(A,i) = Z_mod2BIL_Fq(gel(x,i), bs, T, p);
    1014      240757 :   return A;
    1015             : }
    1016             : 
    1017             : static GEN
    1018       62804 : ZM_mod2BIL_FqM(GEN x, long bs, GEN T, GEN p)
    1019             : {
    1020       62804 :   long i, lx = lg(x);
    1021       62804 :   GEN A = cgetg(lx, t_MAT);
    1022      303561 :   for (i=1; i<lx; i++) gel(A,i) = ZC_mod2BIL_FqC(gel(x,i), bs, T, p);
    1023       62804 :   return A;
    1024             : }
    1025             : 
    1026             : GEN
    1027       62804 : FqM_mul_Kronecker(GEN x, GEN y, GEN T, GEN p)
    1028             : {
    1029       62804 :   pari_sp av = avma;
    1030       62804 :   long ex = ZXM_expi(x), ey = ZXM_expi(y), d= degpol(T), n = lg(x)-1;
    1031       62804 :   long e = ex + ey + expu(d) + expu(n) + 4;
    1032       62804 :   long N = divsBIL(e)+1;
    1033       62804 :   GEN  z = ZM_mul(ZXM_eval2BIL(x,N), ZXM_eval2BIL(y,N));
    1034       62804 :   return gerepileupto(av, ZM_mod2BIL_FqM(z, N, T, p));
    1035             : }
    1036             : 
    1037             : /*******************************************************************/
    1038             : /*                                                                 */
    1039             : /*                                ZXX                              */
    1040             : /*                                                                 */
    1041             : /*******************************************************************/
    1042             : 
    1043             : void
    1044         840 : RgX_check_ZXX(GEN x, const char *s)
    1045             : {
    1046         840 :   long k = lg(x)-1;
    1047        9002 :   for ( ; k>1; k--) {
    1048        8162 :     GEN t = gel(x,k);
    1049        8162 :     switch(typ(t)) {
    1050        7357 :       case t_INT: break;
    1051         805 :       case t_POL: if (RgX_is_ZX(t)) break;
    1052             :       /* fall through */
    1053           0 :       default: pari_err_TYPE(stack_strcat(s, " not in Z[X,Y]"),x);
    1054             :     }
    1055             :   }
    1056         840 : }
    1057             : 
    1058             : /*Renormalize (in place) polynomial with t_INT or ZX coefficients.*/
    1059             : GEN
    1060   141909099 : ZXX_renormalize(GEN x, long lx)
    1061             : {
    1062             :   long i;
    1063   182536693 :   for (i = lx-1; i>1; i--)
    1064   172395211 :     if (signe(gel(x,i))) break;
    1065   141909099 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + (i+1)));
    1066   141909838 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    1067             : }
    1068             : 
    1069             : GEN
    1070       20629 : ZXX_evalx0(GEN y)
    1071             : {
    1072       20629 :   long i, l = lg(y);
    1073       20629 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1074      400260 :   for(i=2; i<l; i++)
    1075             :   {
    1076      379631 :     GEN yi = gel(y,i);
    1077      379631 :     gel(z,i) = typ(yi)==t_INT? yi: constant_coeff(yi);
    1078             :   }
    1079       20629 :   return ZX_renormalize(z,l);
    1080             : }
    1081             : 
    1082             : long
    1083        2296 : ZXX_max_lg(GEN x)
    1084             : {
    1085        2296 :   long i, prec = 0, lx = lg(x);
    1086       13545 :   for (i=2; i<lx; i++)
    1087             :   {
    1088       11249 :     GEN p = gel(x,i);
    1089       11249 :     long l = (typ(p) == t_INT)? lgefint(p): ZX_max_lg(p);
    1090       11249 :     if (l > prec) prec = l;
    1091             :   }
    1092        2296 :   return prec;
    1093             : }
    1094             : 
    1095             : GEN
    1096        5061 : ZXX_Z_mul(GEN y, GEN x)
    1097             : {
    1098        5061 :   long i, l = lg(y);
    1099        5061 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1100      212688 :   for(i=2; i<l; i++)
    1101      207627 :     if(typ(gel(y,i))==t_INT)
    1102           0 :       gel(z,i) = mulii(gel(y,i),x);
    1103             :     else
    1104      207627 :       gel(z,i) = ZX_Z_mul(gel(y,i),x);
    1105        5061 :   return z;
    1106             : }
    1107             : 
    1108             : GEN
    1109          56 : ZXX_Z_add_shallow(GEN x, GEN y)
    1110             : {
    1111          56 :   long i, l = lg(x);
    1112             :   GEN z, a;
    1113          56 :   if (signe(x)==0) return scalarpol(y,varn(x));
    1114          56 :   z = cgetg(l,t_POL); z[1] = x[1];
    1115          56 :   a = gel(x,2);
    1116          56 :   gel(z, 2) = typ(a)==t_INT? addii(a,y): ZX_Z_add(a,y);
    1117         280 :   for(i=3; i<l; i++)
    1118         224 :     gel(z,i) = gel(x,i);
    1119          56 :   return z;
    1120             : }
    1121             : 
    1122             : GEN
    1123       55363 : ZXX_Z_divexact(GEN y, GEN x)
    1124             : {
    1125       55363 :   long i, l = lg(y);
    1126       55363 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1127      465073 :   for(i=2; i<l; i++)
    1128      409710 :     if(typ(gel(y,i))==t_INT)
    1129        3031 :       gel(z,i) = diviiexact(gel(y,i),x);
    1130             :     else
    1131      406679 :       gel(z,i) = ZX_Z_divexact(gel(y,i),x);
    1132       55363 :   return z;
    1133             : }
    1134             : 
    1135             : /* Kronecker substitution, ZXX -> ZX:
    1136             :  * P(X,Y) = sum_{0<=i<lP} P_i(X) * Y^i, where deg P_i < n.
    1137             :  * Returns P(X,X^(2n-1)) */
    1138             : GEN
    1139     2550896 : ZXX_to_Kronecker_spec(GEN P, long lP, long n)
    1140             : {
    1141     2550896 :   long i, k, N = (n<<1) + 1;
    1142             :   GEN y;
    1143     2550896 :   if (!lP) return pol_0(0);
    1144     2535069 :   y = cgetg((N-2)*lP + 2, t_POL) + 2;
    1145    19840187 :   for (k=i=0; i<lP; i++)
    1146             :   {
    1147             :     long j;
    1148    19840187 :     GEN c = gel(P,i);
    1149    19840187 :     if (typ(c)!=t_POL)
    1150             :     {
    1151     1459516 :       gel(y,k++) = c;
    1152     1459516 :       j = 3;
    1153             :     }
    1154             :     else
    1155             :     {
    1156    18380671 :       long l = lg(c);
    1157    18380671 :       if (l-3 >= n)
    1158           0 :         pari_err_BUG("ZXX_to_Kronecker, P is not reduced mod Q");
    1159   108906169 :       for (j=2; j < l; j++) gel(y,k++) = gel(c,j);
    1160             :     }
    1161    19840187 :     if (i == lP-1) break;
    1162    94416740 :     for (   ; j < N; j++) gel(y,k++) = gen_0;
    1163             :   }
    1164     2535069 :   y-=2; setlg(y, k+2); y[1] = evalsigne(1); return y;
    1165             : }
    1166             : 
    1167             : /* shallow, n = deg(T) */
    1168             : GEN
    1169      219247 : Kronecker_to_ZXX(GEN z, long n, long v)
    1170             : {
    1171      219247 :   long i,j,lx,l, N = (n<<1)+1;
    1172             :   GEN x, t;
    1173      219247 :   l = lg(z); lx = (l-2) / (N-2);
    1174      219247 :   x = cgetg(lx+3,t_POL);
    1175      219247 :   x[1] = z[1];
    1176     2868976 :   for (i=2; i<lx+2; i++)
    1177             :   {
    1178     2649729 :     t = cgetg(N,t_POL); t[1] = evalvarn(v);
    1179    52414262 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    1180     2649729 :     z += (N-2);
    1181     2649729 :     gel(x,i) = ZX_renormalize(t,N);
    1182             :   }
    1183      219247 :   N = (l-2) % (N-2) + 2;
    1184      219247 :   t = cgetg(N,t_POL); t[1] = evalvarn(v);
    1185     1122258 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    1186      219247 :   gel(x,i) = ZX_renormalize(t,N);
    1187      219247 :   return ZXX_renormalize(x, i+1);
    1188             : }
    1189             : 
    1190             : GEN
    1191     1271574 : ZXX_to_Kronecker(GEN P, long n)
    1192             : {
    1193     1271574 :   GEN z = ZXX_to_Kronecker_spec(P+2, lgpol(P), n);
    1194     1271574 :   setvarn(z,varn(P)); return z;
    1195             : }
    1196             : GEN
    1197      368851 : ZXX_mul_Kronecker(GEN x, GEN y, long n)
    1198      368851 : { return ZX_mul(ZXX_to_Kronecker(x,n), ZXX_to_Kronecker(y,n)); }
    1199             : 
    1200             : GEN
    1201        5194 : ZXX_sqr_Kronecker(GEN x, long n)
    1202        5194 : { return ZX_sqr(ZXX_to_Kronecker(x,n)); }
    1203             : 
    1204             : /* shallow, n = deg(T) */
    1205             : GEN
    1206       16233 : Kronecker_to_ZXQX(GEN z, GEN T)
    1207             : {
    1208       16233 :   long i,j,lx,l, N = (degpol(T)<<1)+1;
    1209             :   GEN x, t;
    1210       16233 :   l = lg(z); lx = (l-2) / (N-2);
    1211       16233 :   x = cgetg(lx+3,t_POL);
    1212       16233 :   x[1] = z[1];
    1213      154512 :   for (i=2; i<lx+2; i++)
    1214             :   {
    1215      138279 :     t = cgetg(N,t_POL); t[1] = T[1];
    1216      645520 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    1217      138279 :     z += (N-2);
    1218      138279 :     gel(x,i) = ZX_rem(ZX_renormalize(t,N), T);
    1219             :   }
    1220       16233 :   N = (l-2) % (N-2) + 2;
    1221       16233 :   t = cgetg(N,t_POL); t[1] = T[1];
    1222       35136 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    1223       16233 :   gel(x,i) = ZX_rem(ZX_renormalize(t,N), T);
    1224       16233 :   return ZXX_renormalize(x, i+1);
    1225             : }
    1226             : 
    1227             : GEN
    1228        1792 : ZXQX_sqr(GEN x, GEN T)
    1229             : {
    1230        1792 :   pari_sp av = avma;
    1231        1792 :   long n = degpol(T);
    1232        1792 :   GEN z = ZXX_sqr_Kronecker(x, n);
    1233        1792 :   z = Kronecker_to_ZXQX(z, T);
    1234        1792 :   return gerepilecopy(av, z);
    1235             : }
    1236             : 
    1237             : GEN
    1238       14441 : ZXQX_mul(GEN x, GEN y, GEN T)
    1239             : {
    1240       14441 :   pari_sp av = avma;
    1241       14441 :   long n = degpol(T);
    1242       14441 :   GEN z = ZXX_mul_Kronecker(x, y, n);
    1243       14441 :   z = Kronecker_to_ZXQX(z, T);
    1244       14441 :   return gerepilecopy(av, z);
    1245             : }
    1246             : 
    1247             : GEN
    1248        1652 : ZXQX_ZXQ_mul(GEN P, GEN U, GEN T)
    1249             : {
    1250             :   long i, lP;
    1251             :   GEN res;
    1252        1652 :   res = cgetg_copy(P, &lP); res[1] = P[1];
    1253        5992 :   for(i=2; i<lP; i++)
    1254        4340 :     gel(res,i) = typ(gel(P,i))==t_POL? ZXQ_mul(U, gel(P,i), T)
    1255        4340 :                                      : gmul(U, gel(P,i));
    1256        1652 :   return ZXX_renormalize(res,lP);
    1257             : }
    1258             : 
    1259             : GEN
    1260     2653597 : QX_mul(GEN x, GEN y)
    1261             : {
    1262     2653597 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1263     2653597 :   GEN dy, ny = Q_primitive_part(y, &dy);
    1264     2653597 :   GEN z = ZX_mul(nx, ny);
    1265     2653597 :   if (dx || dy)
    1266             :   {
    1267     2562425 :     GEN d = dx ? dy ? gmul(dx, dy): dx : dy;
    1268     2562425 :     return ZX_Q_mul(z, d);
    1269             :   } else
    1270       91172 :     return z;
    1271             : }
    1272             : 
    1273             : GEN
    1274       25025 : QX_sqr(GEN x)
    1275             : {
    1276       25025 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1277       25025 :   GEN z = ZX_sqr(nx);
    1278       25025 :   if (dx)
    1279       14658 :     return ZX_Q_mul(z, gsqr(dx));
    1280             :   else
    1281       10367 :     return z;
    1282             : }
    1283             : 
    1284             : GEN
    1285     1534840 : QX_ZX_rem(GEN x, GEN y)
    1286             : {
    1287     1534840 :   pari_sp av = avma;
    1288     1534840 :   GEN d, nx = Q_primitive_part(x, &d);
    1289     1534840 :   GEN r = ZX_rem(nx, y);
    1290     1534840 :   if (d) r = ZX_Q_mul(r, d);
    1291     1534840 :   return gerepileupto(av, r);
    1292             : }
    1293             : 
    1294             : GEN
    1295       12789 : QXQX_mul(GEN x, GEN y, GEN T)
    1296             : {
    1297       12789 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1298       12789 :   GEN dy, ny = Q_primitive_part(y, &dy);
    1299       12789 :   GEN z = ZXQX_mul(nx, ny, T);
    1300       12789 :   if (dx || dy)
    1301             :   {
    1302        8190 :     GEN d = dx ? dy ? gmul(dx, dy): dx : dy;
    1303        8190 :     return ZXX_Q_mul(z, d);
    1304             :   } else
    1305        4599 :     return z;
    1306             : }
    1307             : 
    1308             : GEN
    1309        1792 : QXQX_sqr(GEN x, GEN T)
    1310             : {
    1311        1792 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1312        1792 :   GEN z = ZXQX_sqr(nx, T);
    1313        1792 :   if (dx)
    1314         588 :     return ZXX_Q_mul(z, gsqr(dx));
    1315             :   else
    1316        1204 :     return z;
    1317             : }
    1318             : 
    1319             : GEN
    1320         448 : QXQX_powers(GEN P, long n, GEN T)
    1321             : {
    1322         448 :   GEN v = cgetg(n+2, t_VEC);
    1323             :   long i;
    1324         448 :   gel(v, 1) = pol_1(varn(T));
    1325         448 :   if (n==0) return v;
    1326         448 :   gel(v, 2) = gcopy(P);
    1327        1512 :   for (i = 2; i <= n; i++) gel(v,i+1) = QXQX_mul(P, gel(v,i), T);
    1328         448 :   return v;
    1329             : }
    1330             : 
    1331             : GEN
    1332        3430 : QXQX_QXQ_mul(GEN P, GEN U, GEN T)
    1333             : {
    1334             :   long i, lP;
    1335             :   GEN res;
    1336        3430 :   res = cgetg_copy(P, &lP); res[1] = P[1];
    1337       22554 :   for(i=2; i<lP; i++)
    1338       19124 :     gel(res,i) = typ(gel(P,i))==t_POL? QXQ_mul(U, gel(P,i), T)
    1339       19124 :                                      : gmul(U, gel(P,i));
    1340        3430 :   return ZXX_renormalize(res,lP);
    1341             : }

Generated by: LCOV version 1.13