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 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.8.0 lcov report (development 19628-9774e23) Lines: 433 458 94.5 %
Date: 2016-10-01 05:54:29 Functions: 55 57 96.5 %
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      108796 : RgX_check_QX(GEN x, const char *s)
      24      108796 : { if (!RgX_is_QX(x)) pari_err_TYPE(stack_strcat(s," [not in Q[X]]"), x); }
      25             : void
      26      604306 : RgX_check_ZX(GEN x, const char *s)
      27      604306 : { if (!RgX_is_ZX(x)) pari_err_TYPE(stack_strcat(s," [not in Z[X]]"), x); }
      28             : long
      29     7846131 : ZX_max_lg(GEN x)
      30             : {
      31     7846131 :   long i, prec = 0, lx = lg(x);
      32             : 
      33     7846131 :   for (i=2; i<lx; i++) { long l = lgefint(gel(x,i)); if (l > prec) prec = l; }
      34     7846131 :   return prec;
      35             : }
      36             : 
      37             : GEN
      38     8229186 : ZX_add(GEN x, GEN y)
      39             : {
      40             :   long lx,ly,i;
      41             :   GEN z;
      42     8229186 :   lx = lg(x); ly = lg(y); if (lx < ly) swapspec(x,y, lx,ly);
      43     8229186 :   z = cgetg(lx,t_POL); z[1] = x[1];
      44     8233257 :   for (i=2; i<ly; i++) gel(z,i) = addii(gel(x,i),gel(y,i));
      45     8229132 :   for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
      46     8229184 :   if (lx == ly) z = ZX_renormalize(z, lx);
      47     8229184 :   if (!lgpol(z)) { avma = (pari_sp)(z + lx); return pol_0(varn(x)); }
      48     7048369 :   return z;
      49             : }
      50             : 
      51             : GEN
      52      535317 : ZX_sub(GEN x,GEN y)
      53             : {
      54      535317 :   long i, lx = lg(x), ly = lg(y);
      55             :   GEN z;
      56      535317 :   if (lx >= ly)
      57             :   {
      58      524619 :     z = cgetg(lx,t_POL); z[1] = x[1];
      59      525262 :     for (i=2; i<ly; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
      60      524619 :     if (lx == ly)
      61             :     {
      62      498992 :       z = ZX_renormalize(z, lx);
      63      498992 :       if (!lgpol(z)) { avma = (pari_sp)(z + lx); z = pol_0(varn(x)); }
      64             :     }
      65             :     else
      66       25627 :       for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
      67             :   }
      68             :   else
      69             :   {
      70       10698 :     z = cgetg(ly,t_POL); z[1] = y[1];
      71       10698 :     for (i=2; i<lx; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
      72       10698 :     for (   ; i<ly; i++) gel(z,i) = negi(gel(y,i));
      73             :   }
      74      535317 :   return z;
      75             : }
      76             : 
      77             : GEN
      78        4220 : ZX_neg(GEN x)
      79             : {
      80        4220 :   long i, l = lg(x);
      81        4220 :   GEN y = cgetg(l,t_POL);
      82        4220 :   y[1] = x[1]; for(i=2; i<l; i++) gel(y,i) = negi(gel(x,i));
      83        4220 :   return y;
      84             : }
      85             : GEN
      86       91897 : ZX_copy(GEN x)
      87             : {
      88       91897 :   long i, l = lg(x);
      89       91897 :   GEN y = cgetg(l, t_POL);
      90       91897 :   y[1] = x[1];
      91     1108028 :   for (i=2; i<l; i++)
      92             :   {
      93     1016131 :     GEN c = gel(x,i);
      94     1016131 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
      95             :   }
      96       91897 :   return y;
      97             : }
      98             : 
      99             : GEN
     100       20061 : scalar_ZX(GEN x, long v)
     101             : {
     102             :   GEN z;
     103       20061 :   if (!signe(x)) return pol_0(v);
     104        2514 :   z = cgetg(3, t_POL);
     105        2514 :   z[1] = evalsigne(1) | evalvarn(v);
     106        2514 :   gel(z,2) = icopy(x); return z;
     107             : }
     108             : 
     109             : GEN
     110       17057 : scalar_ZX_shallow(GEN x, long v)
     111             : {
     112             :   GEN z;
     113       17057 :   if (!signe(x)) return pol_0(v);
     114       16938 :   z = cgetg(3, t_POL);
     115       16938 :   z[1] = evalsigne(1) | evalvarn(v);
     116       16938 :   gel(z,2) = x; return z;
     117             : }
     118             : 
     119             : GEN
     120       66076 : ZX_Z_add(GEN y, GEN x)
     121             : {
     122             :   long lz, i;
     123       66076 :   GEN z = cgetg_copy(y, &lz);
     124       66076 :   if (lz == 2) { avma = (pari_sp)(z + 2); return scalar_ZX(x,varn(y)); }
     125       66022 :   z[1] = y[1];
     126       66022 :   gel(z,2) = addii(gel(y,2),x);
     127       65979 :   for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
     128       66022 :   if (lz==3) z = ZX_renormalize(z,lz);
     129       66022 :   return z;
     130             : }
     131             : GEN
     132        9308 : ZX_Z_add_shallow(GEN y, GEN x)
     133             : {
     134             :   long lz, i;
     135        9308 :   GEN z = cgetg_copy(y, &lz);
     136        9308 :   if (lz == 2) { avma = (pari_sp)(z + 2); return scalar_ZX_shallow(x,varn(y)); }
     137        9175 :   z[1] = y[1];
     138        9175 :   gel(z,2) = addii(gel(y,2),x);
     139        9175 :   for(i=3; i<lz; i++) gel(z,i) = gel(y,i);
     140        9175 :   if (lz==3) z = ZX_renormalize(z,lz);
     141        9175 :   return z;
     142             : }
     143             : 
     144             : GEN
     145       34426 : ZX_Z_sub(GEN y, GEN x)
     146             : {
     147             :   long lz, i;
     148       34426 :   GEN z = cgetg_copy(y, &lz);
     149       34426 :   if (lz == 2)
     150             :   { /* scalarpol(negi(x), v) */
     151           0 :     long v = varn(y);
     152           0 :     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       34426 :   z[1] = y[1];
     159       34426 :   gel(z,2) = subii(gel(y,2),x);
     160       34426 :   for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
     161       34426 :   if (lz==3) z = ZX_renormalize(z,lz);
     162       34426 :   return z;
     163             : }
     164             : 
     165             : GEN
     166      418919 : Z_ZX_sub(GEN x, GEN y)
     167             : {
     168             :   long lz, i;
     169      418919 :   GEN z = cgetg_copy(y, &lz);
     170      418919 :   if (lz == 2) { avma = (pari_sp)(z + 2); return scalar_ZX(x,varn(y)); }
     171      418919 :   z[1] = y[1];
     172      418919 :   gel(z,2) = subii(x, gel(y,2));
     173      418919 :   for(i=3; i<lz; i++) gel(z,i) = negi(gel(y,i));
     174      418919 :   if (lz==3) z = ZX_renormalize(z,lz);
     175      418919 :   return z;
     176             : }
     177             : 
     178             : GEN
     179     2158367 : ZX_Z_divexact(GEN y,GEN x)
     180             : {
     181     2158367 :   long i, l = lg(y);
     182     2158367 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
     183     2158543 :   for(i=2; i<l; i++) gel(z,i) = diviiexact(gel(y,i),x);
     184     2158367 :   return z;
     185             : }
     186             : 
     187             : GEN
     188     7533391 : ZX_Z_mul(GEN y,GEN x)
     189             : {
     190             :   GEN z;
     191             :   long i, l;
     192     7533391 :   if (!signe(x)) return pol_0(varn(y));
     193     5056025 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     194     5060641 :   for(i=2; i<l; i++) gel(z,i) = mulii(gel(y,i),x);
     195     5056025 :   return z;
     196             : }
     197             : 
     198             : GEN
     199      119686 : ZX_mulu(GEN y, ulong x)
     200             : {
     201             :   GEN z;
     202             :   long i, l;
     203      119686 :   if (!x) return pol_0(varn(y));
     204      119686 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     205      119686 :   for(i=2; i<l; i++) gel(z,i) = mului(x,gel(y,i));
     206      119686 :   return z;
     207             : }
     208             : 
     209             : GEN
     210      176657 : ZX_shifti(GEN y, long n)
     211             : {
     212             :   GEN z;
     213             :   long i, l;
     214      176657 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     215      181840 :   for(i=2; i<l; i++) gel(z,i) = shifti(gel(y,i),n);
     216      176648 :   return ZX_renormalize(z,l);
     217             : }
     218             : 
     219             : GEN
     220       93326 : ZX_remi2n(GEN y, long n)
     221             : {
     222             :   GEN z;
     223             :   long i, l;
     224       93326 :   l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
     225       89092 :   for(i=2; i<l; i++) gel(z,i) = remi2n(gel(y,i),n);
     226       93321 :   return ZX_renormalize(z,l);
     227             : }
     228             : 
     229             : GEN
     230       35982 : ZXT_remi2n(GEN z, long n)
     231             : {
     232       35982 :   if (typ(z) == t_POL)
     233       33058 :     return ZX_remi2n(z, n);
     234             :   else
     235             :   {
     236        2924 :     long i,l = lg(z);
     237        2924 :     GEN x = cgetg(l, t_VEC);
     238        2924 :     for (i=1; i<l; i++) gel(x,i) = ZXT_remi2n(gel(z,i), n);
     239        2924 :     return x;
     240             :   }
     241             : }
     242             : 
     243             : GEN
     244        1764 : zx_to_ZX(GEN z)
     245             : {
     246        1764 :   long i, l = lg(z);
     247        1764 :   GEN x = cgetg(l,t_POL);
     248        1764 :   for (i=2; i<l; i++) gel(x,i) = stoi(z[i]);
     249        1764 :   x[1] = evalsigne(l-2!=0)| z[1]; return x;
     250             : }
     251             : 
     252             : GEN
     253     1408415 : ZX_deriv(GEN x)
     254             : {
     255     1408415 :   long i,lx = lg(x)-1;
     256             :   GEN y;
     257             : 
     258     1408415 :   if (lx<3) return pol_0(varn(x));
     259     1407160 :   y = cgetg(lx,t_POL);
     260     1407169 :   for (i=2; i<lx ; i++) gel(y,i) = mului(i-1,gel(x,i+1));
     261     1407160 :   y[1] = x[1]; return y;
     262             : }
     263             : 
     264             : int
     265      990523 : ZX_equal(GEN V, GEN W)
     266             : {
     267      990523 :   long i, l = lg(V);
     268      990523 :   if (lg(W) != l) return 0;
     269     1401722 :   for (i = 2; i < l; i++)
     270     1356842 :     if (!equalii(gel(V,i), gel(W,i))) return 0;
     271       44880 :   return 1;
     272             : }
     273             : 
     274             : static long
     275   156106995 : ZX_valspec(GEN x, long nx)
     276             : {
     277             :   long vx;
     278   213557941 :   for (vx = 0; vx<nx ; vx++)
     279   213557910 :     if (signe(gel(x,vx))) break;
     280   156106995 :   return vx;
     281             : }
     282             : 
     283             : long
     284       16676 : ZX_val(GEN x)
     285             : {
     286             :   long vx;
     287       16676 :   if (!signe(x)) return LONG_MAX;
     288       18048 :   for (vx = 0;; vx++)
     289       18048 :     if (signe(gel(x,2+vx))) break;
     290        1372 :   return vx;
     291             : }
     292             : long
     293     8803627 : ZX_valrem(GEN x, GEN *Z)
     294             : {
     295             :   long vx;
     296     8803627 :   if (!signe(x)) { *Z = pol_0(varn(x)); return LONG_MAX; }
     297    16040685 :   for (vx = 0;; vx++)
     298    16040685 :     if (signe(gel(x,2+vx))) break;
     299     7237058 :   *Z = RgX_shift_shallow(x, -vx);
     300     8803627 :   return vx;
     301             : }
     302             : 
     303             : GEN
     304          21 : ZX_div_by_X_1(GEN a, GEN *r)
     305             : {
     306          21 :   long l = lg(a), i;
     307          21 :   GEN a0, z0, z = cgetg(l-1, t_POL);
     308          21 :   z[1] = a[1];
     309          21 :   a0 = a + l-1;
     310          21 :   z0 = z + l-2; *z0 = *a0--;
     311        4732 :   for (i=l-3; i>1; i--) /* z[i] = a[i+1] + z[i+1] */
     312             :   {
     313        4711 :     GEN t = addii(gel(a0--,0), gel(z0--,0));
     314        4711 :     gel(z0,0) = t;
     315             :   }
     316          21 :   if (r) *r = addii(gel(a0,0), gel(z0,0));
     317          21 :   return z;
     318             : }
     319             : 
     320             : /* Return 2^(n degpol(P))  P(x >> n), not memory clean if P is a ZX */
     321             : GEN
     322       24313 : ZX_rescale2n(GEN P, long n)
     323             : {
     324       24313 :   long i, l = lg(P), ni = n;
     325       24313 :   GEN Q = cgetg(l,t_POL);
     326       24313 :   Q[l-1] = P[l-1];
     327      256775 :   for (i=l-2; i>=2; i--)
     328             :   {
     329      232462 :     gel(Q,i) = shifti(gel(P,i), ni);
     330      232462 :     ni += n;
     331             :   }
     332       24313 :   Q[1] = P[1]; return Q;
     333             : }
     334             : 
     335             : /* Return h^deg(P) P(x / h), not memory clean. h integer, P ZX */
     336             : GEN
     337       11029 : ZX_rescale(GEN P, GEN h)
     338             : {
     339       11029 :   long l = lg(P);
     340       11029 :   GEN Q = cgetg(l,t_POL);
     341       11029 :   if (l != 2)
     342             :   {
     343       11029 :     long i = l-1;
     344       11029 :     GEN hi = h;
     345       11029 :     gel(Q,i) = gel(P,i);
     346       11029 :     if (l != 3) { i--; gel(Q,i) = mulii(gel(P,i), h); }
     347       11029 :     for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
     348             :   }
     349       11029 :   Q[1] = P[1]; return Q;
     350             : }
     351             : /* Return h^(deg(P)-1) P(x / h), P!=0, h=lt(P), memory unclean; monic result */
     352             : GEN
     353           0 : ZX_rescale_lt(GEN P)
     354             : {
     355           0 :   long l = lg(P);
     356           0 :   GEN Q = cgetg(l,t_POL);
     357           0 :   gel(Q,l-1) = gen_1;
     358           0 :   if (l != 3)
     359             :   {
     360           0 :     long i = l-1;
     361           0 :     GEN h = gel(P,i), hi = h;
     362           0 :     i--; gel(Q,i) = gel(P,i);
     363           0 :     if (l != 4) { i--; gel(Q,i) = mulii(gel(P,i), h); }
     364           0 :     for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
     365             :   }
     366           0 :   Q[1] = P[1]; return Q;
     367             : }
     368             : 
     369             : 
     370             : /*Eval x in 2^(k*BIL) in linear time*/
     371             : static GEN
     372   112198455 : ZX_eval2BILspec(GEN x, long k, long nx)
     373             : {
     374   112198455 :   long i,j, lz = k*nx, ki;
     375   112198455 :   GEN pz = cgetipos(2+lz);
     376   112198394 :   GEN nz = cgetipos(2+lz);
     377  1870214557 :   for(i=0; i < lz; i++)
     378             :   {
     379  1758016014 :     *int_W(pz,i) = 0UL;
     380  1758016014 :     *int_W(nz,i) = 0UL;
     381             :   }
     382   684291688 :   for(i=0, ki=0; i<nx; i++, ki+=k)
     383             :   {
     384   572093145 :     GEN c = gel(x,i);
     385   572093145 :     long lc = lgefint(c)-2;
     386   572093145 :     if (signe(c)==0) continue;
     387   482741299 :     if (signe(c) > 0)
     388   290951794 :       for (j=0; j<lc; j++) *int_W(pz,j+ki) = *int_W(c,j);
     389             :     else
     390   191789505 :       for (j=0; j<lc; j++) *int_W(nz,j+ki) = *int_W(c,j);
     391             :   }
     392   112198543 :   pz = int_normalize(pz,0);
     393   112198562 :   nz = int_normalize(nz,0); return subii(pz,nz);
     394             : }
     395             : 
     396             : static long
     397   116195125 : ZX_expispec(GEN x, long nx)
     398             : {
     399   116195125 :   long i, m = 0;
     400   707744511 :   for(i = 0; i < nx; i++)
     401             :   {
     402   591552839 :     long e = expi(gel(x,i));
     403   591549386 :     if (e > m) m = e;
     404             :   }
     405   116191672 :   return m;
     406             : }
     407             : 
     408             : static GEN
     409    56949190 : Z_mod2BIL_ZX(GEN x, long bs, long d, long vx)
     410             : {
     411    56949190 :   long i, offset, lm = lgefint(x)-2, l = d+vx+3, sx = signe(x);
     412    56949190 :   GEN s1 = int2n(bs*BITS_IN_LONG), pol = cgetg(l, t_POL);
     413    57009820 :   int carry = 0;
     414             : 
     415    57009820 :   for (i=0; i<vx; i++) gel(pol,i+2) = gen_0;
     416   598532950 :   for (offset=0; i <= d+vx; i++, offset += bs)
     417             :   {
     418   541583773 :     pari_sp av = avma;
     419   541583773 :     long lz = minss(bs, lm-offset);
     420   541689773 :     GEN z = adduispec_offset(carry, x, offset, lz);
     421   541241822 :     if (lgefint(z) == 3+bs) { carry = 1; z = gen_0;}
     422             :     else
     423             :     {
     424   531294448 :       carry = (lgefint(z) == 2+bs && (HIGHBIT & *int_W(z,bs-1)));
     425   531294448 :       if (carry)
     426    25596390 :         z = gerepileuptoint(av, (sx==-1)? subii(s1,z): subii(z,s1));
     427   505698058 :       else if (sx==-1) togglesign(z);
     428             :     }
     429   541523130 :     gel(pol,i+2) = z;
     430             :   }
     431    56949177 :   return ZX_renormalize(pol,l);
     432             : }
     433             : 
     434             : static GEN
     435     1699862 : ZX_sqrspec_sqri(GEN x, long nx, long ex, long v)
     436             : {
     437     1699862 :   long e = 2*ex + expu(nx) + 3;
     438     1699862 :   long N = divsBIL(e)+1;
     439     1699862 :   GEN  z = sqri(ZX_eval2BILspec(x,N,nx));
     440     1699862 :   return Z_mod2BIL_ZX(z, N, nx*2-2, v);
     441             : }
     442             : 
     443             : static GEN
     444    55249350 : ZX_mulspec_mulii(GEN x, GEN y, long nx, long ny, long ex, long ey, long v)
     445             : {
     446    55249350 :   long e = ex + ey + expu(minss(nx,ny)) + 3;
     447    55249346 :   long N = divsBIL(e)+1;
     448    55249345 :   GEN  z = mulii(ZX_eval2BILspec(x,N,nx), ZX_eval2BILspec(y,N,ny));
     449    55249340 :   return Z_mod2BIL_ZX(z, N, nx+ny-2, v);
     450             : }
     451             : 
     452             : INLINE GEN
     453    34888964 : ZX_sqrspec_basecase_limb(GEN x, long a, long i)
     454             : {
     455    34888964 :   pari_sp av = avma;
     456    34888964 :   GEN s = gen_0;
     457    34888964 :   long j, l = (i+1)>>1;
     458   140024503 :   for (j=a; j<l; j++)
     459             :   {
     460   105033757 :     GEN xj = gel(x,j), xx = gel(x,i-j);
     461   105033757 :     if (signe(xj) && signe(xx))
     462   103284118 :       s = addii(s, mulii(xj, xx));
     463             :   }
     464    34990746 :   s = shifti(s,1);
     465    34959903 :   if ((i&1) == 0)
     466             :   {
     467    19499183 :     GEN t = gel(x, i>>1);
     468    19499183 :     if (signe(t))
     469    19378181 :       s = addii(s, sqri(t));
     470             :   }
     471    34964911 :   return gerepileuptoint(av,s);
     472             : }
     473             : 
     474             : static GEN
     475     3993452 : ZX_sqrspec_basecase(GEN x, long nx, long v)
     476             : {
     477             :   long i, lz, nz;
     478             :   GEN z;
     479             : 
     480     3993452 :   lz = (nx << 1) + 1; nz = lz-2;
     481     3993452 :   lz += v;
     482     3993452 :   z = cgetg(lz,t_POL); z[1] = evalsigne(1); z += 2;
     483     3993789 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
     484    23498396 :   for (i=0; i<nx; i++)
     485    19504897 :     gel(z,i) = ZX_sqrspec_basecase_limb(x, 0, i);
     486     3993499 :   for (  ; i<nz; i++) gel(z,i) = ZX_sqrspec_basecase_limb(x, i-nx+1, i);
     487     3993486 :   z -= v+2; return z;
     488             : }
     489             : 
     490             : static GEN
     491      236307 : Z_sqrshiftspec_ZX(GEN x, long vx)
     492             : {
     493      236307 :   long i, nz = 2*vx+1;
     494      236307 :   GEN z = cgetg(2+nz, t_POL);
     495      236307 :   z[1] = evalsigne(1);
     496      236307 :   for(i=2;i<nz+1;i++) gel(z,i) = gen_0;
     497      236307 :   gel(z,nz+1) = sqri(x);
     498      236307 :   return z;
     499             : }
     500             : 
     501             : static GEN
     502    19839348 : Z_ZX_mulshiftspec(GEN x, GEN y, long ny, long vz)
     503             : {
     504    19839348 :   long i, nz = vz+ny;
     505    19839348 :   GEN z = cgetg(2+nz, t_POL);
     506    19839352 :   z[1] = evalsigne(1);
     507    19839352 :   for (i=0; i<vz; i++)   gel(z,i+2)    = gen_0;
     508    19839352 :   for (i=0; i<ny; i++) gel(z,i+vz+2) = mulii(x, gel(y,i));
     509    19839348 :   return z;
     510             : }
     511             : 
     512             : GEN
     513     5935972 : ZX_sqrspec(GEN x, long nx)
     514             : {
     515             : #ifdef PARI_KERNEL_GMP
     516     3978490 :   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};
     517     3978490 :   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};
     518             : #else
     519     1957482 :   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};
     520     1957482 :   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};
     521             : #endif
     522     5935972 :   const long nblow = numberof(low);
     523             :   pari_sp av;
     524             :   long ex, vx;
     525             :   GEN z;
     526     5935972 :   if (!nx) return pol_0(0);
     527     5929854 :   vx = ZX_valspec(x,nx); nx-=vx; x+=vx;
     528     5929798 :   if (nx==1) return Z_sqrshiftspec_ZX(gel(x, 0), vx);
     529     5693491 :   av = avma;
     530     5693491 :   ex = ZX_expispec(x,nx);
     531     5693344 :   if (nx-2 < nblow && low[nx-2]<=ex && ex<=high[nx-2])
     532     3993461 :     z = ZX_sqrspec_basecase(x, nx, 2*vx);
     533             :   else
     534     1699883 :     z = ZX_sqrspec_sqri(x, nx, ex, 2*vx);
     535     5693282 :   return gerepileupto(av, z);
     536             : }
     537             : 
     538             : GEN
     539     5935975 : ZX_sqr(GEN x)
     540             : {
     541     5935975 :   GEN z = ZX_sqrspec(x+2, lgpol(x));
     542     5935623 :   z[1] = x[1];
     543     5935623 :   return z;
     544             : }
     545             : 
     546             : GEN
     547    78089381 : ZX_mulspec(GEN x, GEN y, long nx, long ny)
     548             : {
     549             :   pari_sp av;
     550             :   long ex, ey, vx, vy;
     551             :   GEN z;
     552    78089381 :   if (!nx || !ny) return pol_0(0);
     553    75088694 :   vx = ZX_valspec(x,nx); nx-=vx; x += vx;
     554    75088679 :   vy = ZX_valspec(y,ny); ny-=vy; y += vy;
     555    75088685 :   if (nx==1) return Z_ZX_mulshiftspec(gel(x,0), y, ny, vx+vy);
     556    59870816 :   if (ny==1) return Z_ZX_mulshiftspec(gel(y,0), x, nx, vy+vx);
     557    55249337 :   av = avma;
     558    55249337 :   ex = ZX_expispec(x, nx); ey = ZX_expispec(y, ny);
     559    55249345 :   z  = ZX_mulspec_mulii(x,y,nx,ny,ex,ey,vx+vy);
     560    55249329 :   return gerepileupto(av, z);
     561             : }
     562             : GEN
     563    76502875 : ZX_mul(GEN x, GEN y)
     564             : {
     565             :   GEN z;
     566    76502875 :   if (x == y) return ZX_sqr(x);
     567    76431250 :   z = ZX_mulspec(x+2,y+2,lgpol(x),lgpol(y));
     568    76431265 :   z[1] = x[1];
     569    76431265 :   if (!signe(y)) z[1] &= VARNBITS;
     570    76431265 :   return z;
     571             : }
     572             : 
     573             : /* x,y two ZX in the same variable; assume y is monic */
     574             : GEN
     575      146454 : ZX_rem(GEN x, GEN y)
     576             : {
     577             :   long vx, dx, dy, dz, i, j, sx, lr;
     578             :   pari_sp av0, av;
     579             :   GEN z,p1,rem;
     580             : 
     581      146454 :   vx = varn(x);
     582      146454 :   dy = degpol(y);
     583      146454 :   dx = degpol(x);
     584      146454 :   if (dx < dy) return ZX_copy(x);
     585      112252 :   if (!dy) return pol_0(vx); /* y is constant */
     586      112252 :   av0 = avma; dz = dx-dy;
     587      112252 :   z=cgetg(dz+3,t_POL); z[1] = x[1];
     588      112252 :   x += 2; y += 2; z += 2;
     589             : 
     590      112252 :   p1 = gel(x,dx);
     591      112252 :   gel(z,dz) = icopy(p1);
     592     2487688 :   for (i=dx-1; i>=dy; i--)
     593             :   {
     594     2375436 :     av=avma; p1=gel(x,i);
     595    47763485 :     for (j=i-dy+1; j<=i && j<=dz; j++)
     596    45388049 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     597     2375436 :     gel(z,i-dy) = avma == av? icopy(p1): gerepileuptoint(av, p1);
     598             :   }
     599      112252 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     600      478282 :   for (sx=0; ; i--)
     601             :   {
     602      478282 :     p1 = gel(x,i);
     603    10976770 :     for (j=0; j<=i && j<=dz; j++)
     604    10498488 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     605      478282 :     if (signe(p1)) { sx = 1; break; }
     606      366639 :     if (!i) break;
     607      366030 :     avma=av;
     608      366030 :   }
     609      112252 :   lr=i+3; rem -= lr;
     610      112252 :   rem[0] = evaltyp(t_POL) | evallg(lr);
     611      112252 :   rem[1] = z[-1];
     612      112252 :   p1 = gerepileuptoint((pari_sp)rem, p1);
     613      112252 :   rem += 2; gel(rem,i) = p1;
     614     3142734 :   for (i--; i>=0; i--)
     615             :   {
     616     3030482 :     av=avma; p1 = gel(x,i);
     617    61763331 :     for (j=0; j<=i && j<=dz; j++)
     618    58732849 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     619     3030482 :     gel(rem,i) = avma == av? icopy(p1): gerepileuptoint(av, p1);
     620             :   }
     621      112252 :   rem -= 2;
     622      112252 :   if (!sx) (void)ZX_renormalize(rem, lr);
     623      112252 :   return gerepileupto(av0,rem);
     624             : }
     625             : 
     626             : /* return x(1) */
     627             : GEN
     628        4718 : ZX_eval1(GEN x)
     629             : {
     630        4718 :   pari_sp av = avma;
     631        4718 :   long i = lg(x)-1;
     632             :   GEN s;
     633        4718 :   if (i < 2) return gen_0;
     634        4193 :   s = gel(x,i); i--;
     635        4193 :   if (i == 1) return icopy(s);
     636       34608 :   for ( ; i>=2; i--)
     637             :   {
     638       31423 :     GEN c = gel(x,i);
     639       31423 :     if (signe(c)) s = addii(s, c);
     640             :   }
     641        3185 :   return gerepileuptoint(av,s);
     642             : }
     643             : 
     644             : /* reduce T mod X^n - 1. Shallow function */
     645             : GEN
     646     1483092 : ZX_mod_Xnm1(GEN T, ulong n)
     647             : {
     648     1483092 :   long i, j, L = lg(T), l = n+2;
     649             :   GEN S;
     650     1483092 :   if (L <= l) return T;
     651     1316634 :   S = cgetg(l, t_POL);
     652     1316800 :   S[1] = T[1];
     653     1316800 :   for (i = 2; i < l; i++) gel(S,i) = gel(T,i);
     654     6024432 :   for (j = 2; i < L; i++) {
     655     4707791 :     gel(S,j) = addii(gel(S,j), gel(T,i));
     656     4707632 :     if (++j == l) j = 2;
     657             :   }
     658     1316641 :   return normalizepol_lg(S, l);
     659             : }
     660             : 
     661             : /*******************************************************************/
     662             : /*                                                                 */
     663             : /*                                ZXV                              */
     664             : /*                                                                 */
     665             : /*******************************************************************/
     666             : 
     667             : int
     668          35 : ZXV_equal(GEN V, GEN W)
     669             : {
     670          35 :   long l = lg(V);
     671          35 :   if (l!=lg(W)) return 0;
     672          70 :   while (--l > 0)
     673          35 :     if (!ZX_equal(gel(V,l), gel(W,l))) return 0;
     674           0 :   return 1;
     675             : }
     676             : 
     677             : GEN
     678        7476 : ZXV_Z_mul(GEN y, GEN x)
     679             : {
     680             :   long i, l;
     681        7476 :   GEN z = cgetg_copy(y, &l);
     682        7476 :   for(i=1; i<l; i++) gel(z,i) = ZX_Z_mul(gel(y,i), x);
     683        7476 :   return z;
     684             : }
     685             : 
     686             : GEN
     687           0 : ZXV_remi2n(GEN y, long N)
     688             : {
     689             :   long i, l;
     690           0 :   GEN z = cgetg_copy(y, &l);
     691           0 :   for(i=1; i<l; i++) gel(z,i) = ZX_remi2n(gel(y,i), N);
     692           0 :   return z;
     693             : }
     694             : GEN
     695       82250 : ZXV_dotproduct(GEN x, GEN y)
     696             : {
     697       82250 :   pari_sp av = avma;
     698       82250 :   long i, lx = lg(x);
     699             :   GEN c;
     700       82250 :   if (lx == 1) return pol_0(varn(x));
     701       82250 :   c = ZX_mul(gel(x,1), gel(y,1));
     702      388626 :   for (i = 2; i < lx; i++)
     703             :   {
     704      306376 :     GEN t = ZX_mul(gel(x,i), gel(y,i));
     705      306376 :     if (signe(t)) c = ZX_add(c, t);
     706             :   }
     707       82250 :   return gerepileupto(av, c);
     708             : }
     709             : 
     710             : /*******************************************************************/
     711             : /*                                                                 */
     712             : /*                                ZXX                              */
     713             : /*                                                                 */
     714             : /*******************************************************************/
     715             : 
     716             : void
     717          63 : RgX_check_ZXX(GEN x, const char *s)
     718             : {
     719          63 :   long k = lg(x)-1;
     720       10122 :   for ( ; k>1; k--) {
     721       10059 :     GEN t = gel(x,k);
     722       10059 :     switch(typ(t)) {
     723       10045 :       case t_INT: break;
     724          14 :       case t_POL: if (RgX_is_ZX(t)) break;
     725             :       /* fall through */
     726           0 :       default: pari_err_TYPE(stack_strcat(s, " not in Z[X,Y]"),x);
     727             :     }
     728             :   }
     729          63 : }
     730             : 
     731             : /*Renormalize (in place) polynomial with t_INT or ZX coefficients.*/
     732             : GEN
     733   169569826 : ZXX_renormalize(GEN x, long lx)
     734             : {
     735             :   long i;
     736   199313244 :   for (i = lx-1; i>1; i--)
     737   194158133 :     if (signe(gel(x,i))) break;
     738   169569826 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + (i+1)));
     739   169569991 :   setlg(x, i+1); setsigne(x, i!=1); return x;
     740             : }
     741             : 
     742             : long
     743         497 : ZXX_max_lg(GEN x)
     744             : {
     745         497 :   long i, prec = 0, lx = lg(x);
     746        3780 :   for (i=2; i<lx; i++)
     747             :   {
     748        3283 :     GEN p = gel(x,i);
     749        3283 :     long l = (typ(p) == t_INT)? lgefint(p): ZX_max_lg(p);
     750        3283 :     if (l > prec) prec = l;
     751             :   }
     752         497 :   return prec;
     753             : }
     754             : 
     755             : GEN
     756        2058 : ZXX_Z_mul(GEN y, GEN x)
     757             : {
     758        2058 :   long i, l = lg(y);
     759        2058 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
     760      149975 :   for(i=2; i<l; i++)
     761      147917 :     if(typ(gel(y,i))==t_INT)
     762           0 :       gel(z,i) = mulii(gel(y,i),x);
     763             :     else
     764      147917 :       gel(z,i) = ZX_Z_mul(gel(y,i),x);
     765        2058 :   return z;
     766             : }
     767             : 
     768             : GEN
     769          42 : ZXX_Z_add_shallow(GEN x, GEN y)
     770             : {
     771          42 :   long i, l = lg(x);
     772             :   GEN z, a;
     773          42 :   if (signe(x)==0) return scalarpol(y,varn(x));
     774          42 :   z = cgetg(l,t_POL); z[1] = x[1];
     775          42 :   a = gel(x,2);
     776          42 :   gel(z, 2) = typ(a)==t_INT? addii(a,y): ZX_Z_add(a,y);
     777         210 :   for(i=3; i<l; i++)
     778         168 :     gel(z,i) = gel(x,i);
     779          42 :   return z;
     780             : }
     781             : 
     782             : GEN
     783       52920 : ZXX_Z_divexact(GEN y, GEN x)
     784             : {
     785       52920 :   long i, l = lg(y);
     786       52920 :   GEN z = cgetg(l,t_POL); z[1] = y[1];
     787      402815 :   for(i=2; i<l; i++)
     788      349895 :     if(typ(gel(y,i))==t_INT)
     789        2856 :       gel(z,i) = diviiexact(gel(y,i),x);
     790             :     else
     791      347039 :       gel(z,i) = ZX_Z_divexact(gel(y,i),x);
     792       52920 :   return z;
     793             : }
     794             : 
     795             : /* Kronecker substitution, ZXX -> ZX:
     796             :  * P(X,Y) = sum_{0<=i<lP} P_i(X) * Y^i, where deg P_i < n.
     797             :  * Returns P(X,X^(2n-1)) */
     798             : GEN
     799     1371878 : ZXX_to_Kronecker_spec(GEN P, long lP, long n)
     800             : {
     801     1371878 :   long i, k, N = (n<<1) + 1;
     802             :   GEN y;
     803     1371878 :   if (!lP) return pol_0(0);
     804     1371801 :   y = cgetg((N-2)*lP + 2, t_POL) + 2;
     805    15353040 :   for (k=i=0; i<lP; i++)
     806             :   {
     807             :     long j;
     808    15353040 :     GEN c = gel(P,i);
     809    15353040 :     if (typ(c)==t_INT)
     810             :     {
     811      867268 :       gel(y,k++) = c;
     812      867268 :       j = 3;
     813             :     }
     814             :     else
     815             :     {
     816    14485772 :       long l = lg(c);
     817    14485772 :       if (l-3 >= n)
     818           0 :         pari_err_BUG("ZXX_to_Kronecker, P is not reduced mod Q");
     819    14485772 :       for (j=2; j < l; j++) gel(y,k++) = gel(c,j);
     820             :     }
     821    15353040 :     if (i == lP-1) break;
     822    13981239 :     for (   ; j < N; j++) gel(y,k++) = gen_0;
     823             :   }
     824     1371801 :   y-=2; setlg(y, k+2); y[1] = evalsigne(1); return y;
     825             : }
     826             : 
     827             : GEN
     828      563728 : ZXX_to_Kronecker(GEN P, long n)
     829             : {
     830      563728 :   GEN z = ZXX_to_Kronecker_spec(P+2, lgpol(P), n);
     831      563728 :   setvarn(z,varn(P)); return z;
     832             : }

Generated by: LCOV version 1.11