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-bordeaux1.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 - ZV.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 17242-6994acc) Lines: 576 629 91.6 %
Date: 2014-12-22 Functions: 91 99 91.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 381 454 83.9 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2000  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                 :            : static int
      18                 :      32228 : check_ZV(GEN x, long l)
      19                 :            : {
      20                 :            :   long i;
      21         [ +  + ]:     196448 :   for (i=1; i<l; i++)
      22         [ +  + ]:     164304 :     if (typ(gel(x,i)) != t_INT) return 0;
      23                 :      32228 :   return 1;
      24                 :            : }
      25                 :            : void
      26                 :     432480 : RgV_check_ZV(GEN A, const char *s)
      27                 :            : {
      28         [ +  + ]:     432480 :   if (!RgV_is_ZV(A)) pari_err_TYPE(stack_strcat(s," [integer vector]"), A);
      29                 :     432466 : }
      30                 :            : void
      31                 :       8960 : RgM_check_ZM(GEN A, const char *s)
      32                 :            : {
      33                 :       8960 :   long n = lg(A);
      34         [ +  + ]:       8960 :   if (n != 1)
      35                 :            :   {
      36                 :       8925 :     long j, m = lgcols(A);
      37         [ +  + ]:      41069 :     for (j=1; j<n; j++)
      38         [ +  + ]:      32228 :       if (!check_ZV(gel(A,j), m))
      39                 :         84 :         pari_err_TYPE(stack_strcat(s," [integer matrix]"), A);
      40                 :            :   }
      41                 :       8876 : }
      42                 :            : 
      43                 :            : long
      44                 :      10612 : ZV_max_lg(GEN x)
      45                 :            : {
      46                 :      10612 :   long i, prec = 2, m = lg(x);
      47 [ +  + ][ +  + ]:      30072 :   for (i=1; i<m; i++) { long l = lgefint(gel(x,i)); if (l > prec) prec = l; }
      48                 :      10612 :   return prec;
      49                 :            : }
      50                 :            : long
      51                 :       1470 : ZM_max_lg(GEN x)
      52                 :            : {
      53                 :       1470 :   long i, prec = 2, n = lg(x);
      54         [ +  - ]:       1470 :   if (n != 1)
      55                 :            :   {
      56                 :       1470 :     long j, m = lgcols(x);
      57         [ +  + ]:      11424 :     for (j=1; j<n; j++)
      58                 :            :     {
      59                 :       9954 :       GEN c = gel(x,j);
      60 [ +  + ][ +  + ]:     166950 :       for (i=1; i<m; i++) { long l = lgefint(gel(c,i)); if (l > prec) prec = l; }
      61                 :            :     }
      62                 :            :   }
      63                 :       1470 :   return prec;
      64                 :            : }
      65                 :            : 
      66                 :            : GEN
      67                 :        525 : ZM_supnorm(GEN x)
      68                 :            : {
      69                 :        525 :   long i, j, h, lx = lg(x);
      70                 :        525 :   GEN s = gen_0;
      71         [ -  + ]:        525 :   if (lx == 1) return gen_1;
      72                 :        525 :   h = lgcols(x);
      73         [ +  + ]:       6734 :   for (j=1; j<lx; j++)
      74                 :            :   {
      75                 :       6209 :     GEN xj = gel(x,j);
      76         [ +  + ]:     137886 :     for (i=1; i<h; i++)
      77                 :            :     {
      78                 :     131677 :       GEN c = gel(xj,i);
      79         [ +  + ]:     131677 :       if (absi_cmp(c, s) > 0) s = c;
      80                 :            :     }
      81                 :            :   }
      82                 :        525 :   return absi(s);
      83                 :            : }
      84                 :            : 
      85                 :            : /********************************************************************/
      86                 :            : /**                                                                **/
      87                 :            : /**                           MULTIPLICATION                       **/
      88                 :            : /**                                                                **/
      89                 :            : /********************************************************************/
      90                 :            : /* x non-empty ZM, y a compatible nc (dimension > 0). */
      91                 :            : static GEN
      92                 :       3270 : ZM_nc_mul_i(GEN x, GEN y, long c, long l)
      93                 :            : {
      94                 :            :   long i, j;
      95                 :            :   pari_sp av;
      96                 :       3270 :   GEN z = cgetg(l,t_COL), s;
      97                 :            : 
      98         [ +  + ]:      63062 :   for (i=1; i<l; i++)
      99                 :            :   {
     100                 :      59792 :     av = avma; s = muliu(gcoeff(x,i,1),y[1]);
     101         [ +  + ]:    1891228 :     for (j=2; j<c; j++)
     102         [ +  + ]:    1831436 :       if (y[j]) s = addii(s, muliu(gcoeff(x,i,j),y[j]));
     103                 :      59792 :     gel(z,i) = gerepileuptoint(av,s);
     104                 :            :   }
     105                 :       3270 :   return z;
     106                 :            : }
     107                 :            : 
     108                 :            : /* x ZV, y a compatible zc. */
     109                 :            : GEN
     110                 :          0 : ZV_zc_mul(GEN x, GEN y)
     111                 :            : {
     112                 :          0 :   long j, l = lg(x);
     113                 :          0 :   pari_sp av = avma;
     114                 :          0 :   GEN s = mulis(gel(x,1),y[1]);
     115         [ #  # ]:          0 :   for (j=2; j<l; j++)
     116         [ #  # ]:          0 :     if (y[j]) s = addii(s, mulis(gel(x,j),y[j]));
     117                 :          0 :   return gerepileuptoint(av,s);
     118                 :            : }
     119                 :            : 
     120                 :            : /* x non-empty ZM, y a compatible zc (dimension > 0). */
     121                 :            : static GEN
     122                 :    1482736 : ZM_zc_mul_i(GEN x, GEN y, long c, long l)
     123                 :            : {
     124                 :            :   long i, j;
     125                 :            :   pari_sp av;
     126                 :    1482736 :   GEN z = cgetg(l,t_COL), s;
     127                 :            : 
     128         [ +  + ]:   12970205 :   for (i=1; i<l; i++)
     129                 :            :   {
     130                 :   11487469 :     av = avma; s = mulis(gcoeff(x,i,1),y[1]);
     131         [ +  + ]:  240669252 :     for (j=2; j<c; j++)
     132         [ +  + ]:  229181783 :       if (y[j]) s = addii(s, mulis(gcoeff(x,i,j),y[j]));
     133                 :   11487469 :     gel(z,i) = gerepileuptoint(av,s);
     134                 :            :   }
     135                 :    1482736 :   return z;
     136                 :            : }
     137                 :            : GEN
     138                 :    1377260 : ZM_zc_mul(GEN x, GEN y) {
     139                 :    1377260 :   long l = lg(x);
     140         [ -  + ]:    1377260 :   if (l == 1) return cgetg(1, t_COL);
     141                 :    1377260 :   return ZM_zc_mul_i(x,y, l, lgcols(x));
     142                 :            : }
     143                 :            : 
     144                 :            : /* x ZM, y a compatible zm (dimension > 0). */
     145                 :            : GEN
     146                 :      40915 : ZM_zm_mul(GEN x, GEN y)
     147                 :            : {
     148                 :      40915 :   long j, c, l = lg(x), ly = lg(y);
     149                 :      40915 :   GEN z = cgetg(ly, t_MAT);
     150         [ -  + ]:      40915 :   if (l == 1) return z;
     151                 :      40915 :   c = lgcols(x);
     152         [ +  + ]:     146391 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_zc_mul_i(x, gel(y,j), l,c);
     153                 :      40915 :   return z;
     154                 :            : }
     155                 :            : /* x ZM, y a compatible zn (dimension > 0). */
     156                 :            : GEN
     157                 :        262 : ZM_nm_mul(GEN x, GEN y)
     158                 :            : {
     159                 :        262 :   long j, c, l = lg(x), ly = lg(y);
     160                 :        262 :   GEN z = cgetg(ly, t_MAT);
     161         [ -  + ]:        262 :   if (l == 1) return z;
     162                 :        262 :   c = lgcols(x);
     163         [ +  + ]:       3532 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_nc_mul_i(x, gel(y,j), l,c);
     164                 :        262 :   return z;
     165                 :            : }
     166                 :            : 
     167                 :            : /* x[i,]*y. Assume lg(x) > 1 and 0 < i < lgcols(x) */
     168                 :            : static GEN
     169                 :   70478507 : ZMrow_ZC_mul_i(GEN x, GEN y, long i, long lx)
     170                 :            : {
     171                 :   70478507 :   pari_sp av = avma;
     172                 :   70478507 :   GEN c = mulii(gcoeff(x,i,1), gel(y,1)), ZERO = gen_0;
     173                 :            :   long k;
     174         [ +  + ]: 1244985628 :   for (k = 2; k < lx; k++)
     175                 :            :   {
     176                 : 1174507121 :     GEN t = mulii(gcoeff(x,i,k), gel(y,k));
     177         [ +  + ]: 1174507121 :     if (t != ZERO) c = addii(c, t);
     178                 :            :   }
     179                 :   70478507 :   return gerepileuptoint(av, c);
     180                 :            : }
     181                 :            : GEN
     182                 :   20677850 : ZMrow_ZC_mul(GEN x, GEN y, long i)
     183                 :   20677850 : { return ZMrow_ZC_mul_i(x, y, i, lg(x)); }
     184                 :            : 
     185                 :            : /* return x * y, 1 < lx = lg(x), l = lgcols(x) */
     186                 :            : static GEN
     187                 :    9439353 : ZM_ZC_mul_i(GEN x, GEN y, long lx, long l)
     188                 :            : {
     189                 :    9439353 :   GEN z = cgetg(l,t_COL);
     190                 :            :   long i;
     191         [ +  + ]:   59240010 :   for (i=1; i<l; i++) gel(z,i) = ZMrow_ZC_mul_i(x,y,i,lx);
     192                 :    9439353 :   return z;
     193                 :            : }
     194                 :            : GEN
     195                 :    1421523 : ZM_mul(GEN x, GEN y)
     196                 :            : {
     197                 :    1421523 :   long j, l, lx=lg(x), ly=lg(y);
     198                 :            :   GEN z;
     199         [ +  + ]:    1421523 :   if (ly==1) return cgetg(1,t_MAT);
     200         [ +  + ]:    1419346 :   if (lx==1) return zeromat(0, ly-1);
     201                 :    1419227 :   l = lgcols(x); z = cgetg(ly,t_MAT);
     202         [ +  + ]:    7199054 :   for (j=1; j<ly; j++) gel(z,j) = ZM_ZC_mul_i(x, gel(y,j), lx, l);
     203                 :    1421523 :   return z;
     204                 :            : }
     205                 :            : /* assume result is symmetric */
     206                 :            : GEN
     207                 :          0 : ZM_multosym(GEN x, GEN y)
     208                 :            : {
     209                 :          0 :   long j, lx, ly = lg(y);
     210                 :            :   GEN M;
     211         [ #  # ]:          0 :   if (ly == 1) return cgetg(1,t_MAT);
     212                 :          0 :   lx = lg(x); /* = lgcols(y) */
     213         [ #  # ]:          0 :   if (lx == 1) return cgetg(1,t_MAT);
     214                 :            :   /* ly = lgcols(x) */
     215                 :          0 :   M = cgetg(ly, t_MAT);
     216         [ #  # ]:          0 :   for (j=1; j<ly; j++)
     217                 :            :   {
     218                 :          0 :     GEN z = cgetg(ly,t_COL), yj = gel(y,j);
     219                 :            :     long i;
     220         [ #  # ]:          0 :     for (i=1; i<j; i++) gel(z,i) = gcoeff(M,j,i);
     221         [ #  # ]:          0 :     for (i=j; i<ly; i++)gel(z,i) = ZMrow_ZC_mul_i(x,yj,i,lx);
     222                 :          0 :     gel(M,j) = z;
     223                 :            :   }
     224                 :          0 :   return M;
     225                 :            : }
     226                 :            : 
     227                 :            : /* assume lx > 1 is lg(x) = lg(y) */
     228                 :            : static GEN
     229                 :   11879582 : ZV_dotproduct_i(GEN x, GEN y, long lx)
     230                 :            : {
     231                 :   11879582 :   pari_sp av = avma;
     232                 :   11879582 :   GEN c = mulii(gel(x,1), gel(y,1));
     233                 :            :   long i;
     234         [ +  + ]:   95144252 :   for (i = 2; i < lx; i++)
     235                 :            :   {
     236                 :   83264670 :     GEN t = mulii(gel(x,i), gel(y,i));
     237         [ +  + ]:   83264670 :     if (t != gen_0) c = addii(c, t);
     238                 :            :   }
     239                 :   11879582 :   return gerepileuptoint(av, c);
     240                 :            : }
     241                 :            : 
     242                 :            : /* x~ * y, assuming result is symmetric */
     243                 :            : GEN
     244                 :     158088 : ZM_transmultosym(GEN x, GEN y)
     245                 :            : {
     246                 :     158088 :   long i, j, l, ly = lg(y);
     247                 :            :   GEN M;
     248         [ -  + ]:     158088 :   if (ly == 1) return cgetg(1,t_MAT);
     249                 :            :   /* lg(x) = ly */
     250                 :     158088 :   l = lgcols(y); /* = lgcols(x) */
     251                 :     158088 :   M = cgetg(ly, t_MAT);
     252         [ +  + ]:    1231261 :   for (i=1; i<ly; i++)
     253                 :            :   {
     254                 :    1073173 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     255                 :    1073173 :     gel(M,i) = c;
     256         [ +  + ]:    4777823 :     for (j=1; j<i; j++)
     257                 :    3704650 :       gcoeff(M,i,j) = gel(c,j) = ZV_dotproduct_i(xi,gel(y,j),l);
     258                 :    1073173 :     gel(c,i) = ZV_dotproduct_i(xi,gel(y,i),l);
     259                 :            :   }
     260                 :     158088 :   return M;
     261                 :            : }
     262                 :            : /* x~ * y */
     263                 :            : GEN
     264                 :        497 : ZM_transmul(GEN x, GEN y)
     265                 :            : {
     266                 :        497 :   long i, j, l, lx, ly = lg(y);
     267                 :            :   GEN M;
     268         [ -  + ]:        497 :   if (ly == 1) return cgetg(1,t_MAT);
     269                 :        497 :   lx = lg(x);
     270                 :        497 :   l = lgcols(y);
     271         [ -  + ]:        497 :   if (lgcols(x) != l) pari_err_OP("operation 'ZM_transmul'", x,y);
     272                 :        497 :   M = cgetg(ly, t_MAT);
     273         [ +  + ]:       1617 :   for (i=1; i<ly; i++)
     274                 :            :   {
     275                 :       1120 :     GEN yi = gel(y,i), c = cgetg(lx,t_COL);
     276                 :       1120 :     gel(M,i) = c;
     277         [ +  + ]:       5061 :     for (j=1; j<lx; j++) gel(c,j) = ZV_dotproduct_i(yi,gel(x,j),l);
     278                 :            :   }
     279                 :        497 :   return M;
     280                 :            : }
     281                 :            : GEN
     282                 :         42 : ZM_sqr(GEN x)
     283                 :            : {
     284                 :         42 :   long j, l, lx=lg(x);
     285                 :            :   GEN z;
     286         [ -  + ]:         42 :   if (lx==1) return cgetg(1,t_MAT);
     287                 :         42 :   l = lgcols(x); z = cgetg(lx,t_MAT);
     288         [ +  + ]:        126 :   for (j=1; j<lx; j++) gel(z,j) = ZM_ZC_mul_i(x, gel(x,j), lx, l);
     289                 :         42 :   return z;
     290                 :            : }
     291                 :            : GEN
     292                 :    3687401 : ZM_ZC_mul(GEN x, GEN y)
     293                 :            : {
     294                 :    3687401 :   long lx = lg(x);
     295         [ +  + ]:    3687401 :   return lx==1? cgetg(1,t_COL): ZM_ZC_mul_i(x, y, lx, lgcols(x));
     296                 :            : }
     297                 :            : 
     298                 :            : GEN
     299                 :       1547 : ZM_Z_div(GEN X, GEN c)
     300                 :            : {
     301                 :       1547 :   long i, j, h, l = lg(X);
     302                 :       1547 :   GEN A = cgetg(l, t_MAT);
     303         [ -  + ]:       1547 :   if (l == 1) return A;
     304                 :       1547 :   h = lgcols(X);
     305         [ +  + ]:      26299 :   for (j=1; j<l; j++)
     306                 :            :   {
     307                 :      24752 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     308         [ +  + ]:     530978 :     for (i = 1; i < h; i++) gel(a,i) = gred_frac2(gel(x,i), c);
     309                 :      24752 :     gel(A,j) = a;
     310                 :            :   }
     311                 :       1547 :   return A;
     312                 :            : }
     313                 :            : 
     314                 :            : long
     315                 :  125500697 : zv_dotproduct(GEN x, GEN y)
     316                 :            : {
     317                 :  125500697 :   long i, lx = lg(x);
     318                 :            :   ulong c;
     319         [ -  + ]:  125500697 :   if (lx == 1) return 0;
     320                 :  125500697 :   c = uel(x,1)*uel(y,1);
     321         [ +  + ]: 1947333227 :   for (i = 2; i < lx; i++)
     322                 : 1821832530 :     c += uel(x,i)*uel(y,i);
     323                 :  125500697 :   return c;
     324                 :            : }
     325                 :            : 
     326                 :            : GEN
     327                 :       3304 : ZV_ZM_mul(GEN x, GEN y)
     328                 :            : {
     329                 :       3304 :   long i, lx = lg(x), ly = lg(y);
     330                 :            :   GEN z;
     331         [ -  + ]:       3304 :   if (lx == 1) return zerovec(ly-1);
     332                 :       3304 :   z = cgetg(ly, t_VEC);
     333         [ +  + ]:      10094 :   for (i = 1; i < ly; i++) gel(z,i) = ZV_dotproduct_i(x, gel(y,i), lx);
     334                 :       3304 :   return z;
     335                 :            : }
     336                 :            : 
     337                 :            : GEN
     338                 :          0 : ZC_ZV_mul(GEN x, GEN y)
     339                 :            : {
     340                 :          0 :   long i,j, lx=lg(x), ly=lg(y);
     341                 :            :   GEN z;
     342         [ #  # ]:          0 :   if (ly==1) return cgetg(1,t_MAT);
     343                 :          0 :   z = cgetg(ly,t_MAT);
     344         [ #  # ]:          0 :   for (j=1; j < ly; j++)
     345                 :            :   {
     346                 :          0 :     gel(z,j) = cgetg(lx,t_COL);
     347         [ #  # ]:          0 :     for (i=1; i<lx; i++) gcoeff(z,i,j) = mulii(gel(x,i),gel(y,j));
     348                 :            :   }
     349                 :          0 :   return z;
     350                 :            : }
     351                 :            : 
     352                 :            : GEN
     353                 :    4033401 : ZV_dotsquare(GEN x)
     354                 :            : {
     355                 :            :   long i, lx;
     356                 :            :   pari_sp av;
     357                 :            :   GEN z;
     358                 :    4033401 :   lx = lg(x);
     359         [ -  + ]:    4033401 :   if (lx == 1) return gen_0;
     360                 :    4033401 :   av = avma; z = sqri(gel(x,1));
     361         [ +  + ]:   16046418 :   for (i=2; i<lx; i++) z = addii(z, sqri(gel(x,i)));
     362                 :    4033401 :   return gerepileuptoint(av,z);
     363                 :            : }
     364                 :            : 
     365                 :            : GEN
     366                 :   10014312 : ZV_dotproduct(GEN x,GEN y)
     367                 :            : {
     368                 :            :   long lx;
     369         [ +  + ]:   10014312 :   if (x == y) return ZV_dotsquare(x);
     370                 :    7091028 :   lx = lg(x);
     371         [ -  + ]:    7091028 :   if (lx == 1) return gen_0;
     372                 :   10014312 :   return ZV_dotproduct_i(x, y, lx);
     373                 :            : }
     374                 :            : 
     375                 :            : static GEN
     376                 :        217 : _ZM_mul(void *data /*ignored*/, GEN x, GEN y)
     377                 :        217 : { (void)data; return ZM_mul(x,y); }
     378                 :            : static GEN
     379                 :      32788 : _ZM_sqr(void *data /*ignored*/, GEN x)
     380                 :      32788 : { (void)data; return ZM_mul(x,x); }
     381                 :            : GEN
     382                 :          0 : ZM_pow(GEN x, GEN n)
     383                 :            : {
     384                 :          0 :   pari_sp av = avma;
     385         [ #  # ]:          0 :   if (!signe(n)) return matid(lg(x)-1);
     386                 :          0 :   return gerepileupto(av, gen_pow(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     387                 :            : }
     388                 :            : GEN
     389                 :      31332 : ZM_powu(GEN x, ulong n)
     390                 :            : {
     391                 :      31332 :   pari_sp av = avma;
     392         [ -  + ]:      31332 :   if (!n) return matid(lg(x)-1);
     393                 :      31332 :   return gerepileupto(av, gen_powu(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     394                 :            : }
     395                 :            : /********************************************************************/
     396                 :            : /**                                                                **/
     397                 :            : /**                           ADD, SUB                             **/
     398                 :            : /**                                                                **/
     399                 :            : /********************************************************************/
     400                 :            : static GEN
     401                 :    1348026 : ZC_add_i(GEN x, GEN y, long lx)
     402                 :            : {
     403                 :    1348026 :   GEN A = cgetg(lx, t_COL);
     404                 :            :   long i;
     405         [ +  + ]:   16139602 :   for (i=1; i<lx; i++) gel(A,i) = addii(gel(x,i), gel(y,i));
     406                 :    1348026 :   return A;
     407                 :            : }
     408                 :            : GEN
     409                 :    1033316 : ZC_add(GEN x, GEN y) { return ZC_add_i(x, y, lg(x)); }
     410                 :            : GEN
     411                 :      69538 : ZC_Z_add(GEN x, GEN y)
     412                 :            : {
     413                 :      69538 :   long k, lx = lg(x);
     414                 :      69538 :   GEN z = cgetg(lx, t_COL);
     415         [ -  + ]:      69538 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     416                 :      69538 :   gel(z,1) = addii(y,gel(x,1));
     417         [ +  + ]:     882609 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     418                 :      69538 :   return z;
     419                 :            : }
     420                 :            : 
     421                 :            : static GEN
     422                 :    1069597 : ZC_sub_i(GEN x, GEN y, long lx)
     423                 :            : {
     424                 :            :   long i;
     425                 :    1069597 :   GEN A = cgetg(lx, t_COL);
     426         [ +  + ]:    7004737 :   for (i=1; i<lx; i++) gel(A,i) = subii(gel(x,i), gel(y,i));
     427                 :    1069597 :   return A;
     428                 :            : }
     429                 :            : GEN
     430                 :    1017635 : ZC_sub(GEN x, GEN y) { return ZC_sub_i(x, y, lg(x)); }
     431                 :            : GEN
     432                 :          0 : ZC_Z_sub(GEN x, GEN y)
     433                 :            : {
     434                 :          0 :   long k, lx = lg(x);
     435                 :          0 :   GEN z = cgetg(lx, t_COL);
     436         [ #  # ]:          0 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     437                 :          0 :   gel(z,1) = subii(gel(x,1), y);
     438         [ #  # ]:          0 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     439                 :          0 :   return z;
     440                 :            : }
     441                 :            : 
     442                 :            : GEN
     443                 :      22119 : ZM_add(GEN x, GEN y)
     444                 :            : {
     445                 :      22119 :   long lx = lg(x), l, j;
     446                 :            :   GEN z;
     447         [ +  + ]:      22119 :   if (lx == 1) return cgetg(1, t_MAT);
     448                 :      20873 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     449         [ +  + ]:     335583 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_add_i(gel(x,j), gel(y,j), l);
     450                 :      22119 :   return z;
     451                 :            : }
     452                 :            : GEN
     453                 :      10573 : ZM_sub(GEN x, GEN y)
     454                 :            : {
     455                 :      10573 :   long lx = lg(x), l, j;
     456                 :            :   GEN z;
     457         [ -  + ]:      10573 :   if (lx == 1) return cgetg(1, t_MAT);
     458                 :      10573 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     459         [ +  + ]:      62535 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_sub_i(gel(x,j), gel(y,j), l);
     460                 :      10573 :   return z;
     461                 :            : }
     462                 :            : /********************************************************************/
     463                 :            : /**                                                                **/
     464                 :            : /**                         LINEAR COMBINATION                     **/
     465                 :            : /**                                                                **/
     466                 :            : /********************************************************************/
     467                 :            : /* return X/c assuming division is exact */
     468                 :            : GEN
     469                 :     548360 : ZC_Z_divexact(GEN X, GEN c)
     470                 :            : {
     471                 :     548360 :   long i, l = lg(X);
     472                 :     548360 :   GEN A = cgetg(l, t_COL);
     473         [ +  + ]:   10591629 :   for (i=1; i<l; i++) gel(A,i) = diviiexact(gel(X,i), c);
     474                 :     548360 :   return A;
     475                 :            : }
     476                 :            : GEN
     477                 :      47967 : ZM_Z_divexact(GEN X, GEN c)
     478                 :            : {
     479                 :      47967 :   long i, l = lg(X);
     480                 :      47967 :   GEN A = cgetg(l, t_MAT);
     481         [ +  + ]:     444371 :   for (i = 1; i < l; i++) gel(A,i) = ZC_Z_divexact(gel(X,i), c);
     482                 :      47967 :   return A;
     483                 :            : }
     484                 :            : /* Return c * X */
     485                 :            : GEN
     486                 :    2445740 : ZC_Z_mul(GEN X, GEN c)
     487                 :            : {
     488                 :            :   long i, l;
     489                 :            :   GEN A;
     490         [ +  + ]:    2445740 :   if (!signe(c)) return zerocol(lg(X)-1);
     491 [ +  + ][ +  + ]:    2423529 :   if (is_pm1(c)) return (signe(c) > 0)? ZC_copy(X): ZC_neg(X);
     492                 :    2349524 :   l = lg(X); A = cgetg(l, t_COL);
     493         [ +  + ]:   14340551 :   for (i=1; i<l; i++) gel(A,i) = mulii(c,gel(X,i));
     494                 :    2445740 :   return A;
     495                 :            : }
     496                 :            : GEN
     497                 :      12789 : ZC_z_mul(GEN X, long c)
     498                 :            : {
     499                 :            :   long i, l;
     500                 :            :   GEN A;
     501         [ +  + ]:      12789 :   if (!c) return zerocol(lg(X)-1);
     502         [ +  + ]:       6664 :   if (c == 1) return ZC_copy(X);
     503         [ +  + ]:       2191 :   if (c ==-1) return ZC_neg(X);
     504                 :        728 :   l = lg(X); A = cgetg(l, t_COL);
     505         [ +  + ]:       2198 :   for (i=1; i<l; i++) gel(A,i) = mulsi(c,gel(X,i));
     506                 :      12789 :   return A;
     507                 :            : }
     508                 :            : 
     509                 :            : GEN
     510                 :       4396 : zv_z_mul(GEN M, long n)
     511                 :            : {
     512                 :            :   long l;
     513                 :       4396 :   GEN N = cgetg_copy(M, &l);
     514         [ +  + ]:      18256 :   while (--l > 0) N[l] = M[l]*n;
     515                 :       4396 :   return N;
     516                 :            : }
     517                 :            : 
     518                 :            : /* return a ZM */
     519                 :            : GEN
     520                 :        262 : nm_Z_mul(GEN X, GEN c)
     521                 :            : {
     522                 :        262 :   long i, j, h, l = lg(X), s = signe(c);
     523                 :            :   GEN A;
     524         [ -  + ]:        262 :   if (l == 1) return cgetg(1, t_MAT);
     525                 :        262 :   h = lgcols(X);
     526         [ -  + ]:        262 :   if (!s) return zeromat(h-1, l-1);
     527         [ -  + ]:        262 :   if (is_pm1(c)) {
     528         [ #  # ]:          0 :     if (s > 0) return Flm_to_ZM(X);
     529                 :          0 :     X = Flm_to_ZM(X); ZM_togglesign(X); return X;
     530                 :            :   }
     531                 :        262 :   A = cgetg(l, t_MAT);
     532         [ +  + ]:       3532 :   for (j = 1; j < l; j++)
     533                 :            :   {
     534                 :       3270 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     535         [ +  + ]:      63062 :     for (i = 1; i < h; i++) gel(a,i) = muliu(c, x[i]);
     536                 :       3270 :     gel(A,j) = a;
     537                 :            :   }
     538                 :        262 :   return A;
     539                 :            : }
     540                 :            : GEN
     541                 :      46659 : ZM_Z_mul(GEN X, GEN c)
     542                 :            : {
     543                 :      46659 :   long i, j, h, l = lg(X);
     544                 :            :   GEN A;
     545         [ -  + ]:      46659 :   if (l == 1) return cgetg(1, t_MAT);
     546                 :      46659 :   h = lgcols(X);
     547         [ +  + ]:      46659 :   if (!signe(c)) return zeromat(h-1, l-1);
     548 [ +  + ][ +  + ]:      46610 :   if (is_pm1(c)) return (signe(c) > 0)? ZM_copy(X): ZM_neg(X);
     549                 :      29530 :   A = cgetg(l, t_MAT);
     550         [ +  + ]:     187780 :   for (j = 1; j < l; j++)
     551                 :            :   {
     552                 :     158250 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     553         [ +  + ]:    2607430 :     for (i = 1; i < h; i++) gel(a,i) = mulii(c, gel(x,i));
     554                 :     158250 :     gel(A,j) = a;
     555                 :            :   }
     556                 :      46659 :   return A;
     557                 :            : }
     558                 :            : 
     559                 :            : /* X <- X + v Y (elementary col operation) */
     560                 :            : void
     561                 :   34919818 : ZC_lincomb1_inplace(GEN X, GEN Y, GEN v)
     562                 :            : {
     563                 :   34919818 :   long i, m = lgefint(v);
     564         [ -  + ]:   69839636 :   if (m == 2) return; /* v = 0 */
     565         [ +  + ]:  758255530 :   for (i = lg(X)-1; i; i--) gel(X,i) = addmulii_inplace(gel(X,i), gel(Y,i), v);
     566                 :            : }
     567                 :            : void
     568                 :    7373724 : Flc_lincomb1_inplace(GEN X, GEN Y, ulong v, ulong q)
     569                 :            : {
     570                 :            :   long i;
     571         [ -  + ]:   14747448 :   if (!v) return; /* v = 0 */
     572         [ +  + ]:  261894635 :   for (i = lg(X)-1; i; i--) X[i] = Fl_add(X[i], Fl_mul(Y[i], v, q), q);
     573                 :            : }
     574                 :            : 
     575                 :            : /* X + v Y, wasteful if (v = 0) */
     576                 :            : static GEN
     577                 :    2344541 : ZC_lincomb1(GEN v, GEN X, GEN Y)
     578                 :            : {
     579                 :    2344541 :   long i, lx = lg(X);
     580                 :    2344541 :   GEN A = cgetg(lx,t_COL);
     581         [ +  + ]:   28755381 :   for (i=1; i<lx; i++) gel(A,i) = addmulii(gel(X,i), gel(Y,i), v);
     582                 :    2344541 :   return A;
     583                 :            : }
     584                 :            : /* -X + vY */
     585                 :            : static GEN
     586                 :     370070 : ZC_lincomb_1(GEN v, GEN X, GEN Y)
     587                 :            : {
     588                 :     370070 :   long i, lx = lg(X);
     589                 :     370070 :   GEN A = cgetg(lx,t_COL);
     590         [ +  + ]:    2083340 :   for (i=1; i<lx; i++) gel(A,i) = mulsubii(gel(Y,i), v, gel(X,i));
     591                 :     370070 :   return A;
     592                 :            : }
     593                 :            : /* X,Y compatible ZV; u,v in Z. Returns A = u*X + v*Y */
     594                 :            : GEN
     595                 :    7361934 : ZC_lincomb(GEN u, GEN v, GEN X, GEN Y)
     596                 :            : {
     597                 :            :   long su, sv;
     598                 :            :   GEN A;
     599                 :            : 
     600         [ -  + ]:    7361934 :   su = signe(u); if (!su) return ZC_Z_mul(Y, v);
     601         [ +  + ]:    7361934 :   sv = signe(v); if (!sv) return ZC_Z_mul(X, u);
     602         [ +  + ]:    7361927 :   if (is_pm1(v))
     603                 :            :   {
     604         [ +  + ]:    1638415 :     if (is_pm1(u))
     605                 :            :     {
     606         [ +  + ]:    1029286 :       if (su != sv) A = ZC_sub(X, Y);
     607                 :     457818 :       else          A = ZC_add(X, Y);
     608         [ +  + ]:    1029286 :       if (su < 0) ZV_togglesign(A); /* in place but was created above */
     609                 :            :     }
     610                 :            :     else
     611                 :            :     {
     612         [ +  + ]:     609129 :       if (sv > 0) A = ZC_lincomb1 (u, Y, X);
     613                 :     265941 :       else        A = ZC_lincomb_1(u, Y, X);
     614                 :            :     }
     615                 :            :   }
     616         [ +  + ]:    5723512 :   else if (is_pm1(u))
     617                 :            :   {
     618         [ +  + ]:    2105482 :     if (su > 0) A = ZC_lincomb1 (v, X, Y);
     619                 :     104129 :     else        A = ZC_lincomb_1(v, X, Y);
     620                 :            :   }
     621                 :            :   else
     622                 :            :   { /* not cgetg_copy: x may be a t_VEC */
     623                 :    3618030 :     long i, lx = lg(X);
     624                 :    3618030 :     A = cgetg(lx,t_COL);
     625         [ +  + ]:   21405408 :     for (i=1; i<lx; i++) gel(A,i) = lincombii(u,v,gel(X,i),gel(Y,i));
     626                 :            :   }
     627                 :    7361934 :   return A;
     628                 :            : }
     629                 :            : 
     630                 :            : /********************************************************************/
     631                 :            : /**                                                                **/
     632                 :            : /**                           CONVERSIONS                          **/
     633                 :            : /**                                                                **/
     634                 :            : /********************************************************************/
     635                 :            : GEN
     636                 :        532 : ZV_to_nv(GEN z)
     637                 :            : {
     638                 :        532 :   long i, l = lg(z);
     639                 :        532 :   GEN x = cgetg(l, t_VECSMALL);
     640         [ +  + ]:        784 :   for (i=1; i<l; i++) x[i] = itou(gel(z,i));
     641                 :        532 :   return x;
     642                 :            : }
     643                 :            : 
     644                 :            : GEN
     645                 :      55874 : zm_to_ZM(GEN z)
     646                 :            : {
     647                 :      55874 :   long i, l = lg(z);
     648                 :      55874 :   GEN x = cgetg(l,t_MAT);
     649         [ +  + ]:     223762 :   for (i=1; i<l; i++) gel(x,i) = zc_to_ZC(gel(z,i));
     650                 :      55874 :   return x;
     651                 :            : }
     652                 :            : 
     653                 :            : GEN
     654                 :         63 : zmV_to_ZMV(GEN z)
     655                 :            : {
     656                 :         63 :   long i, l = lg(z);
     657                 :         63 :   GEN x = cgetg(l,t_VEC);
     658         [ +  + ]:        490 :   for (i=1; i<l; i++) gel(x,i) = zm_to_ZM(gel(z,i));
     659                 :         63 :   return x;
     660                 :            : }
     661                 :            : 
     662                 :            : /* same as Flm_to_ZM but do not assume positivity */
     663                 :            : GEN
     664                 :        238 : ZM_to_zm(GEN z)
     665                 :            : {
     666                 :        238 :   long i, l = lg(z);
     667                 :        238 :   GEN x = cgetg(l,t_MAT);
     668         [ +  + ]:     184548 :   for (i=1; i<l; i++) gel(x,i) = ZV_to_zv(gel(z,i));
     669                 :        238 :   return x;
     670                 :            : }
     671                 :            : 
     672                 :            : GEN
     673                 :     181720 : zv_to_Flv(GEN z, ulong p)
     674                 :            : {
     675                 :     181720 :   long i, l = lg(z);
     676                 :     181720 :   GEN x = cgetg(l,t_VECSMALL);
     677         [ +  + ]:    2877560 :   for (i=1; i<l; i++) x[i] = umodsu(z[i], p);
     678                 :     181720 :   return x;
     679                 :            : }
     680                 :            : 
     681                 :            : GEN
     682                 :      12460 : zm_to_Flm(GEN z, ulong p)
     683                 :            : {
     684                 :      12460 :   long i, l = lg(z);
     685                 :      12460 :   GEN x = cgetg(l,t_MAT);
     686         [ +  + ]:     194180 :   for (i=1; i<l; i++) gel(x,i) = zv_to_Flv(gel(z,i),p);
     687                 :      12460 :   return x;
     688                 :            : }
     689                 :            : 
     690                 :            : GEN
     691                 :          0 : ZMV_to_zmV(GEN z)
     692                 :            : {
     693                 :          0 :   long i,l = lg(z);
     694                 :          0 :   GEN x = cgetg(l, t_VEC);
     695         [ #  # ]:          0 :   for (i=1; i<l; i++) gel(x,i) = ZM_to_zm(gel(z,i));
     696                 :          0 :   return x;
     697                 :            : }
     698                 :            : 
     699                 :            : /********************************************************************/
     700                 :            : /**                                                                **/
     701                 :            : /**                         COPY, NEGATION                         **/
     702                 :            : /**                                                                **/
     703                 :            : /********************************************************************/
     704                 :            : GEN
     705                 :     638264 : ZC_copy(GEN x)
     706                 :            : {
     707                 :     638264 :   long i, lx = lg(x);
     708                 :     638264 :   GEN y = cgetg(lx, t_COL);
     709         [ +  + ]:    6686729 :   for (i=1; i<lx; i++)
     710                 :            :   {
     711                 :    6048465 :     GEN c = gel(x,i);
     712         [ +  + ]:    6048465 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
     713                 :            :   }
     714                 :     638264 :   return y;
     715                 :            : }
     716                 :            : 
     717                 :            : GEN
     718                 :      42021 : ZM_copy(GEN x)
     719                 :            : {
     720                 :            :   long l;
     721                 :      42021 :   GEN y = cgetg_copy(x, &l);
     722         [ +  + ]:     459657 :   while (--l > 0) gel(y,l) = ZC_copy(gel(x,l));
     723                 :      42021 :   return y;
     724                 :            : }
     725                 :            : 
     726                 :            : void
     727                 :      57717 : ZV_neg_inplace(GEN M)
     728                 :            : {
     729                 :      57717 :   long l = lg(M);
     730         [ +  + ]:     438570 :   while (--l > 0) gel(M,l) = negi(gel(M,l));
     731                 :      57717 : }
     732                 :            : GEN
     733                 :    1233572 : ZC_neg(GEN M)
     734                 :            : {
     735                 :    1233572 :   long l = lg(M);
     736                 :    1233572 :   GEN N = cgetg(l, t_COL);
     737         [ +  + ]:    9876848 :   while (--l > 0) gel(N,l) = negi(gel(M,l));
     738                 :    1233572 :   return N;
     739                 :            : }
     740                 :            : GEN
     741                 :     187446 : zv_neg(GEN M)
     742                 :            : {
     743                 :            :   long l;
     744                 :     187446 :   GEN N = cgetg_copy(M, &l);
     745         [ +  + ]:    1592987 :   while (--l > 0) N[l] = -M[l];
     746                 :     187446 :   return N;
     747                 :            : }
     748                 :            : GEN
     749                 :        154 : zv_neg_inplace(GEN M)
     750                 :            : {
     751                 :        154 :   long l = lg(M);
     752         [ +  + ]:        567 :   while (--l > 0) M[l] = -M[l];
     753                 :        154 :   return M;
     754                 :            : }
     755                 :            : GEN
     756                 :       6587 : ZM_neg(GEN x)
     757                 :            : {
     758                 :            :   long l;
     759                 :       6587 :   GEN y = cgetg_copy(x, &l);
     760         [ +  + ]:      41440 :   while (--l > 0) gel(y,l) = ZC_neg(gel(x,l));
     761                 :       6587 :   return y;
     762                 :            : }
     763                 :            : 
     764                 :            : void
     765                 :     893963 : ZV_togglesign(GEN M)
     766                 :            : {
     767                 :     893963 :   long l = lg(M);
     768         [ +  + ]:   23945614 :   while (--l > 0) togglesign_safe(&gel(M,l));
     769                 :     893963 : }
     770                 :            : void
     771                 :          0 : ZM_togglesign(GEN M)
     772                 :            : {
     773                 :          0 :   long l = lg(M);
     774         [ #  # ]:          0 :   while (--l > 0) ZV_togglesign(gel(M,l));
     775                 :          0 : }
     776                 :            : 
     777                 :            : /********************************************************************/
     778                 :            : /**                                                                **/
     779                 :            : /**                        "DIVISION" mod HNF                      **/
     780                 :            : /**                                                                **/
     781                 :            : /********************************************************************/
     782                 :            : /* Reduce ZC x modulo ZM y in HNF, may return x itself (not a copy) */
     783                 :            : GEN
     784                 :     804133 : ZC_hnfremdiv(GEN x, GEN y, GEN *Q)
     785                 :            : {
     786                 :     804133 :   long i, l = lg(x);
     787                 :            :   GEN q;
     788                 :            : 
     789         [ +  + ]:     804133 :   if (Q) *Q = cgetg(l,t_COL);
     790         [ -  + ]:     804133 :   if (l == 1) return cgetg(1,t_COL);
     791         [ +  + ]:    4933539 :   for (i = l-1; i>0; i--)
     792                 :            :   {
     793                 :    4129406 :     q = diviiround(gel(x,i), gcoeff(y,i,i));
     794         [ +  + ]:    4129406 :     if (signe(q)) {
     795                 :    2303896 :       togglesign(q);
     796                 :    2303896 :       x = ZC_lincomb(gen_1, q, x, gel(y,i));
     797                 :            :     }
     798         [ +  + ]:    4129406 :     if (Q) gel(*Q, i) = q;
     799                 :            :   }
     800                 :     804133 :   return x;
     801                 :            : }
     802                 :            : 
     803                 :            : /* x = y Q + R, may return some columns of x (not copies) */
     804                 :            : GEN
     805                 :      29277 : ZM_hnfdivrem(GEN x, GEN y, GEN *Q)
     806                 :            : {
     807                 :      29277 :   long lx = lg(x), i;
     808                 :      29277 :   GEN R = cgetg(lx, t_MAT);
     809         [ +  + ]:      29277 :   if (Q)
     810                 :            :   {
     811                 :       3188 :     GEN q = cgetg(lx, t_MAT); *Q = q;
     812         [ +  + ]:       6012 :     for (i=1; i<lx; i++) gel(R,i) = ZC_hnfremdiv(gel(x,i),y,(GEN*)(q+i));
     813                 :            :   }
     814                 :            :   else
     815         [ +  + ]:      99617 :     for (i=1; i<lx; i++)
     816                 :            :     {
     817                 :      73528 :       pari_sp av = avma;
     818                 :      73528 :       GEN z = ZC_hnfrem(gel(x,i),y);
     819         [ +  + ]:      73528 :       gel(R,i) = (avma == av)? ZC_copy(z): gerepileupto(av, z);
     820                 :            :     }
     821                 :      29277 :   return R;
     822                 :            : }
     823                 :            : 
     824                 :            : 
     825                 :            : /********************************************************************/
     826                 :            : /**                                                                **/
     827                 :            : /**                               TESTS                            **/
     828                 :            : /**                                                                **/
     829                 :            : /********************************************************************/
     830                 :            : int
     831                 :   13928992 : zv_equal0(GEN V)
     832                 :            : {
     833                 :   13928992 :   long l = lg(V);
     834         [ +  + ]:   22053507 :   while (--l > 0)
     835         [ +  + ]:   17506818 :     if (V[l]) return 0;
     836                 :   13928992 :   return 1;
     837                 :            : }
     838                 :            : 
     839                 :            : int
     840                 :     312604 : ZV_equal0(GEN V)
     841                 :            : {
     842                 :     312604 :   long l = lg(V);
     843         [ +  + ]:    1350200 :   while (--l > 0)
     844         [ +  + ]:    1276756 :     if (signe(gel(V,l))) return 0;
     845                 :     312604 :   return 1;
     846                 :            : }
     847                 :            : 
     848                 :            : static int
     849                 :    8969078 : ZV_equal_lg(GEN V, GEN W, long l)
     850                 :            : {
     851         [ +  + ]:   16165874 :   while (--l > 0)
     852         [ +  + ]:   14207208 :     if (!equalii(gel(V,l), gel(W,l))) return 0;
     853                 :    8969078 :   return 1;
     854                 :            : }
     855                 :            : int
     856                 :    7768208 : ZV_equal(GEN V, GEN W)
     857                 :            : {
     858                 :    7768208 :   long l = lg(V);
     859         [ -  + ]:    7768208 :   if (lg(W) != l) return 0;
     860                 :    7768208 :   return ZV_equal_lg(V, W, l);
     861                 :            : }
     862                 :            : int
     863                 :     381528 : ZM_equal(GEN A, GEN B)
     864                 :            : {
     865                 :     381528 :   long i, m, l = lg(A);
     866         [ +  + ]:     381528 :   if (lg(B) != l) return 0;
     867         [ -  + ]:     381276 :   if (l == 1) return 1;
     868                 :     381276 :   m = lgcols(A);
     869         [ -  + ]:     381276 :   if (lgcols(B) != m) return 0;
     870         [ +  + ]:    1538379 :   for (i = 1; i < l; i++)
     871         [ +  + ]:    1200870 :     if (!ZV_equal_lg(gel(A,i), gel(B,i), m)) return 0;
     872                 :     381528 :   return 1;
     873                 :            : }
     874                 :            : int
     875                 :    2962411 : zv_equal(GEN V, GEN W)
     876                 :            : {
     877                 :    2962411 :   long l = lg(V);
     878         [ +  + ]:    2962411 :   if (lg(W) != l) return 0;
     879         [ +  + ]:   19777854 :   while (--l > 0)
     880         [ +  + ]:   17208765 :     if (V[l] != W[l]) return 0;
     881                 :    2962411 :   return 1;
     882                 :            : }
     883                 :            : 
     884                 :            : int
     885                 :        315 : zvV_equal(GEN V, GEN W)
     886                 :            : {
     887                 :        315 :   long l = lg(V);
     888         [ +  + ]:        315 :   if (lg(W) != l) return 0;
     889         [ +  + ]:      58352 :   while (--l > 0)
     890         [ +  + ]:      58170 :     if (!zv_equal(gel(V,l),gel(W,l))) return 0;
     891                 :        315 :   return 1;
     892                 :            : }
     893                 :            : 
     894                 :            : int
     895                 :      51686 : ZM_ishnf(GEN x)
     896                 :            : {
     897                 :      51686 :   long i,j, lx = lg(x);
     898         [ +  + ]:     242168 :   for (i=1; i<lx; i++)
     899                 :            :   {
     900                 :     198042 :     GEN xii = gcoeff(x,i,i);
     901         [ +  + ]:     198042 :     if (signe(xii) <= 0) return 0;
     902         [ +  + ]:     743916 :     for (j=1; j<i; j++)
     903         [ -  + ]:     546385 :       if (signe(gcoeff(x,i,j))) return 0;
     904         [ +  + ]:     773204 :     for (j=i+1; j<lx; j++)
     905                 :            :     {
     906                 :     582722 :       GEN xij = gcoeff(x,i,j);
     907 [ +  + ][ +  + ]:     582722 :       if (signe(xij)<0 || cmpii(xij,xii)>=0) return 0;
     908                 :            :     }
     909                 :            :   }
     910                 :      51686 :   return 1;
     911                 :            : }
     912                 :            : int
     913                 :      89560 : ZM_isidentity(GEN x)
     914                 :            : {
     915                 :      89560 :   long i,j, lx = lg(x);
     916                 :            : 
     917         [ -  + ]:      89560 :   if (lx == 1) return 1;
     918         [ -  + ]:      89560 :   if (lx != lgcols(x)) return 0;
     919         [ +  + ]:     747419 :   for (j=1; j<lx; j++)
     920                 :            :   {
     921                 :     657859 :     GEN c = gel(x,j), t;
     922         [ +  + ]:    3160702 :     for (i=1; i<j; )
     923         [ -  + ]:    2502843 :       if (signe(gel(c,i++))) return 0;
     924                 :            :     /* i = j */
     925                 :     657859 :     t = gel(c,i++);
     926 [ +  - ][ -  + ]:     657859 :       if (!is_pm1(t) || signe(t) < 0) return 0;
     927         [ +  + ]:    3160702 :     for (   ; i<lx; )
     928         [ -  + ]:    2502843 :       if (signe(gel(c,i++))) return 0;
     929                 :            :   }
     930                 :      89560 :   return 1;
     931                 :            : }
     932                 :            : 
     933                 :            : long
     934                 :       8386 : ZC_is_ei(GEN x)
     935                 :            : {
     936                 :       8386 :   long i, j = 0, l = lg(x);
     937         [ +  + ]:      73220 :   for (i = 1; i < l; i++)
     938                 :            :   {
     939                 :      64834 :     GEN c = gel(x,i);
     940                 :      64834 :     long s = signe(c);
     941         [ +  + ]:      64834 :     if (!s) continue;
     942 [ +  - ][ +  - ]:       8379 :     if (s < 0 || !is_pm1(c) || j) return 0;
                 [ -  + ]
     943                 :       8379 :     j = i;
     944                 :            :   }
     945                 :       8386 :   return j;
     946                 :            : }
     947                 :            : 
     948                 :            : /********************************************************************/
     949                 :            : /**                                                                **/
     950                 :            : /**                       MISCELLANEOUS                            **/
     951                 :            : /**                                                                **/
     952                 :            : /********************************************************************/
     953                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
     954                 :            : int
     955                 :     714933 : ZV_cmp(GEN x, GEN y)
     956                 :            : {
     957                 :     714933 :   long fl,i, lx = lg(x);
     958         [ +  + ]:    1626917 :   for (i=1; i<lx; i++)
     959         [ +  + ]:    1336772 :     if (( fl = cmpii(gel(x,i), gel(y,i)) )) return fl;
     960                 :     714933 :   return 0;
     961                 :            : }
     962                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
     963                 :            : int
     964                 :       3466 : ZV_abscmp(GEN x, GEN y)
     965                 :            : {
     966                 :       3466 :   long fl,i, lx = lg(x);
     967         [ +  + ]:      19444 :   for (i=1; i<lx; i++)
     968         [ +  + ]:      19364 :     if (( fl = absi_cmp(gel(x,i), gel(y,i)) )) return fl;
     969                 :       3466 :   return 0;
     970                 :            : }
     971                 :            : 
     972                 :            : long
     973                 :     857518 : zv_content(GEN x)
     974                 :            : {
     975                 :     857518 :   long i, l = lg(x), s = labs(x[1]);
     976 [ +  + ][ +  + ]:    1789018 :   for (i=2; i<l && s!=1; i++) s = cgcd(x[i],s);
     977                 :     857518 :   return s;
     978                 :            : }
     979                 :            : GEN
     980                 :       2912 : ZV_content(GEN x)
     981                 :            : {
     982                 :       2912 :   long i, l = lg(x);
     983                 :       2912 :   pari_sp av = avma;
     984                 :            :   GEN c;
     985         [ -  + ]:       2912 :   if (l == 1) return gen_1;
     986         [ +  + ]:       2912 :   if (l == 2) return absi(gel(x,1));
     987                 :       1295 :   c = gel(x,1);
     988         [ +  + ]:       2814 :   for (i = 2; i < l; i++)
     989                 :            :   {
     990                 :       1869 :     c = gcdii(c, gel(x,i));
     991         [ +  + ]:       1869 :     if (is_pm1(c)) { avma = av; return gen_1; }
     992                 :            :   }
     993                 :       2912 :   return gerepileuptoint(av, c);
     994                 :            : }
     995                 :            : 
     996                 :            : GEN
     997                 :     583396 : ZM_det_triangular(GEN mat)
     998                 :            : {
     999                 :            :   pari_sp av;
    1000                 :     583396 :   long i,l = lg(mat);
    1001                 :            :   GEN s;
    1002                 :            : 
    1003 [ +  + ][ +  + ]:     583396 :   if (l<3) return l<2? gen_1: icopy(gcoeff(mat,1,1));
    1004                 :     568315 :   av = avma; s = gcoeff(mat,1,1);
    1005         [ +  + ]:    1672523 :   for (i=2; i<l; i++) s = mulii(s,gcoeff(mat,i,i));
    1006                 :     583396 :   return gerepileuptoint(av,s);
    1007                 :            : }
    1008                 :            : 
    1009                 :            : /* assumes no overflow */
    1010                 :            : long
    1011                 :     304028 : zv_prod(GEN v)
    1012                 :            : {
    1013                 :     304028 :   long n, i, l = lg(v);
    1014         [ +  + ]:     304028 :   if (l == 1) return 1;
    1015         [ +  + ]:     345038 :   n = v[1]; for (i = 2; i < l; i++) n *= v[i];
    1016                 :     304028 :   return n;
    1017                 :            : }
    1018                 :            : /* product of ulongs */
    1019                 :            : GEN
    1020                 :     363160 : zv_prod_Z(GEN v)
    1021                 :            : {
    1022                 :     363160 :   pari_sp av = avma;
    1023                 :     363160 :   long k, n = lg(v)-1, m;
    1024                 :            :   GEN x;
    1025         [ +  + ]:     363160 :   if (n == 0) return gen_1;
    1026         [ +  + ]:     343714 :   if (n == 1) return utoi(v[1]);
    1027         [ +  + ]:     287728 :   if (n == 2) return muluu(v[1], v[2]);
    1028                 :     163072 :   m = n >> 1;
    1029         [ +  + ]:     163072 :   x = cgetg(m + (odd(n)? 2: 1), t_VEC);
    1030         [ +  + ]:     365176 :   for (k = 1; k <= m; k++) gel(x,k) = muluu(v[k<<1], v[(k<<1)-1]);
    1031         [ +  + ]:     163072 :   if (odd(n)) gel(x,k) = utoipos(v[n]);
    1032                 :     363160 :   return gerepileuptoint(av, divide_conquer_prod(x, mulii));
    1033                 :            : }
    1034                 :            : 
    1035                 :            : GEN
    1036                 :      21298 : ZV_prod(GEN v)
    1037                 :            : {
    1038                 :      21298 :   pari_sp av = avma;
    1039                 :      21298 :   long i, l = lg(v);
    1040                 :            :   GEN n;
    1041         [ +  + ]:      21298 :   if (l == 1) return gen_1;
    1042         [ +  + ]:      20626 :   if (l > 7) return gerepileuptoint(av, divide_conquer_prod(v, mulii));
    1043                 :      18183 :   n = gel(v,1);
    1044         [ +  + ]:      18183 :   if (l == 2) return icopy(n);
    1045         [ +  + ]:      31216 :   for (i = 2; i < l; i++) n = mulii(n, gel(v,i));
    1046                 :      21298 :   return gerepileuptoint(av, n);
    1047                 :            : }
    1048                 :            : /* assumes no overflow */
    1049                 :            : long
    1050                 :        196 : zv_sum(GEN v)
    1051                 :            : {
    1052                 :        196 :   long n, i, l = lg(v);
    1053         [ +  + ]:        196 :   if (l == 1) return 0;
    1054         [ +  + ]:        959 :   n = v[1]; for (i = 2; i < l; i++) n += v[i];
    1055                 :        196 :   return n;
    1056                 :            : }
    1057                 :            : GEN
    1058                 :         56 : ZV_sum(GEN v)
    1059                 :            : {
    1060                 :         56 :   pari_sp av = avma;
    1061                 :         56 :   long i, l = lg(v);
    1062                 :            :   GEN n;
    1063         [ -  + ]:         56 :   if (l == 1) return gen_0;
    1064                 :         56 :   n = gel(v,1);
    1065         [ -  + ]:         56 :   if (l == 2) return icopy(n);
    1066         [ +  + ]:        518 :   for (i = 2; i < l; i++) n = addii(n, gel(v,i));
    1067                 :         56 :   return gerepileuptoint(av, n);
    1068                 :            : }
    1069                 :            : 
    1070                 :            : /********************************************************************/
    1071                 :            : /**                                                                **/
    1072                 :            : /**         GRAM SCHMIDT REDUCTION (integer matrices)              **/
    1073                 :            : /**                                                                **/
    1074                 :            : /********************************************************************/
    1075                 :            : 
    1076                 :            : /* L[k,] += q * L[l,], l < k. Inefficient if q = 0 */
    1077                 :            : static void
    1078                 :     172406 : Zupdate_row(long k, long l, GEN q, GEN L, GEN B)
    1079                 :            : {
    1080                 :     172406 :   long i, qq = itos_or_0(q);
    1081         [ +  + ]:     172406 :   if (!qq)
    1082                 :            :   {
    1083         [ +  + ]:      18214 :     for(i=1;i<l;i++)  gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulii(q,gcoeff(L,l,i)));
    1084                 :       5061 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulii(q,B));
    1085                 :     172406 :     return;
    1086                 :            :   }
    1087         [ +  + ]:     167345 :   if (qq == 1) {
    1088         [ +  + ]:      61457 :     for (i=1;i<l; i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),gcoeff(L,l,i));
    1089                 :      34142 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), B);
    1090         [ +  + ]:     133203 :   } else if (qq == -1) {
    1091         [ +  + ]:     151325 :     for (i=1;i<l; i++) gcoeff(L,k,i) = subii(gcoeff(L,k,i),gcoeff(L,l,i));
    1092                 :      80884 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), negi(B));
    1093                 :            :   } else {
    1094         [ +  + ]:     112231 :     for(i=1;i<l;i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulsi(qq,gcoeff(L,l,i)));
    1095                 :      52319 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulsi(qq,B));
    1096                 :            :   }
    1097                 :            : }
    1098                 :            : 
    1099                 :            : /* update L[k,] */
    1100                 :            : static void
    1101                 :     540562 : ZRED(long k, long l, GEN x, GEN L, GEN B)
    1102                 :            : {
    1103                 :     540562 :   GEN q = truedivii(addii(B,shifti(gcoeff(L,k,l),1)), shifti(B,1));
    1104         [ +  + ]:     712968 :   if (!signe(q)) return;
    1105                 :     172406 :   q = negi(q);
    1106                 :     172406 :   Zupdate_row(k,l,q,L,B);
    1107                 :     172406 :   gel(x,k) = ZC_lincomb(gen_1, q, gel(x,k), gel(x,l));
    1108                 :            : }
    1109                 :            : 
    1110                 :            : /* Gram-Schmidt reduction, x a ZM */
    1111                 :            : static void
    1112                 :     722552 : ZincrementalGS(GEN x, GEN L, GEN B, long k)
    1113                 :            : {
    1114                 :            :   long i, j;
    1115         [ +  + ]:    2596413 :   for (j=1; j<=k; j++)
    1116                 :            :   {
    1117                 :    1873861 :     pari_sp av = avma;
    1118                 :    1873861 :     GEN u = ZV_dotproduct(gel(x,k), gel(x,j));
    1119         [ +  + ]:    4409424 :     for (i=1; i<j; i++)
    1120                 :            :     {
    1121                 :    2535563 :       u = subii(mulii(gel(B,i+1), u), mulii(gcoeff(L,k,i), gcoeff(L,j,i)));
    1122                 :    2535563 :       u = diviiexact(u, gel(B,i));
    1123                 :            :     }
    1124                 :    1873861 :     gcoeff(L,k,j) = gerepileuptoint(av, u);
    1125                 :            :   }
    1126                 :     722552 :   gel(B,k+1) = gcoeff(L,k,k); gcoeff(L,k,k) = gen_1;
    1127                 :     722552 : }
    1128                 :            : 
    1129                 :            : /* Variant reducemodinvertible(ZC v, ZM y), when y singular.
    1130                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1131                 :            : static GEN
    1132                 :     186421 : ZC_reducemodmatrix_i(GEN v, GEN y)
    1133                 :            : {
    1134                 :     186421 :   GEN B, L, x = shallowconcat(y, v);
    1135                 :     186421 :   long k, lx = lg(x), nx = lx-1;
    1136                 :            : 
    1137                 :     186421 :   B = scalarcol_shallow(gen_1, lx);
    1138                 :     186421 :   L = zeromatcopy(nx, nx);
    1139         [ +  + ]:     887980 :   for (k=1; k <= nx; k++) ZincrementalGS(x, L, B, k);
    1140         [ +  + ]:     701559 :   for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1141                 :     186421 :   return gel(x,nx);
    1142                 :            : }
    1143                 :            : GEN
    1144                 :     186421 : ZC_reducemodmatrix(GEN v, GEN y) {
    1145                 :     186421 :   pari_sp av = avma;
    1146                 :     186421 :   return gerepilecopy(av, ZC_reducemodmatrix_i(v,y));
    1147                 :            : }
    1148                 :            : 
    1149                 :            : /* Variant reducemodinvertible(ZM v, ZM y), when y singular.
    1150                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1151                 :            : static GEN
    1152                 :       4627 : ZM_reducemodmatrix_i(GEN v, GEN y)
    1153                 :            : {
    1154                 :            :   GEN B, L, V;
    1155                 :       4627 :   long j, k, lv = lg(v), nx = lg(y), lx = nx+1;
    1156                 :            : 
    1157                 :       4627 :   V = cgetg(lv, t_MAT);
    1158                 :       4627 :   B = scalarcol_shallow(gen_1, lx);
    1159                 :       4627 :   L = zeromatcopy(nx, nx);
    1160         [ +  + ]:      15274 :   for (k=1; k < nx; k++) ZincrementalGS(y, L, B, k);
    1161         [ +  + ]:      14973 :   for (j = 1; j < lg(v); j++)
    1162                 :            :   {
    1163                 :      10346 :     GEN x = shallowconcat(y, gel(v,j));
    1164                 :      10346 :     ZincrementalGS(x, L, B, nx); /* overwrite last */
    1165         [ +  + ]:      35770 :     for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1166                 :      10346 :     gel(V,j) = gel(x,nx);
    1167                 :            :   }
    1168                 :       4627 :   return V;
    1169                 :            : }
    1170                 :            : GEN
    1171                 :       4627 : ZM_reducemodmatrix(GEN v, GEN y) {
    1172                 :       4627 :   pari_sp av = avma;
    1173                 :       4627 :   return gerepilecopy(av, ZM_reducemodmatrix_i(v,y));
    1174                 :            : }
    1175                 :            : 
    1176                 :            : GEN
    1177                 :     186036 : ZC_reducemodlll(GEN x,GEN y)
    1178                 :            : {
    1179                 :     186036 :   pari_sp av = avma;
    1180                 :     186036 :   GEN z = ZC_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1181                 :     186036 :   return gerepilecopy(av, z);
    1182                 :            : }
    1183                 :            : GEN
    1184                 :          0 : ZM_reducemodlll(GEN x,GEN y)
    1185                 :            : {
    1186                 :          0 :   pari_sp av = avma;
    1187                 :          0 :   GEN z = ZM_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1188                 :          0 :   return gerepilecopy(av, z);
    1189                 :            : }

Generated by: LCOV version 1.9