Line data Source code
1 : /* Copyright (C) 2011 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; either version 2 of the License, or (at your option) any later
8 : version. It is distributed in the hope that it will be useful, but WITHOUT
9 : ANY WARRANTY WHATSOEVER.
10 :
11 : Check the License for details. You should have received a copy of it, along
12 : with the package; see the file 'COPYING'. If not, write to the Free Software
13 : Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
14 :
15 : #include "pari.h"
16 : #include "paripriv.h"
17 :
18 : static int
19 11762842 : cmp_G(void *E, GEN x, GEN y) { (void)E; return cmp_universal(x,y); }
20 :
21 : /* a ZG is either a t_INT or a t_VEC of pairs [g,e] representing
22 : * \sum e_i [g_i], e_i in Z, g_i in G. */
23 : GEN
24 2168040 : ZG_normalize(GEN x)
25 : {
26 2168040 : if (typ(x) == t_INT) return x;
27 2168040 : return sort_factor(shallowcopy(x), NULL, &cmp_G);
28 : }
29 : GEN
30 1529556 : ZG_add(GEN x, GEN y)
31 : {
32 1529556 : if (typ(x) == t_INT)
33 : {
34 869330 : if (!signe(x)) return y;
35 0 : if (typ(y) == t_INT)
36 : {
37 0 : if (!signe(y)) return x;
38 0 : return addii(x,y);
39 : }
40 0 : x = to_famat_shallow(gen_1,x);
41 : }
42 660226 : else if (typ(y) == t_INT)
43 : {
44 0 : if (!signe(y)) return x;
45 0 : y = to_famat_shallow(gen_1,y);
46 : }
47 660226 : x = merge_factor(x, y, NULL, &cmp_G);
48 660226 : if (lg(gel(x,1)) == 1) return gen_0;
49 599529 : return x;
50 : }
51 : GEN
52 630 : ZG_neg(GEN x)
53 : {
54 630 : if (typ(x) == t_INT) return negi(x);
55 630 : return mkmat2(gel(x,1),ZC_neg(gel(x,2)));
56 : }
57 : GEN
58 0 : ZG_sub(GEN x, GEN y) { return ZG_add(x, ZG_neg(y)); }
59 :
60 : /* x * c.[1], x in Z[G] */
61 : GEN
62 0 : ZG_Z_mul(GEN x, GEN c)
63 : {
64 0 : if (is_pm1(c)) return signe(c) > 0? x: ZG_neg(x);
65 0 : if (typ(x) == t_INT) return mulii(x,c);
66 0 : return mkmat2(gel(x,1), ZC_Z_mul(gel(x,2), c));
67 : }
68 :
69 : GEN
70 0 : ZG_mul(GEN x, GEN y)
71 : {
72 : pari_sp av;
73 : GEN z, XG, XE;
74 : long i, l;
75 0 : if (typ(x) == t_INT) return ZG_Z_mul(y, x);
76 0 : if (typ(y) == t_INT) return ZG_Z_mul(x, y);
77 0 : av = avma;
78 0 : XG = gel(x,1); XE = gel(x,2); l = lg(XG);
79 0 : z = ZG_Z_mul(G_ZG_mul(gel(XG,1), y), gel(XE,1));
80 0 : for (i = 2; i < l; i++)
81 : {
82 0 : z = ZG_add(z, ZG_Z_mul(G_ZG_mul(gel(XG,i), y), gel(XE,i)));
83 0 : if (gc_needed(av,3))
84 : {
85 0 : if(DEBUGMEM>1) pari_warn(warnmem,"ZG_mul, i = %ld/%ld",i,l-1);
86 0 : z = gc_GEN(av, z);
87 : }
88 : }
89 0 : return z;
90 : }
91 : GEN
92 124831 : ZGCs_add(GEN x, GEN y)
93 : {
94 124831 : GEN xi = gel(x,1), xv = gel(x,2);
95 124831 : GEN yi = gel(y,1), yv = gel(y,2);
96 124831 : long i = 1, j = 1, k = 1, lx = lg(xi), ly = lg(yi), l = lx+ly-1;
97 124831 : GEN zi = cgetg(l, t_VECSMALL), zv = cgetg(l, t_VEC);
98 1082914 : while (i < lx && j < ly)
99 : {
100 958083 : if (xi[i] < yi[j]) { zi[k] = xi[i]; gel(zv,k) = gel(xv,i); i++; }
101 466193 : else if (xi[i] > yi[j]) { zi[k] = yi[j]; gel(zv,k) = gel(yv,j); j++; }
102 245056 : else { zi[k] = xi[i]; gel(zv,k) = ZG_add(gel(xv,i),gel(yv,j)); i++; j++; }
103 958083 : k++;
104 : }
105 398118 : for(; i < lx; i++,k++) { zi[k] = xi[i]; gel(zv,k) = gel(xv,i); }
106 232855 : for(; j < ly; j++,k++) { zi[k] = yi[j]; gel(zv,k) = gel(yv,j); }
107 124831 : setlg(zi,k);
108 124831 : setlg(zv,k); return mkvec2(zi, zv);
109 : }
110 : GEN
111 742378 : ZG_G_mul(GEN x, GEN y)
112 : {
113 : long i, l;
114 : GEN z, X;
115 742378 : if (typ(x) == t_INT) return signe(x)? to_famat_shallow(y, x): gen_0;
116 742378 : X = gel(x,1);
117 742378 : z = cgetg_copy(X, &l);
118 1758470 : for (i = 1; i < l; i++) gel(z,i) = gmul(gel(X,i), y);
119 742378 : return ZG_normalize( mkmat2(z, gel(x,2)) );
120 : }
121 : GEN
122 579957 : G_ZG_mul(GEN x, GEN y)
123 : {
124 : long i, l;
125 : GEN z, Y;
126 579957 : if (typ(y) == t_INT) return to_famat_shallow(x, y);
127 579957 : Y = gel(y,1);
128 579957 : z = cgetg_copy(Y, &l);
129 1159914 : for (i = 1; i < l; i++) gel(z,i) = gmul(x, gel(Y,i));
130 579957 : return ZG_normalize( mkmat2(z, gel(y,2)) );
131 : }
132 : void
133 160454 : ZGC_G_mul_inplace(GEN v, GEN x)
134 : {
135 160454 : long i, l = lg(v);
136 902832 : for (i = 1; i < l; i++) gel(v,i) = ZG_G_mul(gel(v,i), x);
137 160454 : }
138 : GEN
139 0 : ZGC_G_mul(GEN v, GEN x)
140 0 : { pari_APPLY_same(ZG_G_mul(gel(v,i), x)); }
141 : GEN
142 0 : G_ZGC_mul(GEN x, GEN v)
143 0 : { pari_APPLY_same(G_ZG_mul(gel(v,i), x)); }
144 : GEN
145 0 : ZGC_Z_mul(GEN v, GEN x)
146 0 : { pari_APPLY_same(ZG_Z_mul(gel(v,i), x)); }
|
