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 16741-1378b1c) Lines: 561 610 92.0 %
Date: 2014-08-17 Functions: 90 97 92.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 369 438 84.2 %

           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                 :      22765 : check_ZV(GEN x, long l)
      19                 :            : {
      20                 :            :   long i;
      21         [ +  + ]:     139725 :   for (i=1; i<l; i++)
      22         [ +  + ]:     117020 :     if (typ(gel(x,i)) != t_INT) return 0;
      23                 :      22765 :   return 1;
      24                 :            : }
      25                 :            : void
      26                 :     322238 : RgV_check_ZV(GEN A, const char *s)
      27                 :            : {
      28         [ +  + ]:     322238 :   if (!RgV_is_ZV(A)) pari_err_TYPE(stack_strcat(s," [integer vector]"), A);
      29                 :     322228 : }
      30                 :            : void
      31                 :       6270 : RgM_check_ZM(GEN A, const char *s)
      32                 :            : {
      33                 :       6270 :   long n = lg(A);
      34         [ +  + ]:       6270 :   if (n != 1)
      35                 :            :   {
      36                 :       6245 :     long j, m = lgcols(A);
      37         [ +  + ]:      28950 :     for (j=1; j<n; j++)
      38         [ +  + ]:      22765 :       if (!check_ZV(gel(A,j), m))
      39                 :         60 :         pari_err_TYPE(stack_strcat(s," [integer matrix]"), A);
      40                 :            :   }
      41                 :       6210 : }
      42                 :            : 
      43                 :            : long
      44                 :       7580 : ZV_max_lg(GEN x)
      45                 :            : {
      46                 :       7580 :   long i, prec = 2, m = lg(x);
      47 [ +  + ][ +  + ]:      21480 :   for (i=1; i<m; i++) { long l = lgefint(gel(x,i)); if (l > prec) prec = l; }
      48                 :       7580 :   return prec;
      49                 :            : }
      50                 :            : long
      51                 :        410 : ZM_max_lg(GEN x)
      52                 :            : {
      53                 :        410 :   long i, prec = 2, n = lg(x);
      54         [ +  - ]:        410 :   if (n != 1)
      55                 :            :   {
      56                 :        410 :     long j, m = lgcols(x);
      57         [ +  + ]:       4235 :     for (j=1; j<n; j++)
      58                 :            :     {
      59                 :       3825 :       GEN c = gel(x,j);
      60 [ +  + ][ +  + ]:      84480 :       for (i=1; i<m; i++) { long l = lgefint(gel(c,i)); if (l > prec) prec = l; }
      61                 :            :     }
      62                 :            :   }
      63                 :        410 :   return prec;
      64                 :            : }
      65                 :            : 
      66                 :            : GEN
      67                 :         90 : ZM_supnorm(GEN x)
      68                 :            : {
      69                 :         90 :   long i, j, h, lx = lg(x);
      70                 :         90 :   GEN s = gen_0;
      71         [ -  + ]:         90 :   if (lx == 1) return gen_1;
      72                 :         90 :   h = lgcols(x);
      73         [ +  + ]:        485 :   for (j=1; j<lx; j++)
      74                 :            :   {
      75                 :        395 :     GEN xj = gel(x,j);
      76         [ +  + ]:       4270 :     for (i=1; i<h; i++)
      77                 :            :     {
      78                 :       3875 :       GEN c = gel(xj,i);
      79         [ +  + ]:       3875 :       if (absi_cmp(c, s) > 0) s = c;
      80                 :            :     }
      81                 :            :   }
      82                 :         90 :   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                 :       2500 : ZM_nc_mul_i(GEN x, GEN y, long c, long l)
      93                 :            : {
      94                 :            :   long i, j;
      95                 :            :   pari_sp av;
      96                 :       2500 :   GEN z = cgetg(l,t_COL), s;
      97                 :            : 
      98         [ +  + ]:      44378 :   for (i=1; i<l; i++)
      99                 :            :   {
     100                 :      41878 :     av = avma; s = muliu(gcoeff(x,i,1),y[1]);
     101         [ +  + ]:     761302 :     for (j=2; j<c; j++)
     102         [ +  + ]:     719424 :       if (y[j]) s = addii(s, muliu(gcoeff(x,i,j),y[j]));
     103                 :      41878 :     gel(z,i) = gerepileuptoint(av,s);
     104                 :            :   }
     105                 :       2500 :   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                 :     799929 : ZM_zc_mul_i(GEN x, GEN y, long c, long l)
     123                 :            : {
     124                 :            :   long i, j;
     125                 :            :   pari_sp av;
     126                 :     799929 :   GEN z = cgetg(l,t_COL), s;
     127                 :            : 
     128         [ +  + ]:    6493593 :   for (i=1; i<l; i++)
     129                 :            :   {
     130                 :    5693664 :     av = avma; s = mulis(gcoeff(x,i,1),y[1]);
     131         [ +  + ]:  145400216 :     for (j=2; j<c; j++)
     132         [ +  + ]:  139706552 :       if (y[j]) s = addii(s, mulis(gcoeff(x,i,j),y[j]));
     133                 :    5693664 :     gel(z,i) = gerepileuptoint(av,s);
     134                 :            :   }
     135                 :     799929 :   return z;
     136                 :            : }
     137                 :            : GEN
     138                 :     729743 : ZM_zc_mul(GEN x, GEN y) {
     139                 :     729743 :   long l = lg(x);
     140         [ -  + ]:     729743 :   if (l == 1) return cgetg(1, t_COL);
     141                 :     729743 :   return ZM_zc_mul_i(x,y, l, lgcols(x));
     142                 :            : }
     143                 :            : 
     144                 :            : /* x ZM, y a compatible zm (dimension > 0). */
     145                 :            : GEN
     146                 :      27068 : ZM_zm_mul(GEN x, GEN y)
     147                 :            : {
     148                 :      27068 :   long j, c, l = lg(x), ly = lg(y);
     149                 :      27068 :   GEN z = cgetg(ly, t_MAT);
     150         [ -  + ]:      27068 :   if (l == 1) return z;
     151                 :      27068 :   c = lgcols(x);
     152         [ +  + ]:      97254 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_zc_mul_i(x, gel(y,j), l,c);
     153                 :      27068 :   return z;
     154                 :            : }
     155                 :            : /* x ZM, y a compatible zn (dimension > 0). */
     156                 :            : GEN
     157                 :        173 : ZM_nm_mul(GEN x, GEN y)
     158                 :            : {
     159                 :        173 :   long j, c, l = lg(x), ly = lg(y);
     160                 :        173 :   GEN z = cgetg(ly, t_MAT);
     161         [ -  + ]:        173 :   if (l == 1) return z;
     162                 :        173 :   c = lgcols(x);
     163         [ +  + ]:       2673 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_nc_mul_i(x, gel(y,j), l,c);
     164                 :        173 :   return z;
     165                 :            : }
     166                 :            : 
     167                 :            : /* x[i,]*y. Assume lg(x) > 1 and 0 < i < lgcols(x) */
     168                 :            : static GEN
     169                 :   38425312 : ZMrow_ZC_mul_i(GEN x, GEN y, long i, long lx)
     170                 :            : {
     171                 :   38425312 :   pari_sp av = avma;
     172                 :   38425312 :   GEN c = mulii(gcoeff(x,i,1), gel(y,1)), ZERO = gen_0;
     173                 :            :   long k;
     174         [ +  + ]:  735900137 :   for (k = 2; k < lx; k++)
     175                 :            :   {
     176                 :  697474825 :     GEN t = mulii(gcoeff(x,i,k), gel(y,k));
     177         [ +  + ]:  697474825 :     if (t != ZERO) c = addii(c, t);
     178                 :            :   }
     179                 :   38425312 :   return gerepileuptoint(av, c);
     180                 :            : }
     181                 :            : GEN
     182                 :    6427069 : ZMrow_ZC_mul(GEN x, GEN y, long i)
     183                 :    6427069 : { 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                 :    6609812 : ZM_ZC_mul_i(GEN x, GEN y, long lx, long l)
     188                 :            : {
     189                 :    6609812 :   GEN z = cgetg(l,t_COL);
     190                 :            :   long i;
     191         [ +  + ]:   38608055 :   for (i=1; i<l; i++) gel(z,i) = ZMrow_ZC_mul_i(x,y,i,lx);
     192                 :    6609812 :   return z;
     193                 :            : }
     194                 :            : GEN
     195                 :    1015010 : ZM_mul(GEN x, GEN y)
     196                 :            : {
     197                 :    1015010 :   long j, l, lx=lg(x), ly=lg(y);
     198                 :            :   GEN z;
     199         [ +  + ]:    1015010 :   if (ly==1) return cgetg(1,t_MAT);
     200         [ +  + ]:    1013745 :   if (lx==1) return zeromat(0, ly-1);
     201                 :    1013650 :   l = lgcols(x); z = cgetg(ly,t_MAT);
     202         [ +  + ]:    4974494 :   for (j=1; j<ly; j++) gel(z,j) = ZM_ZC_mul_i(x, gel(y,j), lx, l);
     203                 :    1015010 :   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                 :    9835689 : ZV_dotproduct_i(GEN x, GEN y, long lx)
     230                 :            : {
     231                 :    9835689 :   pari_sp av = avma;
     232                 :    9835689 :   GEN c = mulii(gel(x,1), gel(y,1));
     233                 :            :   long i;
     234         [ +  + ]:   88490517 :   for (i = 2; i < lx; i++)
     235                 :            :   {
     236                 :   78654828 :     GEN t = mulii(gel(x,i), gel(y,i));
     237         [ +  + ]:   78654828 :     if (t != gen_0) c = addii(c, t);
     238                 :            :   }
     239                 :    9835689 :   return gerepileuptoint(av, c);
     240                 :            : }
     241                 :            : 
     242                 :            : /* x~ * y, assuming result is symmetric */
     243                 :            : GEN
     244                 :     112870 : ZM_transmultosym(GEN x, GEN y)
     245                 :            : {
     246                 :     112870 :   long i, j, l, ly = lg(y);
     247                 :            :   GEN M;
     248         [ -  + ]:     112870 :   if (ly == 1) return cgetg(1,t_MAT);
     249                 :            :   /* lg(x) = ly */
     250                 :     112870 :   l = lgcols(y); /* = lgcols(x) */
     251                 :     112870 :   M = cgetg(ly, t_MAT);
     252         [ +  + ]:     879268 :   for (i=1; i<ly; i++)
     253                 :            :   {
     254                 :     766398 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     255                 :     766398 :     gel(M,i) = c;
     256         [ +  + ]:    3412418 :     for (j=1; j<i; j++)
     257                 :    2646020 :       gcoeff(M,i,j) = gel(c,j) = ZV_dotproduct_i(xi,gel(y,j),l);
     258                 :     766398 :     gel(c,i) = ZV_dotproduct_i(xi,gel(y,i),l);
     259                 :            :   }
     260                 :     112870 :   return M;
     261                 :            : }
     262                 :            : /* x~ * y */
     263                 :            : GEN
     264                 :        355 : ZM_transmul(GEN x, GEN y)
     265                 :            : {
     266                 :        355 :   long i, j, l, lx, ly = lg(y);
     267                 :            :   GEN M;
     268         [ -  + ]:        355 :   if (ly == 1) return cgetg(1,t_MAT);
     269                 :        355 :   lx = lg(x);
     270                 :        355 :   l = lgcols(y);
     271         [ -  + ]:        355 :   if (lgcols(x) != l) pari_err_OP("operation 'ZM_transmul'", x,y);
     272                 :        355 :   M = cgetg(ly, t_MAT);
     273         [ +  + ]:       1155 :   for (i=1; i<ly; i++)
     274                 :            :   {
     275                 :        800 :     GEN yi = gel(y,i), c = cgetg(lx,t_COL);
     276                 :        800 :     gel(M,i) = c;
     277         [ +  + ]:       3615 :     for (j=1; j<lx; j++) gel(c,j) = ZV_dotproduct_i(yi,gel(x,j),l);
     278                 :            :   }
     279                 :        355 :   return M;
     280                 :            : }
     281                 :            : GEN
     282                 :         15 : ZM_sqr(GEN x)
     283                 :            : {
     284                 :         15 :   long j, l, lx=lg(x);
     285                 :            :   GEN z;
     286         [ -  + ]:         15 :   if (lx==1) return cgetg(1,t_MAT);
     287                 :         15 :   l = lgcols(x); z = cgetg(lx,t_MAT);
     288         [ +  + ]:         45 :   for (j=1; j<lx; j++) gel(z,j) = ZM_ZC_mul_i(x, gel(x,j), lx, l);
     289                 :         15 :   return z;
     290                 :            : }
     291                 :            : GEN
     292                 :    2673571 : ZM_ZC_mul(GEN x, GEN y)
     293                 :            : {
     294                 :    2673571 :   long lx = lg(x);
     295         [ +  + ]:    2673571 :   return lx==1? cgetg(1,t_COL): ZM_ZC_mul_i(x, y, lx, lgcols(x));
     296                 :            : }
     297                 :            : 
     298                 :            : long
     299                 :   89643355 : zv_dotproduct(GEN x, GEN y)
     300                 :            : {
     301                 :   89643355 :   long i, lx = lg(x);
     302                 :            :   ulong c;
     303         [ -  + ]:   89643355 :   if (lx == 1) return 0;
     304                 :   89643355 :   c = uel(x,1)*uel(y,1);
     305         [ +  + ]: 1390952305 :   for (i = 2; i < lx; i++)
     306                 : 1301308950 :     c += uel(x,i)*uel(y,i);
     307                 :   89643355 :   return c;
     308                 :            : }
     309                 :            : 
     310                 :            : GEN
     311                 :       2260 : ZV_ZM_mul(GEN x, GEN y)
     312                 :            : {
     313                 :       2260 :   long i, lx = lg(x), ly = lg(y);
     314                 :            :   GEN z;
     315         [ -  + ]:       2260 :   if (lx == 1) return zerovec(ly-1);
     316                 :       2260 :   z = cgetg(ly, t_VEC);
     317         [ +  + ]:       6915 :   for (i = 1; i < ly; i++) gel(z,i) = ZV_dotproduct_i(x, gel(y,i), lx);
     318                 :       2260 :   return z;
     319                 :            : }
     320                 :            : 
     321                 :            : GEN
     322                 :          0 : ZC_ZV_mul(GEN x, GEN y)
     323                 :            : {
     324                 :          0 :   long i,j, lx=lg(x), ly=lg(y);
     325                 :            :   GEN z;
     326         [ #  # ]:          0 :   if (ly==1) return cgetg(1,t_MAT);
     327                 :          0 :   z = cgetg(ly,t_MAT);
     328         [ #  # ]:          0 :   for (j=1; j < ly; j++)
     329                 :            :   {
     330                 :          0 :     gel(z,j) = cgetg(lx,t_COL);
     331         [ #  # ]:          0 :     for (i=1; i<lx; i++) gcoeff(z,i,j) = mulii(gel(x,i),gel(y,j));
     332                 :            :   }
     333                 :          0 :   return z;
     334                 :            : }
     335                 :            : 
     336                 :            : GEN
     337                 :    3167193 : ZV_dotsquare(GEN x)
     338                 :            : {
     339                 :            :   long i, lx;
     340                 :            :   pari_sp av;
     341                 :            :   GEN z;
     342                 :    3167193 :   lx = lg(x);
     343         [ -  + ]:    3167193 :   if (lx == 1) return gen_0;
     344                 :    3167193 :   av = avma; z = sqri(gel(x,1));
     345         [ +  + ]:   11506937 :   for (i=2; i<lx; i++) z = addii(z, sqri(gel(x,i)));
     346                 :    3167193 :   return gerepileuptoint(av,z);
     347                 :            : }
     348                 :            : 
     349                 :            : GEN
     350                 :    8715288 : ZV_dotproduct(GEN x,GEN y)
     351                 :            : {
     352                 :            :   long lx;
     353         [ +  + ]:    8715288 :   if (x == y) return ZV_dotsquare(x);
     354                 :    6415801 :   lx = lg(x);
     355         [ -  + ]:    6415801 :   if (lx == 1) return gen_0;
     356                 :    8715288 :   return ZV_dotproduct_i(x, y, lx);
     357                 :            : }
     358                 :            : 
     359                 :            : static GEN
     360                 :        155 : _ZM_mul(void *data /*ignored*/, GEN x, GEN y)
     361                 :        155 : { (void)data; return ZM_mul(x,y); }
     362                 :            : static GEN
     363                 :      34771 : _ZM_sqr(void *data /*ignored*/, GEN x)
     364                 :      34771 : { (void)data; return ZM_mul(x,x); }
     365                 :            : GEN
     366                 :         35 : ZM_pow(GEN x, GEN n)
     367                 :            : {
     368                 :         35 :   pari_sp av = avma;
     369         [ -  + ]:         35 :   if (!signe(n)) return matid(lg(x)-1);
     370                 :         35 :   return gerepileupto(av, gen_pow(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     371                 :            : }
     372                 :            : GEN
     373                 :      33976 : ZM_powu(GEN x, ulong n)
     374                 :            : {
     375                 :      33976 :   pari_sp av = avma;
     376         [ -  + ]:      33976 :   if (!n) return matid(lg(x)-1);
     377                 :      33976 :   return gerepileupto(av, gen_powu(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     378                 :            : }
     379                 :            : /********************************************************************/
     380                 :            : /**                                                                **/
     381                 :            : /**                           ADD, SUB                             **/
     382                 :            : /**                                                                **/
     383                 :            : /********************************************************************/
     384                 :            : static GEN
     385                 :     574094 : ZC_add_i(GEN x, GEN y, long lx)
     386                 :            : {
     387                 :     574094 :   GEN A = cgetg(lx, t_COL);
     388                 :            :   long i;
     389         [ +  + ]:    4575153 :   for (i=1; i<lx; i++) gel(A,i) = addii(gel(x,i), gel(y,i));
     390                 :     574094 :   return A;
     391                 :            : }
     392                 :            : GEN
     393                 :     569694 : ZC_add(GEN x, GEN y) { return ZC_add_i(x, y, lg(x)); }
     394                 :            : GEN
     395                 :      44715 : ZC_Z_add(GEN x, GEN y)
     396                 :            : {
     397                 :      44715 :   long k, lx = lg(x);
     398                 :      44715 :   GEN z = cgetg(lx, t_COL);
     399         [ -  + ]:      44715 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     400                 :      44715 :   gel(z,1) = addii(y,gel(x,1));
     401         [ +  + ]:     585140 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     402                 :      44715 :   return z;
     403                 :            : }
     404                 :            : 
     405                 :            : static GEN
     406                 :     757281 : ZC_sub_i(GEN x, GEN y, long lx)
     407                 :            : {
     408                 :            :   long i;
     409                 :     757281 :   GEN A = cgetg(lx, t_COL);
     410         [ +  + ]:    4522055 :   for (i=1; i<lx; i++) gel(A,i) = subii(gel(x,i), gel(y,i));
     411                 :     757281 :   return A;
     412                 :            : }
     413                 :            : GEN
     414                 :     723305 : ZC_sub(GEN x, GEN y) { return ZC_sub_i(x, y, lg(x)); }
     415                 :            : GEN
     416                 :          0 : ZC_Z_sub(GEN x, GEN y)
     417                 :            : {
     418                 :          0 :   long k, lx = lg(x);
     419                 :          0 :   GEN z = cgetg(lx, t_COL);
     420         [ #  # ]:          0 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     421                 :          0 :   gel(z,1) = subii(gel(x,1), y);
     422         [ #  # ]:          0 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     423                 :          0 :   return z;
     424                 :            : }
     425                 :            : 
     426                 :            : GEN
     427                 :       2243 : ZM_add(GEN x, GEN y)
     428                 :            : {
     429                 :       2243 :   long lx = lg(x), l, j;
     430                 :            :   GEN z;
     431         [ +  + ]:       2243 :   if (lx == 1) return cgetg(1, t_MAT);
     432                 :       1513 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     433         [ +  + ]:       5913 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_add_i(gel(x,j), gel(y,j), l);
     434                 :       2243 :   return z;
     435                 :            : }
     436                 :            : GEN
     437                 :       7096 : ZM_sub(GEN x, GEN y)
     438                 :            : {
     439                 :       7096 :   long lx = lg(x), l, j;
     440                 :            :   GEN z;
     441         [ -  + ]:       7096 :   if (lx == 1) return cgetg(1, t_MAT);
     442                 :       7096 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     443         [ +  + ]:      41072 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_sub_i(gel(x,j), gel(y,j), l);
     444                 :       7096 :   return z;
     445                 :            : }
     446                 :            : /********************************************************************/
     447                 :            : /**                                                                **/
     448                 :            : /**                         LINEAR COMBINATION                     **/
     449                 :            : /**                                                                **/
     450                 :            : /********************************************************************/
     451                 :            : /* return X/c assuming division is exact */
     452                 :            : GEN
     453                 :     213963 : ZC_Z_divexact(GEN X, GEN c)
     454                 :            : {
     455                 :     213963 :   long i, l = lg(X);
     456                 :     213963 :   GEN A = cgetg(l, t_COL);
     457         [ +  + ]:    2692460 :   for (i=1; i<l; i++) gel(A,i) = diviiexact(gel(X,i), c);
     458                 :     213963 :   return A;
     459                 :            : }
     460                 :            : GEN
     461                 :      35299 : ZM_Z_divexact(GEN X, GEN c)
     462                 :            : {
     463                 :      35299 :   long i, l = lg(X);
     464                 :      35299 :   GEN A = cgetg(l, t_MAT);
     465         [ +  + ]:     149142 :   for (i = 1; i < l; i++) gel(A,i) = ZC_Z_divexact(gel(X,i), c);
     466                 :      35299 :   return A;
     467                 :            : }
     468                 :            : /* Return c * X */
     469                 :            : GEN
     470                 :    1668316 : ZC_Z_mul(GEN X, GEN c)
     471                 :            : {
     472                 :            :   long i, l;
     473                 :            :   GEN A;
     474         [ +  + ]:    1668316 :   if (!signe(c)) return zerocol(lg(X)-1);
     475 [ +  + ][ +  + ]:    1660696 :   if (is_pm1(c)) return (signe(c) > 0)? ZC_copy(X): ZC_neg(X);
     476                 :    1600499 :   l = lg(X); A = cgetg(l, t_COL);
     477         [ +  + ]:    9030314 :   for (i=1; i<l; i++) gel(A,i) = mulii(c,gel(X,i));
     478                 :    1668316 :   return A;
     479                 :            : }
     480                 :            : GEN
     481                 :       8735 : ZC_z_mul(GEN X, long c)
     482                 :            : {
     483                 :            :   long i, l;
     484                 :            :   GEN A;
     485         [ +  + ]:       8735 :   if (!c) return zerocol(lg(X)-1);
     486         [ +  + ]:       4675 :   if (c == 1) return ZC_copy(X);
     487         [ +  + ]:       1495 :   if (c ==-1) return ZC_neg(X);
     488                 :        520 :   l = lg(X); A = cgetg(l, t_COL);
     489         [ +  + ]:       1570 :   for (i=1; i<l; i++) gel(A,i) = mulsi(c,gel(X,i));
     490                 :       8735 :   return A;
     491                 :            : }
     492                 :            : 
     493                 :            : GEN
     494                 :       3090 : zv_z_mul(GEN M, long n)
     495                 :            : {
     496                 :            :   long l;
     497                 :       3090 :   GEN N = cgetg_copy(M, &l);
     498         [ +  + ]:      12920 :   while (--l > 0) N[l] = M[l]*n;
     499                 :       3090 :   return N;
     500                 :            : }
     501                 :            : 
     502                 :            : /* return a ZM */
     503                 :            : GEN
     504                 :        173 : nm_Z_mul(GEN X, GEN c)
     505                 :            : {
     506                 :        173 :   long i, j, h, l = lg(X), s = signe(c);
     507                 :            :   GEN A;
     508         [ -  + ]:        173 :   if (l == 1) return cgetg(1, t_MAT);
     509                 :        173 :   h = lgcols(X);
     510         [ -  + ]:        173 :   if (!s) return zeromat(h-1, l-1);
     511         [ -  + ]:        173 :   if (is_pm1(c)) {
     512         [ #  # ]:          0 :     if (s > 0) return Flm_to_ZM(X);
     513                 :          0 :     X = Flm_to_ZM(X); ZM_togglesign(X); return X;
     514                 :            :   }
     515                 :        173 :   A = cgetg(l, t_MAT);
     516         [ +  + ]:       2673 :   for (j = 1; j < l; j++)
     517                 :            :   {
     518                 :       2500 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     519         [ +  + ]:      44378 :     for (i = 1; i < h; i++) gel(a,i) = muliu(c, x[i]);
     520                 :       2500 :     gel(A,j) = a;
     521                 :            :   }
     522                 :        173 :   return A;
     523                 :            : }
     524                 :            : GEN
     525                 :      16677 : ZM_Z_mul(GEN X, GEN c)
     526                 :            : {
     527                 :      16677 :   long i, j, h, l = lg(X);
     528                 :            :   GEN A;
     529         [ -  + ]:      16677 :   if (l == 1) return cgetg(1, t_MAT);
     530                 :      16677 :   h = lgcols(X);
     531         [ +  + ]:      16677 :   if (!signe(c)) return zeromat(h-1, l-1);
     532 [ +  + ][ +  - ]:      16652 :   if (is_pm1(c)) return (signe(c) > 0)? ZM_copy(X): ZM_neg(X);
     533                 :      15177 :   A = cgetg(l, t_MAT);
     534         [ +  + ]:      54544 :   for (j = 1; j < l; j++)
     535                 :            :   {
     536                 :      39367 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     537         [ +  + ]:     209625 :     for (i = 1; i < h; i++) gel(a,i) = mulii(c, gel(x,i));
     538                 :      39367 :     gel(A,j) = a;
     539                 :            :   }
     540                 :      16677 :   return A;
     541                 :            : }
     542                 :            : 
     543                 :            : /* X <- X + v Y (elementary col operation) */
     544                 :            : void
     545                 :   24303957 : ZC_lincomb1_inplace(GEN X, GEN Y, GEN v)
     546                 :            : {
     547                 :   24303957 :   long i, m = lgefint(v);
     548         [ -  + ]:   48607914 :   if (m == 2) return; /* v = 0 */
     549         [ +  + ]:  520274825 :   for (i = lg(X)-1; i; i--) gel(X,i) = addmulii_inplace(gel(X,i), gel(Y,i), v);
     550                 :            : }
     551                 :            : void
     552                 :    5035747 : Flc_lincomb1_inplace(GEN X, GEN Y, ulong v, ulong q)
     553                 :            : {
     554                 :            :   long i;
     555         [ -  + ]:   10071494 :   if (!v) return; /* v = 0 */
     556         [ +  + ]:  180185044 :   for (i = lg(X)-1; i; i--) X[i] = Fl_add(X[i], Fl_mul(Y[i], v, q), q);
     557                 :            : }
     558                 :            : 
     559                 :            : /* X + v Y, wasteful if (v = 0) */
     560                 :            : static GEN
     561                 :    1722283 : ZC_lincomb1(GEN v, GEN X, GEN Y)
     562                 :            : {
     563                 :    1722283 :   long i, lx = lg(X);
     564                 :    1722283 :   GEN A = cgetg(lx,t_COL);
     565         [ +  + ]:   20337442 :   for (i=1; i<lx; i++) gel(A,i) = addmulii(gel(X,i), gel(Y,i), v);
     566                 :    1722283 :   return A;
     567                 :            : }
     568                 :            : /* -X + vY */
     569                 :            : static GEN
     570                 :     253869 : ZC_lincomb_1(GEN v, GEN X, GEN Y)
     571                 :            : {
     572                 :     253869 :   long i, lx = lg(X);
     573                 :     253869 :   GEN A = cgetg(lx,t_COL);
     574         [ +  + ]:    1246351 :   for (i=1; i<lx; i++) gel(A,i) = mulsubii(gel(Y,i), v, gel(X,i));
     575                 :     253869 :   return A;
     576                 :            : }
     577                 :            : /* X,Y compatible ZV; u,v in Z. Returns A = u*X + v*Y */
     578                 :            : GEN
     579                 :    5101609 : ZC_lincomb(GEN u, GEN v, GEN X, GEN Y)
     580                 :            : {
     581                 :            :   long su, sv;
     582                 :            :   GEN A;
     583                 :            : 
     584         [ -  + ]:    5101609 :   su = signe(u); if (!su) return ZC_Z_mul(Y, v);
     585         [ +  + ]:    5101609 :   sv = signe(v); if (!sv) return ZC_Z_mul(X, u);
     586         [ +  + ]:    5101599 :   if (is_pm1(v))
     587                 :            :   {
     588         [ +  + ]:    1193005 :     if (is_pm1(u))
     589                 :            :     {
     590         [ +  + ]:     775051 :       if (su != sv) A = ZC_sub(X, Y);
     591                 :     352229 :       else          A = ZC_add(X, Y);
     592         [ +  + ]:     775051 :       if (su < 0) ZV_togglesign(A); /* in place but was created above */
     593                 :            :     }
     594                 :            :     else
     595                 :            :     {
     596         [ +  + ]:     417954 :       if (sv > 0) A = ZC_lincomb1 (u, Y, X);
     597                 :     181119 :       else        A = ZC_lincomb_1(u, Y, X);
     598                 :            :     }
     599                 :            :   }
     600         [ +  + ]:    3908594 :   else if (is_pm1(u))
     601                 :            :   {
     602         [ +  + ]:    1558198 :     if (su > 0) A = ZC_lincomb1 (v, X, Y);
     603                 :      72750 :     else        A = ZC_lincomb_1(v, X, Y);
     604                 :            :   }
     605                 :            :   else
     606                 :            :   { /* not cgetg_copy: x may be a t_VEC */
     607                 :    2350396 :     long i, lx = lg(X);
     608                 :    2350396 :     A = cgetg(lx,t_COL);
     609         [ +  + ]:   12332674 :     for (i=1; i<lx; i++) gel(A,i) = lincombii(u,v,gel(X,i),gel(Y,i));
     610                 :            :   }
     611                 :    5101609 :   return A;
     612                 :            : }
     613                 :            : 
     614                 :            : /********************************************************************/
     615                 :            : /**                                                                **/
     616                 :            : /**                           CONVERSIONS                          **/
     617                 :            : /**                                                                **/
     618                 :            : /********************************************************************/
     619                 :            : GEN
     620                 :        375 : ZV_to_nv(GEN z)
     621                 :            : {
     622                 :        375 :   long i, l = lg(z);
     623                 :        375 :   GEN x = cgetg(l, t_VECSMALL);
     624         [ +  + ]:        570 :   for (i=1; i<l; i++) x[i] = itou(gel(z,i));
     625                 :        375 :   return x;
     626                 :            : }
     627                 :            : 
     628                 :            : GEN
     629                 :      39023 : zm_to_ZM(GEN z)
     630                 :            : {
     631                 :      39023 :   long i, l = lg(z);
     632                 :      39023 :   GEN x = cgetg(l,t_MAT);
     633         [ +  + ]:     156304 :   for (i=1; i<l; i++) gel(x,i) = zc_to_ZC(gel(z,i));
     634                 :      39023 :   return x;
     635                 :            : }
     636                 :            : 
     637                 :            : GEN
     638                 :         45 : zmV_to_ZMV(GEN z)
     639                 :            : {
     640                 :         45 :   long i, l = lg(z);
     641                 :         45 :   GEN x = cgetg(l,t_VEC);
     642         [ +  + ]:        350 :   for (i=1; i<l; i++) gel(x,i) = zm_to_ZM(gel(z,i));
     643                 :         45 :   return x;
     644                 :            : }
     645                 :            : 
     646                 :            : /* same as Flm_to_ZM but do not assume positivity */
     647                 :            : GEN
     648                 :        170 : ZM_to_zm(GEN z)
     649                 :            : {
     650                 :        170 :   long i, l = lg(z);
     651                 :        170 :   GEN x = cgetg(l,t_MAT);
     652         [ +  + ]:     131820 :   for (i=1; i<l; i++) gel(x,i) = ZV_to_zv(gel(z,i));
     653                 :        170 :   return x;
     654                 :            : }
     655                 :            : 
     656                 :            : GEN
     657                 :     129800 : zv_to_Flv(GEN z, ulong p)
     658                 :            : {
     659                 :     129800 :   long i, l = lg(z);
     660                 :     129800 :   GEN x = cgetg(l,t_VECSMALL);
     661         [ +  + ]:    2055400 :   for (i=1; i<l; i++) x[i] = smodss(z[i],p);
     662                 :     129800 :   return x;
     663                 :            : }
     664                 :            : 
     665                 :            : GEN
     666                 :       8900 : zm_to_Flm(GEN z, ulong p)
     667                 :            : {
     668                 :       8900 :   long i, l = lg(z);
     669                 :       8900 :   GEN x = cgetg(l,t_MAT);
     670         [ +  + ]:     138700 :   for (i=1; i<l; i++) gel(x,i) = zv_to_Flv(gel(z,i),p);
     671                 :       8900 :   return x;
     672                 :            : }
     673                 :            : 
     674                 :            : GEN
     675                 :          0 : ZMV_to_zmV(GEN z)
     676                 :            : {
     677                 :          0 :   long i,l = lg(z);
     678                 :          0 :   GEN x = cgetg(l, t_VEC);
     679         [ #  # ]:          0 :   for (i=1; i<l; i++) gel(x,i) = ZM_to_zm(gel(z,i));
     680                 :          0 :   return x;
     681                 :            : }
     682                 :            : 
     683                 :            : /********************************************************************/
     684                 :            : /**                                                                **/
     685                 :            : /**                         COPY, NEGATION                         **/
     686                 :            : /**                                                                **/
     687                 :            : /********************************************************************/
     688                 :            : GEN
     689                 :     349065 : ZC_copy(GEN x)
     690                 :            : {
     691                 :     349065 :   long i, lx = lg(x);
     692                 :     349065 :   GEN y = cgetg(lx, t_COL);
     693         [ +  + ]:    1949819 :   for (i=1; i<lx; i++)
     694                 :            :   {
     695                 :    1600754 :     GEN c = gel(x,i);
     696         [ +  + ]:    1600754 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
     697                 :            :   }
     698                 :     349065 :   return y;
     699                 :            : }
     700                 :            : 
     701                 :            : GEN
     702                 :      19111 : ZM_copy(GEN x)
     703                 :            : {
     704                 :            :   long l;
     705                 :      19111 :   GEN y = cgetg_copy(x, &l);
     706         [ +  + ]:     167499 :   while (--l > 0) gel(y,l) = ZC_copy(gel(x,l));
     707                 :      19111 :   return y;
     708                 :            : }
     709                 :            : 
     710                 :            : void
     711                 :      40809 : ZV_neg_inplace(GEN M)
     712                 :            : {
     713                 :      40809 :   long l = lg(M);
     714         [ +  + ]:     308773 :   while (--l > 0) gel(M,l) = negi(gel(M,l));
     715                 :      40809 : }
     716                 :            : GEN
     717                 :     864333 : ZC_neg(GEN M)
     718                 :            : {
     719                 :     864333 :   long l = lg(M);
     720                 :     864333 :   GEN N = cgetg(l, t_COL);
     721         [ +  + ]:    6271539 :   while (--l > 0) gel(N,l) = negi(gel(M,l));
     722                 :     864333 :   return N;
     723                 :            : }
     724                 :            : GEN
     725                 :     170606 : zv_neg(GEN M)
     726                 :            : {
     727                 :            :   long l;
     728                 :     170606 :   GEN N = cgetg_copy(M, &l);
     729         [ +  + ]:    1359691 :   while (--l > 0) N[l] = -M[l];
     730                 :     170606 :   return N;
     731                 :            : }
     732                 :            : GEN
     733                 :        110 : zv_neg_inplace(GEN M)
     734                 :            : {
     735                 :        110 :   long l = lg(M);
     736         [ +  + ]:        415 :   while (--l > 0) M[l] = -M[l];
     737                 :        110 :   return M;
     738                 :            : }
     739                 :            : GEN
     740                 :       3925 : ZM_neg(GEN x)
     741                 :            : {
     742                 :            :   long l;
     743                 :       3925 :   GEN y = cgetg_copy(x, &l);
     744         [ +  + ]:      17430 :   while (--l > 0) gel(y,l) = ZC_neg(gel(x,l));
     745                 :       3925 :   return y;
     746                 :            : }
     747                 :            : 
     748                 :            : void
     749                 :     631069 : ZV_togglesign(GEN M)
     750                 :            : {
     751                 :     631069 :   long l = lg(M);
     752         [ +  + ]:   16920120 :   while (--l > 0) togglesign_safe(&gel(M,l));
     753                 :     631069 : }
     754                 :            : void
     755                 :          0 : ZM_togglesign(GEN M)
     756                 :            : {
     757                 :          0 :   long l = lg(M);
     758         [ #  # ]:          0 :   while (--l > 0) ZV_togglesign(gel(M,l));
     759                 :          0 : }
     760                 :            : 
     761                 :            : /********************************************************************/
     762                 :            : /**                                                                **/
     763                 :            : /**                        "DIVISION" mod HNF                      **/
     764                 :            : /**                                                                **/
     765                 :            : /********************************************************************/
     766                 :            : /* Reduce ZC x modulo ZM y in HNF, may return x itself (not a copy) */
     767                 :            : GEN
     768                 :     606467 : ZC_hnfremdiv(GEN x, GEN y, GEN *Q)
     769                 :            : {
     770                 :     606467 :   long i, l = lg(x);
     771                 :            :   GEN q;
     772                 :            : 
     773         [ +  + ]:     606467 :   if (Q) *Q = cgetg(l,t_COL);
     774         [ -  + ]:     606467 :   if (l == 1) return cgetg(1,t_COL);
     775         [ +  + ]:    3614085 :   for (i = l-1; i>0; i--)
     776                 :            :   {
     777                 :    3007618 :     q = diviiround(gel(x,i), gcoeff(y,i,i));
     778         [ +  + ]:    3007618 :     if (signe(q)) {
     779                 :    1705115 :       togglesign(q);
     780                 :    1705115 :       x = ZC_lincomb(gen_1, q, x, gel(y,i));
     781                 :            :     }
     782         [ +  + ]:    3007618 :     if (Q) gel(*Q, i) = q;
     783                 :            :   }
     784                 :     606467 :   return x;
     785                 :            : }
     786                 :            : 
     787                 :            : /* x = y Q + R, may return some columns of x (not copies) */
     788                 :            : GEN
     789                 :      20275 : ZM_hnfdivrem(GEN x, GEN y, GEN *Q)
     790                 :            : {
     791                 :      20275 :   long lx = lg(x), i;
     792                 :      20275 :   GEN R = cgetg(lx, t_MAT);
     793         [ +  + ]:      20275 :   if (Q)
     794                 :            :   {
     795                 :       2070 :     GEN q = cgetg(lx, t_MAT); *Q = q;
     796         [ +  + ]:       3970 :     for (i=1; i<lx; i++) gel(R,i) = ZC_hnfremdiv(gel(x,i),y,(GEN*)(q+i));
     797                 :            :   }
     798                 :            :   else
     799         [ +  + ]:      69885 :     for (i=1; i<lx; i++)
     800                 :            :     {
     801                 :      51680 :       pari_sp av = avma;
     802                 :      51680 :       GEN z = ZC_hnfrem(gel(x,i),y);
     803         [ +  + ]:      51680 :       gel(R,i) = (avma == av)? ZC_copy(z): gerepileupto(av, z);
     804                 :            :     }
     805                 :      20275 :   return R;
     806                 :            : }
     807                 :            : 
     808                 :            : 
     809                 :            : /********************************************************************/
     810                 :            : /**                                                                **/
     811                 :            : /**                               TESTS                            **/
     812                 :            : /**                                                                **/
     813                 :            : /********************************************************************/
     814                 :            : int
     815                 :    9949230 : zv_equal0(GEN V)
     816                 :            : {
     817                 :    9949230 :   long l = lg(V);
     818         [ +  + ]:   15752455 :   while (--l > 0)
     819         [ +  + ]:   12504820 :     if (V[l]) return 0;
     820                 :    9949230 :   return 1;
     821                 :            : }
     822                 :            : 
     823                 :            : int
     824                 :     199146 : ZV_equal0(GEN V)
     825                 :            : {
     826                 :     199146 :   long l = lg(V);
     827         [ +  + ]:     744884 :   while (--l > 0)
     828         [ +  + ]:     696466 :     if (signe(gel(V,l))) return 0;
     829                 :     199146 :   return 1;
     830                 :            : }
     831                 :            : 
     832                 :            : static int
     833                 :    6616412 : ZV_equal_lg(GEN V, GEN W, long l)
     834                 :            : {
     835         [ +  + ]:   12236849 :   while (--l > 0)
     836         [ +  + ]:   10620750 :     if (!equalii(gel(V,l), gel(W,l))) return 0;
     837                 :    6616412 :   return 1;
     838                 :            : }
     839                 :            : int
     840                 :    5544456 : ZV_equal(GEN V, GEN W)
     841                 :            : {
     842                 :    5544456 :   long l = lg(V);
     843         [ -  + ]:    5544456 :   if (lg(W) != l) return 0;
     844                 :    5544456 :   return ZV_equal_lg(V, W, l);
     845                 :            : }
     846                 :            : int
     847                 :     347767 : ZM_equal(GEN A, GEN B)
     848                 :            : {
     849                 :     347767 :   long i, m, l = lg(A);
     850         [ +  + ]:     347767 :   if (lg(B) != l) return 0;
     851         [ -  + ]:     347627 :   if (l == 1) return 1;
     852                 :     347627 :   m = lgcols(A);
     853         [ -  + ]:     347627 :   if (lgcols(B) != m) return 0;
     854         [ +  + ]:    1392218 :   for (i = 1; i < l; i++)
     855         [ +  + ]:    1071956 :     if (!ZV_equal_lg(gel(A,i), gel(B,i), m)) return 0;
     856                 :     347767 :   return 1;
     857                 :            : }
     858                 :            : int
     859                 :    1608957 : zv_equal(GEN V, GEN W)
     860                 :            : {
     861                 :    1608957 :   long l = lg(V);
     862         [ +  + ]:    1608957 :   if (lg(W) != l) return 0;
     863         [ +  + ]:   10567954 :   while (--l > 0)
     864         [ +  + ]:    9236987 :     if (V[l] != W[l]) return 0;
     865                 :    1608957 :   return 1;
     866                 :            : }
     867                 :            : 
     868                 :            : int
     869                 :        225 : zvV_equal(GEN V, GEN W)
     870                 :            : {
     871                 :        225 :   long l = lg(V);
     872         [ +  + ]:        225 :   if (lg(W) != l) return 0;
     873         [ +  + ]:      41680 :   while (--l > 0)
     874         [ +  + ]:      41550 :     if (!zv_equal(gel(V,l),gel(W,l))) return 0;
     875                 :        225 :   return 1;
     876                 :            : }
     877                 :            : 
     878                 :            : int
     879                 :      35865 : ZM_ishnf(GEN x)
     880                 :            : {
     881                 :      35865 :   long i,j, lx = lg(x);
     882         [ +  + ]:     168975 :   for (i=1; i<lx; i++)
     883                 :            :   {
     884                 :     138215 :     GEN xii = gcoeff(x,i,i);
     885         [ +  + ]:     138215 :     if (signe(xii) <= 0) return 0;
     886         [ +  + ]:     521380 :     for (j=1; j<i; j++)
     887         [ -  + ]:     383500 :       if (signe(gcoeff(x,i,j))) return 0;
     888         [ +  + ]:     541865 :     for (j=i+1; j<lx; j++)
     889                 :            :     {
     890                 :     408755 :       GEN xij = gcoeff(x,i,j);
     891 [ +  + ][ +  + ]:     408755 :       if (signe(xij)<0 || cmpii(xij,xii)>=0) return 0;
     892                 :            :     }
     893                 :            :   }
     894                 :      35865 :   return 1;
     895                 :            : }
     896                 :            : int
     897                 :      61244 : ZM_isidentity(GEN x)
     898                 :            : {
     899                 :      61244 :   long i,j, lx = lg(x);
     900                 :            : 
     901         [ -  + ]:      61244 :   if (lx == 1) return 1;
     902         [ -  + ]:      61244 :   if (lx != lgcols(x)) return 0;
     903         [ +  + ]:     519769 :   for (j=1; j<lx; j++)
     904                 :            :   {
     905                 :     458525 :     GEN c = gel(x,j), t;
     906         [ +  + ]:    2087281 :     for (i=1; i<j; )
     907         [ -  + ]:    1628756 :       if (signe(gel(c,i++))) return 0;
     908                 :            :     /* i = j */
     909                 :     458525 :     t = gel(c,i++);
     910 [ +  - ][ -  + ]:     458525 :       if (!is_pm1(t) || signe(t) < 0) return 0;
     911         [ +  + ]:    2087281 :     for (   ; i<lx; )
     912         [ -  + ]:    1628756 :       if (signe(gel(c,i++))) return 0;
     913                 :            :   }
     914                 :      61244 :   return 1;
     915                 :            : }
     916                 :            : 
     917                 :            : /********************************************************************/
     918                 :            : /**                                                                **/
     919                 :            : /**                       MISCELLANEOUS                            **/
     920                 :            : /**                                                                **/
     921                 :            : /********************************************************************/
     922                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
     923                 :            : int
     924                 :     320650 : ZV_cmp(GEN x, GEN y)
     925                 :            : {
     926                 :     320650 :   long fl,i, lx = lg(x);
     927         [ +  + ]:     752147 :   for (i=1; i<lx; i++)
     928         [ +  + ]:     616618 :     if (( fl = cmpii(gel(x,i), gel(y,i)) )) return fl;
     929                 :     320650 :   return 0;
     930                 :            : }
     931                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
     932                 :            : int
     933                 :       2376 : ZV_abscmp(GEN x, GEN y)
     934                 :            : {
     935                 :       2376 :   long fl,i, lx = lg(x);
     936         [ +  + ]:      13565 :   for (i=1; i<lx; i++)
     937         [ +  + ]:      13507 :     if (( fl = absi_cmp(gel(x,i), gel(y,i)) )) return fl;
     938                 :       2376 :   return 0;
     939                 :            : }
     940                 :            : 
     941                 :            : long
     942                 :     376667 : zv_content(GEN x)
     943                 :            : {
     944                 :     376667 :   long i, l = lg(x), s = labs(x[1]);
     945 [ +  + ][ +  + ]:     736781 :   for (i=2; i<l && s!=1; i++) s = cgcd(x[i],s);
     946                 :     376667 :   return s;
     947                 :            : }
     948                 :            : GEN
     949                 :       1960 : ZV_content(GEN x)
     950                 :            : {
     951                 :       1960 :   long i, l = lg(x);
     952                 :       1960 :   pari_sp av = avma;
     953                 :            :   GEN c;
     954         [ -  + ]:       1960 :   if (l == 1) return gen_1;
     955         [ +  + ]:       1960 :   if (l == 2) return absi(gel(x,1));
     956                 :        820 :   c = gel(x,1);
     957         [ +  + ]:       1785 :   for (i = 2; i < l; i++)
     958                 :            :   {
     959                 :       1185 :     c = gcdii(c, gel(x,i));
     960         [ +  + ]:       1185 :     if (is_pm1(c)) { avma = av; return gen_1; }
     961                 :            :   }
     962                 :       1960 :   return gerepileuptoint(av, c);
     963                 :            : }
     964                 :            : 
     965                 :            : GEN
     966                 :     503663 : ZM_det_triangular(GEN mat)
     967                 :            : {
     968                 :            :   pari_sp av;
     969                 :     503663 :   long i,l = lg(mat);
     970                 :            :   GEN s;
     971                 :            : 
     972 [ +  + ][ +  + ]:     503663 :   if (l<3) return l<2? gen_1: icopy(gcoeff(mat,1,1));
     973                 :     493019 :   av = avma; s = gcoeff(mat,1,1);
     974         [ +  + ]:    1465056 :   for (i=2; i<l; i++) s = mulii(s,gcoeff(mat,i,i));
     975                 :     503663 :   return gerepileuptoint(av,s);
     976                 :            : }
     977                 :            : 
     978                 :            : /* assumes no overflow */
     979                 :            : long
     980                 :     206755 : zv_prod(GEN v)
     981                 :            : {
     982                 :     206755 :   long n, i, l = lg(v);
     983         [ +  + ]:     206755 :   if (l == 1) return 1;
     984         [ +  + ]:     230245 :   n = v[1]; for (i = 2; i < l; i++) n *= v[i];
     985                 :     206755 :   return n;
     986                 :            : }
     987                 :            : /* product of ulongs */
     988                 :            : GEN
     989                 :     259425 : zv_prod_Z(GEN v)
     990                 :            : {
     991                 :     259425 :   pari_sp av = avma;
     992                 :     259425 :   long k, n = lg(v)-1, m;
     993                 :            :   GEN x;
     994         [ +  + ]:     259425 :   if (n == 0) return gen_1;
     995         [ +  + ]:     245535 :   if (n == 1) return utoi(v[1]);
     996         [ +  + ]:     205545 :   if (n == 2) return muluu(v[1], v[2]);
     997                 :     116490 :   m = n >> 1;
     998         [ +  + ]:     116490 :   x = cgetg(m + (odd(n)? 2: 1), t_VEC);
     999         [ +  + ]:     260870 :   for (k = 1; k <= m; k++) gel(x,k) = muluu(v[k<<1], v[(k<<1)-1]);
    1000         [ +  + ]:     116490 :   if (odd(n)) gel(x,k) = utoipos(v[n]);
    1001                 :     259425 :   return gerepileuptoint(av, divide_conquer_prod(x, mulii));
    1002                 :            : }
    1003                 :            : 
    1004                 :            : GEN
    1005                 :      14919 : ZV_prod(GEN v)
    1006                 :            : {
    1007                 :      14919 :   pari_sp av = avma;
    1008                 :      14919 :   long i, l = lg(v);
    1009                 :            :   GEN n;
    1010         [ +  + ]:      14919 :   if (l == 1) return gen_1;
    1011         [ +  + ]:      14434 :   if (l > 7) return gerepileuptoint(av, divide_conquer_prod(v, mulii));
    1012                 :      12709 :   n = gel(v,1);
    1013         [ +  + ]:      12709 :   if (l == 2) return icopy(n);
    1014         [ +  + ]:      22304 :   for (i = 2; i < l; i++) n = mulii(n, gel(v,i));
    1015                 :      14919 :   return gerepileuptoint(av, n);
    1016                 :            : }
    1017                 :            : /* assumes no overflow */
    1018                 :            : long
    1019                 :        145 : zv_sum(GEN v)
    1020                 :            : {
    1021                 :        145 :   long n, i, l = lg(v);
    1022         [ +  + ]:        145 :   if (l == 1) return 0;
    1023         [ +  + ]:        700 :   n = v[1]; for (i = 2; i < l; i++) n += v[i];
    1024                 :        145 :   return n;
    1025                 :            : }
    1026                 :            : GEN
    1027                 :         40 : ZV_sum(GEN v)
    1028                 :            : {
    1029                 :         40 :   pari_sp av = avma;
    1030                 :         40 :   long i, l = lg(v);
    1031                 :            :   GEN n;
    1032         [ -  + ]:         40 :   if (l == 1) return gen_0;
    1033                 :         40 :   n = gel(v,1);
    1034         [ -  + ]:         40 :   if (l == 2) return icopy(n);
    1035         [ +  + ]:        370 :   for (i = 2; i < l; i++) n = addii(n, gel(v,i));
    1036                 :         40 :   return gerepileuptoint(av, n);
    1037                 :            : }
    1038                 :            : 
    1039                 :            : /********************************************************************/
    1040                 :            : /**                                                                **/
    1041                 :            : /**         GRAM SCHMIDT REDUCTION (integer matrices)              **/
    1042                 :            : /**                                                                **/
    1043                 :            : /********************************************************************/
    1044                 :            : 
    1045                 :            : /* L[k,] += q * L[l,], l < k. Inefficient if q = 0 */
    1046                 :            : static void
    1047                 :     149221 : Zupdate_row(long k, long l, GEN q, GEN L, GEN B)
    1048                 :            : {
    1049                 :     149221 :   long i, qq = itos_or_0(q);
    1050         [ +  + ]:     149221 :   if (!qq)
    1051                 :            :   {
    1052         [ +  + ]:      12377 :     for(i=1;i<l;i++)  gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulii(q,gcoeff(L,l,i)));
    1053                 :       3451 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulii(q,B));
    1054                 :     149221 :     return;
    1055                 :            :   }
    1056         [ +  + ]:     145770 :   if (qq == 1) {
    1057         [ +  + ]:      59699 :     for (i=1;i<l; i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),gcoeff(L,l,i));
    1058                 :      33840 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), B);
    1059         [ +  + ]:     111930 :   } else if (qq == -1) {
    1060         [ +  + ]:     133035 :     for (i=1;i<l; i++) gcoeff(L,k,i) = subii(gcoeff(L,k,i),gcoeff(L,l,i));
    1061                 :      71498 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), negi(B));
    1062                 :            :   } else {
    1063         [ +  + ]:      80305 :     for(i=1;i<l;i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulsi(qq,gcoeff(L,l,i)));
    1064                 :      40432 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulsi(qq,B));
    1065                 :            :   }
    1066                 :            : }
    1067                 :            : 
    1068                 :            : /* update L[k,] */
    1069                 :            : static void
    1070                 :     485771 : ZRED(long k, long l, GEN x, GEN L, GEN B)
    1071                 :            : {
    1072                 :     485771 :   GEN q = truedivii(addii(B,shifti(gcoeff(L,k,l),1)), shifti(B,1));
    1073         [ +  + ]:     634992 :   if (!signe(q)) return;
    1074                 :     149221 :   q = negi(q);
    1075                 :     149221 :   Zupdate_row(k,l,q,L,B);
    1076                 :     149221 :   gel(x,k) = ZC_lincomb(gen_1, q, gel(x,k), gel(x,l));
    1077                 :            : }
    1078                 :            : 
    1079                 :            : /* Gram-Schmidt reduction, x a ZM */
    1080                 :            : static void
    1081                 :     649256 : ZincrementalGS(GEN x, GEN L, GEN B, long k)
    1082                 :            : {
    1083                 :            :   long i, j;
    1084         [ +  + ]:    2311630 :   for (j=1; j<=k; j++)
    1085                 :            :   {
    1086                 :    1662374 :     pari_sp av = avma;
    1087                 :    1662374 :     GEN u = ZV_dotproduct(gel(x,k), gel(x,j));
    1088         [ +  + ]:    3750040 :     for (i=1; i<j; i++)
    1089                 :            :     {
    1090                 :    2087666 :       u = subii(mulii(gel(B,i+1), u), mulii(gcoeff(L,k,i), gcoeff(L,j,i)));
    1091                 :    2087666 :       u = diviiexact(u, gel(B,i));
    1092                 :            :     }
    1093                 :    1662374 :     gcoeff(L,k,j) = gerepileuptoint(av, u);
    1094                 :            :   }
    1095                 :     649256 :   gel(B,k+1) = gcoeff(L,k,k); gcoeff(L,k,k) = gen_1;
    1096                 :     649256 : }
    1097                 :            : 
    1098                 :            : /* Variant reducemodinvertible(ZC v, ZM y), when y singular.
    1099                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1100                 :            : static GEN
    1101                 :     166340 : ZC_reducemodmatrix_i(GEN v, GEN y)
    1102                 :            : {
    1103                 :     166340 :   GEN B, L, x = shallowconcat(y, v);
    1104                 :     166340 :   long k, lx = lg(x), nx = lx-1;
    1105                 :            : 
    1106                 :     166340 :   B = scalarcol_shallow(gen_1, lx);
    1107                 :     166340 :   L = zeromatcopy(nx, nx);
    1108         [ +  + ]:     801351 :   for (k=1; k <= nx; k++) ZincrementalGS(x, L, B, k);
    1109         [ +  + ]:     635011 :   for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1110                 :     166340 :   return gel(x,nx);
    1111                 :            : }
    1112                 :            : GEN
    1113                 :     166340 : ZC_reducemodmatrix(GEN v, GEN y) {
    1114                 :     166340 :   pari_sp av = avma;
    1115                 :     166340 :   return gerepilecopy(av, ZC_reducemodmatrix_i(v,y));
    1116                 :            : }
    1117                 :            : 
    1118                 :            : /* Variant reducemodinvertible(ZM v, ZM y), when y singular.
    1119                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1120                 :            : static GEN
    1121                 :       3145 : ZM_reducemodmatrix_i(GEN v, GEN y)
    1122                 :            : {
    1123                 :            :   GEN B, L, V;
    1124                 :       3145 :   long j, k, lv = lg(v), nx = lg(y), lx = nx+1;
    1125                 :            : 
    1126                 :       3145 :   V = cgetg(lv, t_MAT);
    1127                 :       3145 :   B = scalarcol_shallow(gen_1, lx);
    1128                 :       3145 :   L = zeromatcopy(nx, nx);
    1129         [ +  + ]:      10445 :   for (k=1; k < nx; k++) ZincrementalGS(y, L, B, k);
    1130         [ +  + ]:      10090 :   for (j = 1; j < lg(v); j++)
    1131                 :            :   {
    1132                 :       6945 :     GEN x = shallowconcat(y, gel(v,j));
    1133                 :       6945 :     ZincrementalGS(x, L, B, nx); /* overwrite last */
    1134         [ +  + ]:      24045 :     for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1135                 :       6945 :     gel(V,j) = gel(x,nx);
    1136                 :            :   }
    1137                 :       3145 :   return V;
    1138                 :            : }
    1139                 :            : GEN
    1140                 :       3145 : ZM_reducemodmatrix(GEN v, GEN y) {
    1141                 :       3145 :   pari_sp av = avma;
    1142                 :       3145 :   return gerepilecopy(av, ZM_reducemodmatrix_i(v,y));
    1143                 :            : }
    1144                 :            : 
    1145                 :            : GEN
    1146                 :     166305 : ZC_reducemodlll(GEN x,GEN y)
    1147                 :            : {
    1148                 :     166305 :   pari_sp av = avma;
    1149                 :     166305 :   GEN z = ZC_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1150                 :     166305 :   return gerepilecopy(av, z);
    1151                 :            : }
    1152                 :            : GEN
    1153                 :          0 : ZM_reducemodlll(GEN x,GEN y)
    1154                 :            : {
    1155                 :          0 :   pari_sp av = avma;
    1156                 :          0 :   GEN z = ZM_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1157                 :          0 :   return gerepilecopy(av, z);
    1158                 :            : }

Generated by: LCOV version 1.9