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.18.1 lcov report (development 29950-285c5b69ed) Lines: 714 792 90.2 %
Date: 2025-02-05 09:09:51 Functions: 96 107 89.7 %
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; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : 
      15             : #include "pari.h"
      16             : #include "paripriv.h"
      17             : 
      18             : /*******************************************************************/
      19             : /*                                                                 */
      20             : /*                                ZX                               */
      21             : /*                                                                 */
      22             : /*******************************************************************/
      23             : void
      24      357219 : RgX_check_QX(GEN x, const char *s)
      25      357219 : { if (!RgX_is_QX(x)) pari_err_TYPE(stack_strcat(s," [not in Q[X]]"), x); }
      26             : void
      27     2711692 : RgX_check_ZX(GEN x, const char *s)
      28     2711692 : { if (!RgX_is_ZX(x)) pari_err_TYPE(stack_strcat(s," [not in Z[X]]"), x); }
      29             : long
      30      107281 : ZX_max_lg(GEN x)
      31             : {
      32      107281 :   long i, l = 0, lx = lg(x);
      33      648388 :   for (i = 2; i < lx; i++) l = maxss(l, lgefint(gel(x,i)));
      34      107281 :   return l;
      35             : }
      36             : 
      37             : GEN
      38    40555110 : ZX_add(GEN x, GEN y)
      39             : {
      40             :   long lx,ly,i;
      41             :   GEN z;
      42    40555110 :   lx = lg(x); ly = lg(y); if (lx < ly) swapspec(x,y, lx,ly);
      43    40555110 :   z = cgetg(lx,t_POL); z[1] = x[1];
      44   247971534 :   for (i=2; i<ly; i++) gel(z,i) = addii(gel(x,i),gel(y,i));
      45    79298346 :   for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
      46    40432713 :   if (lx == ly) z = ZX_renormalize(z, lx);
      47    40432385 :   if (!lgpol(z)) { set_avma((pari_sp)(z + lx)); return pol_0(varn(x)); }
      48    39214441 :   return z;
      49             : }
      50             : 
      51             : GEN
      52    29514223 : ZX_sub(GEN x,GEN y)
      53             : {
      54    29514223 :   long i, lx = lg(x), ly = lg(y);
      55             :   GEN z;
      56    29514223 :   if (lx >= ly)
      57             :   {
      58    29060007 :     z = cgetg(lx,t_POL); z[1] = x[1];
      59   118016813 :     for (i=2; i<ly; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
      60    29015642 :     if (lx == ly)
      61             :     {
      62    23386569 :       z = ZX_renormalize(z, lx);
      63    23386296 :       if (!lgpol(z)) { set_avma((pari_sp)(z + lx)); z = pol_0(varn(x)); }
      64             :     }
      65             :     else
      66    17369926 :       for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
      67             :   }
      68             :   else
      69             :   {
      70      454216 :     z = cgetg(ly,t_POL); z[1] = y[1];
      71     1197855 :     for (i=2; i<lx; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
      72     1408509 :     for (   ; i<ly; i++) gel(z,i) = negi(gel(y,i));
      73             :   }
      74    29511124 :   return z;
      75             : }
      76             : 
      77             : GEN
      78      599023 : ZX_neg(GEN x)
      79             : {
      80      599023 :   long i, l = lg(x);
      81      599023 :   GEN y = cgetg(l,t_POL);
      82     2469398 :   y[1] = x[1]; for(i=2; i<l; i++) gel(y,i) = negi(gel(x,i));
      83      599087 :   return y;
      84             : }
      85             : GEN
      86     5358782 : ZX_copy(GEN x)
      87             : {
      88     5358782 :   long i, l = lg(x);
      89     5358782 :   GEN y = cgetg(l, t_POL);
      90     5358791 :   y[1] = x[1];
      91    21989931 :   for (i=2; i<l; i++)
      92             :   {
      93    16631142 :     GEN c = gel(x,i);
      94    16631142 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
      95             :   }
      96     5358789 :   return y;
      97             : }
      98             : 
      99             : GEN
     100       56464 : scalar_ZX(GEN x, long v)
     101             : {
     102             :   GEN z;
     103       56464 :   if (!signe(x)) return pol_0(v);
     104        4558 :   z = cgetg(3, t_POL);
     105        4558 :   z[1] = evalsigne(1) | evalvarn(v);
     106        4558 :   gel(z,2) = icopy(x); return z;
     107             : }
     108             : 
     109             : GEN
     110       23155 : scalar_ZX_shallow(GEN x, long v)
     111             : {
     112             :   GEN z;
     113       23155 :   if (!signe(x)) return pol_0(v);
     114       19991 :   z = cgetg(3, t_POL);
     115       19991 :   z[1] = evalsigne(1) | evalvarn(v);
     116       19991 :   gel(z,2) = x; return z;
     117             : }
     118             : 
     119             : GEN
     120       87484 : ZX_Z_add(GEN y, GEN x)
     121             : {
     122             :   long lz, i;
     123       87484 :   GEN z = cgetg_copy(y, &lz);
     124       87484 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX(x,varn(y)); }
     125       76746 :   z[1] = y[1];
     126       76746 :   gel(z,2) = addii(gel(y,2),x);
     127     1796690 :   for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
     128       76792 :   if (lz==3) z = ZX_renormalize(z,lz);
     129       76746 :   return z;
     130             : }
     131             : GEN
     132       94556 : ZX_Z_add_shallow(GEN y, GEN x)
     133             : {
     134             :   long lz, i;
     135       94556 :   GEN z = cgetg_copy(y, &lz);
     136       94556 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX_shallow(x,varn(y)); }
     137       94325 :   z[1] = y[1];
     138       94325 :   gel(z,2) = addii(gel(y,2),x);
     139      553887 :   for(i=3; i<lz; i++) gel(z,i) = gel(y,i);
     140       94320 :   if (lz==3) z = ZX_renormalize(z,lz);
     141       94319 :   return z;
     142             : }
     143             : 
     144             : GEN
     145      181714 : ZX_Z_sub(GEN y, GEN x)
     146             : {
     147             :   long lz, i;
     148      181714 :   GEN z = cgetg_copy(y, &lz);
     149      181714 :   if (lz == 2)
     150             :   { /* scalarpol(negi(x), v) */
     151         441 :     long v = varn(y);
     152         441 :     set_avma((pari_sp)(z + 2));
     153         441 :     if (!signe(x)) return pol_0(v);
     154         441 :     z = cgetg(3,t_POL);
     155         441 :     z[1] = evalvarn(v) | evalsigne(1);
     156         441 :     gel(z,2) = negi(x); return z;
     157             :   }
     158      181273 :   z[1] = y[1];
     159      181273 :   gel(z,2) = subii(gel(y,2),x);
     160      909299 :   for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
     161      181273 :   if (lz==3) z = ZX_renormalize(z,lz);
     162      181273 :   return z;
     163             : }
     164             : 
     165             : GEN
     166     2715958 : Z_ZX_sub(GEN x, GEN y)
     167             : {
     168             :   long lz, i;
     169     2715958 :   GEN z = cgetg_copy(y, &lz);
     170     2716003 :   if (lz == 2) { set_avma((pari_sp)(z + 2)); return scalar_ZX(x,varn(y)); }
     171     2716003 :   z[1] = y[1];
     172     2716003 :   gel(z,2) = subii(x, gel(y,2));
     173    13613894 :   for(i=3; i<lz; i++) gel(z,i) = negi(gel(y,i));
     174     2716343 :   if (lz==3) z = ZX_renormalize(z,lz);
     175     2716068 :   return z;
     176             : }
     177             : 
     178             : GEN
     179     5087267 : ZX_Z_divexact(GEN y,GEN x)
     180             : {
     181     5087267 :   long i, l = lg(y);
     182     5087267 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
     183    32500331 :   for(i=2; i<l; i++) gel(z,i) = diviiexact(gel(y,i),x);
     184     5084929 :   return z;
     185             : }
     186             : 
     187             : GEN
     188      977795 : ZX_divuexact(GEN y, ulong x)
     189             : {
     190      977795 :   long i, l = lg(y);
     191      977795 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
     192     9684353 :   for(i=2; i<l; i++) gel(z,i) = diviuexact(gel(y,i),x);
     193      977795 :   return z;
     194             : }
     195             : 
     196             : GEN
     197         112 : zx_z_divexact(GEN y, long x)
     198             : {
     199         112 :   long i, l = lg(y);
     200         112 :   GEN z = cgetg(l,t_VECSMALL); z[1] = y[1];
     201         595 :   for (i=2; i<l; i++) z[i] = y[i]/x;
     202         112 :   return z;
     203             : }
     204             : 
     205             : GEN
     206    17011256 : ZX_Z_mul(GEN y,GEN x)
     207             : {
     208             :   GEN z;
     209             :   long i, l;
     210    17011256 :   if (!signe(x)) return pol_0(varn(y));
     211    13964387 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     212    92843457 :   for(i=2; i<l; i++) gel(z,i) = mulii(gel(y,i),x);
     213    13957382 :   return z;
     214             : }
     215             : 
     216             : GEN
     217      253094 : ZX_mulu(GEN y, ulong x)
     218             : {
     219             :   GEN z;
     220             :   long i, l;
     221      253094 :   if (!x) return pol_0(varn(y));
     222      253094 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     223     1025517 :   for(i=2; i<l; i++) gel(z,i) = mului(x,gel(y,i));
     224      253094 :   return z;
     225             : }
     226             : 
     227             : GEN
     228     6403210 : ZX_shifti(GEN y, long n)
     229             : {
     230             :   GEN z;
     231             :   long i, l;
     232     6403210 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     233    30961052 :   for(i=2; i<l; i++) gel(z,i) = shifti(gel(y,i),n);
     234     6400150 :   return ZX_renormalize(z,l);
     235             : }
     236             : 
     237             : GEN
     238      106236 : ZX_remi2n(GEN y, long n)
     239             : {
     240             :   GEN z;
     241             :   long i, l;
     242      106236 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     243     4819929 :   for(i=2; i<l; i++) gel(z,i) = remi2n(gel(y,i),n);
     244      104538 :   return ZX_renormalize(z,l);
     245             : }
     246             : 
     247             : GEN
     248       45661 : ZXT_remi2n(GEN z, long n)
     249             : {
     250       45661 :   if (typ(z) == t_POL)
     251       39514 :     return ZX_remi2n(z, n);
     252             :   else
     253             :   {
     254        6147 :     long i,l = lg(z);
     255        6147 :     GEN x = cgetg(l, t_VEC);
     256       18463 :     for (i=1; i<l; i++) gel(x,i) = ZXT_remi2n(gel(z,i), n);
     257        6150 :     return x;
     258             :   }
     259             : }
     260             : 
     261             : GEN
     262        1330 : zx_to_ZX(GEN z)
     263             : {
     264        1330 :   long i, l = lg(z);
     265        1330 :   GEN x = cgetg(l,t_POL);
     266      100954 :   for (i=2; i<l; i++) gel(x,i) = stoi(z[i]);
     267        1330 :   x[1] = evalsigne(l-2!=0)| z[1]; return x;
     268             : }
     269             : 
     270             : GEN
     271     7411317 : ZX_deriv(GEN x)
     272             : {
     273     7411317 :   long i,lx = lg(x)-1;
     274             :   GEN y;
     275             : 
     276     7411317 :   if (lx<3) return pol_0(varn(x));
     277     7328880 :   y = cgetg(lx,t_POL);
     278    38929411 :   for (i=2; i<lx ; i++) gel(y,i) = mului(i-1,gel(x,i+1));
     279     7327631 :   y[1] = x[1]; return y;
     280             : }
     281             : 
     282             : int
     283     1957338 : ZX_equal(GEN V, GEN W)
     284             : {
     285     1957338 :   long i, l = lg(V);
     286     1957338 :   if (lg(W) != l) return 0;
     287     5893681 :   for (i = 2; i < l; i++)
     288     4562864 :     if (!equalii(gel(V,i), gel(W,i))) return 0;
     289     1330817 :   return 1;
     290             : }
     291             : 
     292             : static long
     293   308540934 : ZX_valspec(GEN x, long nx)
     294             : {
     295             :   long vx;
     296   380882214 :   for (vx = 0; vx<nx ; vx++)
     297   380897264 :     if (signe(gel(x,vx))) break;
     298   308540934 :   return vx;
     299             : }
     300             : 
     301             : long
     302      330814 : ZX_val(GEN x)
     303             : {
     304             :   long vx;
     305      330814 :   if (!signe(x)) return LONG_MAX;
     306      265135 :   for (vx = 0;; vx++)
     307      265135 :     if (signe(gel(x,2+vx))) break;
     308      215181 :   return vx;
     309             : }
     310             : long
     311    28586928 : ZX_valrem(GEN x, GEN *Z)
     312             : {
     313             :   long vx;
     314    28586928 :   if (!signe(x)) { *Z = pol_0(varn(x)); return LONG_MAX; }
     315    49313212 :   for (vx = 0;; vx++)
     316    49313212 :     if (signe(gel(x,2+vx))) break;
     317    28586928 :   *Z = RgX_shift_shallow(x, -vx);
     318    28586934 :   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     3562045 : ZX_translate_basecase(GEN P, GEN c)
     341             : {
     342     3562045 :   pari_sp av = avma;
     343             :   GEN Q, R;
     344             :   long i, k, n;
     345             : 
     346     3562045 :   if (!signe(P) || !signe(c)) return ZX_copy(P);
     347     3522245 :   Q = leafcopy(P);
     348     3522298 :   R = Q+2; n = degpol(P);
     349     3522297 :   if (equali1(c))
     350             :   {
     351    17247714 :     for (i=1; i<=n; i++)
     352             :     {
     353    98383506 :       for (k=n-i; k<n; k++) gel(R,k) = addii(gel(R,k), gel(R,k+1));
     354    14598351 :       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      872936 :   else if (equalim1(c))
     362             :   {
     363      952789 :     for (i=1; i<=n; i++)
     364             :     {
     365     3167917 :       for (k=n-i; k<n; k++) gel(R,k) = subii(gel(R,k), gel(R,k+1));
     366      726902 :       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     4584661 :     for (i=1; i<=n; i++)
     376             :     {
     377    26238991 :       for (k=n-i; k<n; k++) gel(R,k) = addmulii_inplace(gel(R,k), c, gel(R,k+1));
     378     3937613 :       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     3521901 :   return gerepilecopy(av, Q);
     386             : }
     387             : 
     388             : GEN
     389         434 : Xpm1_powu(long n, long s, long v)
     390             : {
     391             :   long d, k;
     392             :   GEN C;
     393         434 :   if (!n) return pol_1(v);
     394         434 :   d = (n + 1) >> 1;
     395         434 :   C = cgetg(n+3, t_POL);
     396         434 :   C[1] = evalsigne(1)| evalvarn(v);
     397         434 :   gel(C,2) = gen_1;
     398         434 :   gel(C,3) = utoipos(n);
     399        1771 :   for (k=2; k <= d; k++)
     400        1337 :     gel(C,k+2) = diviuexact(mului(n-k+1, gel(C,k+1)), k);
     401         434 :   if (s < 0)
     402           0 :     for (k = odd(n)? 0: 1; k <= d; k += 2)
     403           0 :       togglesign_safe(&gel(C,k+2));
     404         434 :   if (s > 0 || !odd(n))
     405        2058 :     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         434 :   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 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     3578749 : ZX_translate(GEN P, GEN c)
     432             : {
     433     3578749 :   pari_sp av = avma;
     434             :   long n;
     435     3578749 :   if (!signe(c)) return ZX_copy(P);
     436     3562049 :   n = degpol(P);
     437     3562046 :   if (n < 220)
     438     3562046 :     return ZX_translate_basecase(P, c);
     439             :   else
     440             :   {
     441           0 :     long d = n >> 1;
     442           0 :     GEN Q = ZX_translate(RgX_shift_shallow(P, -d), c);
     443           0 :     GEN R = ZX_translate(RgXn_red_shallow(P, d), c);
     444           0 :     GEN S = Z_XpN_powu(c, d, varn(P));
     445           0 :     return gerepileupto(av, ZX_add(ZX_mul(Q, S), R));
     446             :   }
     447             : }
     448             : 
     449             : /* P(ax + b) */
     450             : GEN
     451     1000649 : ZX_affine(GEN P, GEN a, GEN b)
     452             : {
     453     1000649 :   if (signe(b)) P = ZX_translate(P, b);
     454     1000649 :   return ZX_unscale(P, a);
     455             : }
     456             : 
     457             : GEN
     458      531320 : ZX_Z_eval(GEN x, GEN y)
     459             : {
     460      531320 :   long i = lg(x)-1, j;
     461      531320 :   pari_sp av = avma;
     462             :   GEN t, r;
     463             : 
     464      531320 :   if (i<=2) return (i==2)? icopy(gel(x,2)): gen_0;
     465      493198 :   if (!signe(y)) return icopy(gel(x,2));
     466             : 
     467      493079 :   t = gel(x,i); i--;
     468             : #if 0 /* standard Horner's rule */
     469             :   for ( ; i>=2; i--)
     470             :     t = addii(mulii(t,y),gel(x,i));
     471             : #endif
     472             :   /* specific attention to sparse polynomials */
     473     2437994 :   for ( ; i>=2; i = j-1)
     474             :   {
     475     2121286 :     for (j = i; !signe(gel(x,j)); j--)
     476      176379 :       if (j==2)
     477             :       {
     478        2975 :         if (i != j) y = powiu(y, i-j+1);
     479        2975 :         return gerepileuptoint(av, mulii(t,y));
     480             :       }
     481     1944907 :     r = (i==j)? y: powiu(y, i-j+1);
     482     1944923 :     t = addii(mulii(t,r), gel(x,j));
     483     1944921 :     if (gc_needed(av,2))
     484             :     {
     485           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"ZX_Z_eval: i = %ld",i);
     486           0 :       t = gerepileuptoint(av, t);
     487             :     }
     488             :   }
     489      490112 :   return gerepileuptoint(av, t);
     490             : }
     491             : 
     492             : /* Return 2^(n degpol(P))  P(x >> n) */
     493             : GEN
     494           0 : ZX_rescale2n(GEN P, long n)
     495             : {
     496           0 :   long i, l = lg(P), ni = n;
     497             :   GEN Q;
     498           0 :   if (l==2) return pol_0(varn(P));
     499           0 :   Q = cgetg(l,t_POL);
     500           0 :   gel(Q,l-1) = icopy(gel(P,l-1));
     501           0 :   for (i=l-2; i>=2; i--)
     502             :   {
     503           0 :     gel(Q,i) = shifti(gel(P,i), ni);
     504           0 :     ni += n;
     505             :   }
     506           0 :   Q[1] = P[1]; return Q;
     507             : }
     508             : 
     509             : /* Return h^deg(P) P(x / h), not memory clean. h integer, P ZX */
     510             : GEN
     511       35840 : ZX_rescale(GEN P, GEN h)
     512             : {
     513       35840 :   long l = lg(P);
     514       35840 :   GEN Q = cgetg(l,t_POL);
     515       35841 :   if (l != 2)
     516             :   {
     517       35841 :     long i = l-1;
     518       35841 :     GEN hi = h;
     519       35841 :     gel(Q,i) = gel(P,i);
     520       35841 :     if (l != 3) { i--; gel(Q,i) = mulii(gel(P,i), h); }
     521      111424 :     for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
     522             :   }
     523       35842 :   Q[1] = P[1]; return Q;
     524             : }
     525             : /* Return h^(deg(P)-1) P(x / h), P!=0, h=lt(P), memory unclean; monic result */
     526             : GEN
     527           0 : ZX_rescale_lt(GEN P)
     528             : {
     529           0 :   long l = lg(P);
     530           0 :   GEN Q = cgetg(l,t_POL);
     531           0 :   gel(Q,l-1) = gen_1;
     532           0 :   if (l != 3)
     533             :   {
     534           0 :     long i = l-1;
     535           0 :     GEN h = gel(P,i), hi = h;
     536           0 :     i--; gel(Q,i) = gel(P,i);
     537           0 :     if (l != 4) { i--; gel(Q,i) = mulii(gel(P,i), h); }
     538           0 :     for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
     539             :   }
     540           0 :   Q[1] = P[1]; return Q;
     541             : }
     542             : 
     543             : /*Eval x in 2^(k*BIL) in linear time*/
     544             : static GEN
     545    92466251 : ZX_eval2BILspec(GEN x, long k, long nx)
     546             : {
     547    92466251 :   pari_sp av = avma;
     548    92466251 :   long i,j, lz = k*nx, ki;
     549    92466251 :   GEN pz = cgetipos(2+lz);
     550    92461734 :   GEN nz = cgetipos(2+lz);
     551  3271812600 :   for(i=0; i < lz; i++)
     552             :   {
     553  3179341259 :     *int_W(pz,i) = 0UL;
     554  3179341259 :     *int_W(nz,i) = 0UL;
     555             :   }
     556   996295197 :   for(i=0, ki=0; i<nx; i++, ki+=k)
     557             :   {
     558   903823856 :     GEN c = gel(x,i);
     559   903823856 :     long lc = lgefint(c)-2;
     560   903823856 :     if (signe(c)==0) continue;
     561   679925308 :     if (signe(c) > 0)
     562  1716705015 :       for (j=0; j<lc; j++) *int_W(pz,j+ki) = *int_W(c,j);
     563             :     else
     564   340151909 :       for (j=0; j<lc; j++) *int_W(nz,j+ki) = *int_W(c,j);
     565             :   }
     566    92471341 :   pz = int_normalize(pz,0);
     567    92478564 :   nz = int_normalize(nz,0); return gerepileuptoint(av, subii(pz,nz));
     568             : }
     569             : 
     570             : static long
     571   168630556 : ZX_expispec(GEN x, long nx)
     572             : {
     573   168630556 :   long i, m = 0;
     574  1268206475 :   for(i = 0; i < nx; i++)
     575             :   {
     576  1099602206 :     long e = expi(gel(x,i));
     577  1099575919 :     if (e > m) m = e;
     578             :   }
     579   168604269 :   return m;
     580             : }
     581             : 
     582             : static GEN
     583    55679852 : Z_mod2BIL_ZX(GEN x, long bs, long d, long vx)
     584             : {
     585    55679852 :   long i, offset, lm = lgefint(x)-2, l = d+vx+3, sx = signe(x);
     586    55679852 :   GEN s1 = int2n(bs*BITS_IN_LONG), pol = cgetg(l, t_POL);
     587    55657396 :   int carry = 0;
     588    55657396 :   pol[1] = evalsigne(1);
     589    76145963 :   for (i=0; i<vx; i++) gel(pol,i+2) = gen_0;
     590   991768279 :   for (offset=0; i <= d+vx; i++, offset += bs)
     591             :   {
     592   936231407 :     pari_sp av = avma;
     593   936231407 :     long lz = minss(bs, lm-offset);
     594   936155824 :     GEN z = lz > 0 ?adduispec_offset(carry, x, offset, lz): utoi(carry);
     595   935992386 :     if (lgefint(z) == 3+bs) { carry = 1; z = gen_0;}
     596             :     else
     597             :     {
     598   922532236 :       carry = (lgefint(z) == 2+bs && (HIGHBIT & *int_W(z,bs-1)));
     599   922532236 :       if (carry)
     600    57144797 :         z = gerepileuptoint(av, (sx==-1)? subii(s1,z): subii(z,s1));
     601   865387439 :       else if (sx==-1) togglesign(z);
     602             :     }
     603   936110883 :     gel(pol,i+2) = z;
     604             :   }
     605    55536872 :   return ZX_renormalize(pol,l);
     606             : }
     607             : 
     608             : static GEN
     609    17689436 : ZX_sqrspec_sqri(GEN x, long nx, long ex, long v)
     610             : {
     611    17689436 :   long e = 2*ex + expu(nx) + 3;
     612    17689375 :   long N = divsBIL(e)+1;
     613    17689279 :   GEN  z = sqri(ZX_eval2BILspec(x,N,nx));
     614    17686874 :   return Z_mod2BIL_ZX(z, N, nx*2-2, v);
     615             : }
     616             : 
     617             : static GEN
     618    36739660 : ZX_mulspec_mulii(GEN x, GEN y, long nx, long ny, long ex, long ey, long v)
     619             : {
     620    36739660 :   long e = ex + ey + expu(minss(nx,ny)) + 3;
     621    36739257 :   long N = divsBIL(e)+1;
     622    36739144 :   GEN  z = mulii(ZX_eval2BILspec(x,N,nx), ZX_eval2BILspec(y,N,ny));
     623    36734450 :   return Z_mod2BIL_ZX(z, N, nx+ny-2, v);
     624             : }
     625             : 
     626             : INLINE GEN
     627   314974089 : ZX_sqrspec_basecase_limb(GEN x, long a, long i)
     628             : {
     629   314974089 :   pari_sp av = avma;
     630   314974089 :   GEN s = gen_0;
     631   314974089 :   long j, l = (i+1)>>1;
     632   622267080 :   for (j=a; j<l; j++)
     633             :   {
     634   308181834 :     GEN xj = gel(x,j), xx = gel(x,i-j);
     635   308181834 :     if (signe(xj) && signe(xx))
     636   304141049 :       s = addii(s, mulii(xj, xx));
     637             :   }
     638   314085246 :   s = shifti(s,1);
     639   314372662 :   if ((i&1) == 0)
     640             :   {
     641   195598834 :     GEN t = gel(x, i>>1);
     642   195598834 :     if (signe(t))
     643   195306336 :       s = addii(s, sqri(t));
     644             :   }
     645   313946864 :   return gerepileuptoint(av,s);
     646             : }
     647             : 
     648             : static GEN
     649    76148540 : ZX_sqrspec_basecase(GEN x, long nx, long v)
     650             : {
     651             :   long i, lz, nz;
     652             :   GEN z;
     653             : 
     654    76148540 :   lz = (nx << 1) + 1; nz = lz-2;
     655    76148540 :   lz += v;
     656    76148540 :   z = cgetg(lz,t_POL); z[1] = evalsigne(1); z += 2;
     657    76342793 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
     658   271665842 :   for (i=0; i<nx; i++)
     659   195645410 :     gel(z,i) = ZX_sqrspec_basecase_limb(x, 0, i);
     660   195613526 :   for (  ; i<nz; i++) gel(z,i) = ZX_sqrspec_basecase_limb(x, i-nx+1, i);
     661    75982153 :   z -= v+2; return z;
     662             : }
     663             : 
     664             : static GEN
     665    43507085 : Z_sqrshiftspec_ZX(GEN x, long vx)
     666             : {
     667    43507085 :   long i, nz = 2*vx+1;
     668    43507085 :   GEN z = cgetg(2+nz, t_POL);
     669    43504154 :   z[1] = evalsigne(1);
     670    46081488 :   for(i=2;i<nz+1;i++) gel(z,i) = gen_0;
     671    43504154 :   gel(z,nz+1) = sqri(x);
     672    43466205 :   return z;
     673             : }
     674             : 
     675             : static GEN
     676    36705834 : Z_ZX_mulshiftspec(GEN x, GEN y, long ny, long vz)
     677             : {
     678    36705834 :   long i, nz = vz+ny;
     679    36705834 :   GEN z = cgetg(2+nz, t_POL);
     680    36705833 :   z[1] = evalsigne(1);
     681    85249314 :   for (i=0; i<vz; i++)   gel(z,i+2)    = gen_0;
     682   112919726 :   for (i=0; i<ny; i++) gel(z,i+vz+2) = mulii(x, gel(y,i));
     683    36698449 :   return z;
     684             : }
     685             : 
     686             : GEN
     687   138035715 : ZX_sqrspec(GEN x, long nx)
     688             : {
     689             : #ifdef PARI_KERNEL_GMP
     690    79410657 :   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};
     691    79410657 :   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};
     692             : #else
     693    58625058 :   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};
     694    58625058 :   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};
     695             : #endif
     696   138035715 :   const long nblow = numberof(low);
     697             :   pari_sp av;
     698             :   long ex, vx;
     699             :   GEN z;
     700   138035715 :   if (!nx) return pol_0(0);
     701   137246542 :   vx = ZX_valspec(x,nx); nx-=vx; x+=vx;
     702   137345470 :   if (nx==1) return Z_sqrshiftspec_ZX(gel(x, 0), vx);
     703    93838267 :   av = avma;
     704    93838267 :   ex = ZX_expispec(x,nx);
     705    93830577 :   if (nx-2 < nblow && low[nx-2]<=ex && ex<=high[nx-2])
     706    76149575 :     z = ZX_sqrspec_basecase(x, nx, 2*vx);
     707             :   else
     708    17681002 :     z = ZX_sqrspec_sqri(x, nx, ex, 2*vx);
     709    93756811 :   return gerepileupto(av, z);
     710             : }
     711             : 
     712             : GEN
     713   138039107 : ZX_sqr(GEN x)
     714             : {
     715   138039107 :   GEN z = ZX_sqrspec(x+2, lgpol(x));
     716   137909946 :   z[1] = x[1];
     717   137909946 :   return z;
     718             : }
     719             : 
     720             : GEN
     721    95312136 : ZX_mulspec(GEN x, GEN y, long nx, long ny)
     722             : {
     723             :   pari_sp av;
     724             :   long ex, ey, vx, vy, v;
     725    95312136 :   if (!nx || !ny) return pol_0(0);
     726    85610911 :   vx = ZX_valspec(x,nx); nx-=vx; x += vx;
     727    85611100 :   vy = ZX_valspec(y,ny); ny-=vy; y += vy;
     728    85613813 :   v = vx + vy;
     729    85613813 :   if (nx==1) return Z_ZX_mulshiftspec(gel(x,0), y, ny, v);
     730    58774083 :   if (ny==1) return Z_ZX_mulshiftspec(gel(y,0), x, nx, v);
     731    48907970 :   if (nx == 2 && ny == 2)
     732             :   {
     733    12168993 :     GEN a0 = gel(x,0), a1 = gel(x,1), A0, A1, A2;
     734    12168993 :     GEN b0 = gel(y,0), b1 = gel(y,1), z = cgetg(5 + v, t_POL);
     735             :     long i;
     736    12169043 :     z[1] = evalvarn(0) | evalsigne(1);
     737    12169043 :     A0 = mulii(a0, b0);
     738    12168645 :     A2 = mulii(a1, b1); av = avma;
     739    12168496 :     A1 = gerepileuptoint(av, subii(addii(A0,A2),
     740             :                                    mulii(subii(a1,a0), subii(b1,b0))));
     741    12168915 :     i = 4 + v;
     742    12168915 :     gel(z,i--) = A2;
     743    12168915 :     gel(z,i--) = A1;
     744    14247847 :     gel(z,i--) = A0; while (i > 1) gel(z, i--) = gen_0;
     745    12168915 :     return z;
     746             :   }
     747             : #if 0
     748             :   /* generically slower even when degrees differ a lot; sometimes about twice
     749             :    * faster when bitsize is moderate */
     750             :   if (DEBUGVAR)
     751             :     return RgX_mulspec(x - vx, y - vy, nx + vx, ny + vy);
     752             : #endif
     753    36738977 :   av = avma;
     754    36738977 :   ex = ZX_expispec(x, nx);
     755    36738897 :   ey = ZX_expispec(y, ny);
     756    36739206 :   return gerepileupto(av,  ZX_mulspec_mulii(x,y,nx,ny,ex,ey,v));
     757             : }
     758             : GEN
     759    88055551 : ZX_mul(GEN x, GEN y)
     760             : {
     761             :   GEN z;
     762    88055551 :   if (x == y) return ZX_sqr(x);
     763    87317021 :   z = ZX_mulspec(x+2,y+2,lgpol(x),lgpol(y));
     764    87309925 :   z[1] = x[1];
     765    87309925 :   if (!signe(y)) z[1] &= VARNBITS;
     766    87309925 :   return z;
     767             : }
     768             : 
     769             : /* x,y two ZX in the same variable; assume y is monic */
     770             : GEN
     771    11018847 : ZX_rem(GEN x, GEN y)
     772             : {
     773             :   long vx, dx, dy, dz, i, j, sx, lr;
     774             :   pari_sp av0, av;
     775             :   GEN z,p1,rem;
     776             : 
     777    11018847 :   vx = varn(x);
     778    11018847 :   dy = degpol(y);
     779    11018791 :   dx = degpol(x);
     780    11018763 :   if (dx < dy) return ZX_copy(x);
     781     6053653 :   if (!dy) return pol_0(vx); /* y is constant */
     782     6050888 :   av0 = avma; dz = dx-dy;
     783     6050888 :   z=cgetg(dz+3,t_POL); z[1] = x[1];
     784     6050944 :   x += 2; y += 2; z += 2;
     785             : 
     786     6050944 :   p1 = gel(x,dx);
     787     6050944 :   gel(z,dz) = icopy(p1);
     788    28611643 :   for (i=dx-1; i>=dy; i--)
     789             :   {
     790    22560627 :     av=avma; p1=gel(x,i);
     791   212909957 :     for (j=i-dy+1; j<=i && j<=dz; j++)
     792   190360954 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     793    22549003 :     gel(z,i-dy) = avma == av? icopy(p1): gerepileuptoint(av, p1);
     794             :   }
     795     6051016 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     796     8950658 :   for (sx=0; ; i--)
     797             :   {
     798     8950658 :     p1 = gel(x,i);
     799    57489397 :     for (j=0; j<=i && j<=dz; j++)
     800    48539033 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     801     8950364 :     if (signe(p1)) { sx = 1; break; }
     802     3276376 :     if (!i) break;
     803     2899645 :     set_avma(av);
     804             :   }
     805     6050719 :   lr=i+3; rem -= lr;
     806     6050719 :   rem[0] = evaltyp(t_POL) | _evallg(lr);
     807     6050719 :   rem[1] = z[-1];
     808     6050719 :   p1 = gerepileuptoint((pari_sp)rem, p1);
     809     6050989 :   rem += 2; gel(rem,i) = p1;
     810    33819923 :   for (i--; i>=0; i--)
     811             :   {
     812    27769094 :     av=avma; p1 = gel(x,i);
     813   249768405 :     for (j=0; j<=i && j<=dz; j++)
     814   222035146 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     815    27733259 :     gel(rem,i) = avma == av? icopy(p1): gerepileuptoint(av, p1);
     816             :   }
     817     6050829 :   rem -= 2;
     818     6050829 :   if (!sx) (void)ZX_renormalize(rem, lr);
     819     6050829 :   return gerepileupto(av0,rem);
     820             : }
     821             : 
     822             : /* return x(1) */
     823             : GEN
     824        4718 : ZX_eval1(GEN x)
     825             : {
     826        4718 :   pari_sp av = avma;
     827        4718 :   long i = lg(x)-1;
     828             :   GEN s;
     829        4718 :   if (i < 2) return gen_0;
     830        4193 :   s = gel(x,i); i--;
     831        4193 :   if (i == 1) return icopy(s);
     832       34608 :   for ( ; i>=2; i--)
     833             :   {
     834       31423 :     GEN c = gel(x,i);
     835       31423 :     if (signe(c)) s = addii(s, c);
     836             :   }
     837        3185 :   return gerepileuptoint(av,s);
     838             : }
     839             : 
     840             : /* reduce T mod X^n - 1. Shallow function */
     841             : GEN
     842     1735768 : ZX_mod_Xnm1(GEN T, ulong n)
     843             : {
     844     1735768 :   long i, j, L = lg(T), l = n+2;
     845             :   GEN S;
     846     1735768 :   if (L <= l) return T;
     847     1573130 :   S = cgetg(l, t_POL);
     848     1572871 :   S[1] = T[1];
     849    12138556 :   for (i = 2; i < l; i++) gel(S,i) = gel(T,i);
     850     7386746 :   for (j = 2; i < L; i++) {
     851     5822052 :     gel(S,j) = addii(gel(S,j), gel(T,i));
     852     5813875 :     if (++j == l) j = 2;
     853             :   }
     854     1564694 :   return normalizepol_lg(S, l);
     855             : }
     856             : 
     857             : static GEN
     858           0 : _ZX_mul(void* E, GEN x, GEN y)
     859           0 : { (void) E; return ZX_mul(x, y); }
     860             : static GEN
     861           0 : _ZX_sqr(void *E, GEN x)
     862           0 : { (void) E; return ZX_sqr(x); }
     863             : 
     864             : static GEN
     865           0 : _ZX_divrem(void * E, GEN x, GEN y, GEN *r)
     866           0 : { (void) E; return RgX_divrem(x, y, r); }
     867             : 
     868             : static GEN
     869           0 : _ZX_add(void * E, GEN x, GEN y)
     870           0 : { (void) E; return ZX_add(x, y); }
     871             : 
     872             : static struct bb_ring ZX_ring = { _ZX_add,_ZX_mul,_ZX_sqr };
     873             : 
     874             : GEN
     875           0 : ZX_digits(GEN x, GEN T)
     876             : {
     877           0 :   long d = degpol(T), n = (lgpol(x)+d-1)/d;
     878           0 :   return gen_digits(x, T, n, NULL, &ZX_ring, _ZX_divrem);
     879             : }
     880             : 
     881             : GEN
     882           0 : ZXV_ZX_fromdigits(GEN x, GEN T)
     883           0 : { return gen_fromdigits(x,T, NULL, &ZX_ring); }
     884             : 
     885             : /*******************************************************************/
     886             : /*                                                                 */
     887             : /*                                ZXV                              */
     888             : /*                                                                 */
     889             : /*******************************************************************/
     890             : 
     891             : int
     892          28 : ZXV_equal(GEN V, GEN W)
     893             : {
     894          28 :   long l = lg(V);
     895          28 :   if (l!=lg(W)) return 0;
     896          28 :   while (--l > 0)
     897          28 :     if (!ZX_equal(gel(V,l), gel(W,l))) return 0;
     898           0 :   return 1;
     899             : }
     900             : 
     901             : GEN
     902        7476 : ZXV_Z_mul(GEN x, GEN y)
     903       29904 : { pari_APPLY_same(ZX_Z_mul(gel(x,i), y)) }
     904             : 
     905             : GEN
     906           0 : ZXV_remi2n(GEN x, long N)
     907           0 : { pari_APPLY_same(ZX_remi2n(gel(x,i), N)) }
     908             : 
     909             : GEN
     910       82943 : ZXV_dotproduct(GEN x, GEN y)
     911             : {
     912       82943 :   pari_sp av = avma;
     913       82943 :   long i, lx = lg(x);
     914             :   GEN c;
     915       82943 :   if (lx == 1) return pol_0(varn(x));
     916       82943 :   c = ZX_mul(gel(x,1), gel(y,1));
     917      392175 :   for (i = 2; i < lx; i++)
     918             :   {
     919      309232 :     GEN t = ZX_mul(gel(x,i), gel(y,i));
     920      309232 :     if (signe(t)) c = ZX_add(c, t);
     921             :   }
     922       82943 :   return gerepileupto(av, c);
     923             : }
     924             : 
     925             : GEN
     926      107483 : ZXC_to_FlxC(GEN x, ulong p, long sv)
     927     4805234 : { pari_APPLY_type(t_COL,typ(gel(x,i))==t_INT ?
     928             :                   Z_to_Flx(gel(x,i), p, sv): ZX_to_Flx(gel(x,i), p)) }
     929             : 
     930             : GEN
     931        8302 : ZXM_to_FlxM(GEN x, ulong p, long sv)
     932       84065 : { pari_APPLY_same(ZXC_to_FlxC(gel(x,i), p, sv)) }
     933             : 
     934             : /*******************************************************************/
     935             : /*                                                                 */
     936             : /*                                ZXQM                             */
     937             : /*                                                                 */
     938             : /*******************************************************************/
     939             : 
     940             : GEN
     941     2598199 : ZXn_mul(GEN x, GEN y, long n)
     942     2598199 : { return RgXn_red_shallow(ZX_mul(x, y), n); }
     943             : 
     944             : GEN
     945        1407 : ZXn_sqr(GEN x, long n)
     946        1407 : { return RgXn_red_shallow(ZX_sqr(x), n); }
     947             : 
     948             : /*******************************************************************/
     949             : /*                                                                 */
     950             : /*                                ZXQM                             */
     951             : /*                                                                 */
     952             : /*******************************************************************/
     953             : 
     954             : static long
     955     5552396 : ZX_expi(GEN x)
     956             : {
     957     5552396 :   if (signe(x)==0) return 0;
     958     2896816 :   if (typ(x)==t_INT) return expi(x);
     959     1311813 :   return ZX_expispec(x+2, lgpol(x));
     960             : }
     961             : 
     962             : static long
     963     1090479 : ZXC_expi(GEN x)
     964             : {
     965     1090479 :   long i, l = lg(x), m=0;
     966     6642875 :   for(i = 1; i < l; i++)
     967             :   {
     968     5552396 :     long e = ZX_expi(gel(x,i));
     969     5552396 :     if (e > m) m = e;
     970             :   }
     971     1090479 :   return m;
     972             : }
     973             : 
     974             : static long
     975      176148 : ZXM_expi(GEN x)
     976             : {
     977      176148 :   long i, l = lg(x), m=0;
     978     1266627 :   for(i = 1; i < l; i++)
     979             :   {
     980     1090479 :     long e = ZXC_expi(gel(x,i));
     981     1090479 :     if (e > m) m = e;
     982             :   }
     983      176148 :   return m;
     984             : }
     985             : 
     986             : static GEN
     987     5552396 : ZX_eval2BIL(GEN x, long k)
     988             : {
     989     5552396 :   if (signe(x)==0) return gen_0;
     990     2896816 :   if (typ(x)==t_INT) return x;
     991     1311813 :   return ZX_eval2BILspec(x+2, k, lgpol(x));
     992             : }
     993             : 
     994             : /*Eval x in 2^(k*BIL) in linear time*/
     995             : static GEN
     996     1090479 : ZXC_eval2BIL(GEN x, long k)
     997             : {
     998     1090479 :   long i, lx = lg(x);
     999     1090479 :   GEN A = cgetg(lx, t_COL);
    1000     6642875 :   for (i=1; i<lx; i++) gel(A,i) = ZX_eval2BIL(gel(x,i), k);
    1001     1090479 :   return A;
    1002             : }
    1003             : 
    1004             : static GEN
    1005      176148 : ZXM_eval2BIL(GEN x, long k)
    1006             : {
    1007      176148 :   long i, lx = lg(x);
    1008      176148 :   GEN A = cgetg(lx, t_MAT);
    1009     1266627 :   for (i=1; i<lx; i++) gel(A,i) = ZXC_eval2BIL(gel(x,i), k);
    1010      176148 :   return A;
    1011             : }
    1012             : 
    1013             : static GEN
    1014       63336 : Z_mod2BIL_ZXQ(GEN x, long bs, GEN T)
    1015             : {
    1016       63336 :   pari_sp av = avma;
    1017       63336 :   long v = varn(T), d = 2*(degpol(T)-1);
    1018       63336 :   GEN z = Z_mod2BIL_ZX(x, bs, d, 0);
    1019       63336 :   setvarn(z, v);
    1020       63336 :   return gerepileupto(av, ZX_rem(z, T));
    1021             : }
    1022             : 
    1023             : static GEN
    1024       13804 : ZC_mod2BIL_ZXQC(GEN x, long bs, GEN T)
    1025             : {
    1026       13804 :   long i, lx = lg(x);
    1027       13804 :   GEN A = cgetg(lx, t_COL);
    1028       77140 :   for (i=1; i<lx; i++) gel(A,i) = Z_mod2BIL_ZXQ(gel(x,i), bs, T);
    1029       13804 :   return A;
    1030             : }
    1031             : 
    1032             : static GEN
    1033        6293 : ZM_mod2BIL_ZXQM(GEN x, long bs, GEN T)
    1034             : {
    1035        6293 :   long i, lx = lg(x);
    1036        6293 :   GEN A = cgetg(lx, t_MAT);
    1037       20097 :   for (i=1; i<lx; i++) gel(A,i) = ZC_mod2BIL_ZXQC(gel(x,i), bs, T);
    1038        6293 :   return A;
    1039             : }
    1040             : 
    1041             : GEN
    1042        6153 : ZXQM_mul(GEN x, GEN y, GEN T)
    1043             : {
    1044        6153 :   long d = degpol(T);
    1045             :   GEN z;
    1046        6153 :   pari_sp av = avma;
    1047        6153 :   if (d == 0)
    1048           0 :     z = ZM_mul(simplify_shallow(x),simplify_shallow(y));
    1049             :   else
    1050             :   {
    1051        6153 :     long e, N, ex = ZXM_expi(x), ey = ZXM_expi(y), n = lg(x)-1;
    1052        6153 :     e = ex + ey + expu(d) + expu(n) + 4;
    1053        6153 :     N = divsBIL(e)+1;
    1054        6153 :     z = ZM_mul(ZXM_eval2BIL(x,N), ZXM_eval2BIL(y,N));
    1055        6153 :     z = ZM_mod2BIL_ZXQM(z, N, T);
    1056             :   }
    1057        6153 :   return gerepileupto(av, z);
    1058             : }
    1059             : 
    1060             : GEN
    1061         140 : ZXQM_sqr(GEN x, GEN T)
    1062             : {
    1063         140 :   long d = degpol(T);
    1064             :   GEN z;
    1065         140 :   pari_sp av = avma;
    1066         140 :   if (d == 0)
    1067           0 :     z = ZM_sqr(simplify_shallow(x));
    1068             :   else
    1069             :   {
    1070         140 :     long ex = ZXM_expi(x), d = degpol(T), n = lg(x)-1;
    1071         140 :     long e = 2*ex + expu(d) + expu(n) + 4;
    1072         140 :     long N = divsBIL(e)+1;
    1073         140 :     z = ZM_sqr(ZXM_eval2BIL(x,N));
    1074         140 :     z = ZM_mod2BIL_ZXQM(z, N, T);
    1075             :   }
    1076         140 :   return gerepileupto(av, z);
    1077             : }
    1078             : 
    1079             : GEN
    1080        4704 : QXQM_mul(GEN x, GEN y, GEN T)
    1081             : {
    1082        4704 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1083        4704 :   GEN dy, ny = Q_primitive_part(y, &dy);
    1084        4704 :   GEN z = ZXQM_mul(nx, ny, T);
    1085        4704 :   if (dx || dy)
    1086             :   {
    1087        4704 :     GEN d = dx ? dy ? gmul(dx, dy): dx : dy;
    1088        4704 :     if (!gequal1(d)) z = RgM_Rg_mul(z, d);
    1089             :   }
    1090        4704 :   return z;
    1091             : }
    1092             : 
    1093             : GEN
    1094           7 : QXQM_sqr(GEN x, GEN T)
    1095             : {
    1096           7 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1097           7 :   GEN z = ZXQM_sqr(nx, T);
    1098           7 :   if (dx) z = RgM_Rg_mul(z, gsqr(dx));
    1099           7 :   return z;
    1100             : }
    1101             : 
    1102             : static GEN
    1103     1199133 : Z_mod2BIL_Fq(GEN x, long bs, GEN T, GEN p)
    1104             : {
    1105     1199133 :   pari_sp av = avma;
    1106     1199133 :   long v = get_FpX_var(T), d = 2*(get_FpX_degree(T)-1);
    1107     1199133 :   GEN z = Z_mod2BIL_ZX(x, bs, d, 0);
    1108     1199133 :   setvarn(z, v);
    1109     1199133 :   return gerepileupto(av, FpX_rem(z, T, p));
    1110             : }
    1111             : 
    1112             : static GEN
    1113      305402 : ZC_mod2BIL_FqC(GEN x, long bs, GEN T, GEN p)
    1114             : {
    1115      305402 :   long i, lx = lg(x);
    1116      305402 :   GEN A = cgetg(lx, t_COL);
    1117     1504535 :   for (i=1; i<lx; i++) gel(A,i) = Z_mod2BIL_Fq(gel(x,i), bs, T, p);
    1118      305402 :   return A;
    1119             : }
    1120             : 
    1121             : static GEN
    1122       81851 : ZM_mod2BIL_FqM(GEN x, long bs, GEN T, GEN p)
    1123             : {
    1124       81851 :   long i, lx = lg(x);
    1125       81851 :   GEN A = cgetg(lx, t_MAT);
    1126      387253 :   for (i=1; i<lx; i++) gel(A,i) = ZC_mod2BIL_FqC(gel(x,i), bs, T, p);
    1127       81851 :   return A;
    1128             : }
    1129             : 
    1130             : GEN
    1131       81851 : FqM_mul_Kronecker(GEN x, GEN y, GEN T, GEN p)
    1132             : {
    1133       81851 :   pari_sp av = avma;
    1134       81851 :   long ex = ZXM_expi(x), ey = ZXM_expi(y), d= degpol(T), n = lg(x)-1;
    1135       81851 :   long e = ex + ey + expu(d) + expu(n) + 4;
    1136       81851 :   long N = divsBIL(e)+1;
    1137       81851 :   GEN  z = ZM_mul(ZXM_eval2BIL(x,N), ZXM_eval2BIL(y,N));
    1138       81851 :   return gerepileupto(av, ZM_mod2BIL_FqM(z, N, T, p));
    1139             : }
    1140             : 
    1141             : /*******************************************************************/
    1142             : /*                                                                 */
    1143             : /*                                ZXX                              */
    1144             : /*                                                                 */
    1145             : /*******************************************************************/
    1146             : 
    1147             : void
    1148        1022 : RgX_check_ZXX(GEN x, const char *s)
    1149             : {
    1150        1022 :   long k = lg(x)-1;
    1151        9891 :   for ( ; k>1; k--) {
    1152        8869 :     GEN t = gel(x,k);
    1153        8869 :     switch(typ(t)) {
    1154        7812 :       case t_INT: break;
    1155        1057 :       case t_POL: if (RgX_is_ZX(t)) break;
    1156             :       /* fall through */
    1157           0 :       default: pari_err_TYPE(stack_strcat(s, " not in Z[X,Y]"),x);
    1158             :     }
    1159             :   }
    1160        1022 : }
    1161             : 
    1162             : /*Renormalize (in place) polynomial with t_INT or ZX coefficients.*/
    1163             : GEN
    1164   299841460 : ZXX_renormalize(GEN x, long lx)
    1165             : {
    1166             :   long i;
    1167   370278169 :   for (i = lx-1; i>1; i--)
    1168   356274753 :     if (signe(gel(x,i))) break;
    1169   299841460 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + (i+1)));
    1170   299828116 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    1171             : }
    1172             : 
    1173             : GEN
    1174       28548 : ZXX_evalx0(GEN y)
    1175             : {
    1176       28548 :   long i, l = lg(y);
    1177       28548 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1178      480693 :   for(i=2; i<l; i++)
    1179             :   {
    1180      452145 :     GEN yi = gel(y,i);
    1181      452145 :     gel(z,i) = typ(yi)==t_INT? yi: constant_coeff(yi);
    1182             :   }
    1183       28548 :   return ZX_renormalize(z,l);
    1184             : }
    1185             : 
    1186             : long
    1187        5376 : ZXX_max_lg(GEN x)
    1188             : {
    1189        5376 :   long i, prec = 0, lx = lg(x);
    1190       37562 :   for (i=2; i<lx; i++)
    1191             :   {
    1192       32186 :     GEN p = gel(x,i);
    1193       32186 :     long l = (typ(p) == t_INT)? lgefint(p): ZX_max_lg(p);
    1194       32186 :     if (l > prec) prec = l;
    1195             :   }
    1196        5376 :   return prec;
    1197             : }
    1198             : 
    1199             : GEN
    1200        8925 : ZXX_Z_mul(GEN y, GEN x)
    1201             : {
    1202        8925 :   long i, l = lg(y);
    1203        8925 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1204      230895 :   for(i=2; i<l; i++)
    1205      221970 :     if(typ(gel(y,i))==t_INT)
    1206           0 :       gel(z,i) = mulii(gel(y,i),x);
    1207             :     else
    1208      221970 :       gel(z,i) = ZX_Z_mul(gel(y,i),x);
    1209        8925 :   return z;
    1210             : }
    1211             : 
    1212             : GEN
    1213           0 : ZXX_Z_add_shallow(GEN x, GEN y)
    1214             : {
    1215           0 :   long i, l = lg(x);
    1216             :   GEN z, a;
    1217           0 :   if (signe(x)==0) return scalarpol(y,varn(x));
    1218           0 :   z = cgetg(l,t_POL); z[1] = x[1];
    1219           0 :   a = gel(x,2);
    1220           0 :   gel(z, 2) = typ(a)==t_INT? addii(a,y): ZX_Z_add(a,y);
    1221           0 :   for(i=3; i<l; i++)
    1222           0 :     gel(z,i) = gel(x,i);
    1223           0 :   return z;
    1224             : }
    1225             : 
    1226             : GEN
    1227       56469 : ZXX_Z_divexact(GEN y, GEN x)
    1228             : {
    1229       56469 :   long i, l = lg(y);
    1230       56469 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
    1231      467026 :   for(i=2; i<l; i++)
    1232      410557 :     if(typ(gel(y,i))==t_INT)
    1233        2989 :       gel(z,i) = diviiexact(gel(y,i),x);
    1234             :     else
    1235      407568 :       gel(z,i) = ZX_Z_divexact(gel(y,i),x);
    1236       56469 :   return z;
    1237             : }
    1238             : 
    1239             : /* Kronecker substitution, ZXX -> ZX:
    1240             :  * P(X,Y) = sum_{0<=i<lP} P_i(X) * Y^i, where deg P_i < n.
    1241             :  * Returns P(X,X^(2n-1)) */
    1242             : GEN
    1243    10015692 : RgXX_to_Kronecker_spec(GEN P, long lP, long n)
    1244             : {
    1245    10015692 :   long i, k, N = (n<<1) + 1;
    1246             :   GEN y;
    1247    10015692 :   if (!lP) return pol_0(0);
    1248     9996066 :   y = cgetg((N-2)*lP + 2, t_POL) + 2;
    1249    45125382 :   for (k=i=0; i<lP; i++)
    1250             :   {
    1251             :     long j;
    1252    45128548 :     GEN c = gel(P,i);
    1253    45128548 :     if (typ(c)!=t_POL)
    1254             :     {
    1255     3207870 :       gel(y,k++) = c;
    1256     3207870 :       j = 3;
    1257             :     }
    1258             :     else
    1259             :     {
    1260    41920678 :       long l = lg(c);
    1261    41920678 :       if (l-3 >= n)
    1262           0 :         pari_err_BUG("RgXX_to_Kronecker, P is not reduced mod Q");
    1263   247629172 :       for (j=2; j < l; j++) gel(y,k++) = gel(c,j);
    1264             :     }
    1265    45128518 :     if (i == lP-1) break;
    1266   195642456 :     for (   ; j < N; j++) gel(y,k++) = gen_0;
    1267             :   }
    1268     9994750 :   y-=2; setlg(y, k+2); y[1] = evalsigne(1); return y;
    1269             : }
    1270             : 
    1271             : /* shallow, n = deg(T) */
    1272             : GEN
    1273     1768258 : Kronecker_to_ZXX(GEN z, long n, long v)
    1274             : {
    1275     1768258 :   long i,j,lx,l, N = (n<<1)+1;
    1276             :   GEN x, t;
    1277     1768258 :   l = lg(z); lx = (l-2) / (N-2);
    1278     1768258 :   x = cgetg(lx+3,t_POL);
    1279     1768324 :   x[1] = z[1];
    1280     8933005 :   for (i=2; i<lx+2; i++)
    1281             :   {
    1282     7164171 :     t = cgetg(N,t_POL); t[1] = evalvarn(v);
    1283   107232315 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    1284     7163539 :     z += (N-2);
    1285     7163539 :     gel(x,i) = ZX_renormalize(t,N);
    1286             :   }
    1287     1768834 :   N = (l-2) % (N-2) + 2;
    1288     1768834 :   t = cgetg(N,t_POL); t[1] = evalvarn(v);
    1289     5138068 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    1290     1768616 :   gel(x,i) = ZX_renormalize(t,N);
    1291     1768571 :   return ZXX_renormalize(x, i+1);
    1292             : }
    1293             : 
    1294             : GEN
    1295     6678509 : RgXX_to_Kronecker(GEN P, long n)
    1296             : {
    1297     6678509 :   GEN z = RgXX_to_Kronecker_spec(P+2, lgpol(P), n);
    1298     6678560 :   setvarn(z,varn(P)); return z;
    1299             : }
    1300             : GEN
    1301     3028337 : ZXX_mul_Kronecker(GEN x, GEN y, long n)
    1302     3028337 : { return ZX_mul(RgXX_to_Kronecker(x,n), RgXX_to_Kronecker(y,n)); }
    1303             : 
    1304             : GEN
    1305        5306 : ZXX_sqr_Kronecker(GEN x, long n)
    1306        5306 : { return ZX_sqr(RgXX_to_Kronecker(x,n)); }
    1307             : 
    1308             : /* shallow, n = deg(T) */
    1309             : GEN
    1310       24283 : Kronecker_to_ZXQX(GEN z, GEN T)
    1311             : {
    1312       24283 :   long i,j,lx,l, N = (degpol(T)<<1)+1;
    1313             :   GEN x, t;
    1314       24283 :   l = lg(z); lx = (l-2) / (N-2);
    1315       24283 :   x = cgetg(lx+3,t_POL);
    1316       24283 :   x[1] = z[1];
    1317      236356 :   for (i=2; i<lx+2; i++)
    1318             :   {
    1319      212073 :     t = cgetg(N,t_POL); t[1] = T[1];
    1320     1899232 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    1321      212073 :     z += (N-2);
    1322      212073 :     gel(x,i) = ZX_rem(ZX_renormalize(t,N), T);
    1323             :   }
    1324       24283 :   N = (l-2) % (N-2) + 2;
    1325       24283 :   t = cgetg(N,t_POL); t[1] = T[1];
    1326       57250 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    1327       24283 :   gel(x,i) = ZX_rem(ZX_renormalize(t,N), T);
    1328       24283 :   return ZXX_renormalize(x, i+1);
    1329             : }
    1330             : 
    1331             : GEN
    1332        1904 : ZXQX_sqr(GEN x, GEN T)
    1333             : {
    1334        1904 :   pari_sp av = avma;
    1335        1904 :   long n = degpol(T);
    1336        1904 :   GEN z = ZXX_sqr_Kronecker(x, n);
    1337        1904 :   z = Kronecker_to_ZXQX(z, T);
    1338        1904 :   return gerepilecopy(av, z);
    1339             : }
    1340             : 
    1341             : GEN
    1342       22379 : ZXQX_mul(GEN x, GEN y, GEN T)
    1343             : {
    1344       22379 :   pari_sp av = avma;
    1345       22379 :   long n = degpol(T);
    1346       22379 :   GEN z = ZXX_mul_Kronecker(x, y, n);
    1347       22379 :   z = Kronecker_to_ZXQX(z, T);
    1348       22379 :   return gerepilecopy(av, z);
    1349             : }
    1350             : 
    1351             : GEN
    1352        9002 : ZXQX_ZXQ_mul(GEN P, GEN U, GEN T)
    1353             : {
    1354             :   long i, lP;
    1355             :   GEN res;
    1356        9002 :   res = cgetg_copy(P, &lP); res[1] = P[1];
    1357       47148 :   for(i=2; i<lP; i++)
    1358       38148 :     gel(res,i) = typ(gel(P,i))==t_POL? ZXQ_mul(U, gel(P,i), T)
    1359       38148 :                                      : gmul(U, gel(P,i));
    1360        9000 :   return ZXX_renormalize(res,lP);
    1361             : }
    1362             : 
    1363             : GEN
    1364     3519075 : QX_mul(GEN x, GEN y)
    1365             : {
    1366     3519075 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1367     3519075 :   GEN dy, ny = Q_primitive_part(y, &dy);
    1368     3519075 :   GEN z = ZX_mul(nx, ny);
    1369     3519075 :   if (dx || dy)
    1370             :   {
    1371     3426626 :     GEN d = dx ? dy ? gmul(dx, dy): dx : dy;
    1372     3426626 :     return ZX_Q_mul(z, d);
    1373             :   } else
    1374       92449 :     return z;
    1375             : }
    1376             : 
    1377             : GEN
    1378       91459 : QX_sqr(GEN x)
    1379             : {
    1380       91459 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1381       91455 :   GEN z = ZX_sqr(nx);
    1382       91459 :   if (dx)
    1383       81087 :     return ZX_Q_mul(z, gsqr(dx));
    1384             :   else
    1385       10372 :     return z;
    1386             : }
    1387             : 
    1388             : GEN
    1389     1810889 : QX_ZX_rem(GEN x, GEN y)
    1390             : {
    1391     1810889 :   pari_sp av = avma;
    1392     1810889 :   GEN d, nx = Q_primitive_part(x, &d);
    1393     1810889 :   GEN r = ZX_rem(nx, y);
    1394     1810889 :   if (d) r = ZX_Q_mul(r, d);
    1395     1810889 :   return gerepileupto(av, r);
    1396             : }
    1397             : 
    1398             : GEN
    1399       13377 : QXQX_mul(GEN x, GEN y, GEN T)
    1400             : {
    1401       13377 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1402       13377 :   GEN dy, ny = Q_primitive_part(y, &dy);
    1403       13377 :   GEN z = ZXQX_mul(nx, ny, T);
    1404       13377 :   if (dx || dy)
    1405             :   {
    1406        8309 :     GEN d = dx ? dy ? gmul(dx, dy): dx : dy;
    1407        8309 :     return ZXX_Q_mul(z, d);
    1408             :   } else
    1409        5068 :     return z;
    1410             : }
    1411             : 
    1412             : GEN
    1413        1904 : QXQX_sqr(GEN x, GEN T)
    1414             : {
    1415        1904 :   GEN dx, nx = Q_primitive_part(x, &dx);
    1416        1904 :   GEN z = ZXQX_sqr(nx, T);
    1417        1904 :   if (dx)
    1418         588 :     return ZXX_Q_mul(z, gsqr(dx));
    1419             :   else
    1420        1316 :     return z;
    1421             : }
    1422             : 
    1423             : GEN
    1424         476 : QXQX_powers(GEN P, long n, GEN T)
    1425             : {
    1426         476 :   GEN v = cgetg(n+2, t_VEC);
    1427             :   long i;
    1428         476 :   gel(v, 1) = pol_1(varn(T));
    1429         476 :   if (n==0) return v;
    1430         476 :   gel(v, 2) = gcopy(P);
    1431        1554 :   for (i = 2; i <= n; i++) gel(v,i+1) = QXQX_mul(P, gel(v,i), T);
    1432         476 :   return v;
    1433             : }
    1434             : 
    1435             : GEN
    1436        3465 : QXQX_QXQ_mul(GEN P, GEN U, GEN T)
    1437             : {
    1438             :   long i, lP;
    1439             :   GEN res;
    1440        3465 :   res = cgetg_copy(P, &lP); res[1] = P[1];
    1441       22715 :   for(i=2; i<lP; i++)
    1442       19250 :     gel(res,i) = typ(gel(P,i))==t_POL? QXQ_mul(U, gel(P,i), T)
    1443       19250 :                                      : gmul(U, gel(P,i));
    1444        3465 :   return ZXX_renormalize(res,lP);
    1445             : }

Generated by: LCOV version 1.16