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 - RgV.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16746-c2cb716) Lines: 402 470 85.5 %
Date: 2014-08-31 Functions: 67 77 87.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 237 340 69.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                 :            : int
      18                 :      16271 : RgM_is_ZM(GEN x)
      19                 :            : {
      20                 :      16271 :   long i, j, h, l = lg(x);
      21         [ +  + ]:      16271 :   if (l == 1) return 1;
      22                 :      16081 :   h = lgcols(x);
      23         [ -  + ]:      16081 :   if (h == 1) return 1;
      24         [ +  + ]:      72534 :   for (j = l-1; j > 0; j--)
      25         [ +  + ]:     430896 :     for (i = h-1; i > 0; i--)
      26         [ +  + ]:     374443 :       if (typ(gcoeff(x,i,j)) != t_INT) return 0;
      27                 :      16271 :   return 1;
      28                 :            : }
      29                 :            : 
      30                 :            : int
      31                 :          0 : RgV_is_ZMV(GEN V)
      32                 :            : {
      33                 :          0 :   long i, l = lg(V);
      34         [ #  # ]:          0 :   for (i=1; i<l; i++)
      35 [ #  # ][ #  # ]:          0 :     if (typ(gel(V,i))!=t_MAT || !RgM_is_ZM(gel(V,i)))
      36                 :          0 :       return 0;
      37                 :          0 :   return 1;
      38                 :            : }
      39                 :            : 
      40                 :            : /********************************************************************/
      41                 :            : /**                                                                **/
      42                 :            : /**                   GENERIC LINEAR ALGEBRA                       **/
      43                 :            : /**                                                                **/
      44                 :            : /********************************************************************/
      45                 :            : /*           GENERIC  MULTIPLICATION involving zc/zm                */
      46                 :            : /* x non-empty t_MAT, y a compatible zc (dimension > 0). */
      47                 :            : static GEN
      48                 :      18761 : RgM_zc_mul_i(GEN x, GEN y, long c, long l)
      49                 :            : {
      50                 :            :   long i, j;
      51                 :            :   pari_sp av;
      52                 :      18761 :   GEN z = cgetg(l,t_COL), s;
      53                 :            : 
      54         [ +  + ]:     186928 :   for (i=1; i<l; i++)
      55                 :            :   {
      56                 :     168167 :     av = avma; s = gmulgs(gcoeff(x,i,1),y[1]);
      57         [ +  + ]:   13141849 :     for (j=2; j<c; j++)
      58                 :            :     {
      59                 :   12973682 :       long t = y[j];
      60   [ +  +  +  + ]:   12973682 :       switch(t)
      61                 :            :       {
      62                 :   11859459 :         case  0: break;
      63                 :     770022 :         case  1: s = gadd(s, gcoeff(x,i,j)); break;
      64                 :     290730 :         case -1: s = gsub(s, gcoeff(x,i,j)); break;
      65                 :      53471 :         default: s = gadd(s, gmulgs(gcoeff(x,i,j), t)); break;
      66                 :            :       }
      67                 :            :     }
      68                 :     168167 :     gel(z,i) = gerepileupto(av,s);
      69                 :            :   }
      70                 :      18761 :   return z;
      71                 :            : }
      72                 :            : GEN
      73                 :       4460 : RgM_zc_mul(GEN x, GEN y) { return RgM_zc_mul_i(x,y, lg(x), lgcols(x)); }
      74                 :            : /* x t_MAT, y a compatible zm (dimension > 0). */
      75                 :            : GEN
      76                 :       3483 : RgM_zm_mul(GEN x, GEN y)
      77                 :            : {
      78                 :       3483 :   long j, c, l = lg(x), ly = lg(y);
      79                 :       3483 :   GEN z = cgetg(ly, t_MAT);
      80         [ -  + ]:       3483 :   if (l == 1) return z;
      81                 :       3483 :   c = lgcols(x);
      82         [ +  + ]:      17784 :   for (j = 1; j < ly; j++) gel(z,j) = RgM_zc_mul_i(x, gel(y,j), l,c);
      83                 :       3483 :   return z;
      84                 :            : }
      85                 :            : 
      86                 :            : static GEN
      87                 :      15245 : RgV_zc_mul_i(GEN x, GEN y, long l)
      88                 :            : {
      89                 :            :   long i;
      90                 :      15245 :   GEN z = gen_0;
      91                 :      15245 :   pari_sp av = avma;
      92         [ +  + ]:    1093555 :   for (i = 1; i < l; i++) z = gadd(z, gmulgs(gel(x,i), y[i]));
      93                 :      15245 :   return gerepileupto(av, z);
      94                 :            : }
      95                 :            : GEN
      96                 :          0 : RgV_zc_mul(GEN x, GEN y) { return RgV_zc_mul_i(x, y, lg(x)); }
      97                 :            : 
      98                 :            : GEN
      99                 :       3265 : RgV_zm_mul(GEN x, GEN y)
     100                 :            : {
     101                 :       3265 :   long j, l = lg(x), ly = lg(y);
     102                 :       3265 :   GEN z = cgetg(ly, t_VEC);
     103         [ +  + ]:      18510 :   for (j = 1; j < ly; j++) gel(z,j) = RgV_zc_mul_i(x, gel(y,j), l);
     104                 :       3265 :   return z;
     105                 :            : }
     106                 :            : 
     107                 :            : /* scalar product x.x */
     108                 :            : GEN
     109                 :        515 : RgV_dotsquare(GEN x)
     110                 :            : {
     111                 :        515 :   long i, lx = lg(x);
     112                 :        515 :   pari_sp av = avma, lim = stack_lim(av,3);
     113                 :            :   GEN z;
     114         [ -  + ]:        515 :   if (lx == 1) return gen_0;
     115                 :        515 :   z = gsqr(gel(x,1));
     116         [ +  + ]:       2070 :   for (i=2; i<lx; i++)
     117                 :            :   {
     118                 :       1555 :     z = gadd(z, gsqr(gel(x,i)));
     119         [ -  + ]:       1555 :     if (low_stack(lim,stack_lim(av,3)))
     120                 :            :     {
     121         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgV_dotsquare, i = %ld",i);
     122                 :          0 :       z = gerepileupto(av, z);
     123                 :            :     }
     124                 :            :   }
     125                 :        515 :   return gerepileupto(av,z);
     126                 :            : }
     127                 :            : 
     128                 :            : /* scalar product x.y, lx = lg(x) = lg(y) */
     129                 :            : static GEN
     130                 :     575739 : RgV_dotproduct_i(GEN x, GEN y, long lx)
     131                 :            : {
     132                 :     575739 :   pari_sp av = avma, lim = stack_lim(av,3);
     133                 :            :   long i;
     134                 :            :   GEN z;
     135         [ +  + ]:     575739 :   if (lx == 1) return gen_0;
     136                 :     575369 :   z = gmul(gel(x,1),gel(y,1));
     137         [ +  + ]:   25901283 :   for (i=2; i<lx; i++)
     138                 :            :   {
     139                 :   25325914 :     z = gadd(z, gmul(gel(x,i), gel(y,i)));
     140         [ -  + ]:   25325914 :     if (low_stack(lim,stack_lim(av,3)))
     141                 :            :     {
     142         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgV_dotproduct, i = %ld",i);
     143                 :          0 :       z = gerepileupto(av, z);
     144                 :            :     }
     145                 :            :   }
     146                 :     575739 :   return gerepileupto(av,z);
     147                 :            : }
     148                 :            : GEN
     149                 :      42235 : RgV_dotproduct(GEN x,GEN y)
     150                 :            : {
     151         [ -  + ]:      42235 :   if (x == y) return RgV_dotsquare(x);
     152                 :      42235 :   return RgV_dotproduct_i(x, y, lg(x));
     153                 :            : }
     154                 :            : /* v[1] + ... + v[lg(v)-1] */
     155                 :            : GEN
     156                 :     179410 : RgV_sum(GEN v)
     157                 :            : {
     158                 :            :   GEN p;
     159                 :     179410 :   long i, l = lg(v);
     160         [ -  + ]:     179410 :   if (l == 1) return gen_0;
     161         [ +  + ]:     509000 :   p = gel(v,1); for (i=2; i<l; i++) p = gadd(p, gel(v,i));
     162                 :     179410 :   return p;
     163                 :            : }
     164                 :            : /* v[1] + ... + v[n]. Assume lg(v) > n. */
     165                 :            : GEN
     166                 :        270 : RgV_sumpart(GEN v, long n)
     167                 :            : {
     168                 :            :   GEN p;
     169                 :            :   long i;
     170         [ -  + ]:        270 :   if (!n) return gen_0;
     171         [ +  + ]:        740 :   p = gel(v,1); for (i=2; i<=n; i++) p = gadd(p, gel(v,i));
     172                 :        270 :   return p;
     173                 :            : }
     174                 :            : /* v[m] + ... + v[n]. Assume lg(v) > n, m > 0. */
     175                 :            : GEN
     176                 :          0 : RgV_sumpart2(GEN v, long m, long n)
     177                 :            : {
     178                 :            :   GEN p;
     179                 :            :   long i;
     180         [ #  # ]:          0 :   if (n < m) return gen_0;
     181         [ #  # ]:          0 :   p = gel(v,m); for (i=m+1; i<=n; i++) p = gadd(p, gel(v,i));
     182                 :          0 :   return p;
     183                 :            : }
     184                 :            : 
     185                 :            : /*                    ADDITION SCALAR + MATRIX                     */
     186                 :            : /* x square matrix, y scalar; create the square matrix x + y*Id */
     187                 :            : GEN
     188                 :       7345 : RgM_Rg_add(GEN x, GEN y)
     189                 :            : {
     190                 :       7345 :   long l = lg(x), i, j;
     191                 :       7345 :   GEN z = cgetg(l,t_MAT);
     192                 :            : 
     193         [ -  + ]:       7345 :   if (l==1) return z;
     194         [ -  + ]:       7345 :   if (l != lgcols(x)) pari_err_OP( "+", x, y);
     195                 :       7345 :   z = cgetg(l,t_MAT);
     196         [ +  + ]:      24950 :   for (i=1; i<l; i++)
     197                 :            :   {
     198                 :      17605 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     199                 :      17605 :     gel(z,i) = zi;
     200         [ +  + ]:     653860 :     for (j=1; j<l; j++)
     201         [ +  + ]:     636255 :       gel(zi,j) = i==j? gadd(y,gel(xi,j)): gcopy(gel(xi,j));
     202                 :            :   }
     203                 :       7345 :   return z;
     204                 :            : }
     205                 :            : GEN
     206                 :          0 : RgM_Rg_sub(GEN x, GEN y)
     207                 :            : {
     208                 :          0 :   long l = lg(x), i, j;
     209                 :          0 :   GEN z = cgetg(l,t_MAT);
     210                 :            : 
     211         [ #  # ]:          0 :   if (l==1) return z;
     212         [ #  # ]:          0 :   if (l != lgcols(x)) pari_err_OP( "-", x, y);
     213                 :          0 :   z = cgetg(l,t_MAT);
     214         [ #  # ]:          0 :   for (i=1; i<l; i++)
     215                 :            :   {
     216                 :          0 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     217                 :          0 :     gel(z,i) = zi;
     218         [ #  # ]:          0 :     for (j=1; j<l; j++)
     219         [ #  # ]:          0 :       gel(zi,j) = i==j? gsub(y,gel(xi,j)): gcopy(gel(xi,j));
     220                 :            :   }
     221                 :          0 :   return z;
     222                 :            : }
     223                 :            : GEN
     224                 :      23070 : RgM_Rg_add_shallow(GEN x, GEN y)
     225                 :            : {
     226                 :      23070 :   long l = lg(x), i, j;
     227                 :      23070 :   GEN z = cgetg(l,t_MAT);
     228                 :            : 
     229         [ +  + ]:      23070 :   if (l==1) return z;
     230         [ -  + ]:      23030 :   if (l != lgcols(x)) pari_err_OP( "+", x, y);
     231         [ +  + ]:     287480 :   for (i=1; i<l; i++)
     232                 :            :   {
     233                 :     264450 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     234                 :     264450 :     gel(z,i) = zi;
     235         [ +  + ]:    5671530 :     for (j=1; j<l; j++) gel(zi,j) = gel(xi,j);
     236                 :     264450 :     gel(zi,i) = gadd(gel(zi,i), y);
     237                 :            :   }
     238                 :      23070 :   return z;
     239                 :            : }
     240                 :            : GEN
     241                 :        125 : RgM_Rg_sub_shallow(GEN x, GEN y)
     242                 :            : {
     243                 :        125 :   long l = lg(x), i, j;
     244                 :        125 :   GEN z = cgetg(l,t_MAT);
     245                 :            : 
     246         [ -  + ]:        125 :   if (l==1) return z;
     247         [ -  + ]:        125 :   if (l != lgcols(x)) pari_err_OP( "-", x, y);
     248         [ +  + ]:       1380 :   for (i=1; i<l; i++)
     249                 :            :   {
     250                 :       1255 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     251                 :       1255 :     gel(z,i) = zi;
     252         [ +  + ]:      20430 :     for (j=1; j<l; j++) gel(zi,j) = gel(xi,j);
     253                 :       1255 :     gel(zi,i) = gsub(gel(zi,i), y);
     254                 :            :   }
     255                 :        125 :   return z;
     256                 :            : }
     257                 :            : 
     258                 :            : GEN
     259                 :      32085 : RgC_Rg_add(GEN x, GEN y)
     260                 :            : {
     261                 :      32085 :   long k, lx = lg(x);
     262                 :      32085 :   GEN z = cgetg(lx, t_COL);
     263         [ +  + ]:      32085 :   if (lx == 1)
     264                 :            :   {
     265         [ +  - ]:          5 :     if (isintzero(y)) return z;
     266                 :          0 :     pari_err_TYPE2("+",x,y);
     267                 :            :   }
     268                 :      32080 :   gel(z,1) = gadd(y,gel(x,1));
     269         [ +  + ]:     133070 :   for (k = 2; k < lx; k++) gel(z,k) = gcopy(gel(x,k));
     270                 :      32085 :   return z;
     271                 :            : }
     272                 :            : 
     273                 :            : static GEN
     274                 :    3170286 : RgC_add_i(GEN x, GEN y, long lx)
     275                 :            : {
     276                 :    3170286 :   GEN A = cgetg(lx, t_COL);
     277                 :            :   long i;
     278         [ +  + ]:   78907484 :   for (i=1; i<lx; i++) gel(A,i) = gadd(gel(x,i), gel(y,i));
     279                 :    3170286 :   return A;
     280                 :            : }
     281                 :            : GEN
     282                 :    3166871 : RgC_add(GEN x, GEN y) { return RgC_add_i(x, y, lg(x)); }
     283                 :            : GEN
     284                 :     426291 : RgV_add(GEN x, GEN y)
     285                 :            : {
     286                 :     426291 :   long i, lx = lg(x);
     287                 :     426291 :   GEN A = cgetg(lx, t_VEC);
     288         [ +  + ]:    1625008 :   for (i=1; i<lx; i++) gel(A,i) = gadd(gel(x,i), gel(y,i));
     289                 :     426291 :   return A;
     290                 :            : }
     291                 :            : 
     292                 :            : static GEN
     293                 :     777059 : RgC_sub_i(GEN x, GEN y, long lx)
     294                 :            : {
     295                 :            :   long i;
     296                 :     777059 :   GEN A = cgetg(lx, t_COL);
     297         [ +  + ]:    3415319 :   for (i=1; i<lx; i++) gel(A,i) = gsub(gel(x,i), gel(y,i));
     298                 :     777059 :   return A;
     299                 :            : }
     300                 :            : GEN
     301                 :     762248 : RgC_sub(GEN x, GEN y) { return RgC_sub_i(x, y, lg(x)); }
     302                 :            : GEN
     303                 :      41670 : RgV_sub(GEN x, GEN y)
     304                 :            : {
     305                 :      41670 :   long i, lx = lg(x);
     306                 :      41670 :   GEN A = cgetg(lx, t_VEC);
     307         [ +  + ]:     224725 :   for (i=1; i<lx; i++) gel(A,i) = gsub(gel(x,i), gel(y,i));
     308                 :      41670 :   return A;
     309                 :            : }
     310                 :            : 
     311                 :            : GEN
     312                 :        510 : RgM_add(GEN x, GEN y)
     313                 :            : {
     314                 :        510 :   long lx = lg(x), l, j;
     315                 :            :   GEN z;
     316         [ -  + ]:        510 :   if (lx == 1) return cgetg(1, t_MAT);
     317                 :        510 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     318         [ +  + ]:       3925 :   for (j = 1; j < lx; j++) gel(z,j) = RgC_add_i(gel(x,j), gel(y,j), l);
     319                 :        510 :   return z;
     320                 :            : }
     321                 :            : GEN
     322                 :       3518 : RgM_sub(GEN x, GEN y)
     323                 :            : {
     324                 :       3518 :   long lx = lg(x), l, j;
     325                 :            :   GEN z;
     326         [ -  + ]:       3518 :   if (lx == 1) return cgetg(1, t_MAT);
     327                 :       3518 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     328         [ +  + ]:      18329 :   for (j = 1; j < lx; j++) gel(z,j) = RgC_sub_i(gel(x,j), gel(y,j), l);
     329                 :       3518 :   return z;
     330                 :            : }
     331                 :            : 
     332                 :            : static GEN
     333                 :      70893 : RgC_neg_i(GEN x, long lx)
     334                 :            : {
     335                 :            :   long i;
     336                 :      70893 :   GEN y = cgetg(lx, t_COL);
     337         [ +  + ]:     438122 :   for (i=1; i<lx; i++) gel(y,i) = gneg(gel(x,i));
     338                 :      70893 :   return y;
     339                 :            : }
     340                 :            : GEN
     341                 :      36188 : RgC_neg(GEN x) { return RgC_neg_i(x, lg(x)); }
     342                 :            : GEN
     343                 :       3450 : RgV_neg(GEN x)
     344                 :            : {
     345                 :       3450 :   long i, lx = lg(x);
     346                 :       3450 :   GEN y = cgetg(lx, t_VEC);
     347         [ +  + ]:      94685 :   for (i=1; i<lx; i++) gel(y,i) = gneg(gel(x,i));
     348                 :       3450 :   return y;
     349                 :            : }
     350                 :            : GEN
     351                 :       9135 : RgM_neg(GEN x)
     352                 :            : {
     353                 :       9135 :   long i, hx, lx = lg(x);
     354                 :       9135 :   GEN y = cgetg(lx, t_MAT);
     355         [ -  + ]:       9135 :   if (lx == 1) return y;
     356                 :       9135 :   hx = lgcols(x);
     357         [ +  + ]:      43840 :   for (i=1; i<lx; i++) gel(y,i) = RgC_neg_i(gel(x,i), hx);
     358                 :       9135 :   return y;
     359                 :            : }
     360                 :            : 
     361                 :            : GEN
     362                 :     158963 : RgV_RgC_mul(GEN x, GEN y)
     363                 :            : {
     364                 :     158963 :   long lx = lg(x);
     365         [ +  + ]:     158963 :   if (lx != lg(y)) pari_err_OP("operation 'RgV_RgC_mul'", x, y);
     366                 :     158908 :   return RgV_dotproduct_i(x, y, lx);
     367                 :            : }
     368                 :            : GEN
     369                 :         10 : RgC_RgV_mul(GEN x, GEN y)
     370                 :            : {
     371                 :         10 :   long i, ly = lg(y);
     372                 :         10 :   GEN z = cgetg(ly,t_MAT);
     373         [ +  + ]:         30 :   for (i=1; i<ly; i++) gel(z,i) = RgC_Rg_mul(x, gel(y,i));
     374                 :         10 :   return z;
     375                 :            : }
     376                 :            : GEN
     377                 :          0 : RgC_RgM_mul(GEN x, GEN y)
     378                 :            : {
     379                 :          0 :   long i, ly = lg(y);
     380                 :          0 :   GEN z = cgetg(ly,t_MAT);
     381 [ #  # ][ #  # ]:          0 :   if (ly != 1 && lgcols(y) != 2) pari_err_OP("operation 'RgC_RgM_mul'",x,y);
     382         [ #  # ]:          0 :   for (i=1; i<ly; i++) gel(z,i) = RgC_Rg_mul(x, gcoeff(y,1,i));
     383                 :          0 :   return z;
     384                 :            : }
     385                 :            : GEN
     386                 :          0 : RgM_RgV_mul(GEN x, GEN y)
     387                 :            : {
     388         [ #  # ]:          0 :   if (lg(x) != 2) pari_err_OP("operation 'RgM_RgV_mul'", x,y);
     389                 :          0 :   return RgC_RgV_mul(gel(x,1), y);
     390                 :            : }
     391                 :            : 
     392                 :            : /* x[i,]*y, l = lg(y) > 1 */
     393                 :            : static GEN
     394                 :   11701979 : RgMrow_RgC_mul_i(GEN x, GEN y, long i, long l)
     395                 :            : {
     396                 :   11701979 :   pari_sp av = avma;
     397                 :   11701979 :   GEN t = gmul(gcoeff(x,i,1), gel(y,1)); /* l > 1 ! */
     398                 :            :   long j;
     399         [ +  + ]:  116332667 :   for (j=2; j<l; j++) t = gadd(t, gmul(gcoeff(x,i,j), gel(y,j)));
     400                 :   11701979 :   return gerepileupto(av,t);
     401                 :            : }
     402                 :            : GEN
     403                 :          0 : RgMrow_RgC_mul(GEN x, GEN y, long i)
     404                 :          0 : { return RgMrow_RgC_mul_i(x, y, i, lg(x)); }
     405                 :            : 
     406                 :            : /* compatible t_MAT * t_COL, lx = lg(x) = lg(y) > 1, l = lgcols(x) */
     407                 :            : static GEN
     408                 :    2685468 : RgM_RgC_mul_i(GEN x, GEN y, long lx, long l)
     409                 :            : {
     410                 :    2685468 :   GEN z = cgetg(l,t_COL);
     411                 :            :   long i;
     412         [ +  + ]:   14387447 :   for (i=1; i<l; i++) gel(z,i) = RgMrow_RgC_mul_i(x,y,i,lx);
     413                 :    2685468 :   return z;
     414                 :            : }
     415                 :            : 
     416                 :            : GEN
     417                 :    1361465 : RgM_RgC_mul(GEN x, GEN y)
     418                 :            : {
     419                 :    1361465 :   long lx = lg(x);
     420                 :    1361465 :   GEN ffx = NULL, ffy = NULL;
     421         [ -  + ]:    1361465 :   if (lx != lg(y)) pari_err_OP("operation 'RgM_RgC_mul'", x,y);
     422         [ -  + ]:    1361465 :   if (lx == 1) return cgetg(1,t_COL);
     423 [ +  + ][ +  - ]:    1361465 :   if (RgM_is_FFM(x, &ffx) && RgC_is_FFC(y, &ffy)) {
     424         [ -  + ]:         15 :     if (!FF_samefield(ffx, ffy))
     425                 :          0 :       pari_err_OP("*", ffx, ffy);
     426                 :         15 :     return FFM_FFC_mul(x, y, ffx);
     427                 :            :   }
     428                 :    1361465 :   return RgM_RgC_mul_i(x, y, lx, lgcols(x));
     429                 :            : }
     430                 :            : 
     431                 :            : GEN
     432                 :      18320 : RgV_RgM_mul(GEN x, GEN y)
     433                 :            : {
     434                 :      18320 :   long i, lx, ly = lg(y);
     435                 :            :   GEN z;
     436         [ +  + ]:      18320 :   if (ly == 1) return cgetg(1,t_VEC);
     437                 :      18315 :   lx = lg(x);
     438         [ +  + ]:      18315 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgV_RgM_mul'", x,y);
     439                 :      18310 :   z = cgetg(ly, t_VEC);
     440         [ +  + ]:     390430 :   for (i=1; i<ly; i++) gel(z,i) = RgV_dotproduct_i(x, gel(y,i), lx);
     441                 :      18315 :   return z;
     442                 :            : }
     443                 :            : 
     444                 :            : static int
     445                 :     323220 : is_modular_mul(GEN a, GEN b, GEN *z)
     446                 :            : {
     447                 :     323220 :   GEN p1 = NULL, p2 = NULL, p;
     448                 :            :   ulong pp;
     449 [ +  + ][ +  + ]:     323220 :   if (!RgM_is_FpM(a, &p1) || !p1) return 0;
     450 [ +  - ][ -  + ]:         55 :   if (!RgM_is_FpM(b, &p2) || !p2) return 0;
     451                 :         55 :   p = gcdii(p1, p2);
     452                 :         55 :   a = RgM_Fp_init(a, p, &pp);
     453      [ +  +  + ]:         55 :   switch(pp)
     454                 :            :   {
     455                 :            :   case 0:
     456                 :         11 :     b = RgM_to_FpM(b,p);
     457                 :         11 :     b = FpM_mul(a,b,p);
     458                 :         11 :     *z = FpM_to_mod(b,p);
     459                 :         11 :     break;
     460                 :            :   case 2:
     461                 :         20 :     b = RgM_to_F2m(b);
     462                 :         20 :     b = F2m_mul(a,b);
     463                 :         20 :     *z = F2m_to_mod(b);
     464                 :         20 :     break;
     465                 :            :   default:
     466                 :         24 :     b = RgM_to_Flm(b,pp);
     467                 :         24 :     b = Flm_mul(a,b,pp);
     468                 :         24 :     *z = Flm_to_mod(b,pp);
     469                 :            :   }
     470                 :     323220 :   return 1;
     471                 :            : }
     472                 :            : static int
     473                 :        165 : is_modular_sqr(GEN a, GEN *z)
     474                 :            : {
     475                 :        165 :   GEN p = NULL;
     476                 :            :   ulong pp;
     477 [ +  + ][ +  + ]:        165 :   if (!RgM_is_FpM(a, &p) || !p) return 0;
     478                 :         45 :   a = RgM_Fp_init(a, p, &pp);
     479      [ +  +  + ]:         45 :   switch(pp)
     480                 :            :   {
     481                 :         11 :     case 0: *z = FpM_to_mod(FpM_mul(a,a, p), p); break;
     482                 :         10 :     case 2: *z = F2m_to_mod(F2m_mul(a,a)); break;
     483                 :         24 :     default:*z = Flm_to_mod(Flm_mul(a,a, pp), pp); break;
     484                 :            :   }
     485                 :        165 :   return 1;
     486                 :            : }
     487                 :            : 
     488                 :            : GEN
     489                 :     323490 : RgM_mul(GEN x, GEN y)
     490                 :            : {
     491                 :     323490 :   pari_sp av = avma;
     492                 :     323490 :   long j, l, lx, ly = lg(y);
     493                 :     323490 :   GEN z, ffx = NULL, ffy = NULL;
     494         [ +  + ]:     323490 :   if (ly == 1) return cgetg(1,t_MAT);
     495                 :     323225 :   lx = lg(x);
     496         [ -  + ]:     323225 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgM_mul'", x,y);
     497         [ +  + ]:     323225 :   if (lx == 1) return zeromat(0,ly-1);
     498         [ +  + ]:     323220 :   if (is_modular_mul(x,y,&z)) return gerepileupto(av, z);
     499 [ +  + ][ +  - ]:     323165 :   if (RgM_is_FFM(x, &ffx) && RgM_is_FFM(y, &ffy)) {
     500         [ -  + ]:         15 :     if (!FF_samefield(ffx, ffy))
     501                 :          0 :       pari_err_OP("*", ffx, ffy);
     502                 :         15 :     return FFM_mul(x, y, ffx);
     503                 :            :   }
     504                 :     323150 :   z = cgetg(ly, t_MAT);
     505                 :     323150 :   l = lgcols(x);
     506         [ +  + ]:    1646668 :   for (j=1; j<ly; j++) gel(z,j) = RgM_RgC_mul_i(x, gel(y,j), lx, l);
     507                 :     323490 :   return z;
     508                 :            : }
     509                 :            : /* assume result is symmetric */
     510                 :            : GEN
     511                 :          0 : RgM_multosym(GEN x, GEN y)
     512                 :            : {
     513                 :          0 :   long j, lx, ly = lg(y);
     514                 :            :   GEN M;
     515         [ #  # ]:          0 :   if (ly == 1) return cgetg(1,t_MAT);
     516                 :          0 :   lx = lg(x);
     517         [ #  # ]:          0 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgM_multosym'", x,y);
     518         [ #  # ]:          0 :   if (lx == 1) return cgetg(1,t_MAT);
     519         [ #  # ]:          0 :   if (ly != lgcols(x)) pari_err_OP("operation 'RgM_multosym'", x,y);
     520                 :          0 :   M = cgetg(ly, t_MAT);
     521         [ #  # ]:          0 :   for (j=1; j<ly; j++)
     522                 :            :   {
     523                 :          0 :     GEN z = cgetg(ly,t_COL), yj = gel(y,j);
     524                 :            :     long i;
     525         [ #  # ]:          0 :     for (i=1; i<j; i++) gel(z,i) = gcoeff(M,j,i);
     526         [ #  # ]:          0 :     for (i=j; i<ly; i++)gel(z,i) = RgMrow_RgC_mul_i(x,yj,i,lx);
     527                 :          0 :     gel(M,j) = z;
     528                 :            :   }
     529                 :          0 :   return M;
     530                 :            : }
     531                 :            : /* x~ * y, assuming result is symmetric */
     532                 :            : GEN
     533                 :        317 : RgM_transmultosym(GEN x, GEN y)
     534                 :            : {
     535                 :        317 :   long i, j, l, ly = lg(y);
     536                 :            :   GEN M;
     537         [ -  + ]:        317 :   if (ly == 1) return cgetg(1,t_MAT);
     538         [ -  + ]:        317 :   if (lg(x) != ly) pari_err_OP("operation 'RgM_transmultosym'", x,y);
     539                 :        317 :   l = lgcols(y);
     540         [ -  + ]:        317 :   if (lgcols(x) != l) pari_err_OP("operation 'RgM_transmultosym'", x,y);
     541                 :        317 :   M = cgetg(ly, t_MAT);
     542         [ +  + ]:       1349 :   for (i=1; i<ly; i++)
     543                 :            :   {
     544                 :       1032 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     545                 :       1032 :     gel(M,i) = c;
     546         [ +  + ]:       2411 :     for (j=1; j<i; j++)
     547                 :       1379 :       gcoeff(M,i,j) = gel(c,j) = RgV_dotproduct_i(xi,gel(y,j),l);
     548                 :       1032 :     gel(c,i) = RgV_dotproduct_i(xi,gel(y,i),l);
     549                 :            :   }
     550                 :        317 :   return M;
     551                 :            : }
     552                 :            : /* x~ * y */
     553                 :            : GEN
     554                 :          0 : RgM_transmul(GEN x, GEN y)
     555                 :            : {
     556                 :          0 :   long i, j, l, lx, ly = lg(y);
     557                 :            :   GEN M;
     558         [ #  # ]:          0 :   if (ly == 1) return cgetg(1,t_MAT);
     559                 :          0 :   lx = lg(x);
     560                 :          0 :   l = lgcols(y);
     561         [ #  # ]:          0 :   if (lgcols(x) != l) pari_err_OP("operation 'RgM_transmul'", x,y);
     562                 :          0 :   M = cgetg(ly, t_MAT);
     563         [ #  # ]:          0 :   for (i=1; i<ly; i++)
     564                 :            :   {
     565                 :          0 :     GEN yi = gel(y,i), c = cgetg(lx,t_COL);
     566                 :          0 :     gel(M,i) = c;
     567         [ #  # ]:          0 :     for (j=1; j<lx; j++) gel(c,j) = RgV_dotproduct_i(yi,gel(x,j),l);
     568                 :            :   }
     569                 :          0 :   return M;
     570                 :            : }
     571                 :            : 
     572                 :            : GEN
     573                 :         85 : gram_matrix(GEN x)
     574                 :            : {
     575                 :         85 :   long i,j, l, lx = lg(x);
     576                 :            :   GEN M;
     577         [ -  + ]:         85 :   if (!is_matvec_t(typ(x))) pari_err_TYPE("gram",x);
     578         [ +  + ]:         85 :   if (lx == 1) return cgetg(1,t_MAT);
     579                 :         75 :   l = lgcols(x);
     580                 :         75 :   M = cgetg(lx,t_MAT);
     581         [ +  + ]:        210 :   for (i=1; i<lx; i++)
     582                 :            :   {
     583                 :        135 :     GEN xi = gel(x,i), c = cgetg(lx,t_COL);
     584                 :        135 :     gel(M,i) = c;
     585         [ +  + ]:        200 :     for (j=1; j<i; j++)
     586                 :         65 :       gcoeff(M,i,j) = gel(c,j) = RgV_dotproduct_i(xi,gel(x,j),l);
     587                 :        135 :     gel(c,i) = RgV_dotsquare(xi);
     588                 :            :   }
     589                 :         85 :   return M;
     590                 :            : }
     591                 :            : 
     592                 :            : GEN
     593                 :        190 : RgM_sqr(GEN x)
     594                 :            : {
     595                 :        190 :   pari_sp av = avma;
     596                 :        190 :   long j, lx = lg(x);
     597                 :            :   GEN z;
     598         [ +  + ]:        190 :   if (lx == 1) return cgetg(1, t_MAT);
     599         [ -  + ]:        165 :   if (lx != lgcols(x)) pari_err_OP("operation 'RgM_mul'", x,x);
     600         [ +  + ]:        165 :   if (is_modular_sqr(x,&z)) return gerepileupto(av, z);
     601                 :        120 :   z = cgetg(lx, t_MAT);
     602         [ +  + ]:        620 :   for (j=1; j<lx; j++) gel(z,j) = RgM_RgC_mul_i(x, gel(x,j), lx, lx);
     603                 :        190 :   return z;
     604                 :            : }
     605                 :            : 
     606                 :            : static GEN
     607                 :        130 : _RgM_add(void *E, GEN x, GEN y) { (void)E; return RgM_add(x, y); }
     608                 :            : 
     609                 :            : static GEN
     610                 :        185 : _RgM_cmul(void *E, GEN P, long a, GEN x) { (void)E; return RgM_Rg_mul(x,gel(P,a+2)); }
     611                 :            : 
     612                 :            : static GEN
     613                 :         15 : _RgM_sqr(void *E, GEN x) { (void) E; return RgM_sqr(x); }
     614                 :            : 
     615                 :            : static GEN
     616                 :         25 : _RgM_mul(void *E, GEN x, GEN y) { (void) E; return RgM_mul(x, y); }
     617                 :            : 
     618                 :            : static GEN
     619                 :        105 : _RgM_one(void *E) { long *n = (long*) E; return matid(*n); }
     620                 :            : 
     621                 :            : static GEN
     622                 :          0 : _RgM_zero(void *E) { long *n = (long*) E; return zeromat(*n,*n); }
     623                 :            : 
     624                 :            : static GEN
     625                 :         85 : _RgM_red(void *E, GEN x) { (void)E; return x; }
     626                 :            : 
     627                 :            : static struct bb_algebra RgM_algebra = { _RgM_red,_RgM_add,_RgM_mul,_RgM_sqr,_RgM_one,_RgM_zero };
     628                 :            : 
     629                 :            : /* generates the list of powers of x of degree 0,1,2,...,l*/
     630                 :            : GEN
     631                 :          5 : RgM_powers(GEN x, long l)
     632                 :            : {
     633                 :          5 :   long n = lg(x)-1;
     634                 :          5 :   return gen_powers(x,l,1,(void *) &n, &_RgM_sqr, &_RgM_mul, &_RgM_one);
     635                 :            : }
     636                 :            : 
     637                 :            : GEN
     638                 :         25 : RgX_RgMV_eval(GEN Q, GEN x)
     639                 :            : {
     640         [ +  - ]:         25 :   long n = lg(x)>1 ? lg(gel(x,1))-1:0;
     641                 :         25 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)&n,&RgM_algebra,&_RgM_cmul);
     642                 :            : }
     643                 :            : 
     644                 :            : GEN
     645                 :         30 : RgX_RgM_eval(GEN Q, GEN x)
     646                 :            : {
     647                 :         30 :   long n = lg(x)-1;
     648                 :         30 :   return gen_bkeval(Q,degpol(Q),x,1,(void*)&n,&RgM_algebra,&_RgM_cmul);
     649                 :            : }
     650                 :            : 
     651                 :            : GEN
     652                 :     276804 : RgC_Rg_div(GEN x, GEN y) {
     653                 :     276804 :   long i, lx = lg(x);
     654                 :     276804 :   GEN z = cgetg(lx, t_COL);
     655         [ +  + ]:    1109692 :   for (i=1; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
     656                 :     276804 :   return z;
     657                 :            : }
     658                 :            : GEN
     659                 :     317356 : RgC_Rg_mul(GEN x, GEN y) {
     660                 :     317356 :   long i, lx = lg(x);
     661                 :     317356 :   GEN z = cgetg(lx, t_COL);
     662         [ +  + ]:    1608504 :   for (i=1; i<lx; i++) gel(z,i) = gmul(gel(x,i),y);
     663                 :     317356 :   return z;
     664                 :            : }
     665                 :            : GEN
     666                 :       2347 : RgV_Rg_mul(GEN x, GEN y) {
     667                 :       2347 :   long i, lx = lg(x);
     668                 :       2347 :   GEN z = cgetg(lx, t_VEC);
     669         [ +  + ]:       9276 :   for (i=1; i<lx; i++) gel(z,i) = gmul(gel(x,i),y);
     670                 :       2347 :   return z;
     671                 :            : }
     672                 :            : GEN
     673                 :      69210 : RgM_Rg_div(GEN X, GEN c) {
     674                 :      69210 :   long i, j, h, l = lg(X);
     675                 :      69210 :   GEN A = cgetg(l, t_MAT);
     676         [ -  + ]:      69210 :   if (l == 1) return A;
     677                 :      69210 :   h = lgcols(X);
     678         [ +  + ]:     487925 :   for (j=1; j<l; j++)
     679                 :            :   {
     680                 :     418715 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     681         [ +  + ]:    4373665 :     for (i = 1; i < h; i++) gel(a,i) = gdiv(gel(x,i), c);
     682                 :     418715 :     gel(A,j) = a;
     683                 :            :   }
     684                 :      69210 :   return A;
     685                 :            : }
     686                 :            : GEN
     687                 :      36507 : RgM_Rg_mul(GEN X, GEN c) {
     688                 :      36507 :   long i, j, h, l = lg(X);
     689                 :      36507 :   GEN A = cgetg(l, t_MAT);
     690         [ +  + ]:      36507 :   if (l == 1) return A;
     691                 :      36497 :   h = lgcols(X);
     692         [ +  + ]:     130606 :   for (j=1; j<l; j++)
     693                 :            :   {
     694                 :      94109 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     695         [ +  + ]:     519387 :     for (i = 1; i < h; i++) gel(a,i) = gmul(gel(x,i), c);
     696                 :      94109 :     gel(A,j) = a;
     697                 :            :   }
     698                 :      36507 :   return A;
     699                 :            : }
     700                 :            : 
     701                 :            : /********************************************************************/
     702                 :            : /*                                                                  */
     703                 :            : /*                    SCALAR TO MATRIX/VECTOR                       */
     704                 :            : /*                                                                  */
     705                 :            : /********************************************************************/
     706                 :            : /* fill the square nxn matrix equal to t*Id */
     707                 :            : static void
     708                 :     980722 : fill_scalmat(GEN y, GEN t, long n)
     709                 :            : {
     710                 :            :   long i;
     711         [ +  + ]:    4540836 :   for (i = 1; i <= n; i++)
     712                 :            :   {
     713                 :    3560114 :     gel(y,i) = zerocol(n);
     714                 :    3560114 :     gcoeff(y,i,i) = t;
     715                 :            :   }
     716                 :     980722 : }
     717                 :            : 
     718                 :            : GEN
     719                 :     113649 : scalarmat(GEN x, long n) {
     720                 :     113649 :   GEN y = cgetg(n+1, t_MAT);
     721         [ -  + ]:     113649 :   if (!n) return y;
     722                 :     113649 :   fill_scalmat(y, gcopy(x), n); return y;
     723                 :            : }
     724                 :            : GEN
     725                 :         60 : scalarmat_shallow(GEN x, long n) {
     726                 :         60 :   GEN y = cgetg(n+1, t_MAT);
     727                 :         60 :   fill_scalmat(y, x, n); return y;
     728                 :            : }
     729                 :            : GEN
     730                 :         50 : scalarmat_s(long x, long n) {
     731                 :         50 :   GEN y = cgetg(n+1, t_MAT);
     732         [ -  + ]:         50 :   if (!n) return y;
     733                 :         50 :   fill_scalmat(y, stoi(x), n); return y;
     734                 :            : }
     735                 :            : GEN
     736                 :     866968 : matid(long n) {
     737                 :            :   GEN y;
     738         [ +  + ]:     866968 :   if (n < 0) pari_err_DOMAIN("matid", "size", "<", gen_0, stoi(n));
     739                 :     866963 :   y = cgetg(n+1, t_MAT);
     740                 :     866963 :   fill_scalmat(y, gen_1, n); return y;
     741                 :            : }
     742                 :            : 
     743                 :            : INLINE GEN
     744                 :     393335 : scalarcol_i(GEN x, long n, long c)
     745                 :            : {
     746                 :            :   long i;
     747                 :     393335 :   GEN y = cgetg(n+1,t_COL);
     748         [ -  + ]:     393335 :   if (!n) return y;
     749         [ +  + ]:     393335 :   gel(y,1) = c? gcopy(x): x;
     750         [ +  + ]:    1576999 :   for (i=2; i<=n; i++) gel(y,i) = gen_0;
     751                 :     393335 :   return y;
     752                 :            : }
     753                 :            : 
     754                 :            : GEN
     755                 :      73597 : scalarcol(GEN x, long n) { return scalarcol_i(x,n,1); }
     756                 :            : 
     757                 :            : GEN
     758                 :     319738 : scalarcol_shallow(GEN x, long n) { return scalarcol_i(x,n,0); }
     759                 :            : 
     760                 :            : int
     761                 :       6875 : RgM_isscalar(GEN x, GEN s)
     762                 :            : {
     763                 :       6875 :   long i, j, lx = lg(x);
     764                 :            : 
     765         [ -  + ]:       6875 :   if (lx == 1) return 1;
     766         [ -  + ]:       6875 :   if (lx != lgcols(x)) return 0;
     767         [ +  + ]:       6875 :   if (!s) s = gcoeff(x,1,1);
     768                 :            : 
     769         [ +  + ]:      30160 :   for (j=1; j<lx; j++)
     770                 :            :   {
     771                 :      26210 :     GEN c = gel(x,j);
     772         [ +  + ]:     165965 :     for (i=1; i<j; )
     773         [ +  + ]:     141940 :       if (!gequal0(gel(c,i++))) return 0;
     774                 :            :     /* i = j */
     775         [ +  + ]:      24025 :       if (!gequal(gel(c,i++),s)) return 0;
     776         [ +  + ]:     166225 :     for (   ; i<lx; )
     777         [ -  + ]:     142940 :       if (!gequal0(gel(c,i++))) return 0;
     778                 :            :   }
     779                 :       6875 :   return 1;
     780                 :            : }
     781                 :            : 
     782                 :            : int
     783                 :        500 : RgM_isidentity(GEN x)
     784                 :            : {
     785                 :        500 :   long i,j, lx = lg(x);
     786                 :            : 
     787         [ -  + ]:        500 :   if (lx == 1) return 1;
     788         [ -  + ]:        500 :   if (lx != lgcols(x)) return 0;
     789         [ +  + ]:        965 :   for (j=1; j<lx; j++)
     790                 :            :   {
     791                 :        960 :     GEN c = gel(x,j);
     792         [ +  + ]:       1130 :     for (i=1; i<j; )
     793         [ +  + ]:        460 :       if (!gequal0(gel(c,i++))) return 0;
     794                 :            :     /* i = j */
     795         [ +  + ]:        670 :       if (!gequal1(gel(c,i++))) return 0;
     796         [ +  + ]:       1055 :     for (   ; i<lx; )
     797         [ -  + ]:        590 :       if (!gequal0(gel(c,i++))) return 0;
     798                 :            :   }
     799                 :        500 :   return 1;
     800                 :            : }
     801                 :            : 
     802                 :            : int
     803                 :         25 : RgM_isdiagonal(GEN x)
     804                 :            : {
     805                 :         25 :   long i,j, lx = lg(x);
     806         [ -  + ]:         25 :   if (lx == 1) return 1;
     807         [ -  + ]:         25 :   if (lx != lgcols(x)) return 0;
     808                 :            : 
     809         [ +  + ]:         75 :   for (j=1; j<lx; j++)
     810                 :            :   {
     811                 :         55 :     GEN c = gel(x,j);
     812         [ +  + ]:         95 :     for (i=1; i<j; i++)
     813         [ -  + ]:         40 :       if (!gequal0(gel(c,i))) return 0;
     814         [ +  + ]:         95 :     for (i++; i<lx; i++)
     815         [ +  + ]:         45 :       if (!gequal0(gel(c,i))) return 0;
     816                 :            :   }
     817                 :         25 :   return 1;
     818                 :            : }
     819                 :            : int
     820                 :         10 : isdiagonal(GEN x)
     821                 :            : {
     822 [ +  - ][ +  - ]:         10 :   return (typ(x)==t_MAT) && RgM_isdiagonal(x);
     823                 :            : }
     824                 :            : 
     825                 :            : /* returns the first index i<=n such that x=v[i] if it exists, 0 otherwise */
     826                 :            : long
     827                 :      15570 : RgV_isin(GEN v, GEN x)
     828                 :            : {
     829                 :      15570 :   long i, l = lg(v);
     830         [ +  + ]:     289615 :   for (i = 1; i < l; i++)
     831         [ +  + ]:     289595 :     if (gequal(gel(v,i), x)) return i;
     832                 :      15570 :   return 0;
     833                 :            : }
     834                 :            : 
     835                 :            : GEN
     836                 :       2985 : RgM_det_triangular(GEN mat)
     837                 :            : {
     838                 :       2985 :   long i,l = lg(mat);
     839                 :            :   pari_sp av;
     840                 :            :   GEN s;
     841                 :            : 
     842 [ +  + ][ +  - ]:       2985 :   if (l<3) return l<2? gen_1: gcopy(gcoeff(mat,1,1));
     843                 :       2970 :   av = avma; s = gcoeff(mat,1,1);
     844         [ +  + ]:       7380 :   for (i=2; i<l; i++) s = gmul(s,gcoeff(mat,i,i));
     845         [ -  + ]:       2985 :   return av==avma? gcopy(s): gerepileupto(av,s);
     846                 :            : }
     847                 :            : 

Generated by: LCOV version 1.9