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 18590-b5f7c1c) Lines: 727 807 90.1 %
Date: 2016-02-09 Functions: 103 110 93.6 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 474 580 81.7 %

           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                 :      36239 : check_ZV(GEN x, long l)
      19                 :            : {
      20                 :            :   long i;
      21         [ +  + ]:     208208 :   for (i=1; i<l; i++)
      22         [ +  + ]:     172053 :     if (typ(gel(x,i)) != t_INT) return 0;
      23                 :      36239 :   return 1;
      24                 :            : }
      25                 :            : void
      26                 :     455265 : RgV_check_ZV(GEN A, const char *s)
      27                 :            : {
      28         [ +  + ]:     455265 :   if (!RgV_is_ZV(A)) pari_err_TYPE(stack_strcat(s," [integer vector]"), A);
      29                 :     455251 : }
      30                 :            : void
      31                 :      11851 : RgM_check_ZM(GEN A, const char *s)
      32                 :            : {
      33                 :      11851 :   long n = lg(A);
      34         [ +  + ]:      11851 :   if (n != 1)
      35                 :            :   {
      36                 :      11816 :     long j, m = lgcols(A);
      37         [ +  + ]:      47971 :     for (j=1; j<n; j++)
      38         [ +  + ]:      36239 :       if (!check_ZV(gel(A,j), m))
      39                 :         84 :         pari_err_TYPE(stack_strcat(s," [integer matrix]"), A);
      40                 :            :   }
      41                 :      11767 : }
      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                 :       1799 : ZM_max_lg(GEN x)
      52                 :            : {
      53                 :       1799 :   long i, prec = 2, n = lg(x);
      54         [ +  - ]:       1799 :   if (n != 1)
      55                 :            :   {
      56                 :       1799 :     long j, m = lgcols(x);
      57         [ +  + ]:      12810 :     for (j=1; j<n; j++)
      58                 :            :     {
      59                 :      11011 :       GEN c = gel(x,j);
      60 [ +  + ][ +  + ]:     172032 :       for (i=1; i<m; i++) { long l = lgefint(gel(c,i)); if (l > prec) prec = l; }
      61                 :            :     }
      62                 :            :   }
      63                 :       1799 :   return prec;
      64                 :            : }
      65                 :            : 
      66                 :            : GEN
      67                 :       1085 : ZM_supnorm(GEN x)
      68                 :            : {
      69                 :       1085 :   long i, j, h, lx = lg(x);
      70                 :       1085 :   GEN s = gen_0;
      71         [ -  + ]:       1085 :   if (lx == 1) return gen_1;
      72                 :       1085 :   h = lgcols(x);
      73         [ +  + ]:       9842 :   for (j=1; j<lx; j++)
      74                 :            :   {
      75                 :       8757 :     GEN xj = gel(x,j);
      76         [ +  + ]:     167636 :     for (i=1; i<h; i++)
      77                 :            :     {
      78                 :     158879 :       GEN c = gel(xj,i);
      79         [ +  + ]:     158879 :       if (absi_cmp(c, s) > 0) s = c;
      80                 :            :     }
      81                 :            :   }
      82                 :       1085 :   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                 :      14661 : ZM_nc_mul_i(GEN x, GEN y, long c, long l)
      93                 :            : {
      94                 :            :   long i, j;
      95                 :            :   pari_sp av;
      96                 :      14661 :   GEN z = cgetg(l,t_COL), s;
      97                 :            : 
      98         [ +  + ]:     719253 :   for (i=1; i<l; i++)
      99                 :            :   {
     100                 :     704592 :     av = avma; s = muliu(gcoeff(x,i,1),y[1]);
     101         [ +  + ]:   62728700 :     for (j=2; j<c; j++)
     102         [ +  + ]:   62024108 :       if (y[j]) s = addii(s, muliu(gcoeff(x,i,j),y[j]));
     103                 :     704592 :     gel(z,i) = gerepileuptoint(av,s);
     104                 :            :   }
     105                 :      14661 :   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                 :    1960448 : ZM_zc_mul_i(GEN x, GEN y, long c, long l)
     123                 :            : {
     124                 :            :   long i, j;
     125                 :    1960448 :   GEN z = cgetg(l,t_COL);
     126                 :            : 
     127         [ +  + ]:   13673380 :   for (i=1; i<l; i++)
     128                 :            :   {
     129                 :   11712932 :     pari_sp av = avma;
     130                 :   11712932 :     GEN s = mulis(gcoeff(x,i,1),y[1]);
     131         [ +  + ]:  238444718 :     for (j=2; j<c; j++)
     132         [ +  + ]:  226731786 :       if (y[j]) s = addii(s, mulis(gcoeff(x,i,j),y[j]));
     133                 :   11712932 :     gel(z,i) = gerepileuptoint(av,s);
     134                 :            :   }
     135                 :    1960448 :   return z;
     136                 :            : }
     137                 :            : GEN
     138                 :    1295330 : ZM_zc_mul(GEN x, GEN y) {
     139                 :    1295330 :   long l = lg(x);
     140         [ -  + ]:    1295330 :   if (l == 1) return cgetg(1, t_COL);
     141                 :    1295330 :   return ZM_zc_mul_i(x,y, l, lgcols(x));
     142                 :            : }
     143                 :            : 
     144                 :            : /* y non-empty ZM, x a compatible zv (dimension > 0). */
     145                 :            : GEN
     146                 :       1064 : zv_ZM_mul(GEN x, GEN y) {
     147                 :       1064 :   long i,j, lx = lg(x), ly = lg(y);
     148                 :            :   GEN z;
     149         [ -  + ]:       1064 :   if (lx == 1) return zerovec(ly-1);
     150                 :       1064 :   z = cgetg(ly,t_VEC);
     151         [ +  + ]:       2688 :   for (j=1; j<ly; j++)
     152                 :            :   {
     153                 :       1624 :     pari_sp av = avma;
     154                 :       1624 :     GEN s = mulsi(x[1], gcoeff(y,1,j));
     155         [ +  + ]:       3276 :     for (i=2; i<lx; i++)
     156         [ +  + ]:       1652 :       if (x[i]) s = addii(s, mulsi(x[i], gcoeff(y,i,j)));
     157                 :       1624 :     gel(z,j) = gerepileuptoint(av,s);
     158                 :            :   }
     159                 :       1064 :   return z;
     160                 :            : }
     161                 :            : 
     162                 :            : /* x ZM, y a compatible zm (dimension > 0). */
     163                 :            : GEN
     164                 :     316479 : ZM_zm_mul(GEN x, GEN y)
     165                 :            : {
     166                 :     316479 :   long j, c, l = lg(x), ly = lg(y);
     167                 :     316479 :   GEN z = cgetg(ly, t_MAT);
     168         [ -  + ]:     316479 :   if (l == 1) return z;
     169                 :     316479 :   c = lgcols(x);
     170         [ +  + ]:     981597 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_zc_mul_i(x, gel(y,j), l,c);
     171                 :     316479 :   return z;
     172                 :            : }
     173                 :            : /* x ZM, y a compatible zn (dimension > 0). */
     174                 :            : GEN
     175                 :       1558 : ZM_nm_mul(GEN x, GEN y)
     176                 :            : {
     177                 :       1558 :   long j, c, l = lg(x), ly = lg(y);
     178                 :       1558 :   GEN z = cgetg(ly, t_MAT);
     179         [ -  + ]:       1558 :   if (l == 1) return z;
     180                 :       1558 :   c = lgcols(x);
     181         [ +  + ]:      16219 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_nc_mul_i(x, gel(y,j), l,c);
     182                 :       1558 :   return z;
     183                 :            : }
     184                 :            : 
     185                 :            : /* Strassen-Winograd algorithm */
     186                 :            : 
     187                 :            : /*
     188                 :            :   Return A[ma+1..ma+da, na+1..na+ea] - B[mb+1..mb+db, nb+1..nb+eb]
     189                 :            :   as an (m x n)-matrix, padding the input with zeroes as necessary.
     190                 :            : */
     191                 :            : static GEN
     192                 :      92176 : add_slices(long m, long n,
     193                 :            :            GEN A, long ma, long da, long na, long ea,
     194                 :            :            GEN B, long mb, long db, long nb, long eb)
     195                 :            : {
     196                 :      92176 :   long min_d = minss(da, db), min_e = minss(ea, eb), i, j;
     197                 :      92176 :   GEN M = cgetg(n + 1, t_MAT), C;
     198                 :            : 
     199         [ +  + ]:    2490481 :   for (j = 1; j <= min_e; j++) {
     200                 :    2398305 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     201         [ +  + ]:   69672673 :     for (i = 1; i <= min_d; i++)
     202                 :   67274368 :       gel(C, i) = addii(gcoeff(A, ma + i, na + j),
     203                 :   67274368 :                         gcoeff(B, mb + i, nb + j));
     204         [ +  + ]:    2437834 :     for (; i <= da; i++)
     205                 :      39529 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     206         [ -  + ]:    2398305 :     for (; i <= db; i++)
     207                 :          0 :       gel(C, i) = gcoeff(B, mb + i, nb + j);
     208         [ -  + ]:    2398305 :     for (; i <= m; i++)
     209                 :          0 :       gel(C, i) = gen_0;
     210                 :            :   }
     211         [ +  + ]:      95872 :   for (; j <= ea; j++) {
     212                 :       3696 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     213         [ +  + ]:     108094 :     for (i = 1; i <= da; i++)
     214                 :     104398 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     215         [ -  + ]:       3696 :     for (; i <= m; i++)
     216                 :          0 :       gel(C, i) = gen_0;
     217                 :            :   }
     218         [ -  + ]:      92176 :   for (; j <= eb; j++) {
     219                 :          0 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     220         [ #  # ]:          0 :     for (i = 1; i <= db; i++)
     221                 :          0 :       gel(C, i) = gcoeff(B, mb + i, nb + j);
     222         [ #  # ]:          0 :     for (; i <= m; i++)
     223                 :          0 :       gel(C, i) = gen_0;
     224                 :            :   }
     225         [ -  + ]:      92176 :   for (; j <= n; j++)
     226                 :          0 :     gel(M, j) = zerocol(m);
     227                 :      92176 :   return M;
     228                 :            : }
     229                 :            : 
     230                 :            : /*
     231                 :            :   Return A[ma+1..ma+da, na+1..na+ea] - B[mb+1..mb+db, nb+1..nb+eb]
     232                 :            :   as an (m x n)-matrix, padding the input with zeroes as necessary.
     233                 :            : */
     234                 :            : static GEN
     235                 :      80654 : subtract_slices(long m, long n,
     236                 :            :                 GEN A, long ma, long da, long na, long ea,
     237                 :            :                 GEN B, long mb, long db, long nb, long eb)
     238                 :            : {
     239                 :      80654 :   long min_d = minss(da, db), min_e = minss(ea, eb), i, j;
     240                 :      80654 :   GEN M = cgetg(n + 1, t_MAT), C;
     241                 :            : 
     242         [ +  + ]:    2270996 :   for (j = 1; j <= min_e; j++) {
     243                 :    2190342 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     244         [ +  + ]:   67763045 :     for (i = 1; i <= min_d; i++)
     245                 :   65572703 :       gel(C, i) = subii(gcoeff(A, ma + i, na + j),
     246                 :   65572703 :                         gcoeff(B, mb + i, nb + j));
     247         [ +  + ]:    2251340 :     for (; i <= da; i++)
     248                 :      60998 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     249         [ +  + ]:    2243584 :     for (; i <= db; i++)
     250                 :      53242 :       gel(C, i) = negi(gcoeff(B, mb + i, nb + j));
     251         [ -  + ]:    2190342 :     for (; i <= m; i++)
     252                 :          0 :       gel(C, i) = gen_0;
     253                 :            :   }
     254         [ -  + ]:      80654 :   for (; j <= ea; j++) {
     255                 :          0 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     256         [ #  # ]:          0 :     for (i = 1; i <= da; i++)
     257                 :          0 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     258         [ #  # ]:          0 :     for (; i <= m; i++)
     259                 :          0 :       gel(C, i) = gen_0;
     260                 :            :   }
     261         [ +  + ]:      82229 :   for (; j <= eb; j++) {
     262                 :       1575 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     263         [ +  + ]:      58128 :     for (i = 1; i <= db; i++)
     264                 :      56553 :       gel(C, i) = negi(gcoeff(B, mb + i, nb + j));
     265         [ -  + ]:       1575 :     for (; i <= m; i++)
     266                 :          0 :       gel(C, i) = gen_0;
     267                 :            :   }
     268         [ +  + ]:      82229 :   for (; j <= n; j++)
     269                 :       1575 :     gel(M, j) = zerocol(m);
     270                 :      80654 :   return M;
     271                 :            : }
     272                 :            : 
     273                 :            : static GEN ZM_mul_i(GEN x, GEN y, long l, long lx, long ly);
     274                 :            : 
     275                 :            : /* Strassen-Winograd matrix product A (m x n) * B (n x p) */
     276                 :            : static GEN
     277                 :      11522 : ZM_mul_sw(GEN A, GEN B, long m, long n, long p)
     278                 :            : {
     279                 :      11522 :   pari_sp av = avma;
     280                 :      11522 :   long m1 = (m + 1)/2, m2 = m/2,
     281                 :      11522 :     n1 = (n + 1)/2, n2 = n/2,
     282                 :      11522 :     p1 = (p + 1)/2, p2 = p/2;
     283                 :            :   GEN A11, A12, A22, B11, B21, B22,
     284                 :            :     S1, S2, S3, S4, T1, T2, T3, T4,
     285                 :            :     M1, M2, M3, M4, M5, M6, M7,
     286                 :            :     V1, V2, V3, C11, C12, C21, C22, C;
     287                 :            : 
     288                 :      11522 :   T2 = subtract_slices(n1, p2, B, 0, n1, p1, p2, B, n1, n2, p1, p2);
     289                 :      11522 :   S1 = subtract_slices(m2, n1, A, m1, m2, 0, n1, A, 0, m2, 0, n1);
     290                 :      11522 :   M2 = ZM_mul_i(S1, T2, m2 + 1, n1 + 1, p2 + 1);
     291         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     292                 :          0 :     gerepileall(av, 2, &T2, &M2);  /* destroy S1 */
     293                 :      11522 :   T3 = subtract_slices(n1, p1, T2, 0, n1, 0, p2, B, 0, n1, 0, p1);
     294         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     295                 :          0 :     gerepileall(av, 2, &M2, &T3);  /* destroy T2 */
     296                 :      11522 :   S2 = add_slices(m2, n1, A, m1, m2, 0, n1, A, m1, m2, n1, n2);
     297                 :      11522 :   T1 = subtract_slices(n1, p1, B, 0, n1, p1, p2, B, 0, n1, 0, p2);
     298                 :      11522 :   M3 = ZM_mul_i(S2, T1, m2 + 1, n1 + 1, p2 + 1);
     299         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     300                 :          0 :     gerepileall(av, 4, &M2, &T3, &S2, &M3);  /* destroy T1 */
     301                 :      11522 :   S3 = subtract_slices(m1, n1, S2, 0, m2, 0, n1, A, 0, m1, 0, n1);
     302         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     303                 :          0 :     gerepileall(av, 4, &M2, &T3, &M3, &S3);  /* destroy S2 */
     304                 :      11522 :   A11 = matslice(A, 1, m1, 1, n1);
     305                 :      11522 :   B11 = matslice(B, 1, n1, 1, p1);
     306                 :      11522 :   M1 = ZM_mul_i(A11, B11, m1 + 1, n1 + 1, p1 + 1);
     307         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     308                 :          0 :     gerepileall(av, 5, &M2, &T3, &M3, &S3, &M1);  /* destroy A11, B11 */
     309                 :      11522 :   A12 = matslice(A, 1, m1, n1 + 1, n);
     310                 :      11522 :   B21 = matslice(B, n1 + 1, n, 1, p1);
     311                 :      11522 :   M4 = ZM_mul_i(A12, B21, m1 + 1, n2 + 1, p1 + 1);
     312         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     313                 :          0 :     gerepileall(av, 6, &M2, &T3, &M3, &S3, &M1, &M4);  /* destroy A12, B21 */
     314                 :      11522 :   C11 = add_slices(m1, p1, M1, 0, m1, 0, p1, M4, 0, m1, 0, p1);
     315         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     316                 :          0 :     gerepileall(av, 6, &M2, &T3, &M3, &S3, &M1, &C11);  /* destroy M4 */
     317                 :      11522 :   M5 = ZM_mul_i(S3, T3, m1 + 1, n1 + 1, p1 + 1);
     318                 :      11522 :   S4 = subtract_slices(m1, n2, A, 0, m1, n1, n2, S3, 0, m1, 0, n2);
     319         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     320                 :          0 :     gerepileall(av, 7, &M2, &T3, &M3, &M1, &C11, &M5, &S4);  /* destroy S3 */
     321                 :      11522 :   T4 = add_slices(n2, p1, B, n1, n2, 0, p1, T3, 0, n2, 0, p1);
     322         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     323                 :          0 :     gerepileall(av, 7, &M2, &M3, &M1, &C11, &M5, &S4, &T4);  /* destroy T3 */
     324                 :      11522 :   V1 = subtract_slices(m1, p1, M1, 0, m1, 0, p1, M5, 0, m1, 0, p1);
     325         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     326                 :          0 :     gerepileall(av, 6, &M2, &M3, &S4, &T4, &C11, &V1);  /* destroy M1, M5 */
     327                 :      11522 :   B22 = matslice(B, n1 + 1, n, p1 + 1, p);
     328                 :      11522 :   M6 = ZM_mul_i(S4, B22, m1 + 1, n2 + 1, p2 + 1);
     329         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     330                 :          0 :     gerepileall(av, 6, &M2, &M3, &T4, &C11, &V1, &M6);  /* destroy S4, B22 */
     331                 :      11522 :   A22 = matslice(A, m1 + 1, m, n1 + 1, n);
     332                 :      11522 :   M7 = ZM_mul_i(A22, T4, m2 + 1, n2 + 1, p1 + 1);
     333         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     334                 :          0 :     gerepileall(av, 6, &M2, &M3, &C11, &V1, &M6, &M7);  /* destroy A22, T4 */
     335                 :      11522 :   V3 = add_slices(m1, p2, V1, 0, m1, 0, p2, M3, 0, m2, 0, p2);
     336                 :      11522 :   C12 = add_slices(m1, p2, V3, 0, m1, 0, p2, M6, 0, m1, 0, p2);
     337         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     338                 :          0 :     gerepileall(av, 6, &M2, &M3, &C11, &V1, &M7, &C12);  /* destroy V3, M6 */
     339                 :      11522 :   V2 = add_slices(m2, p1, V1, 0, m2, 0, p1, M2, 0, m2, 0, p2);
     340         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     341                 :          0 :     gerepileall(av, 5, &M3, &C11, &M7, &C12, &V2);  /* destroy V1, M2 */
     342                 :      11522 :   C21 = add_slices(m2, p1, V2, 0, m2, 0, p1, M7, 0, m2, 0, p1);
     343         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     344                 :          0 :     gerepileall(av, 5, &M3, &C11, &C12, &V2, &C21);  /* destroy M7 */
     345                 :      11522 :   C22 = add_slices(m2, p2, V2, 0, m2, 0, p2, M3, 0, m2, 0, p2);
     346         [ -  + ]:      11522 :   if (gc_needed(av, 1))
     347                 :          0 :     gerepileall(av, 4, &C11, &C12, &C21, &C22);  /* destroy V2, M3 */
     348                 :      11522 :   C = mkmat2(mkcol2(C11, C21), mkcol2(C12, C22));
     349                 :      11522 :   return gerepileupto(av, matconcat(C));
     350                 :            : }
     351                 :            : 
     352                 :            : /* x[i,]*y. Assume lg(x) > 1 and 0 < i < lgcols(x) */
     353                 :            : static GEN
     354                 :  129865417 : ZMrow_ZC_mul_i(GEN x, GEN y, long i, long lx)
     355                 :            : {
     356                 :  129865417 :   pari_sp av = avma;
     357                 :  129865417 :   GEN c = mulii(gcoeff(x,i,1), gel(y,1)), ZERO = gen_0;
     358                 :            :   long k;
     359         [ +  + ]: 2575917148 :   for (k = 2; k < lx; k++)
     360                 :            :   {
     361                 : 2446051731 :     GEN t = mulii(gcoeff(x,i,k), gel(y,k));
     362         [ +  + ]: 2446051731 :     if (t != ZERO) c = addii(c, t);
     363                 :            :   }
     364                 :  129865417 :   return gerepileuptoint(av, c);
     365                 :            : }
     366                 :            : GEN
     367                 :   14950998 : ZMrow_ZC_mul(GEN x, GEN y, long i)
     368                 :   14950998 : { return ZMrow_ZC_mul_i(x, y, i, lg(x)); }
     369                 :            : 
     370                 :            : /* return x * y, 1 < lx = lg(x), l = lgcols(x) */
     371                 :            : static GEN
     372                 :   15027229 : ZM_ZC_mul_i(GEN x, GEN y, long lx, long l)
     373                 :            : {
     374                 :   15027229 :   GEN z = cgetg(l,t_COL);
     375                 :            :   long i;
     376         [ +  + ]:  129941648 :   for (i=1; i<l; i++) gel(z,i) = ZMrow_ZC_mul_i(x,y,i,lx);
     377                 :   15027229 :   return z;
     378                 :            : }
     379                 :            : 
     380                 :            : static GEN
     381                 :    2610287 : ZM_mul_classical(GEN x, GEN y, long l, long lx, long ly)
     382                 :            : {
     383                 :            :   long j;
     384                 :    2610287 :   GEN z = cgetg(ly, t_MAT);
     385         [ +  + ]:   13588242 :   for (j = 1; j < ly; j++)
     386                 :   10977955 :     gel(z, j) = ZM_ZC_mul_i(x, gel(y, j), lx, l);
     387                 :    2610287 :   return z;
     388                 :            : }
     389                 :            : 
     390                 :            : /* Strassen-Winograd used for dim >= ZM_sw_bound */
     391                 :            : static const long ZM_sw_bound = 36;
     392                 :            : 
     393                 :            : static GEN
     394                 :    2589133 : ZM_mul_i(GEN x, GEN y, long l, long lx, long ly)
     395                 :            : {
     396 [ +  + ][ +  + ]:    2589133 :   if (l <= ZM_sw_bound || lx <= ZM_sw_bound || ly <= ZM_sw_bound)
                 [ +  + ]
     397                 :    2577611 :     return ZM_mul_classical(x, y, l, lx, ly);
     398                 :            :   else
     399                 :    2589133 :     return ZM_mul_sw(x, y, l - 1, lx - 1, ly - 1);
     400                 :            : }
     401                 :            : 
     402                 :            : GEN
     403                 :    2511034 : ZM_mul(GEN x, GEN y)
     404                 :            : {
     405                 :    2511034 :   long lx=lg(x), ly=lg(y);
     406         [ +  + ]:    2511034 :   if (ly==1) return cgetg(1,t_MAT);
     407         [ +  + ]:    2508612 :   if (lx==1) return zeromat(0, ly-1);
     408                 :    2511034 :   return ZM_mul_i(x, y, lgcols(x), lx, ly);
     409                 :            : }
     410                 :            : /* assume result is symmetric */
     411                 :            : GEN
     412                 :          0 : ZM_multosym(GEN x, GEN y)
     413                 :            : {
     414                 :          0 :   long j, lx, ly = lg(y);
     415                 :            :   GEN M;
     416         [ #  # ]:          0 :   if (ly == 1) return cgetg(1,t_MAT);
     417                 :          0 :   lx = lg(x); /* = lgcols(y) */
     418         [ #  # ]:          0 :   if (lx == 1) return cgetg(1,t_MAT);
     419                 :            :   /* ly = lgcols(x) */
     420                 :          0 :   M = cgetg(ly, t_MAT);
     421         [ #  # ]:          0 :   for (j=1; j<ly; j++)
     422                 :            :   {
     423                 :          0 :     GEN z = cgetg(ly,t_COL), yj = gel(y,j);
     424                 :            :     long i;
     425         [ #  # ]:          0 :     for (i=1; i<j; i++) gel(z,i) = gcoeff(M,j,i);
     426         [ #  # ]:          0 :     for (i=j; i<ly; i++)gel(z,i) = ZMrow_ZC_mul_i(x,yj,i,lx);
     427                 :          0 :     gel(M,j) = z;
     428                 :            :   }
     429                 :          0 :   return M;
     430                 :            : }
     431                 :            : 
     432                 :            : /* compute m*diagonal(d), assume lg(d) = lg(m). Shallow */
     433                 :            : GEN
     434                 :         14 : ZM_mul_diag(GEN m, GEN d)
     435                 :            : {
     436                 :            :   long j, l;
     437                 :         14 :   GEN y = cgetg_copy(m, &l);
     438         [ +  + ]:         56 :   for (j=1; j<l; j++)
     439                 :            :   {
     440                 :         42 :     GEN c = gel(d,j);
     441         [ +  + ]:         42 :     gel(y,j) = equali1(c)? gel(m,j): ZC_Z_mul(gel(m,j), c);
     442                 :            :   }
     443                 :         14 :   return y;
     444                 :            : }
     445                 :            : /* compute diagonal(d)*m, assume lg(d) = lg(m~). Shallow */
     446                 :            : GEN
     447                 :        784 : ZM_diag_mul(GEN d, GEN m)
     448                 :            : {
     449                 :        784 :   long i, j, l = lg(d), lm = lg(m);
     450                 :        784 :   GEN y = cgetg(lm, t_MAT);
     451         [ +  + ]:       2163 :   for (j=1; j<lm; j++) gel(y,j) = cgetg(l, t_COL);
     452         [ +  + ]:       2205 :   for (i=1; i<l; i++)
     453                 :            :   {
     454                 :       1421 :     GEN c = gel(d,i);
     455         [ +  + ]:       1421 :     if (equali1(c))
     456         [ +  + ]:        686 :       for (j=1; j<lm; j++) gcoeff(y,i,j) = gcoeff(m,i,j);
     457                 :            :     else
     458         [ +  + ]:       3780 :       for (j=1; j<lm; j++) gcoeff(y,i,j) = mulii(gcoeff(m,i,j), c);
     459                 :            :   }
     460                 :        784 :   return y;
     461                 :            : }
     462                 :            : 
     463                 :            : /* assume lx > 1 is lg(x) = lg(y) */
     464                 :            : static GEN
     465                 :   11937632 : ZV_dotproduct_i(GEN x, GEN y, long lx)
     466                 :            : {
     467                 :   11937632 :   pari_sp av = avma;
     468                 :   11937632 :   GEN c = mulii(gel(x,1), gel(y,1));
     469                 :            :   long i;
     470         [ +  + ]:   97257144 :   for (i = 2; i < lx; i++)
     471                 :            :   {
     472                 :   85319512 :     GEN t = mulii(gel(x,i), gel(y,i));
     473         [ +  + ]:   85319512 :     if (t != gen_0) c = addii(c, t);
     474                 :            :   }
     475                 :   11937632 :   return gerepileuptoint(av, c);
     476                 :            : }
     477                 :            : 
     478                 :            : /* x~ * y, assuming result is symmetric */
     479                 :            : GEN
     480                 :     159544 : ZM_transmultosym(GEN x, GEN y)
     481                 :            : {
     482                 :     159544 :   long i, j, l, ly = lg(y);
     483                 :            :   GEN M;
     484         [ -  + ]:     159544 :   if (ly == 1) return cgetg(1,t_MAT);
     485                 :            :   /* lg(x) = ly */
     486                 :     159544 :   l = lgcols(y); /* = lgcols(x) */
     487                 :     159544 :   M = cgetg(ly, t_MAT);
     488         [ +  + ]:    1243609 :   for (i=1; i<ly; i++)
     489                 :            :   {
     490                 :    1084065 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     491                 :    1084065 :     gel(M,i) = c;
     492         [ +  + ]:    4863167 :     for (j=1; j<i; j++)
     493                 :    3779102 :       gcoeff(M,i,j) = gel(c,j) = ZV_dotproduct_i(xi,gel(y,j),l);
     494                 :    1084065 :     gel(c,i) = ZV_dotproduct_i(xi,gel(y,i),l);
     495                 :            :   }
     496                 :     159544 :   return M;
     497                 :            : }
     498                 :            : /* x~ * y */
     499                 :            : GEN
     500                 :        497 : ZM_transmul(GEN x, GEN y)
     501                 :            : {
     502                 :        497 :   long i, j, l, lx, ly = lg(y);
     503                 :            :   GEN M;
     504         [ -  + ]:        497 :   if (ly == 1) return cgetg(1,t_MAT);
     505                 :        497 :   lx = lg(x);
     506                 :        497 :   l = lgcols(y);
     507         [ -  + ]:        497 :   if (lgcols(x) != l) pari_err_OP("operation 'ZM_transmul'", x,y);
     508                 :        497 :   M = cgetg(ly, t_MAT);
     509         [ +  + ]:       1617 :   for (i=1; i<ly; i++)
     510                 :            :   {
     511                 :       1120 :     GEN yi = gel(y,i), c = cgetg(lx,t_COL);
     512                 :       1120 :     gel(M,i) = c;
     513         [ +  + ]:       5061 :     for (j=1; j<lx; j++) gel(c,j) = ZV_dotproduct_i(yi,gel(x,j),l);
     514                 :            :   }
     515                 :        497 :   return M;
     516                 :            : }
     517                 :            : 
     518                 :            : static GEN
     519                 :      32676 : ZM_sqr_i(GEN x, long l)
     520                 :            : {
     521         [ +  - ]:      32676 :   if (l <= ZM_sw_bound)
     522                 :      32676 :     return ZM_mul_classical(x, x, l, l, l);
     523                 :            :   else
     524                 :      32676 :     return ZM_mul_sw(x, x, l - 1, l - 1, l - 1);
     525                 :            : }
     526                 :            : 
     527                 :            : GEN
     528                 :      32676 : ZM_sqr(GEN x)
     529                 :            : {
     530                 :      32676 :   long lx=lg(x);
     531         [ -  + ]:      32676 :   if (lx==1) return cgetg(1,t_MAT);
     532                 :      32676 :   return ZM_sqr_i(x, lx);
     533                 :            : }
     534                 :            : GEN
     535                 :    4117553 : ZM_ZC_mul(GEN x, GEN y)
     536                 :            : {
     537                 :    4117553 :   long lx = lg(x);
     538         [ +  + ]:    4117553 :   return lx==1? cgetg(1,t_COL): ZM_ZC_mul_i(x, y, lx, lgcols(x));
     539                 :            : }
     540                 :            : 
     541                 :            : GEN
     542                 :       1904 : ZM_Z_div(GEN X, GEN c)
     543                 :            : {
     544                 :       1904 :   long i, j, h, l = lg(X);
     545                 :       1904 :   GEN A = cgetg(l, t_MAT);
     546         [ -  + ]:       1904 :   if (l == 1) return A;
     547                 :       1904 :   h = lgcols(X);
     548         [ +  + ]:      30156 :   for (j=1; j<l; j++)
     549                 :            :   {
     550                 :      28252 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     551         [ +  + ]:     720888 :     for (i = 1; i < h; i++) gel(a,i) = gred_frac2(gel(x,i), c);
     552                 :      28252 :     gel(A,j) = a;
     553                 :            :   }
     554                 :       1904 :   return A;
     555                 :            : }
     556                 :            : 
     557                 :            : long
     558                 :  146054748 : zv_dotproduct(GEN x, GEN y)
     559                 :            : {
     560                 :  146054748 :   long i, lx = lg(x);
     561                 :            :   ulong c;
     562         [ -  + ]:  146054748 :   if (lx == 1) return 0;
     563                 :  146054748 :   c = uel(x,1)*uel(y,1);
     564         [ +  + ]: 2275977361 :   for (i = 2; i < lx; i++)
     565                 : 2129922613 :     c += uel(x,i)*uel(y,i);
     566                 :  146054748 :   return c;
     567                 :            : }
     568                 :            : 
     569                 :            : GEN
     570                 :       6125 : ZV_ZM_mul(GEN x, GEN y)
     571                 :            : {
     572                 :       6125 :   long i, lx = lg(x), ly = lg(y);
     573                 :            :   GEN z;
     574         [ +  + ]:       6125 :   if (lx == 1) return zerovec(ly-1);
     575                 :       6111 :   z = cgetg(ly, t_VEC);
     576         [ +  + ]:      17010 :   for (i = 1; i < ly; i++) gel(z,i) = ZV_dotproduct_i(x, gel(y,i), lx);
     577                 :       6125 :   return z;
     578                 :            : }
     579                 :            : 
     580                 :            : GEN
     581                 :          0 : ZC_ZV_mul(GEN x, GEN y)
     582                 :            : {
     583                 :          0 :   long i,j, lx=lg(x), ly=lg(y);
     584                 :            :   GEN z;
     585         [ #  # ]:          0 :   if (ly==1) return cgetg(1,t_MAT);
     586                 :          0 :   z = cgetg(ly,t_MAT);
     587         [ #  # ]:          0 :   for (j=1; j < ly; j++)
     588                 :            :   {
     589                 :          0 :     gel(z,j) = cgetg(lx,t_COL);
     590         [ #  # ]:          0 :     for (i=1; i<lx; i++) gcoeff(z,i,j) = mulii(gel(x,i),gel(y,j));
     591                 :            :   }
     592                 :          0 :   return z;
     593                 :            : }
     594                 :            : 
     595                 :            : GEN
     596                 :    4215594 : ZV_dotsquare(GEN x)
     597                 :            : {
     598                 :            :   long i, lx;
     599                 :            :   pari_sp av;
     600                 :            :   GEN z;
     601                 :    4215594 :   lx = lg(x);
     602         [ -  + ]:    4215594 :   if (lx == 1) return gen_0;
     603                 :    4215594 :   av = avma; z = sqri(gel(x,1));
     604         [ +  + ]:   16290985 :   for (i=2; i<lx; i++) z = addii(z, sqri(gel(x,i)));
     605                 :    4215594 :   return gerepileuptoint(av,z);
     606                 :            : }
     607                 :            : 
     608                 :            : GEN
     609                 :   10086324 : ZV_dotproduct(GEN x,GEN y)
     610                 :            : {
     611                 :            :   long lx;
     612         [ +  + ]:   10086324 :   if (x == y) return ZV_dotsquare(x);
     613                 :    7059625 :   lx = lg(x);
     614         [ -  + ]:    7059625 :   if (lx == 1) return gen_0;
     615                 :   10086324 :   return ZV_dotproduct_i(x, y, lx);
     616                 :            : }
     617                 :            : 
     618                 :            : static GEN
     619                 :        217 : _ZM_mul(void *data /*ignored*/, GEN x, GEN y)
     620                 :        217 : { (void)data; return ZM_mul(x,y); }
     621                 :            : static GEN
     622                 :      32522 : _ZM_sqr(void *data /*ignored*/, GEN x)
     623                 :      32522 : { (void)data; return ZM_sqr(x); }
     624                 :            : GEN
     625                 :          0 : ZM_pow(GEN x, GEN n)
     626                 :            : {
     627                 :          0 :   pari_sp av = avma;
     628         [ #  # ]:          0 :   if (!signe(n)) return matid(lg(x)-1);
     629                 :          0 :   return gerepileupto(av, gen_pow(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     630                 :            : }
     631                 :            : GEN
     632                 :      31066 : ZM_powu(GEN x, ulong n)
     633                 :            : {
     634                 :      31066 :   pari_sp av = avma;
     635         [ -  + ]:      31066 :   if (!n) return matid(lg(x)-1);
     636                 :      31066 :   return gerepileupto(av, gen_powu(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     637                 :            : }
     638                 :            : /********************************************************************/
     639                 :            : /**                                                                **/
     640                 :            : /**                           ADD, SUB                             **/
     641                 :            : /**                                                                **/
     642                 :            : /********************************************************************/
     643                 :            : static GEN
     644                 :    1874862 : ZC_add_i(GEN x, GEN y, long lx)
     645                 :            : {
     646                 :    1874862 :   GEN A = cgetg(lx, t_COL);
     647                 :            :   long i;
     648         [ +  + ]:   38160889 :   for (i=1; i<lx; i++) gel(A,i) = addii(gel(x,i), gel(y,i));
     649                 :    1874862 :   return A;
     650                 :            : }
     651                 :            : GEN
     652                 :    1072383 : ZC_add(GEN x, GEN y) { return ZC_add_i(x, y, lg(x)); }
     653                 :            : GEN
     654                 :      86037 : ZC_Z_add(GEN x, GEN y)
     655                 :            : {
     656                 :      86037 :   long k, lx = lg(x);
     657                 :      86037 :   GEN z = cgetg(lx, t_COL);
     658         [ -  + ]:      86037 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     659                 :      86037 :   gel(z,1) = addii(y,gel(x,1));
     660         [ +  + ]:    1037484 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     661                 :      86037 :   return z;
     662                 :            : }
     663                 :            : 
     664                 :            : static GEN
     665                 :    1147954 : ZC_sub_i(GEN x, GEN y, long lx)
     666                 :            : {
     667                 :            :   long i;
     668                 :    1147954 :   GEN A = cgetg(lx, t_COL);
     669         [ +  + ]:    7795751 :   for (i=1; i<lx; i++) gel(A,i) = subii(gel(x,i), gel(y,i));
     670                 :    1147954 :   return A;
     671                 :            : }
     672                 :            : GEN
     673                 :    1063721 : ZC_sub(GEN x, GEN y) { return ZC_sub_i(x, y, lg(x)); }
     674                 :            : GEN
     675                 :          0 : ZC_Z_sub(GEN x, GEN y)
     676                 :            : {
     677                 :          0 :   long k, lx = lg(x);
     678                 :          0 :   GEN z = cgetg(lx, t_COL);
     679         [ #  # ]:          0 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     680                 :          0 :   gel(z,1) = subii(gel(x,1), y);
     681         [ #  # ]:          0 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     682                 :          0 :   return z;
     683                 :            : }
     684                 :            : 
     685                 :            : GEN
     686                 :      38633 : ZM_add(GEN x, GEN y)
     687                 :            : {
     688                 :      38633 :   long lx = lg(x), l, j;
     689                 :            :   GEN z;
     690         [ +  + ]:      38633 :   if (lx == 1) return cgetg(1, t_MAT);
     691                 :      37247 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     692         [ +  + ]:     839726 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_add_i(gel(x,j), gel(y,j), l);
     693                 :      38633 :   return z;
     694                 :            : }
     695                 :            : GEN
     696                 :      18052 : ZM_sub(GEN x, GEN y)
     697                 :            : {
     698                 :      18052 :   long lx = lg(x), l, j;
     699                 :            :   GEN z;
     700         [ -  + ]:      18052 :   if (lx == 1) return cgetg(1, t_MAT);
     701                 :      18052 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     702         [ +  + ]:     102285 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_sub_i(gel(x,j), gel(y,j), l);
     703                 :      18052 :   return z;
     704                 :            : }
     705                 :            : /********************************************************************/
     706                 :            : /**                                                                **/
     707                 :            : /**                         LINEAR COMBINATION                     **/
     708                 :            : /**                                                                **/
     709                 :            : /********************************************************************/
     710                 :            : /* return X/c assuming division is exact */
     711                 :            : GEN
     712                 :    1472029 : ZC_Z_divexact(GEN X, GEN c)
     713                 :            : {
     714                 :    1472029 :   long i, l = lg(X);
     715                 :    1472029 :   GEN A = cgetg(l, t_COL);
     716         [ +  + ]:   46842526 :   for (i=1; i<l; i++) gel(A,i) = diviiexact(gel(X,i), c);
     717                 :    1472022 :   return A;
     718                 :            : }
     719                 :            : GEN
     720                 :      78110 : ZM_Z_divexact(GEN X, GEN c)
     721                 :            : {
     722                 :      78110 :   long i, l = lg(X);
     723                 :      78110 :   GEN A = cgetg(l, t_MAT);
     724         [ +  + ]:    1354857 :   for (i = 1; i < l; i++) gel(A,i) = ZC_Z_divexact(gel(X,i), c);
     725                 :      78103 :   return A;
     726                 :            : }
     727                 :            : /* Return c * X */
     728                 :            : GEN
     729                 :    2400737 : ZC_Z_mul(GEN X, GEN c)
     730                 :            : {
     731                 :            :   long i, l;
     732                 :            :   GEN A;
     733         [ +  + ]:    2400737 :   if (!signe(c)) return zerocol(lg(X)-1);
     734 [ +  + ][ +  + ]:    2378365 :   if (is_pm1(c)) return (signe(c) > 0)? ZC_copy(X): ZC_neg(X);
     735                 :    2303876 :   l = lg(X); A = cgetg(l, t_COL);
     736         [ +  + ]:   13755663 :   for (i=1; i<l; i++) gel(A,i) = mulii(c,gel(X,i));
     737                 :    2400737 :   return A;
     738                 :            : }
     739                 :            : GEN
     740                 :      13202 : ZC_z_mul(GEN X, long c)
     741                 :            : {
     742                 :            :   long i, l;
     743                 :            :   GEN A;
     744         [ +  + ]:      13202 :   if (!c) return zerocol(lg(X)-1);
     745         [ +  + ]:       6685 :   if (c == 1) return ZC_copy(X);
     746         [ +  + ]:       2212 :   if (c ==-1) return ZC_neg(X);
     747                 :        749 :   l = lg(X); A = cgetg(l, t_COL);
     748         [ +  + ]:       2282 :   for (i=1; i<l; i++) gel(A,i) = mulsi(c,gel(X,i));
     749                 :      13202 :   return A;
     750                 :            : }
     751                 :            : 
     752                 :            : GEN
     753                 :       4360 : zv_z_mul(GEN M, long n)
     754                 :            : {
     755                 :            :   long l;
     756                 :       4360 :   GEN N = cgetg_copy(M, &l);
     757         [ +  + ]:      18156 :   while (--l > 0) N[l] = M[l]*n;
     758                 :       4360 :   return N;
     759                 :            : }
     760                 :            : 
     761                 :            : /* return a ZM */
     762                 :            : GEN
     763                 :       1558 : nm_Z_mul(GEN X, GEN c)
     764                 :            : {
     765                 :       1558 :   long i, j, h, l = lg(X), s = signe(c);
     766                 :            :   GEN A;
     767         [ -  + ]:       1558 :   if (l == 1) return cgetg(1, t_MAT);
     768                 :       1558 :   h = lgcols(X);
     769         [ -  + ]:       1558 :   if (!s) return zeromat(h-1, l-1);
     770         [ -  + ]:       1558 :   if (is_pm1(c)) {
     771         [ #  # ]:          0 :     if (s > 0) return Flm_to_ZM(X);
     772                 :          0 :     X = Flm_to_ZM(X); ZM_togglesign(X); return X;
     773                 :            :   }
     774                 :       1558 :   A = cgetg(l, t_MAT);
     775         [ +  + ]:      16219 :   for (j = 1; j < l; j++)
     776                 :            :   {
     777                 :      14661 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     778         [ +  + ]:     719253 :     for (i = 1; i < h; i++) gel(a,i) = muliu(c, x[i]);
     779                 :      14661 :     gel(A,j) = a;
     780                 :            :   }
     781                 :       1558 :   return A;
     782                 :            : }
     783                 :            : GEN
     784                 :      63383 : ZM_Z_mul(GEN X, GEN c)
     785                 :            : {
     786                 :      63383 :   long i, j, h, l = lg(X);
     787                 :            :   GEN A;
     788         [ -  + ]:      63383 :   if (l == 1) return cgetg(1, t_MAT);
     789                 :      63383 :   h = lgcols(X);
     790         [ +  + ]:      63383 :   if (!signe(c)) return zeromat(h-1, l-1);
     791 [ +  + ][ +  + ]:      63320 :   if (is_pm1(c)) return (signe(c) > 0)? ZM_copy(X): ZM_neg(X);
     792                 :      46751 :   A = cgetg(l, t_MAT);
     793         [ +  + ]:     695411 :   for (j = 1; j < l; j++)
     794                 :            :   {
     795                 :     648660 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     796         [ +  + ]:   22516255 :     for (i = 1; i < h; i++) gel(a,i) = mulii(c, gel(x,i));
     797                 :     648660 :     gel(A,j) = a;
     798                 :            :   }
     799                 :      63383 :   return A;
     800                 :            : }
     801                 :            : 
     802                 :            : /* X <- X + v Y (elementary col operation) */
     803                 :            : void
     804                 :   37717413 : ZC_lincomb1_inplace(GEN X, GEN Y, GEN v)
     805                 :            : {
     806                 :   37717413 :   long i, m = lgefint(v);
     807         [ -  + ]:   75434826 :   if (m == 2) return; /* v = 0 */
     808         [ +  + ]:  786915259 :   for (i = lg(X)-1; i; i--) gel(X,i) = addmulii_inplace(gel(X,i), gel(Y,i), v);
     809                 :            : }
     810                 :            : void
     811                 :    7383503 : Flc_lincomb1_inplace(GEN X, GEN Y, ulong v, ulong q)
     812                 :            : {
     813                 :            :   long i;
     814         [ -  + ]:   14767006 :   if (!v) return; /* v = 0 */
     815         [ +  + ]:  261959596 :   for (i = lg(X)-1; i; i--) X[i] = Fl_add(X[i], Fl_mul(Y[i], v, q), q);
     816                 :            : }
     817                 :            : 
     818                 :            : /* X + v Y, wasteful if (v = 0) */
     819                 :            : static GEN
     820                 :    2383021 : ZC_lincomb1(GEN v, GEN X, GEN Y)
     821                 :            : {
     822                 :    2383021 :   long i, lx = lg(X);
     823                 :    2383021 :   GEN A = cgetg(lx,t_COL);
     824         [ +  + ]:   30226581 :   for (i=1; i<lx; i++) gel(A,i) = addmulii(gel(X,i), gel(Y,i), v);
     825                 :    2383021 :   return A;
     826                 :            : }
     827                 :            : /* -X + vY */
     828                 :            : static GEN
     829                 :     367398 : ZC_lincomb_1(GEN v, GEN X, GEN Y)
     830                 :            : {
     831                 :     367398 :   long i, lx = lg(X);
     832                 :     367398 :   GEN A = cgetg(lx,t_COL);
     833         [ +  + ]:    1993364 :   for (i=1; i<lx; i++) gel(A,i) = mulsubii(gel(Y,i), v, gel(X,i));
     834                 :     367398 :   return A;
     835                 :            : }
     836                 :            : /* X,Y compatible ZV; u,v in Z. Returns A = u*X + v*Y */
     837                 :            : GEN
     838                 :    7503457 : ZC_lincomb(GEN u, GEN v, GEN X, GEN Y)
     839                 :            : {
     840                 :            :   long su, sv;
     841                 :            :   GEN A;
     842                 :            : 
     843         [ +  + ]:    7503457 :   su = signe(u); if (!su) return ZC_Z_mul(Y, v);
     844         [ +  + ]:    7503450 :   sv = signe(v); if (!sv) return ZC_Z_mul(X, u);
     845         [ +  + ]:    7503429 :   if (is_pm1(v))
     846                 :            :   {
     847         [ +  + ]:    1703930 :     if (is_pm1(u))
     848                 :            :     {
     849         [ +  + ]:    1103130 :       if (su != sv) A = ZC_sub(X, Y);
     850                 :     495968 :       else          A = ZC_add(X, Y);
     851         [ +  + ]:    1103130 :       if (su < 0) ZV_togglesign(A); /* in place but was created above */
     852                 :            :     }
     853                 :            :     else
     854                 :            :     {
     855         [ +  + ]:     600800 :       if (sv > 0) A = ZC_lincomb1 (u, Y, X);
     856                 :     260808 :       else        A = ZC_lincomb_1(u, Y, X);
     857                 :            :     }
     858                 :            :   }
     859         [ +  + ]:    5799499 :   else if (is_pm1(u))
     860                 :            :   {
     861         [ +  + ]:    2149619 :     if (su > 0) A = ZC_lincomb1 (v, X, Y);
     862                 :     106590 :     else        A = ZC_lincomb_1(v, X, Y);
     863                 :            :   }
     864                 :            :   else
     865                 :            :   { /* not cgetg_copy: x may be a t_VEC */
     866                 :    3649880 :     long i, lx = lg(X);
     867                 :    3649880 :     A = cgetg(lx,t_COL);
     868         [ +  + ]:   20724230 :     for (i=1; i<lx; i++) gel(A,i) = lincombii(u,v,gel(X,i),gel(Y,i));
     869                 :            :   }
     870                 :    7503457 :   return A;
     871                 :            : }
     872                 :            : 
     873                 :            : /********************************************************************/
     874                 :            : /**                                                                **/
     875                 :            : /**                           CONVERSIONS                          **/
     876                 :            : /**                                                                **/
     877                 :            : /********************************************************************/
     878                 :            : GEN
     879                 :       5873 : ZV_to_nv(GEN z)
     880                 :            : {
     881                 :       5873 :   long i, l = lg(z);
     882                 :       5873 :   GEN x = cgetg(l, t_VECSMALL);
     883         [ +  + ]:      12474 :   for (i=1; i<l; i++) x[i] = itou(gel(z,i));
     884                 :       5873 :   return x;
     885                 :            : }
     886                 :            : 
     887                 :            : GEN
     888                 :      92556 : zm_to_ZM(GEN z)
     889                 :            : {
     890                 :      92556 :   long i, l = lg(z);
     891                 :      92556 :   GEN x = cgetg(l,t_MAT);
     892         [ +  + ]:     350008 :   for (i=1; i<l; i++) gel(x,i) = zc_to_ZC(gel(z,i));
     893                 :      92556 :   return x;
     894                 :            : }
     895                 :            : 
     896                 :            : GEN
     897                 :         84 : zmV_to_ZMV(GEN z)
     898                 :            : {
     899                 :         84 :   long i, l = lg(z);
     900                 :         84 :   GEN x = cgetg(l,t_VEC);
     901         [ +  + ]:        630 :   for (i=1; i<l; i++) gel(x,i) = zm_to_ZM(gel(z,i));
     902                 :         84 :   return x;
     903                 :            : }
     904                 :            : 
     905                 :            : /* same as Flm_to_ZM but do not assume positivity */
     906                 :            : GEN
     907                 :        770 : ZM_to_zm(GEN z)
     908                 :            : {
     909                 :        770 :   long i, l = lg(z);
     910                 :        770 :   GEN x = cgetg(l,t_MAT);
     911         [ +  + ]:     205751 :   for (i=1; i<l; i++) gel(x,i) = ZV_to_zv(gel(z,i));
     912                 :        770 :   return x;
     913                 :            : }
     914                 :            : 
     915                 :            : GEN
     916                 :     219128 : zv_to_Flv(GEN z, ulong p)
     917                 :            : {
     918                 :     219128 :   long i, l = lg(z);
     919                 :     219128 :   GEN x = cgetg(l,t_VECSMALL);
     920         [ +  + ]:    3488856 :   for (i=1; i<l; i++) x[i] = umodsu(z[i], p);
     921                 :     219128 :   return x;
     922                 :            : }
     923                 :            : 
     924                 :            : GEN
     925                 :      15106 : zm_to_Flm(GEN z, ulong p)
     926                 :            : {
     927                 :      15106 :   long i, l = lg(z);
     928                 :      15106 :   GEN x = cgetg(l,t_MAT);
     929         [ +  + ]:     234234 :   for (i=1; i<l; i++) gel(x,i) = zv_to_Flv(gel(z,i),p);
     930                 :      15106 :   return x;
     931                 :            : }
     932                 :            : 
     933                 :            : GEN
     934                 :         21 : ZMV_to_zmV(GEN z)
     935                 :            : {
     936                 :         21 :   long i,l = lg(z);
     937                 :         21 :   GEN x = cgetg(l, t_VEC);
     938         [ +  + ]:        252 :   for (i=1; i<l; i++) gel(x,i) = ZM_to_zm(gel(z,i));
     939                 :         21 :   return x;
     940                 :            : }
     941                 :            : 
     942                 :            : /********************************************************************/
     943                 :            : /**                                                                **/
     944                 :            : /**                         COPY, NEGATION                         **/
     945                 :            : /**                                                                **/
     946                 :            : /********************************************************************/
     947                 :            : GEN
     948                 :     921860 : ZC_copy(GEN x)
     949                 :            : {
     950                 :     921860 :   long i, lx = lg(x);
     951                 :     921860 :   GEN y = cgetg(lx, t_COL);
     952         [ +  + ]:    9002589 :   for (i=1; i<lx; i++)
     953                 :            :   {
     954                 :    8080729 :     GEN c = gel(x,i);
     955         [ +  + ]:    8080729 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
     956                 :            :   }
     957                 :     921860 :   return y;
     958                 :            : }
     959                 :            : 
     960                 :            : GEN
     961                 :      80590 : ZM_copy(GEN x)
     962                 :            : {
     963                 :            :   long l;
     964                 :      80590 :   GEN y = cgetg_copy(x, &l);
     965         [ +  + ]:     765714 :   while (--l > 0) gel(y,l) = ZC_copy(gel(x,l));
     966                 :      80590 :   return y;
     967                 :            : }
     968                 :            : 
     969                 :            : void
     970                 :      57894 : ZV_neg_inplace(GEN M)
     971                 :            : {
     972                 :      57894 :   long l = lg(M);
     973         [ +  + ]:     440139 :   while (--l > 0) gel(M,l) = negi(gel(M,l));
     974                 :      57894 : }
     975                 :            : GEN
     976                 :    1672570 : ZC_neg(GEN M)
     977                 :            : {
     978                 :    1672570 :   long l = lg(M);
     979                 :    1672570 :   GEN N = cgetg(l, t_COL);
     980         [ +  + ]:   12020549 :   while (--l > 0) gel(N,l) = negi(gel(M,l));
     981                 :    1672570 :   return N;
     982                 :            : }
     983                 :            : GEN
     984                 :     210372 : zv_neg(GEN M)
     985                 :            : {
     986                 :            :   long l;
     987                 :     210372 :   GEN N = cgetg_copy(M, &l);
     988         [ +  + ]:    1700039 :   while (--l > 0) N[l] = -M[l];
     989                 :     210372 :   return N;
     990                 :            : }
     991                 :            : GEN
     992                 :        264 : zv_neg_inplace(GEN M)
     993                 :            : {
     994                 :        264 :   long l = lg(M);
     995         [ +  + ]:       1038 :   while (--l > 0) M[l] = -M[l];
     996                 :        264 :   return M;
     997                 :            : }
     998                 :            : GEN
     999                 :     130347 : ZM_neg(GEN x)
    1000                 :            : {
    1001                 :            :   long l;
    1002                 :     130347 :   GEN y = cgetg_copy(x, &l);
    1003         [ +  + ]:     409976 :   while (--l > 0) gel(y,l) = ZC_neg(gel(x,l));
    1004                 :     130347 :   return y;
    1005                 :            : }
    1006                 :            : 
    1007                 :            : void
    1008                 :    1680531 : ZV_togglesign(GEN M)
    1009                 :            : {
    1010                 :    1680531 :   long l = lg(M);
    1011         [ +  + ]:   29407792 :   while (--l > 0) togglesign_safe(&gel(M,l));
    1012                 :    1680531 : }
    1013                 :            : void
    1014                 :          0 : ZM_togglesign(GEN M)
    1015                 :            : {
    1016                 :          0 :   long l = lg(M);
    1017         [ #  # ]:          0 :   while (--l > 0) ZV_togglesign(gel(M,l));
    1018                 :          0 : }
    1019                 :            : 
    1020                 :            : /********************************************************************/
    1021                 :            : /**                                                                **/
    1022                 :            : /**                        "DIVISION" mod HNF                      **/
    1023                 :            : /**                                                                **/
    1024                 :            : /********************************************************************/
    1025                 :            : /* Reduce ZC x modulo ZM y in HNF, may return x itself (not a copy) */
    1026                 :            : GEN
    1027                 :     883651 : ZC_hnfremdiv(GEN x, GEN y, GEN *Q)
    1028                 :            : {
    1029                 :     883651 :   long i, l = lg(x);
    1030                 :            :   GEN q;
    1031                 :            : 
    1032         [ +  + ]:     883651 :   if (Q) *Q = cgetg(l,t_COL);
    1033         [ -  + ]:     883651 :   if (l == 1) return cgetg(1,t_COL);
    1034         [ +  + ]:    5218033 :   for (i = l-1; i>0; i--)
    1035                 :            :   {
    1036                 :    4334382 :     q = diviiround(gel(x,i), gcoeff(y,i,i));
    1037         [ +  + ]:    4334382 :     if (signe(q)) {
    1038                 :    2362685 :       togglesign(q);
    1039                 :    2362685 :       x = ZC_lincomb(gen_1, q, x, gel(y,i));
    1040                 :            :     }
    1041         [ +  + ]:    4334382 :     if (Q) gel(*Q, i) = q;
    1042                 :            :   }
    1043                 :     883651 :   return x;
    1044                 :            : }
    1045                 :            : 
    1046                 :            : /* x = y Q + R, may return some columns of x (not copies) */
    1047                 :            : GEN
    1048                 :      56160 : ZM_hnfdivrem(GEN x, GEN y, GEN *Q)
    1049                 :            : {
    1050                 :      56160 :   long lx = lg(x), i;
    1051                 :      56160 :   GEN R = cgetg(lx, t_MAT);
    1052         [ +  + ]:      56160 :   if (Q)
    1053                 :            :   {
    1054                 :       3370 :     GEN q = cgetg(lx, t_MAT); *Q = q;
    1055         [ +  + ]:       6208 :     for (i=1; i<lx; i++) gel(R,i) = ZC_hnfremdiv(gel(x,i),y,(GEN*)(q+i));
    1056                 :            :   }
    1057                 :            :   else
    1058         [ +  + ]:     162784 :     for (i=1; i<lx; i++)
    1059                 :            :     {
    1060                 :     109994 :       pari_sp av = avma;
    1061                 :     109994 :       GEN z = ZC_hnfrem(gel(x,i),y);
    1062         [ +  + ]:     109994 :       gel(R,i) = (avma == av)? ZC_copy(z): gerepileupto(av, z);
    1063                 :            :     }
    1064                 :      56160 :   return R;
    1065                 :            : }
    1066                 :            : 
    1067                 :            : 
    1068                 :            : /********************************************************************/
    1069                 :            : /**                                                                **/
    1070                 :            : /**                               TESTS                            **/
    1071                 :            : /**                                                                **/
    1072                 :            : /********************************************************************/
    1073                 :            : int
    1074                 :   16412844 : zv_equal0(GEN V)
    1075                 :            : {
    1076                 :   16412844 :   long l = lg(V);
    1077         [ +  + ]:   26304467 :   while (--l > 0)
    1078         [ +  + ]:   21118069 :     if (V[l]) return 0;
    1079                 :   16412844 :   return 1;
    1080                 :            : }
    1081                 :            : 
    1082                 :            : int
    1083                 :     439044 : ZV_equal0(GEN V)
    1084                 :            : {
    1085                 :     439044 :   long l = lg(V);
    1086         [ +  + ]:    1545943 :   while (--l > 0)
    1087         [ +  + ]:    1453939 :     if (signe(gel(V,l))) return 0;
    1088                 :     439044 :   return 1;
    1089                 :            : }
    1090                 :            : 
    1091                 :            : static int
    1092                 :    9102162 : ZV_equal_lg(GEN V, GEN W, long l)
    1093                 :            : {
    1094         [ +  + ]:   16685551 :   while (--l > 0)
    1095         [ +  + ]:   14588735 :     if (!equalii(gel(V,l), gel(W,l))) return 0;
    1096                 :    9102162 :   return 1;
    1097                 :            : }
    1098                 :            : int
    1099                 :    7763126 : ZV_equal(GEN V, GEN W)
    1100                 :            : {
    1101                 :    7763126 :   long l = lg(V);
    1102         [ -  + ]:    7763126 :   if (lg(W) != l) return 0;
    1103                 :    7763126 :   return ZV_equal_lg(V, W, l);
    1104                 :            : }
    1105                 :            : int
    1106                 :     424073 : ZM_equal(GEN A, GEN B)
    1107                 :            : {
    1108                 :     424073 :   long i, m, l = lg(A);
    1109         [ +  + ]:     424073 :   if (lg(B) != l) return 0;
    1110         [ -  + ]:     423786 :   if (l == 1) return 1;
    1111                 :     423786 :   m = lgcols(A);
    1112         [ -  + ]:     423786 :   if (lgcols(B) != m) return 0;
    1113         [ +  + ]:    1719201 :   for (i = 1; i < l; i++)
    1114         [ +  + ]:    1339036 :     if (!ZV_equal_lg(gel(A,i), gel(B,i), m)) return 0;
    1115                 :     424073 :   return 1;
    1116                 :            : }
    1117                 :            : int
    1118                 :    3018202 : zv_equal(GEN V, GEN W)
    1119                 :            : {
    1120                 :    3018202 :   long l = lg(V);
    1121         [ +  + ]:    3018202 :   if (lg(W) != l) return 0;
    1122         [ +  + ]:   21970233 :   while (--l > 0)
    1123         [ +  + ]:   19346773 :     if (V[l] != W[l]) return 0;
    1124                 :    3018202 :   return 1;
    1125                 :            : }
    1126                 :            : 
    1127                 :            : int
    1128                 :        343 : zvV_equal(GEN V, GEN W)
    1129                 :            : {
    1130                 :        343 :   long l = lg(V);
    1131         [ +  + ]:        343 :   if (lg(W) != l) return 0;
    1132         [ +  + ]:      58520 :   while (--l > 0)
    1133         [ +  + ]:      58310 :     if (!zv_equal(gel(V,l),gel(W,l))) return 0;
    1134                 :        343 :   return 1;
    1135                 :            : }
    1136                 :            : 
    1137                 :            : int
    1138                 :      77939 : ZM_ishnf(GEN x)
    1139                 :            : {
    1140                 :      77939 :   long i,j, lx = lg(x);
    1141         [ +  + ]:     306883 :   for (i=1; i<lx; i++)
    1142                 :            :   {
    1143                 :     236707 :     GEN xii = gcoeff(x,i,i);
    1144         [ +  + ]:     236707 :     if (signe(xii) <= 0) return 0;
    1145         [ +  + ]:     801440 :     for (j=1; j<i; j++)
    1146         [ -  + ]:     565342 :       if (signe(gcoeff(x,i,j))) return 0;
    1147         [ +  + ]:     832695 :     for (j=i+1; j<lx; j++)
    1148                 :            :     {
    1149                 :     603751 :       GEN xij = gcoeff(x,i,j);
    1150 [ +  + ][ +  + ]:     603751 :       if (signe(xij)<0 || cmpii(xij,xii)>=0) return 0;
    1151                 :            :     }
    1152                 :            :   }
    1153                 :      77939 :   return 1;
    1154                 :            : }
    1155                 :            : int
    1156                 :      97813 : ZM_isidentity(GEN x)
    1157                 :            : {
    1158                 :      97813 :   long i,j, lx = lg(x);
    1159                 :            : 
    1160         [ -  + ]:      97813 :   if (lx == 1) return 1;
    1161         [ -  + ]:      97813 :   if (lx != lgcols(x)) return 0;
    1162         [ +  + ]:     797504 :   for (j=1; j<lx; j++)
    1163                 :            :   {
    1164                 :     699691 :     GEN c = gel(x,j);
    1165         [ +  + ]:    3423174 :     for (i=1; i<j; )
    1166         [ -  + ]:    2723483 :       if (signe(gel(c,i++))) return 0;
    1167                 :            :     /* i = j */
    1168         [ -  + ]:     699691 :       if (!equali1(gel(c,i++))) return 0;
    1169         [ +  + ]:    3423174 :     for (   ; i<lx; )
    1170         [ -  + ]:    2723483 :       if (signe(gel(c,i++))) return 0;
    1171                 :            :   }
    1172                 :      97813 :   return 1;
    1173                 :            : }
    1174                 :            : int
    1175                 :      12936 : ZM_isscalar(GEN x, GEN s)
    1176                 :            : {
    1177                 :      12936 :   long i, j, lx = lg(x);
    1178                 :            : 
    1179         [ -  + ]:      12936 :   if (lx == 1) return 1;
    1180         [ -  + ]:      12936 :   if (lx != lgcols(x)) return 0;
    1181         [ -  + ]:      12936 :   if (!s) s = gcoeff(x,1,1);
    1182         [ +  + ]:     109060 :   for (j=1; j<lx; j++)
    1183                 :            :   {
    1184                 :      96558 :     GEN c = gel(x,j);
    1185         [ +  + ]:    1031408 :     for (i=1; i<j; )
    1186         [ +  + ]:     934934 :       if (signe(gel(c,i++))) return 0;
    1187                 :            :     /* i = j */
    1188         [ +  + ]:      96474 :       if (!equalii(gel(c,i++), s)) return 0;
    1189         [ +  + ]:    1031569 :     for (   ; i<lx; )
    1190         [ -  + ]:     935445 :       if (signe(gel(c,i++))) return 0;
    1191                 :            :   }
    1192                 :      12936 :   return 1;
    1193                 :            : }
    1194                 :            : 
    1195                 :            : 
    1196                 :            : long
    1197                 :      37548 : ZC_is_ei(GEN x)
    1198                 :            : {
    1199                 :      37548 :   long i, j = 0, l = lg(x);
    1200         [ +  + ]:     605416 :   for (i = 1; i < l; i++)
    1201                 :            :   {
    1202                 :     567868 :     GEN c = gel(x,i);
    1203                 :     567868 :     long s = signe(c);
    1204         [ +  + ]:     567868 :     if (!s) continue;
    1205 [ +  - ][ +  - ]:      37541 :     if (s < 0 || !is_pm1(c) || j) return 0;
                 [ -  + ]
    1206                 :      37541 :     j = i;
    1207                 :            :   }
    1208                 :      37548 :   return j;
    1209                 :            : }
    1210                 :            : 
    1211                 :            : /********************************************************************/
    1212                 :            : /**                                                                **/
    1213                 :            : /**                       MISCELLANEOUS                            **/
    1214                 :            : /**                                                                **/
    1215                 :            : /********************************************************************/
    1216                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
    1217                 :            : int
    1218                 :     492066 : ZV_cmp(GEN x, GEN y)
    1219                 :            : {
    1220                 :     492066 :   long fl,i, lx = lg(x);
    1221         [ +  + ]:    1103413 :   for (i=1; i<lx; i++)
    1222         [ +  + ]:     917887 :     if (( fl = cmpii(gel(x,i), gel(y,i)) )) return fl;
    1223                 :     492066 :   return 0;
    1224                 :            : }
    1225                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
    1226                 :            : int
    1227                 :       3480 : ZV_abscmp(GEN x, GEN y)
    1228                 :            : {
    1229                 :       3480 :   long fl,i, lx = lg(x);
    1230         [ +  + ]:      19454 :   for (i=1; i<lx; i++)
    1231         [ +  + ]:      19374 :     if (( fl = absi_cmp(gel(x,i), gel(y,i)) )) return fl;
    1232                 :       3480 :   return 0;
    1233                 :            : }
    1234                 :            : 
    1235                 :            : long
    1236                 :     713451 : zv_content(GEN x)
    1237                 :            : {
    1238                 :     713451 :   long i, s, l = lg(x);
    1239         [ +  + ]:     713451 :   if (l == 1) return 0;
    1240                 :     713444 :   s = labs(x[1]);
    1241 [ +  + ][ +  + ]:    1451844 :   for (i=2; i<l && s!=1; i++) s = cgcd(x[i],s);
    1242                 :     713451 :   return s;
    1243                 :            : }
    1244                 :            : GEN
    1245                 :       8988 : ZV_content(GEN x)
    1246                 :            : {
    1247                 :       8988 :   long i, l = lg(x);
    1248                 :       8988 :   pari_sp av = avma;
    1249                 :            :   GEN c;
    1250         [ -  + ]:       8988 :   if (l == 1) return gen_0;
    1251         [ +  + ]:       8988 :   if (l == 2) return absi(gel(x,1));
    1252                 :       3374 :   c = gel(x,1);
    1253         [ +  + ]:       6279 :   for (i = 2; i < l; i++)
    1254                 :            :   {
    1255                 :       4053 :     c = gcdii(c, gel(x,i));
    1256         [ +  + ]:       4053 :     if (is_pm1(c)) { avma = av; return gen_1; }
    1257                 :            :   }
    1258                 :       8988 :   return gerepileuptoint(av, c);
    1259                 :            : }
    1260                 :            : 
    1261                 :            : GEN
    1262                 :     727131 : ZM_det_triangular(GEN mat)
    1263                 :            : {
    1264                 :            :   pari_sp av;
    1265                 :     727131 :   long i,l = lg(mat);
    1266                 :            :   GEN s;
    1267                 :            : 
    1268 [ +  + ][ +  + ]:     727131 :   if (l<3) return l<2? gen_1: icopy(gcoeff(mat,1,1));
    1269                 :     668322 :   av = avma; s = gcoeff(mat,1,1);
    1270         [ +  + ]:    2008852 :   for (i=2; i<l; i++) s = mulii(s,gcoeff(mat,i,i));
    1271                 :     727131 :   return gerepileuptoint(av,s);
    1272                 :            : }
    1273                 :            : 
    1274                 :            : /* assumes no overflow */
    1275                 :            : long
    1276                 :     351036 : zv_prod(GEN v)
    1277                 :            : {
    1278                 :     351036 :   long n, i, l = lg(v);
    1279         [ +  + ]:     351036 :   if (l == 1) return 1;
    1280         [ +  + ]:     400149 :   n = v[1]; for (i = 2; i < l; i++) n *= v[i];
    1281                 :     351036 :   return n;
    1282                 :            : }
    1283                 :            : 
    1284                 :            : static GEN
    1285                 :     906108 : _mulii(void *E, GEN a, GEN b)
    1286                 :     906108 : { (void) E; return mulii(a, b); }
    1287                 :            : 
    1288                 :            : /* product of ulongs */
    1289                 :            : GEN
    1290                 :     365177 : zv_prod_Z(GEN v)
    1291                 :            : {
    1292                 :     365177 :   pari_sp av = avma;
    1293                 :     365177 :   long k, n = lg(v)-1, m;
    1294                 :            :   GEN x;
    1295         [ +  + ]:     365177 :   if (n == 0) return gen_1;
    1296         [ +  + ]:     345710 :   if (n == 1) return utoi(v[1]);
    1297         [ +  + ]:     288905 :   if (n == 2) return muluu(v[1], v[2]);
    1298                 :     163444 :   m = n >> 1;
    1299         [ +  + ]:     163444 :   x = cgetg(m + (odd(n)? 2: 1), t_VEC);
    1300         [ +  + ]:     367696 :   for (k = 1; k <= m; k++) gel(x,k) = muluu(v[k<<1], v[(k<<1)-1]);
    1301         [ +  + ]:     163444 :   if (odd(n)) gel(x,k) = utoipos(v[n]);
    1302                 :     365177 :   return gerepileuptoint(av, gen_product(x, NULL, _mulii));
    1303                 :            : }
    1304                 :            : 
    1305                 :            : GEN
    1306                 :      35274 : ZV_prod(GEN v)
    1307                 :            : {
    1308                 :      35274 :   pari_sp av = avma;
    1309                 :      35274 :   long i, l = lg(v);
    1310                 :            :   GEN n;
    1311         [ +  + ]:      35274 :   if (l == 1) return gen_1;
    1312         [ +  + ]:      34161 :   if (l > 7) return gerepileuptoint(av, gen_product(v, NULL, _mulii));
    1313                 :      26625 :   n = gel(v,1);
    1314         [ +  + ]:      26625 :   if (l == 2) return icopy(n);
    1315         [ +  + ]:      40785 :   for (i = 2; i < l; i++) n = mulii(n, gel(v,i));
    1316                 :      35274 :   return gerepileuptoint(av, n);
    1317                 :            : }
    1318                 :            : /* assumes no overflow */
    1319                 :            : long
    1320                 :     140749 : zv_sum(GEN v)
    1321                 :            : {
    1322                 :     140749 :   long n, i, l = lg(v);
    1323         [ +  + ]:     140749 :   if (l == 1) return 0;
    1324         [ +  + ]:     214347 :   n = v[1]; for (i = 2; i < l; i++) n += v[i];
    1325                 :     140749 :   return n;
    1326                 :            : }
    1327                 :            : GEN
    1328                 :         56 : ZV_sum(GEN v)
    1329                 :            : {
    1330                 :         56 :   pari_sp av = avma;
    1331                 :         56 :   long i, l = lg(v);
    1332                 :            :   GEN n;
    1333         [ -  + ]:         56 :   if (l == 1) return gen_0;
    1334                 :         56 :   n = gel(v,1);
    1335         [ -  + ]:         56 :   if (l == 2) return icopy(n);
    1336         [ +  + ]:        518 :   for (i = 2; i < l; i++) n = addii(n, gel(v,i));
    1337                 :         56 :   return gerepileuptoint(av, n);
    1338                 :            : }
    1339                 :            : 
    1340                 :            : /********************************************************************/
    1341                 :            : /**                                                                **/
    1342                 :            : /**         GRAM SCHMIDT REDUCTION (integer matrices)              **/
    1343                 :            : /**                                                                **/
    1344                 :            : /********************************************************************/
    1345                 :            : 
    1346                 :            : /* L[k,] += q * L[l,], l < k. Inefficient if q = 0 */
    1347                 :            : static void
    1348                 :     174384 : Zupdate_row(long k, long l, GEN q, GEN L, GEN B)
    1349                 :            : {
    1350                 :     174384 :   long i, qq = itos_or_0(q);
    1351         [ +  + ]:     174384 :   if (!qq)
    1352                 :            :   {
    1353         [ +  + ]:      17621 :     for(i=1;i<l;i++)  gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulii(q,gcoeff(L,l,i)));
    1354                 :       5034 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulii(q,B));
    1355                 :     174384 :     return;
    1356                 :            :   }
    1357         [ +  + ]:     169350 :   if (qq == 1) {
    1358         [ +  + ]:      62025 :     for (i=1;i<l; i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),gcoeff(L,l,i));
    1359                 :      34674 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), B);
    1360         [ +  + ]:     134676 :   } else if (qq == -1) {
    1361         [ +  + ]:     152858 :     for (i=1;i<l; i++) gcoeff(L,k,i) = subii(gcoeff(L,k,i),gcoeff(L,l,i));
    1362                 :      81899 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), negi(B));
    1363                 :            :   } else {
    1364         [ +  + ]:     113648 :     for(i=1;i<l;i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulsi(qq,gcoeff(L,l,i)));
    1365                 :      52777 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulsi(qq,B));
    1366                 :            :   }
    1367                 :            : }
    1368                 :            : 
    1369                 :            : /* update L[k,] */
    1370                 :            : static void
    1371                 :     543365 : ZRED(long k, long l, GEN x, GEN L, GEN B)
    1372                 :            : {
    1373                 :     543365 :   GEN q = truedivii(addii(B,shifti(gcoeff(L,k,l),1)), shifti(B,1));
    1374         [ +  + ]:     717749 :   if (!signe(q)) return;
    1375                 :     174384 :   q = negi(q);
    1376                 :     174384 :   Zupdate_row(k,l,q,L,B);
    1377                 :     174384 :   gel(x,k) = ZC_lincomb(gen_1, q, gel(x,k), gel(x,l));
    1378                 :            : }
    1379                 :            : 
    1380                 :            : /* Gram-Schmidt reduction, x a ZM */
    1381                 :            : static void
    1382                 :     726327 : ZincrementalGS(GEN x, GEN L, GEN B, long k)
    1383                 :            : {
    1384                 :            :   long i, j;
    1385         [ +  + ]:    2609931 :   for (j=1; j<=k; j++)
    1386                 :            :   {
    1387                 :    1883604 :     pari_sp av = avma;
    1388                 :    1883604 :     GEN u = ZV_dotproduct(gel(x,k), gel(x,j));
    1389         [ +  + ]:    4433476 :     for (i=1; i<j; i++)
    1390                 :            :     {
    1391                 :    2549872 :       u = subii(mulii(gel(B,i+1), u), mulii(gcoeff(L,k,i), gcoeff(L,j,i)));
    1392                 :    2549872 :       u = diviiexact(u, gel(B,i));
    1393                 :            :     }
    1394                 :    1883604 :     gcoeff(L,k,j) = gerepileuptoint(av, u);
    1395                 :            :   }
    1396                 :     726327 :   gel(B,k+1) = gcoeff(L,k,k); gcoeff(L,k,k) = gen_1;
    1397                 :     726327 : }
    1398                 :            : 
    1399                 :            : /* Variant reducemodinvertible(ZC v, ZM y), when y singular.
    1400                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1401                 :            : static GEN
    1402                 :     186784 : ZC_reducemodmatrix_i(GEN v, GEN y)
    1403                 :            : {
    1404                 :     186784 :   GEN B, L, x = shallowconcat(y, v);
    1405                 :     186784 :   long k, lx = lg(x), nx = lx-1;
    1406                 :            : 
    1407                 :     186784 :   B = scalarcol_shallow(gen_1, lx);
    1408                 :     186784 :   L = zeromatcopy(nx, nx);
    1409         [ +  + ]:     890424 :   for (k=1; k <= nx; k++) ZincrementalGS(x, L, B, k);
    1410         [ +  + ]:     703640 :   for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1411                 :     186784 :   return gel(x,nx);
    1412                 :            : }
    1413                 :            : GEN
    1414                 :     186784 : ZC_reducemodmatrix(GEN v, GEN y) {
    1415                 :     186784 :   pari_sp av = avma;
    1416                 :     186784 :   return gerepilecopy(av, ZC_reducemodmatrix_i(v,y));
    1417                 :            : }
    1418                 :            : 
    1419                 :            : /* Variant reducemodinvertible(ZM v, ZM y), when y singular.
    1420                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1421                 :            : static GEN
    1422                 :       5250 : ZM_reducemodmatrix_i(GEN v, GEN y)
    1423                 :            : {
    1424                 :            :   GEN B, L, V;
    1425                 :       5250 :   long j, k, lv = lg(v), nx = lg(y), lx = nx+1;
    1426                 :            : 
    1427                 :       5250 :   V = cgetg(lv, t_MAT);
    1428                 :       5250 :   B = scalarcol_shallow(gen_1, lx);
    1429                 :       5250 :   L = zeromatcopy(nx, nx);
    1430         [ +  + ]:      16450 :   for (k=1; k < nx; k++) ZincrementalGS(y, L, B, k);
    1431         [ +  + ]:      16737 :   for (j = 1; j < lg(v); j++)
    1432                 :            :   {
    1433                 :      11487 :     GEN x = shallowconcat(y, gel(v,j));
    1434                 :      11487 :     ZincrementalGS(x, L, B, nx); /* overwrite last */
    1435         [ +  + ]:      37996 :     for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1436                 :      11487 :     gel(V,j) = gel(x,nx);
    1437                 :            :   }
    1438                 :       5250 :   return V;
    1439                 :            : }
    1440                 :            : GEN
    1441                 :       5250 : ZM_reducemodmatrix(GEN v, GEN y) {
    1442                 :       5250 :   pari_sp av = avma;
    1443                 :       5250 :   return gerepilecopy(av, ZM_reducemodmatrix_i(v,y));
    1444                 :            : }
    1445                 :            : 
    1446                 :            : GEN
    1447                 :     185251 : ZC_reducemodlll(GEN x,GEN y)
    1448                 :            : {
    1449                 :     185251 :   pari_sp av = avma;
    1450                 :     185251 :   GEN z = ZC_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1451                 :     185251 :   return gerepilecopy(av, z);
    1452                 :            : }
    1453                 :            : GEN
    1454                 :          0 : ZM_reducemodlll(GEN x,GEN y)
    1455                 :            : {
    1456                 :          0 :   pari_sp av = avma;
    1457                 :          0 :   GEN z = ZM_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1458                 :          0 :   return gerepilecopy(av, z);
    1459                 :            : }

Generated by: LCOV version 1.9