Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 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.12.0 lcov report (development 23332-367b47754) Lines: 484 537 90.1 %
Date: 2018-12-10 05:41:52 Functions: 89 96 92.7 %
Legend: Lines: hit not hit

          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      378031 : RgM_is_ZM(GEN x)
      19             : {
      20      378031 :   long i, j, h, l = lg(x);
      21      378031 :   if (l == 1) return 1;
      22      377933 :   h = lgcols(x);
      23      377933 :   if (h == 1) return 1;
      24     1816424 :   for (j = l-1; j > 0; j--)
      25    10573680 :     for (i = h-1; i > 0; i--)
      26     9135189 :       if (typ(gcoeff(x,i,j)) != t_INT) return 0;
      27      339478 :   return 1;
      28             : }
      29             : 
      30             : int
      31         147 : RgM_is_QM(GEN x)
      32             : {
      33         147 :   long i, j, h, l = lg(x);
      34         147 :   if (l == 1) return 1;
      35         147 :   h = lgcols(x);
      36         147 :   if (h == 1) return 1;
      37        1078 :   for (j = l-1; j > 0; j--)
      38       14644 :     for (i = h-1; i > 0; i--)
      39       13713 :       if (!is_rational_t(typ(gcoeff(x,i,j)))) return 0;
      40         133 :   return 1;
      41             : }
      42             : 
      43             : int
      44          35 : RgV_is_ZMV(GEN V)
      45             : {
      46          35 :   long i, l = lg(V);
      47         357 :   for (i=1; i<l; i++)
      48         322 :     if (typ(gel(V,i))!=t_MAT || !RgM_is_ZM(gel(V,i)))
      49           0 :       return 0;
      50          35 :   return 1;
      51             : }
      52             : 
      53             : /********************************************************************/
      54             : /**                                                                **/
      55             : /**                   GENERIC LINEAR ALGEBRA                       **/
      56             : /**                                                                **/
      57             : /********************************************************************/
      58             : /*           GENERIC  MULTIPLICATION involving zc/zm                */
      59             : 
      60             : /* x[i,] * y */
      61             : static GEN
      62      427295 : RgMrow_zc_mul_i(GEN x, GEN y, long c, long i)
      63             : {
      64      427295 :   pari_sp av = avma;
      65      427295 :   GEN s = NULL;
      66             :   long j;
      67    17784072 :   for (j=1; j<c; j++)
      68             :   {
      69    17356777 :     long t = y[j];
      70    17356777 :     if (!t) continue;
      71     1827837 :     if (!s) { s = gmulgs(gcoeff(x,i,j),t); continue; }
      72     1404403 :     switch(t)
      73             :     {
      74      666132 :       case  1: s = gadd(s, gcoeff(x,i,j)); break;
      75      234325 :       case -1: s = gsub(s, gcoeff(x,i,j)); break;
      76      503946 :       default: s = gadd(s, gmulgs(gcoeff(x,i,j), t)); break;
      77             :     }
      78             :   }
      79      427295 :   if (!s) { set_avma(av); return gen_0; }
      80      423434 :   return gerepileupto(av, s);
      81             : }
      82             : GEN
      83       69937 : RgMrow_zc_mul(GEN x, GEN y, long i) { return RgMrow_zc_mul_i(x,y,lg(y),i); }
      84             : /* x non-empty t_MAT, y a compatible zc (dimension > 0). */
      85             : static GEN
      86      112769 : RgM_zc_mul_i(GEN x, GEN y, long c, long l)
      87             : {
      88      112769 :   GEN z = cgetg(l,t_COL);
      89             :   long i;
      90      112769 :   for (i = 1; i < l; i++) gel(z,i) = RgMrow_zc_mul_i(x,y,c,i);
      91      112769 :   return z;
      92             : }
      93             : GEN
      94       71666 : RgM_zc_mul(GEN x, GEN y) { return RgM_zc_mul_i(x,y, lg(x), lgcols(x)); }
      95             : /* x t_MAT, y a compatible zm (dimension > 0). */
      96             : GEN
      97       12783 : RgM_zm_mul(GEN x, GEN y)
      98             : {
      99       12783 :   long j, c, l = lg(x), ly = lg(y);
     100       12783 :   GEN z = cgetg(ly, t_MAT);
     101       12783 :   if (l == 1) return z;
     102       12783 :   c = lgcols(x);
     103       12783 :   for (j = 1; j < ly; j++) gel(z,j) = RgM_zc_mul_i(x, gel(y,j), l,c);
     104       12783 :   return z;
     105             : }
     106             : 
     107             : static GEN
     108       38023 : RgV_zc_mul_i(GEN x, GEN y, long l)
     109             : {
     110             :   long i;
     111       38023 :   GEN z = gen_0;
     112       38023 :   pari_sp av = avma;
     113       38023 :   for (i = 1; i < l; i++) z = gadd(z, gmulgs(gel(x,i), y[i]));
     114       38023 :   return gerepileupto(av, z);
     115             : }
     116             : GEN
     117        6804 : RgV_zc_mul(GEN x, GEN y) { return RgV_zc_mul_i(x, y, lg(x)); }
     118             : 
     119             : GEN
     120        7551 : RgV_zm_mul(GEN x, GEN y)
     121             : {
     122        7551 :   long j, l = lg(x), ly = lg(y);
     123        7551 :   GEN z = cgetg(ly, t_VEC);
     124        7551 :   for (j = 1; j < ly; j++) gel(z,j) = RgV_zc_mul_i(x, gel(y,j), l);
     125        7551 :   return z;
     126             : }
     127             : 
     128             : /* scalar product x.x */
     129             : GEN
     130        1638 : RgV_dotsquare(GEN x)
     131             : {
     132        1638 :   long i, lx = lg(x);
     133        1638 :   pari_sp av = avma;
     134             :   GEN z;
     135        1638 :   if (lx == 1) return gen_0;
     136        1638 :   z = gsqr(gel(x,1));
     137        6496 :   for (i=2; i<lx; i++)
     138             :   {
     139        4858 :     z = gadd(z, gsqr(gel(x,i)));
     140        4858 :     if (gc_needed(av,3))
     141             :     {
     142           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgV_dotsquare, i = %ld",i);
     143           0 :       z = gerepileupto(av, z);
     144             :     }
     145             :   }
     146        1638 :   return gerepileupto(av,z);
     147             : }
     148             : 
     149             : /* scalar product x.y, lx = lg(x) = lg(y) */
     150             : static GEN
     151     1175199 : RgV_dotproduct_i(GEN x, GEN y, long lx)
     152             : {
     153     1175199 :   pari_sp av = avma;
     154             :   long i;
     155             :   GEN z;
     156     1175199 :   if (lx == 1) return gen_0;
     157     1174233 :   z = gmul(gel(x,1),gel(y,1));
     158    41298661 :   for (i=2; i<lx; i++)
     159             :   {
     160    40124428 :     z = gadd(z, gmul(gel(x,i), gel(y,i)));
     161    40124428 :     if (gc_needed(av,3))
     162             :     {
     163           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgV_dotproduct, i = %ld",i);
     164           0 :       z = gerepileupto(av, z);
     165             :     }
     166             :   }
     167     1174233 :   return gerepileupto(av,z);
     168             : }
     169             : GEN
     170      150594 : RgV_dotproduct(GEN x,GEN y)
     171             : {
     172      150594 :   if (x == y) return RgV_dotsquare(x);
     173      150594 :   return RgV_dotproduct_i(x, y, lg(x));
     174             : }
     175             : /* v[1] + ... + v[lg(v)-1] */
     176             : GEN
     177      573546 : RgV_sum(GEN v)
     178             : {
     179             :   GEN p;
     180      573546 :   long i, l = lg(v);
     181      573546 :   if (l == 1) return gen_0;
     182      573546 :   p = gel(v,1); for (i=2; i<l; i++) p = gadd(p, gel(v,i));
     183      573546 :   return p;
     184             : }
     185             : /* v[1] + ... + v[n]. Assume lg(v) > n. */
     186             : GEN
     187         644 : RgV_sumpart(GEN v, long n)
     188             : {
     189             :   GEN p;
     190             :   long i;
     191         644 :   if (!n) return gen_0;
     192         644 :   p = gel(v,1); for (i=2; i<=n; i++) p = gadd(p, gel(v,i));
     193         644 :   return p;
     194             : }
     195             : /* v[m] + ... + v[n]. Assume lg(v) > n, m > 0. */
     196             : GEN
     197           0 : RgV_sumpart2(GEN v, long m, long n)
     198             : {
     199             :   GEN p;
     200             :   long i;
     201           0 :   if (n < m) return gen_0;
     202           0 :   p = gel(v,m); for (i=m+1; i<=n; i++) p = gadd(p, gel(v,i));
     203           0 :   return p;
     204             : }
     205             : GEN
     206         362 : RgM_sumcol(GEN A)
     207             : {
     208         362 :   long i,j,m,l = lg(A);
     209             :   GEN v;
     210             : 
     211         362 :   if (l == 1) return cgetg(1,t_MAT);
     212         362 :   if (l == 2) return gcopy(gel(A,1));
     213         208 :   m = lgcols(A);
     214         208 :   v = cgetg(m, t_COL);
     215         680 :   for (i = 1; i < m; i++)
     216             :   {
     217         472 :     pari_sp av = avma;
     218         472 :     GEN s = gcoeff(A,i,1);
     219         472 :     for (j = 2; j < l; j++) s = gadd(s, gcoeff(A,i,j));
     220         472 :     gel(v, i) = gerepileupto(av, s);
     221             :   }
     222         208 :   return v;
     223             : }
     224             : 
     225             : static GEN
     226      745262 : _gmul(void *data, GEN x, GEN y)
     227      745262 : { (void)data; return gmul(x,y); }
     228             : 
     229             : GEN
     230       42950 : RgV_prod(GEN x)
     231             : {
     232       42950 :   return gen_product(x, NULL, _gmul);
     233             : }
     234             : 
     235             : /*                    ADDITION SCALAR + MATRIX                     */
     236             : /* x square matrix, y scalar; create the square matrix x + y*Id */
     237             : GEN
     238        5669 : RgM_Rg_add(GEN x, GEN y)
     239             : {
     240        5669 :   long l = lg(x), i, j;
     241        5669 :   GEN z = cgetg(l,t_MAT);
     242             : 
     243        5669 :   if (l==1) return z;
     244        5669 :   if (l != lgcols(x)) pari_err_OP( "+", x, y);
     245        5669 :   z = cgetg(l,t_MAT);
     246       42298 :   for (i=1; i<l; i++)
     247             :   {
     248       36629 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     249       36629 :     gel(z,i) = zi;
     250     1892136 :     for (j=1; j<l; j++)
     251     1855507 :       gel(zi,j) = i==j? gadd(y,gel(xi,j)): gcopy(gel(xi,j));
     252             :   }
     253        5669 :   return z;
     254             : }
     255             : GEN
     256        5899 : RgM_Rg_sub(GEN x, GEN y)
     257             : {
     258        5899 :   long l = lg(x), i, j;
     259        5899 :   GEN z = cgetg(l,t_MAT);
     260             : 
     261        5899 :   if (l==1) return z;
     262        5899 :   if (l != lgcols(x)) pari_err_OP( "-", x, y);
     263        5899 :   z = cgetg(l,t_MAT);
     264       21975 :   for (i=1; i<l; i++)
     265             :   {
     266       16076 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     267       16076 :     gel(z,i) = zi;
     268       71844 :     for (j=1; j<l; j++)
     269       55768 :       gel(zi,j) = i==j? gsub(gel(xi,j), y): gcopy(gel(xi,j));
     270             :   }
     271        5899 :   return z;
     272             : }
     273             : GEN
     274         497 : RgM_Rg_add_shallow(GEN x, GEN y)
     275             : {
     276         497 :   long l = lg(x), i, j;
     277         497 :   GEN z = cgetg(l,t_MAT);
     278             : 
     279         497 :   if (l==1) return z;
     280         497 :   if (l != lgcols(x)) pari_err_OP( "+", x, y);
     281        1729 :   for (i=1; i<l; i++)
     282             :   {
     283        1232 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     284        1232 :     gel(z,i) = zi;
     285        1232 :     for (j=1; j<l; j++) gel(zi,j) = gel(xi,j);
     286        1232 :     gel(zi,i) = gadd(gel(zi,i), y);
     287             :   }
     288         497 :   return z;
     289             : }
     290             : GEN
     291       51063 : RgM_Rg_sub_shallow(GEN x, GEN y)
     292             : {
     293       51063 :   long l = lg(x), i, j;
     294       51063 :   GEN z = cgetg(l,t_MAT);
     295             : 
     296       51063 :   if (l==1) return z;
     297       51063 :   if (l != lgcols(x)) pari_err_OP( "-", x, y);
     298      599232 :   for (i=1; i<l; i++)
     299             :   {
     300      548169 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     301      548169 :     gel(z,i) = zi;
     302      548169 :     for (j=1; j<l; j++) gel(zi,j) = gel(xi,j);
     303      548169 :     gel(zi,i) = gsub(gel(zi,i), y);
     304             :   }
     305       51063 :   return z;
     306             : }
     307             : 
     308             : GEN
     309     3309794 : RgC_Rg_add(GEN x, GEN y)
     310             : {
     311     3309794 :   long k, lx = lg(x);
     312     3309794 :   GEN z = cgetg(lx, t_COL);
     313     3309794 :   if (lx == 1)
     314             :   {
     315           7 :     if (isintzero(y)) return z;
     316           0 :     pari_err_TYPE2("+",x,y);
     317             :   }
     318     3309787 :   gel(z,1) = gadd(y,gel(x,1));
     319     3309787 :   for (k = 2; k < lx; k++) gel(z,k) = gcopy(gel(x,k));
     320     3309787 :   return z;
     321             : }
     322             : GEN
     323       21364 : RgC_Rg_sub(GEN x, GEN y)
     324             : {
     325       21364 :   long k, lx = lg(x);
     326       21364 :   GEN z = cgetg(lx, t_COL);
     327       21364 :   if (lx == 1)
     328             :   {
     329           0 :     if (isintzero(y)) return z;
     330           0 :     pari_err_TYPE2("-",x,y);
     331             :   }
     332       21364 :   gel(z,1) = gsub(gel(x,1), y);
     333       21364 :   for (k = 2; k < lx; k++) gel(z,k) = gcopy(gel(x,k));
     334       21364 :   return z;
     335             : }
     336             : /* a - x */
     337             : GEN
     338      101873 : Rg_RgC_sub(GEN a, GEN x)
     339             : {
     340      101873 :   long k, lx = lg(x);
     341      101873 :   GEN z = cgetg(lx,t_COL);
     342      101873 :   if (lx == 1)
     343             :   {
     344           0 :     if (isintzero(a)) return z;
     345           0 :     pari_err_TYPE2("-",a,x);
     346             :   }
     347      101873 :   gel(z,1) = gsub(a, gel(x,1));
     348      101873 :   for (k = 2; k < lx; k++) gel(z,k) = gneg(gel(x,k));
     349      101873 :   return z;
     350             : }
     351             : 
     352             : 
     353             : static GEN
     354    13969867 : RgC_add_i(GEN x, GEN y, long lx)
     355             : {
     356    13969867 :   GEN A = cgetg(lx, t_COL);
     357             :   long i;
     358    13969867 :   for (i=1; i<lx; i++) gel(A,i) = gadd(gel(x,i), gel(y,i));
     359    13969867 :   return A;
     360             : }
     361             : GEN
     362    10764658 : RgC_add(GEN x, GEN y) { return RgC_add_i(x, y, lg(x)); }
     363             : GEN
     364      623164 : RgV_add(GEN x, GEN y)
     365      623164 : { pari_APPLY_type(t_VEC, gadd(gel(x,i), gel(y,i))) }
     366             : 
     367             : static GEN
     368     3805124 : RgC_sub_i(GEN x, GEN y, long lx)
     369             : {
     370             :   long i;
     371     3805124 :   GEN A = cgetg(lx, t_COL);
     372     3805124 :   for (i=1; i<lx; i++) gel(A,i) = gsub(gel(x,i), gel(y,i));
     373     3805124 :   return A;
     374             : }
     375             : GEN
     376     3757777 : RgC_sub(GEN x, GEN y) { return RgC_sub_i(x, y, lg(x)); }
     377             : GEN
     378      282696 : RgV_sub(GEN x, GEN y)
     379      282696 : { pari_APPLY_type(t_VEC, gsub(gel(x,i), gel(y,i))) }
     380             : 
     381             : GEN
     382      675381 : RgM_add(GEN x, GEN y)
     383             : {
     384      675381 :   long lx = lg(x), l, j;
     385             :   GEN z;
     386      675381 :   if (lx == 1) return cgetg(1, t_MAT);
     387      675381 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     388      675381 :   for (j = 1; j < lx; j++) gel(z,j) = RgC_add_i(gel(x,j), gel(y,j), l);
     389      675381 :   return z;
     390             : }
     391             : GEN
     392       13441 : RgM_sub(GEN x, GEN y)
     393             : {
     394       13441 :   long lx = lg(x), l, j;
     395             :   GEN z;
     396       13441 :   if (lx == 1) return cgetg(1, t_MAT);
     397       13441 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     398       13441 :   for (j = 1; j < lx; j++) gel(z,j) = RgC_sub_i(gel(x,j), gel(y,j), l);
     399       13441 :   return z;
     400             : }
     401             : 
     402             : static GEN
     403     3108683 : RgC_neg_i(GEN x, long lx)
     404             : {
     405             :   long i;
     406     3108683 :   GEN y = cgetg(lx, t_COL);
     407     3108683 :   for (i=1; i<lx; i++) gel(y,i) = gneg(gel(x,i));
     408     3108683 :   return y;
     409             : }
     410             : GEN
     411      138534 : RgC_neg(GEN x) { return RgC_neg_i(x, lg(x)); }
     412             : GEN
     413       34300 : RgV_neg(GEN x)
     414       34300 : { pari_APPLY_type(t_VEC, gneg(gel(x,i))) }
     415             : GEN
     416      536375 : RgM_neg(GEN x)
     417             : {
     418      536375 :   long i, hx, lx = lg(x);
     419      536375 :   GEN y = cgetg(lx, t_MAT);
     420      536375 :   if (lx == 1) return y;
     421      536368 :   hx = lgcols(x);
     422      536368 :   for (i=1; i<lx; i++) gel(y,i) = RgC_neg_i(gel(x,i), hx);
     423      536368 :   return y;
     424             : }
     425             : 
     426             : GEN
     427      185321 : RgV_RgC_mul(GEN x, GEN y)
     428             : {
     429      185321 :   long lx = lg(x);
     430      185321 :   if (lx != lg(y)) pari_err_OP("operation 'RgV_RgC_mul'", x, y);
     431      185258 :   return RgV_dotproduct_i(x, y, lx);
     432             : }
     433             : GEN
     434        1687 : RgC_RgV_mul(GEN x, GEN y)
     435             : {
     436        1687 :   long i, ly = lg(y);
     437        1687 :   GEN z = cgetg(ly,t_MAT);
     438        1687 :   for (i=1; i<ly; i++) gel(z,i) = RgC_Rg_mul(x, gel(y,i));
     439        1687 :   return z;
     440             : }
     441             : GEN
     442           0 : RgC_RgM_mul(GEN x, GEN y)
     443             : {
     444           0 :   long i, ly = lg(y);
     445           0 :   GEN z = cgetg(ly,t_MAT);
     446           0 :   if (ly != 1 && lgcols(y) != 2) pari_err_OP("operation 'RgC_RgM_mul'",x,y);
     447           0 :   for (i=1; i<ly; i++) gel(z,i) = RgC_Rg_mul(x, gcoeff(y,1,i));
     448           0 :   return z;
     449             : }
     450             : GEN
     451           0 : RgM_RgV_mul(GEN x, GEN y)
     452             : {
     453           0 :   if (lg(x) != 2) pari_err_OP("operation 'RgM_RgV_mul'", x,y);
     454           0 :   return RgC_RgV_mul(gel(x,1), y);
     455             : }
     456             : 
     457             : /* x[i,]*y, l = lg(y) > 1 */
     458             : static GEN
     459    82873174 : RgMrow_RgC_mul_i(GEN x, GEN y, long i, long l)
     460             : {
     461    82873174 :   pari_sp av = avma;
     462    82873174 :   GEN t = gmul(gcoeff(x,i,1), gel(y,1)); /* l > 1 ! */
     463             :   long j;
     464    82873174 :   for (j=2; j<l; j++) t = gadd(t, gmul(gcoeff(x,i,j), gel(y,j)));
     465    82873174 :   return gerepileupto(av,t);
     466             : }
     467             : GEN
     468        4396 : RgMrow_RgC_mul(GEN x, GEN y, long i)
     469        4396 : { return RgMrow_RgC_mul_i(x, y, i, lg(x)); }
     470             : 
     471             : /* compatible t_MAT * t_COL, lx = lg(x) = lg(y) > 1, l = lgcols(x) */
     472             : static GEN
     473    14363409 : RgM_RgC_mul_i(GEN x, GEN y, long lx, long l)
     474             : {
     475    14363409 :   GEN z = cgetg(l,t_COL);
     476             :   long i;
     477    14363409 :   for (i=1; i<l; i++) gel(z,i) = RgMrow_RgC_mul_i(x,y,i,lx);
     478    14363409 :   return z;
     479             : }
     480             : 
     481             : GEN
     482    11481102 : RgM_RgC_mul(GEN x, GEN y)
     483             : {
     484    11481102 :   long lx = lg(x);
     485    11481102 :   GEN ffx = NULL, ffy = NULL;
     486    11481102 :   if (lx != lg(y)) pari_err_OP("operation 'RgM_RgC_mul'", x,y);
     487    11481102 :   if (lx == 1) return cgetg(1,t_COL);
     488    11481102 :   if (RgM_is_FFM(x, &ffx) && RgC_is_FFC(y, &ffy)) {
     489          77 :     if (!FF_samefield(ffx, ffy))
     490           0 :       pari_err_OP("*", ffx, ffy);
     491          77 :     return FFM_FFC_mul(x, y, ffx);
     492             :   }
     493    11481025 :   return RgM_RgC_mul_i(x, y, lx, lgcols(x));
     494             : }
     495             : 
     496             : GEN
     497       61617 : RgV_RgM_mul(GEN x, GEN y)
     498             : {
     499       61617 :   long i, lx, ly = lg(y);
     500             :   GEN z;
     501       61617 :   if (ly == 1) return cgetg(1,t_VEC);
     502       61610 :   lx = lg(x);
     503       61610 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgV_RgM_mul'", x,y);
     504       61603 :   z = cgetg(ly, t_VEC);
     505       61603 :   for (i=1; i<ly; i++) gel(z,i) = RgV_dotproduct_i(x, gel(y,i), lx);
     506       61603 :   return z;
     507             : }
     508             : 
     509             : static GEN
     510       56238 : RgM_mul_FpM(GEN x, GEN y, GEN p)
     511             : {
     512       56238 :   pari_sp av = avma;
     513             :   GEN r;
     514       56238 :   if (lgefint(p) == 3)
     515             :   {
     516       56166 :     ulong pp = uel(p, 2);
     517       56166 :     r = Flm_to_ZM_inplace(Flm_mul(RgM_to_Flm(x, pp),
     518             :                                   RgM_to_Flm(y, pp), pp));
     519             :   }
     520             :   else
     521          72 :     r = FpM_mul(RgM_to_FpM(x, p), RgM_to_FpM(y, p), p);
     522       56238 :   return gerepileupto(av, FpM_to_mod(r, p));
     523             : }
     524             : 
     525             : static GEN
     526       26019 : RgM_mul_FqM(GEN x, GEN y, GEN pol, GEN p)
     527             : {
     528       26019 :   pari_sp av = avma;
     529       26019 :   GEN b, T = RgX_to_FpX(pol, p);
     530       26019 :   if (signe(T) == 0) pari_err_OP("*", x, y);
     531       26019 :   b = FqM_mul(RgM_to_FqM(x, T, p), RgM_to_FqM(y, T, p), T, p);
     532       26019 :   return gerepileupto(av, FqM_to_mod(b, T, p));
     533             : }
     534             : 
     535             : static GEN
     536       14812 : RgM_liftred(GEN x, GEN T)
     537       14812 : { return RgXQM_red(liftpol_shallow(x), T); }
     538             : 
     539             : static GEN
     540        2765 : RgM_mul_ZXQM(GEN x, GEN y, GEN T)
     541             : {
     542        2765 :   pari_sp av = avma;
     543        2765 :   GEN b = ZXQM_mul(RgM_liftred(x,T), RgM_liftred(y, T), T);
     544        2765 :   return gerepilecopy(av, QXQM_to_mod_shallow(b,T));
     545             : }
     546             : 
     547             : static GEN
     548         133 : RgM_sqr_ZXQM(GEN x, GEN T)
     549             : {
     550         133 :   pari_sp av = avma;
     551         133 :   GEN b = ZXQM_sqr(RgM_liftred(x, T), T);
     552         133 :   return gerepilecopy(av, QXQM_to_mod_shallow(b,T));
     553             : }
     554             : 
     555             : static GEN
     556        4571 : RgM_mul_QXQM(GEN x, GEN y, GEN T)
     557             : {
     558        4571 :   pari_sp av = avma;
     559        4571 :   GEN b = QXQM_mul(RgM_liftred(x, T), RgM_liftred(y, T), T);
     560        4571 :   return gerepilecopy(av, QXQM_to_mod_shallow(b,T));
     561             : }
     562             : 
     563             : static GEN
     564           7 : RgM_sqr_QXQM(GEN x, GEN T)
     565             : {
     566           7 :   pari_sp av = avma;
     567           7 :   GEN b = QXQM_sqr(RgM_liftred(x, T), T);
     568           7 :   return gerepilecopy(av, QXQM_to_mod_shallow(b,T));
     569             : }
     570             : 
     571             : INLINE int
     572        4620 : RgX_is_monic_ZX(GEN pol)
     573        4620 : { return RgX_is_ZX(pol) && ZX_is_monic(pol); }
     574             : 
     575             : #define code(t1,t2) ((t1 << 6) | t2)
     576             : static GEN
     577     3716529 : RgM_mul_fast(GEN x, GEN y)
     578             : {
     579             :   GEN p, pol;
     580             :   long pa;
     581     3716529 :   long t = RgM_type2(x,y, &p,&pol,&pa);
     582     3716529 :   switch(t)
     583             :   {
     584     2367619 :     case t_INT:    return ZM_mul(x,y);
     585      143269 :     case t_FRAC:   return QM_mul(x,y);
     586        3920 :     case t_FFELT:  return FFM_mul(x, y, pol);
     587       56175 :     case t_INTMOD: return RgM_mul_FpM(x, y, p);
     588             :     case code(t_POLMOD, t_INT):
     589        2772 :                    return ZX_is_monic(pol)? RgM_mul_ZXQM(x, y, pol): NULL;
     590             :     case code(t_POLMOD, t_FRAC):
     591        4592 :                    return RgX_is_monic_ZX(pol)? RgM_mul_QXQM(x, y, pol): NULL;
     592             :     case code(t_POLMOD, t_INTMOD):
     593       26019 :                    return RgM_mul_FqM(x, y, pol, p);
     594     1112163 :     default:       return NULL;
     595             :   }
     596             : }
     597             : 
     598             : static GEN
     599        1106 : RgM_sqr_fast(GEN x)
     600             : {
     601             :   GEN p, pol;
     602             :   long pa;
     603        1106 :   long t = RgM_type(x, &p,&pol,&pa);
     604        1106 :   switch(t)
     605             :   {
     606         126 :     case t_INT:    return ZM_sqr(x);
     607         700 :     case t_FRAC:   return QM_mul(x, x);
     608          28 :     case t_FFELT:  return FFM_mul(x, x, pol);
     609          63 :     case t_INTMOD: return RgM_mul_FpM(x, x, p);
     610             :     case code(t_POLMOD, t_INT):
     611         140 :                    return ZX_is_monic(pol)? RgM_sqr_ZXQM(x, pol): NULL;
     612             :     case code(t_POLMOD, t_FRAC):
     613          28 :                    return RgX_is_monic_ZX(pol)? RgM_sqr_QXQM(x, pol): NULL;
     614             :     case code(t_POLMOD, t_INTMOD):
     615           0 :                    return RgM_mul_FqM(x, x, pol, p);
     616          21 :     default:       return NULL;
     617             :   }
     618             : }
     619             : 
     620             : #undef code
     621             : 
     622             : GEN
     623     3738376 : RgM_mul(GEN x, GEN y)
     624             : {
     625     3738376 :   long j, l, lx, ly = lg(y);
     626             :   GEN z;
     627     3738376 :   if (ly == 1) return cgetg(1,t_MAT);
     628     3716550 :   lx = lg(x);
     629     3716550 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgM_mul'", x,y);
     630     3716550 :   if (lx == 1) return zeromat(0,ly-1);
     631     3716529 :   z = RgM_mul_fast(x, y);
     632     3716529 :   if (z) return z;
     633     1112191 :   z = cgetg(ly, t_MAT);
     634     1112191 :   l = lgcols(x);
     635     1112191 :   for (j=1; j<ly; j++) gel(z,j) = RgM_RgC_mul_i(x, gel(y,j), lx, l);
     636     1112191 :   return z;
     637             : }
     638             : 
     639             : GEN
     640        1141 : RgM_sqr(GEN x)
     641             : {
     642        1141 :   long j, lx = lg(x);
     643             :   GEN z;
     644        1141 :   if (lx == 1) return cgetg(1, t_MAT);
     645        1106 :   if (lx != lgcols(x)) pari_err_OP("operation 'RgM_mul'", x,x);
     646        1106 :   z = RgM_sqr_fast(x);
     647        1106 :   if (z) return z;
     648          49 :   z = cgetg(lx, t_MAT);
     649          49 :   for (j=1; j<lx; j++) gel(z,j) = RgM_RgC_mul_i(x, gel(x,j), lx, lx);
     650          49 :   return z;
     651             : }
     652             : 
     653             : /* assume result is symmetric */
     654             : GEN
     655           0 : RgM_multosym(GEN x, GEN y)
     656             : {
     657           0 :   long j, lx, ly = lg(y);
     658             :   GEN M;
     659           0 :   if (ly == 1) return cgetg(1,t_MAT);
     660           0 :   lx = lg(x);
     661           0 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgM_multosym'", x,y);
     662           0 :   if (lx == 1) return cgetg(1,t_MAT);
     663           0 :   if (ly != lgcols(x)) pari_err_OP("operation 'RgM_multosym'", x,y);
     664           0 :   M = cgetg(ly, t_MAT);
     665           0 :   for (j=1; j<ly; j++)
     666             :   {
     667           0 :     GEN z = cgetg(ly,t_COL), yj = gel(y,j);
     668             :     long i;
     669           0 :     for (i=1; i<j; i++) gel(z,i) = gcoeff(M,j,i);
     670           0 :     for (i=j; i<ly; i++)gel(z,i) = RgMrow_RgC_mul_i(x,yj,i,lx);
     671           0 :     gel(M,j) = z;
     672             :   }
     673           0 :   return M;
     674             : }
     675             : /* x~ * y, assuming result is symmetric */
     676             : GEN
     677         447 : RgM_transmultosym(GEN x, GEN y)
     678             : {
     679         447 :   long i, j, l, ly = lg(y);
     680             :   GEN M;
     681         447 :   if (ly == 1) return cgetg(1,t_MAT);
     682         447 :   if (lg(x) != ly) pari_err_OP("operation 'RgM_transmultosym'", x,y);
     683         447 :   l = lgcols(y);
     684         447 :   if (lgcols(x) != l) pari_err_OP("operation 'RgM_transmultosym'", x,y);
     685         447 :   M = cgetg(ly, t_MAT);
     686        2019 :   for (i=1; i<ly; i++)
     687             :   {
     688        1572 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     689        1572 :     gel(M,i) = c;
     690        4418 :     for (j=1; j<i; j++)
     691        2846 :       gcoeff(M,i,j) = gel(c,j) = RgV_dotproduct_i(xi,gel(y,j),l);
     692        1572 :     gel(c,i) = RgV_dotproduct_i(xi,gel(y,i),l);
     693             :   }
     694         447 :   return M;
     695             : }
     696             : /* x~ * y */
     697             : GEN
     698           0 : RgM_transmul(GEN x, GEN y)
     699             : {
     700           0 :   long i, j, l, lx, ly = lg(y);
     701             :   GEN M;
     702           0 :   if (ly == 1) return cgetg(1,t_MAT);
     703           0 :   lx = lg(x);
     704           0 :   l = lgcols(y);
     705           0 :   if (lgcols(x) != l) pari_err_OP("operation 'RgM_transmul'", x,y);
     706           0 :   M = cgetg(ly, t_MAT);
     707           0 :   for (i=1; i<ly; i++)
     708             :   {
     709           0 :     GEN yi = gel(y,i), c = cgetg(lx,t_COL);
     710           0 :     gel(M,i) = c;
     711           0 :     for (j=1; j<lx; j++) gel(c,j) = RgV_dotproduct_i(yi,gel(x,j),l);
     712             :   }
     713           0 :   return M;
     714             : }
     715             : 
     716             : GEN
     717         119 : gram_matrix(GEN x)
     718             : {
     719         119 :   long i,j, l, lx = lg(x);
     720             :   GEN M;
     721         119 :   if (!is_matvec_t(typ(x))) pari_err_TYPE("gram",x);
     722         119 :   if (lx == 1) return cgetg(1,t_MAT);
     723         105 :   l = lgcols(x);
     724         105 :   M = cgetg(lx,t_MAT);
     725         294 :   for (i=1; i<lx; i++)
     726             :   {
     727         189 :     GEN xi = gel(x,i), c = cgetg(lx,t_COL);
     728         189 :     gel(M,i) = c;
     729         280 :     for (j=1; j<i; j++)
     730          91 :       gcoeff(M,i,j) = gel(c,j) = RgV_dotproduct_i(xi,gel(x,j),l);
     731         189 :     gel(c,i) = RgV_dotsquare(xi);
     732             :   }
     733         105 :   return M;
     734             : }
     735             : 
     736             : static GEN
     737        2464 : _RgM_add(void *E, GEN x, GEN y) { (void)E; return RgM_add(x, y); }
     738             : 
     739             : static GEN
     740           0 : _RgM_sub(void *E, GEN x, GEN y) { (void)E; return RgM_sub(x, y); }
     741             : 
     742             : static GEN
     743        4123 : _RgM_cmul(void *E, GEN P, long a, GEN x) { (void)E; return RgM_Rg_mul(x,gel(P,a+2)); }
     744             : 
     745             : static GEN
     746         161 : _RgM_sqr(void *E, GEN x) { (void) E; return RgM_sqr(x); }
     747             : 
     748             : static GEN
     749         392 : _RgM_mul(void *E, GEN x, GEN y) { (void) E; return RgM_mul(x, y); }
     750             : 
     751             : static GEN
     752        3332 : _RgM_one(void *E) { long *n = (long*) E; return matid(*n); }
     753             : 
     754             : static GEN
     755           0 : _RgM_zero(void *E) { long *n = (long*) E; return zeromat(*n,*n); }
     756             : 
     757             : static GEN
     758        2205 : _RgM_red(void *E, GEN x) { (void)E; return x; }
     759             : 
     760             : static struct bb_algebra RgM_algebra = { _RgM_red, _RgM_add, _RgM_sub,
     761             :        _RgM_mul, _RgM_sqr, _RgM_one, _RgM_zero };
     762             : 
     763             : /* generates the list of powers of x of degree 0,1,2,...,l*/
     764             : GEN
     765         154 : RgM_powers(GEN x, long l)
     766             : {
     767         154 :   long n = lg(x)-1;
     768         154 :   return gen_powers(x,l,1,(void *) &n, &_RgM_sqr, &_RgM_mul, &_RgM_one);
     769             : }
     770             : 
     771             : GEN
     772         462 : RgX_RgMV_eval(GEN Q, GEN x)
     773             : {
     774         462 :   long n = lg(x)>1 ? lg(gel(x,1))-1:0;
     775         462 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)&n,&RgM_algebra,&_RgM_cmul);
     776             : }
     777             : 
     778             : GEN
     779        1197 : RgX_RgM_eval(GEN Q, GEN x)
     780             : {
     781        1197 :   long n = lg(x)-1;
     782        1197 :   return gen_bkeval(Q,degpol(Q),x,1,(void*)&n,&RgM_algebra,&_RgM_cmul);
     783             : }
     784             : 
     785             : GEN
     786     1203611 : RgC_Rg_div(GEN x, GEN y)
     787     1203611 : { pari_APPLY_type(t_COL, gdiv(gel(x,i),y)) }
     788             : 
     789             : GEN
     790     5968057 : RgC_Rg_mul(GEN x, GEN y)
     791     5968057 : { pari_APPLY_type(t_COL, gmul(gel(x,i),y)) }
     792             : 
     793             : GEN
     794       13232 : RgV_Rg_mul(GEN x, GEN y)
     795       13232 : { pari_APPLY_type(t_VEC, gmul(gel(x,i),y)) }
     796             : 
     797             : GEN
     798      153655 : RgM_Rg_div(GEN X, GEN c) {
     799      153655 :   long i, j, h, l = lg(X);
     800      153655 :   GEN A = cgetg(l, t_MAT);
     801      153655 :   if (l == 1) return A;
     802      153606 :   h = lgcols(X);
     803      988083 :   for (j=1; j<l; j++)
     804             :   {
     805      834477 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     806      834477 :     for (i = 1; i < h; i++) gel(a,i) = gdiv(gel(x,i), c);
     807      834477 :     gel(A,j) = a;
     808             :   }
     809      153606 :   return A;
     810             : }
     811             : GEN
     812      160733 : RgM_Rg_mul(GEN X, GEN c) {
     813      160733 :   long i, j, h, l = lg(X);
     814      160733 :   GEN A = cgetg(l, t_MAT);
     815      160733 :   if (l == 1) return A;
     816      160572 :   h = lgcols(X);
     817      782766 :   for (j=1; j<l; j++)
     818             :   {
     819      622194 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     820      622194 :     for (i = 1; i < h; i++) gel(a,i) = gmul(gel(x,i), c);
     821      622194 :     gel(A,j) = a;
     822             :   }
     823      160572 :   return A;
     824             : }
     825             : 
     826             : /********************************************************************/
     827             : /*                                                                  */
     828             : /*                    SCALAR TO MATRIX/VECTOR                       */
     829             : /*                                                                  */
     830             : /********************************************************************/
     831             : /* fill the square nxn matrix equal to t*Id */
     832             : static void
     833     5383875 : fill_scalmat(GEN y, GEN t, long n)
     834             : {
     835             :   long i;
     836    20031134 :   for (i = 1; i <= n; i++)
     837             :   {
     838    14647193 :     gel(y,i) = zerocol(n);
     839    14647259 :     gcoeff(y,i,i) = t;
     840             :   }
     841     5383941 : }
     842             : 
     843             : GEN
     844      450141 : scalarmat(GEN x, long n) {
     845      450141 :   GEN y = cgetg(n+1, t_MAT);
     846      450141 :   if (!n) return y;
     847      450141 :   fill_scalmat(y, gcopy(x), n); return y;
     848             : }
     849             : GEN
     850     1642642 : scalarmat_shallow(GEN x, long n) {
     851     1642642 :   GEN y = cgetg(n+1, t_MAT);
     852     1642652 :   fill_scalmat(y, x, n); return y;
     853             : }
     854             : GEN
     855         154 : scalarmat_s(long x, long n) {
     856         154 :   GEN y = cgetg(n+1, t_MAT);
     857         154 :   if (!n) return y;
     858         154 :   fill_scalmat(y, stoi(x), n); return y;
     859             : }
     860             : GEN
     861     3290952 : matid(long n) {
     862             :   GEN y;
     863     3290952 :   if (n < 0) pari_err_DOMAIN("matid", "size", "<", gen_0, stoi(n));
     864     3290945 :   y = cgetg(n+1, t_MAT);
     865     3290945 :   fill_scalmat(y, gen_1, n); return y;
     866             : }
     867             : 
     868             : INLINE GEN
     869      438251 : scalarcol_i(GEN x, long n, long c)
     870             : {
     871             :   long i;
     872      438251 :   GEN y = cgetg(n+1,t_COL);
     873      438251 :   if (!n) return y;
     874      438251 :   gel(y,1) = c? gcopy(x): x;
     875      438251 :   for (i=2; i<=n; i++) gel(y,i) = gen_0;
     876      438251 :   return y;
     877             : }
     878             : 
     879             : GEN
     880      164418 : scalarcol(GEN x, long n) { return scalarcol_i(x,n,1); }
     881             : 
     882             : GEN
     883      273833 : scalarcol_shallow(GEN x, long n) { return scalarcol_i(x,n,0); }
     884             : 
     885             : int
     886       26237 : RgM_isscalar(GEN x, GEN s)
     887             : {
     888       26237 :   long i, j, lx = lg(x);
     889             : 
     890       26237 :   if (lx == 1) return 1;
     891       26237 :   if (lx != lgcols(x)) return 0;
     892       26237 :   if (!s) s = gcoeff(x,1,1);
     893             : 
     894       68504 :   for (j=1; j<lx; j++)
     895             :   {
     896       55134 :     GEN c = gel(x,j);
     897      131338 :     for (i=1; i<j; )
     898       32159 :       if (!gequal0(gel(c,i++))) return 0;
     899             :     /* i = j */
     900       44045 :       if (!gequal(gel(c,i++),s)) return 0;
     901      119955 :     for (   ; i<lx; )
     902       35421 :       if (!gequal0(gel(c,i++))) return 0;
     903             :   }
     904       13370 :   return 1;
     905             : }
     906             : 
     907             : int
     908       12411 : RgM_isidentity(GEN x)
     909             : {
     910       12411 :   long i,j, lx = lg(x);
     911             : 
     912       12411 :   if (lx == 1) return 1;
     913       12411 :   if (lx != lgcols(x)) return 0;
     914       17444 :   for (j=1; j<lx; j++)
     915             :   {
     916       16660 :     GEN c = gel(x,j);
     917       35042 :     for (i=1; i<j; )
     918        4809 :       if (!gequal0(gel(c,i++))) return 0;
     919             :     /* i = j */
     920       13573 :       if (!gequal1(gel(c,i++))) return 0;
     921       15659 :     for (   ; i<lx; )
     922        5593 :       if (!gequal0(gel(c,i++))) return 0;
     923             :   }
     924         784 :   return 1;
     925             : }
     926             : 
     927             : long
     928         308 : RgC_is_ei(GEN x)
     929             : {
     930         308 :   long i, j = 0, l = lg(x);
     931        1792 :   for (i = 1; i < l; i++)
     932             :   {
     933        1484 :     GEN c = gel(x,i);
     934        1484 :     if (gequal0(c)) continue;
     935         308 :     if (!gequal1(c) || j) return 0;
     936         308 :     j = i;
     937             :   }
     938         308 :   return j;
     939             : }
     940             : 
     941             : int
     942         336 : RgM_isdiagonal(GEN x)
     943             : {
     944         336 :   long i,j, lx = lg(x);
     945         336 :   if (lx == 1) return 1;
     946         336 :   if (lx != lgcols(x)) return 0;
     947             : 
     948        3220 :   for (j=1; j<lx; j++)
     949             :   {
     950        2891 :     GEN c = gel(x,j);
     951       18452 :     for (i=1; i<j; i++)
     952       15561 :       if (!gequal0(gel(c,i))) return 0;
     953       18452 :     for (i++; i<lx; i++)
     954       15568 :       if (!gequal0(gel(c,i))) return 0;
     955             :   }
     956         329 :   return 1;
     957             : }
     958             : int
     959         315 : isdiagonal(GEN x)
     960             : {
     961         315 :   return (typ(x)==t_MAT) && RgM_isdiagonal(x);
     962             : }
     963             : 
     964             : /* returns the first index i<=n such that x=v[i] if it exists, 0 otherwise */
     965             : long
     966       21917 : RgV_isin(GEN v, GEN x)
     967             : {
     968       21917 :   long i, l = lg(v);
     969      408681 :   for (i = 1; i < l; i++)
     970      408422 :     if (gequal(gel(v,i), x)) return i;
     971         259 :   return 0;
     972             : }
     973             : 
     974             : GEN
     975       15932 : RgM_det_triangular(GEN mat)
     976             : {
     977       15932 :   long i,l = lg(mat);
     978             :   pari_sp av;
     979             :   GEN s;
     980             : 
     981       15932 :   if (l<3) return l<2? gen_1: gcopy(gcoeff(mat,1,1));
     982       14882 :   av = avma; s = gcoeff(mat,1,1);
     983       14882 :   for (i=2; i<l; i++) s = gmul(s,gcoeff(mat,i,i));
     984       14882 :   return av==avma? gcopy(s): gerepileupto(av,s);
     985             : }
     986             : 
     987             : GEN
     988        4340 : RgV_kill0(GEN v)
     989             : {
     990             :   long i, l;
     991        4340 :   GEN w = cgetg_copy(v, &l);
     992     1879115 :   for (i = 1; i < l; i++)
     993             :   {
     994     1874775 :     GEN a = gel(v,i);
     995     1874775 :     gel(w,i) = gequal0(a) ? NULL: a;
     996             :   }
     997        4340 :   return w;
     998             : }

Generated by: LCOV version 1.13