Branch data Line data Source code
1 : : /* Copyright (C) 2000-2010 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 : : /*******************************************************************/
15 : : /* */
16 : : /* CONSTRUCTORS */
17 : : /* */
18 : : /*******************************************************************/
19 : : #define retmkfrac(x,y)\
20 : : do { GEN _v = cgetg(3, t_FRAC);\
21 : : gel(_v,1) = (x);\
22 : : gel(_v,2) = (y); return _v; } while(0)
23 : : #define retmkintmod(x,y)\
24 : : do { GEN _v = cgetg(3, t_INTMOD);\
25 : : gel(_v,1) = (y);\
26 : : gel(_v,2) = (x); return _v; } while(0)
27 : : #define retmkcomplex(x,y)\
28 : : do { GEN _v = cgetg(3, t_COMPLEX);\
29 : : gel(_v,1) = (x);\
30 : : gel(_v,2) = (y); return _v; } while(0)
31 : : #define retmkpolmod(x,y)\
32 : : do { GEN _v = cgetg(3, t_POLMOD);\
33 : : gel(_v,1) = (y);\
34 : : gel(_v,2) = (x); return _v; } while(0)
35 : : #define retmkvec(x)\
36 : : do { GEN _v = cgetg(2, t_VEC);\
37 : : gel(_v,1) = (x); return _v; } while(0)
38 : : #define retmkvec2(x,y)\
39 : : do { GEN _v = cgetg(3, t_VEC);\
40 : : gel(_v,1) = (x);\
41 : : gel(_v,2) = (y); return _v; } while(0)
42 : : #define retmkvec3(x,y,z)\
43 : : do { GEN _v = cgetg(4, t_VEC);\
44 : : gel(_v,1) = (x);\
45 : : gel(_v,2) = (y);\
46 : : gel(_v,3) = (z); return _v; } while(0)
47 : : #define retmkqfi(x,y,z)\
48 : : do { GEN _v = cgetg(4, t_QFI);\
49 : : gel(_v,1) = (x);\
50 : : gel(_v,2) = (y);\
51 : : gel(_v,3) = (z); return _v; } while(0)
52 : : #define retmkqfr(x,y,z,d)\
53 : : do { GEN _v = cgetg(5, t_QFR);\
54 : : gel(_v,1) = (x);\
55 : : gel(_v,2) = (y);\
56 : : gel(_v,3) = (z);\
57 : : gel(_v,4) = (d); return _v; } while(0)
58 : : #define retmkquad(x,y,z)\
59 : : do { GEN _v = cgetg(4, t_QUAD);\
60 : : gel(_v,1) = (x);\
61 : : gel(_v,2) = (y);\
62 : : gel(_v,3) = (z); return _v; } while(0)
63 : : #define retmkvec4(x,y,z,t)\
64 : : do { GEN _v = cgetg(5, t_VEC);\
65 : : gel(_v,1) = (x);\
66 : : gel(_v,2) = (y);\
67 : : gel(_v,3) = (z);\
68 : : gel(_v,4) = (t); return _v; } while(0)
69 : : #define retmkvec5(x,y,z,t,u)\
70 : : do { GEN _v = cgetg(6, t_VEC);\
71 : : gel(_v,1) = (x);\
72 : : gel(_v,2) = (y);\
73 : : gel(_v,3) = (z);\
74 : : gel(_v,4) = (t);\
75 : : gel(_v,5) = (u); return _v; } while(0)
76 : : #define retmkcol(x)\
77 : : do { GEN _v = cgetg(2, t_COL);\
78 : : gel(_v,1) = (x); return _v; } while(0)
79 : : #define retmkcol2(x,y)\
80 : : do { GEN _v = cgetg(3, t_COL);\
81 : : gel(_v,1) = (x);\
82 : : gel(_v,2) = (y); return _v; } while(0)
83 : : #define retmkcol3(x,y,z)\
84 : : do { GEN _v = cgetg(4, t_COL);\
85 : : gel(_v,1) = (x);\
86 : : gel(_v,2) = (y);\
87 : : gel(_v,3) = (z); return _v; } while(0)
88 : : #define retmkcol4(x,y,z,t)\
89 : : do { GEN _v = cgetg(5, t_COL);\
90 : : gel(_v,1) = (x);\
91 : : gel(_v,2) = (y);\
92 : : gel(_v,3) = (z);\
93 : : gel(_v,4) = (t); return _v; } while(0)
94 : : #define retmkcol5(x,y,z,t,u)\
95 : : do { GEN _v = cgetg(6, t_COL);\
96 : : gel(_v,1) = (x);\
97 : : gel(_v,2) = (y);\
98 : : gel(_v,3) = (z);\
99 : : gel(_v,4) = (t);\
100 : : gel(_v,5) = (u); return _v; } while(0)
101 : : #define retmkmat(x)\
102 : : do { GEN _v = cgetg(2, t_MAT);\
103 : : gel(_v,1) = (x); return _v; } while(0)
104 : : #define retmkmat2(x,y)\
105 : : do { GEN _v = cgetg(3, t_MAT);\
106 : : gel(_v,1) = (x);\
107 : : gel(_v,2) = (y); return _v; } while(0)
108 : : #define retmkmat3(x,y,z)\
109 : : do { GEN _v = cgetg(4, t_MAT);\
110 : : gel(_v,1) = (x);\
111 : : gel(_v,2) = (y);\
112 : : gel(_v,3) = (z); return _v; } while(0)
113 : : #define retmkmat4(x,y,z,t)\
114 : : do { GEN _v = cgetg(5, t_MAT);\
115 : : gel(_v,1) = (x);\
116 : : gel(_v,2) = (y);\
117 : : gel(_v,3) = (z);\
118 : : gel(_v,4) = (t); return _v; } while(0)
119 : : #define retmkmat5(x,y,z,t,u)\
120 : : do { GEN _v = cgetg(6, t_MAT);\
121 : : gel(_v,1) = (x);\
122 : : gel(_v,2) = (y);\
123 : : gel(_v,3) = (z);\
124 : : gel(_v,4) = (t);\
125 : : gel(_v,5) = (u); return _v; } while(0)
126 : :
127 : : INLINE GEN
128 : 379595 : mkintmod(GEN x, GEN y) { retmkintmod(x,y); }
129 : : INLINE GEN
130 : 3577 : mkintmodu(ulong x, ulong y) {
131 : 3577 : GEN v = cgetg(3,t_INTMOD);
132 : 3577 : gel(v,1) = utoipos(y);
133 : 3577 : gel(v,2) = utoi(x); return v;
134 : : }
135 : : INLINE GEN
136 : 63309 : mkpolmod(GEN x, GEN y) { retmkpolmod(x,y); }
137 : : INLINE GEN
138 : 38768 : mkfrac(GEN x, GEN y) { retmkfrac(x,y); }
139 : : INLINE GEN
140 : 1369500 : mkfraccopy(GEN x, GEN y) { retmkfrac(icopy(x), icopy(y)); }
141 : : INLINE GEN
142 : 7 : mkrfrac(GEN x, GEN y) { GEN v = cgetg(3, t_RFRAC);
143 : 7 : gel(v,1) = x; gel(v,2) = y; return v; }
144 : : INLINE GEN
145 : 14 : mkrfraccopy(GEN x, GEN y) { GEN v = cgetg(3, t_RFRAC);
146 : 14 : gel(v,1) = gcopy(x); gel(v,2) = gcopy(y); return v; }
147 : : INLINE GEN
148 : 3143000 : mkcomplex(GEN x, GEN y) { retmkcomplex(x,y); }
149 : : INLINE GEN
150 : 166262 : gen_I(void) { return mkcomplex(gen_0, gen_1); }
151 : : INLINE GEN
152 : 45357 : cgetc(long l) { retmkcomplex(cgetr(l), cgetr(l)); }
153 : : INLINE GEN
154 : 63 : mkquad(GEN n, GEN x, GEN y) { GEN v = cgetg(4, t_QUAD);
155 : 63 : gel(v,1) = n; gel(v,2) = x; gel(v,3) = y; return v; }
156 : : /* vecsmall */
157 : : INLINE GEN
158 : 21983767 : mkvecsmall(long x) { GEN v = cgetg(2, t_VECSMALL); v[1] = x; return v; }
159 : : INLINE GEN
160 : 75988252 : mkvecsmall2(long x,long y) { GEN v = cgetg(3, t_VECSMALL);
161 : 75988252 : v[1]=x; v[2]=y; return v; }
162 : : INLINE GEN
163 : 28732105 : mkvecsmall3(long x,long y,long z) { GEN v = cgetg(4, t_VECSMALL);
164 : 28732105 : v[1]=x; v[2]=y; v[3]=z; return v; }
165 : : INLINE GEN
166 : 399171 : mkvecsmall4(long x,long y,long z,long t) { GEN v = cgetg(5, t_VECSMALL);
167 : 399171 : v[1]=x; v[2]=y; v[3]=z; v[4]=t; return v; }
168 : :
169 : : INLINE GEN
170 : 151228 : mkqfi(GEN x, GEN y, GEN z) { retmkqfi(x,y,z); }
171 : : /* vec */
172 : : INLINE GEN
173 : 1612342 : mkvec(GEN x) { retmkvec(x); }
174 : : INLINE GEN
175 : 13469154 : mkvec2(GEN x, GEN y) { retmkvec2(x,y); }
176 : : INLINE GEN
177 : 19791667 : mkvec3(GEN x, GEN y, GEN z) { retmkvec3(x,y,z); }
178 : : INLINE GEN
179 : 3492441 : mkvec4(GEN x, GEN y, GEN z, GEN t) { retmkvec4(x,y,z,t); }
180 : : INLINE GEN
181 : 11630603 : mkvec5(GEN x, GEN y, GEN z, GEN t, GEN u) { retmkvec5(x,y,z,t,u); }
182 : : INLINE GEN
183 : 7 : mkvecs(long x) { retmkvec(stoi(x)); }
184 : : INLINE GEN
185 : 4459 : mkvec2s(long x, long y) { retmkvec2(stoi(x),stoi(y)); }
186 : : INLINE GEN
187 : 456701 : mkvec3s(long x, long y, long z) { retmkvec3(stoi(x),stoi(y),stoi(z)); }
188 : : INLINE GEN
189 : 7 : mkvec4s(long x, long y, long z, long t) { retmkvec4(stoi(x),stoi(y),stoi(z),stoi(t)); }
190 : : INLINE GEN
191 : 32249 : mkveccopy(GEN x) { GEN v = cgetg(2, t_VEC); gel(v,1) = gcopy(x); return v; }
192 : : INLINE GEN
193 : 160698 : mkvec2copy(GEN x, GEN y) {
194 : 160698 : GEN v = cgetg(3,t_VEC); gel(v,1) = gcopy(x); gel(v,2) = gcopy(y); return v; }
195 : : /* col */
196 : : INLINE GEN
197 : 555440 : mkcol(GEN x) { retmkcol(x); }
198 : : INLINE GEN
199 : 11100742 : mkcol2(GEN x, GEN y) { retmkcol2(x,y); }
200 : : INLINE GEN
201 : 0 : mkcol3(GEN x, GEN y, GEN z) { retmkcol3(x,y,z); }
202 : : INLINE GEN
203 : 0 : mkcol4(GEN x, GEN y, GEN z, GEN t) { retmkcol4(x,y,z,t); }
204 : : INLINE GEN
205 : 0 : mkcol5(GEN x, GEN y, GEN z, GEN t, GEN u) { retmkcol5(x,y,z,t,u); }
206 : : INLINE GEN
207 : 0 : mkcols(long x) { retmkcol(stoi(x)); }
208 : : INLINE GEN
209 : 0 : mkcol2s(long x, long y) { retmkcol2(stoi(x),stoi(y)); }
210 : : INLINE GEN
211 : 0 : mkcol3s(long x, long y, long z) { retmkcol3(stoi(x),stoi(y),stoi(z)); }
212 : : INLINE GEN
213 : 0 : mkcol4s(long x, long y, long z, long t) { retmkcol4(stoi(x),stoi(y),stoi(z),stoi(t)); }
214 : : INLINE GEN
215 : 26752 : mkcolcopy(GEN x) { GEN v = cgetg(2, t_COL); gel(v,1) = gcopy(x); return v; }
216 : : /* mat */
217 : : INLINE GEN
218 : 189534 : mkmat(GEN x) { retmkmat(x); }
219 : : INLINE GEN
220 : 8318740 : mkmat2(GEN x, GEN y) { retmkmat2(x,y); }
221 : : INLINE GEN
222 : 21 : mkmat3(GEN x, GEN y, GEN z) { retmkmat3(x,y,z); }
223 : : INLINE GEN
224 : 0 : mkmat4(GEN x, GEN y, GEN z, GEN t) { retmkmat4(x,y,z,t); }
225 : : INLINE GEN
226 : 0 : mkmat5(GEN x, GEN y, GEN z, GEN t, GEN u) { retmkmat5(x,y,z,t,u); }
227 : : INLINE GEN
228 : 5145 : mkmatcopy(GEN x) { GEN v = cgetg(2, t_MAT); gel(v,1) = gcopy(x); return v; }
229 : : INLINE GEN
230 : 0 : mkerr(long x) { GEN v = cgetg(2, t_ERROR); v[1] = x; return v; }
231 : : INLINE GEN
232 : 392 : mkoo() { GEN v = cgetg(2, t_INFINITY); gel(v,1) = gen_1; return v; }
233 : : INLINE GEN
234 : 231 : mkmoo() { GEN v = cgetg(2, t_INFINITY); gel(v,1) = gen_m1; return v; }
235 : : INLINE long
236 : 686 : inf_get_sign(GEN x) { return signe(gel(x,1)); }
237 : : /* pol */
238 : : INLINE GEN
239 : 169123 : pol_x(long v) {
240 : 169123 : GEN p = cgetg(4, t_POL);
241 : 169123 : p[1] = evalsigne(1)|evalvarn(v);
242 : 169123 : gel(p,2) = gen_0;
243 : 169123 : gel(p,3) = gen_1; return p;
244 : : }
245 : : INLINE GEN
246 : 559818 : pol_1(long v) {
247 : 559818 : GEN p = cgetg(3, t_POL);
248 : 559818 : p[1] = evalsigne(1)|evalvarn(v);
249 : 559818 : gel(p,2) = gen_1; return p;
250 : : }
251 : : INLINE GEN
252 : 11941936 : pol_0(long v)
253 : : {
254 : 11941936 : GEN x = cgetg(2,t_POL);
255 : 11941936 : x[1] = evalvarn(v); return x;
256 : : }
257 : : #define retconst_vec(n,x)\
258 : : do { long _i, _n = (n);\
259 : : GEN _v = cgetg(n+1, t_VEC), _x = (x);\
260 : : for (_i = 1; _i <= _n; _i++) gel(_v,_i) = _x;\
261 : : return _v; } while(0)
262 : : INLINE GEN
263 [ + + ]: 33627438 : const_vec(long n, GEN x) { retconst_vec(n, x); }
264 : : #define retconst_col(n,x)\
265 : : do { long _i, _n = (n);\
266 : : GEN _v = cgetg(n+1, t_COL), _x = (x);\
267 : : for (_i = 1; _i <= _n; _i++) gel(_v,_i) = _x;\
268 : : return _v; } while(0)
269 : : INLINE GEN
270 [ + + ]: 35404 : const_col(long n, GEN x) { retconst_col(n, x); }
271 : : INLINE GEN
272 : 3633626 : const_vecsmall(long n, long c)
273 : : {
274 : : long i;
275 : 3633626 : GEN V = cgetg(n+1,t_VECSMALL);
276 [ + + ]: 16038397 : for(i=1;i<=n;i++) V[i] = c;
277 : 3633626 : return V;
278 : : }
279 : :
280 : : /*** ZERO ***/
281 : : /* O(p^e) */
282 : : INLINE GEN
283 : 6762 : zeropadic(GEN p, long e)
284 : : {
285 : 6762 : GEN y = cgetg(5,t_PADIC);
286 : 6762 : gel(y,4) = gen_0;
287 : 6762 : gel(y,3) = gen_1;
288 : 6762 : gel(y,2) = icopy(p);
289 : 6762 : y[1] = evalvalp(e) | _evalprecp(0);
290 : 6762 : return y;
291 : : }
292 : : INLINE GEN
293 : 280 : zeropadic_shallow(GEN p, long e)
294 : : {
295 : 280 : GEN y = cgetg(5,t_PADIC);
296 : 280 : gel(y,4) = gen_0;
297 : 280 : gel(y,3) = gen_1;
298 : 280 : gel(y,2) = p;
299 : 280 : y[1] = evalvalp(e) | _evalprecp(0);
300 : 280 : return y;
301 : : }
302 : : /* O(pol_x(v)^e) */
303 : : INLINE GEN
304 : 4550 : zeroser(long v, long e)
305 : : {
306 : 4550 : GEN x = cgetg(2, t_SER);
307 : 4550 : x[1] = evalvalp(e) | evalvarn(v); return x;
308 : : }
309 : : /* 0 * pol_x(v) */
310 : : INLINE GEN
311 : 4070560 : zeropol(long v) { return pol_0(v); }
312 : : /* vector(n) */
313 : : INLINE GEN
314 : 20145775 : zerocol(long n)
315 : : {
316 : 20145775 : GEN y = cgetg(n+1,t_COL);
317 [ + + ]: 147437694 : long i; for (i=1; i<=n; i++) gel(y,i) = gen_0;
318 : 20145775 : return y;
319 : : }
320 : : /* vectorv(n) */
321 : : INLINE GEN
322 : 5452750 : zerovec(long n)
323 : : {
324 : 5452750 : GEN y = cgetg(n+1,t_VEC);
325 [ + + ]: 50282992 : long i; for (i=1; i<=n; i++) gel(y,i) = gen_0;
326 : 5452750 : return y;
327 : : }
328 : : /* matrix(m, n) */
329 : : INLINE GEN
330 : 5192 : zeromat(long m, long n)
331 : : {
332 : 5192 : GEN y = cgetg(n+1,t_MAT);
333 : 5192 : GEN v = zerocol(m);
334 [ + + ]: 17518 : long i; for (i=1; i<=n; i++) gel(y,i) = v;
335 : 5192 : return y;
336 : : }
337 : : /* = zero_zx, sv is a evalvarn()*/
338 : : INLINE GEN
339 : 46359 : zero_Flx(long sv) { return pol0_Flx(sv); }
340 : : INLINE GEN
341 : 11929710 : zero_Flv(long n)
342 : : {
343 : 11929710 : GEN y = cgetg(n+1,t_VECSMALL);
344 [ + + ]: 420221310 : long i; for (i=1; i<=n; i++) y[i] = 0;
345 : 11929710 : return y;
346 : : }
347 : : /* matrix(m, n) */
348 : : INLINE GEN
349 : 140 : zero_Flm(long m, long n)
350 : : {
351 : 140 : GEN y = cgetg(n+1,t_MAT);
352 : 140 : GEN v = zero_Flv(m);
353 [ + + ]: 532 : long i; for (i=1; i<=n; i++) gel(y,i) = v;
354 : 140 : return y;
355 : : }
356 : : /* matrix(m, n) */
357 : : INLINE GEN
358 : 11375 : zero_Flm_copy(long m, long n)
359 : : {
360 : 11375 : GEN y = cgetg(n+1,t_MAT);
361 [ + + ]: 118474 : long i; for (i=1; i<=n; i++) gel(y,i) = zero_Flv(m);
362 : 11375 : return y;
363 : : }
364 : :
365 : : INLINE GEN
366 : 525238 : zero_F2v(long m)
367 : : {
368 : 525238 : long l = nbits2nlong(m);
369 : 525238 : GEN v = zero_Flv(l+1);
370 : 525238 : v[1] = m;
371 : 525238 : return v;
372 : : }
373 : :
374 : : INLINE GEN
375 : 0 : zero_F2m(long m, long n)
376 : : {
377 : : long i;
378 : 0 : GEN M = cgetg(n+1, t_MAT);
379 : 0 : GEN v = zero_F2v(m);
380 [ # # ]: 0 : for (i = 1; i <= n; i++)
381 : 0 : gel(M,i) = v;
382 : 0 : return M;
383 : : }
384 : :
385 : :
386 : : INLINE GEN
387 : 74706 : zero_F2m_copy(long m, long n)
388 : : {
389 : : long i;
390 : 74706 : GEN M = cgetg(n+1, t_MAT);
391 [ + + ]: 279588 : for (i = 1; i <= n; i++)
392 : 204882 : gel(M,i)= zero_F2v(m);
393 : 74706 : return M;
394 : : }
395 : :
396 : : /* matrix(m, n) */
397 : : INLINE GEN
398 : 2127281 : zeromatcopy(long m, long n)
399 : : {
400 : 2127281 : GEN y = cgetg(n+1,t_MAT);
401 [ + + ]: 9135834 : long i; for (i=1; i<=n; i++) gel(y,i) = zerocol(m);
402 : 2127281 : return y;
403 : : }
404 : :
405 : : /* i-th vector in the standard basis */
406 : : INLINE GEN
407 : 1199272 : col_ei(long n, long i) { GEN e = zerocol(n); gel(e,i) = gen_1; return e; }
408 : : INLINE GEN
409 : 295827 : vec_ei(long n, long i) { GEN e = zerovec(n); gel(e,i) = gen_1; return e; }
410 : : INLINE GEN
411 : 7 : F2v_ei(long n, long i) { GEN e = zero_F2v(n); F2v_set(e,i); return e; }
412 : : INLINE GEN
413 : 7066 : vecsmall_ei(long n, long i) { GEN e = zero_zv(n); e[i] = 1; return e; }
414 : : INLINE GEN
415 : 3682763 : Rg_col_ei(GEN x, long n, long i) { GEN e = zerocol(n); gel(e,i) = x; return e; }
416 : :
417 : : INLINE GEN
418 : 138309 : shallowcopy(GEN x)
419 [ + + ]: 138309 : { return typ(x) == t_MAT ? RgM_shallowcopy(x): leafcopy(x); }
420 : :
421 : : /* routines for naive growarrays */
422 : : INLINE GEN
423 : 539258 : vectrunc_init(long l)
424 : : {
425 : 539258 : GEN z = new_chunk(l);
426 : 539258 : z[0] = evaltyp(t_VEC) | _evallg(1); return z;
427 : : }
428 : : INLINE void
429 : 861625 : vectrunc_append(GEN x, GEN t)
430 : 861625 : { long l = lg(x); gel(x,l) = t; setlg(x, l+1); }
431 : : INLINE void
432 : 0 : vectrunc_append_batch(GEN x, GEN y)
433 : : {
434 : 0 : long i, l = lg(x), ly = lg(y);
435 : 0 : GEN z = x + l-1;
436 [ # # ]: 0 : for (i = 1; i < ly; i++) gel(z,i) = gel(y,i);
437 : 0 : setlg(x, l+ly-1);
438 : 0 : }
439 : : INLINE GEN
440 : 1374766 : vecsmalltrunc_init(long l)
441 : : {
442 : 1374766 : GEN z = new_chunk(l);
443 : 1374766 : z[0] = evaltyp(t_VECSMALL) | _evallg(1); return z;
444 : : }
445 : : INLINE void
446 : 2587044 : vecsmalltrunc_append(GEN x, long t)
447 : 2587044 : { long l = lg(x); x[l] = t; setlg(x, l+1); }
448 : :
449 : : /*******************************************************************/
450 : : /* */
451 : : /* VEC / COL / VECSMALL */
452 : : /* */
453 : : /*******************************************************************/
454 : : /* shallow*/
455 : : INLINE GEN
456 : 0 : vec_shorten(GEN v, long n)
457 : : {
458 : : long i;
459 : 0 : GEN V = cgetg(n+1,t_VEC);
460 [ # # ]: 0 : for(i=1;i<=n;i++) gel(V,i) = gel(v,i);
461 : 0 : return V;
462 : : }
463 : : /* shallow*/
464 : : INLINE GEN
465 : 7398 : vec_lengthen(GEN v, long n)
466 : : {
467 : : long i;
468 : 7398 : long l=lg(v);
469 : 7398 : GEN V = cgetg(n+1,t_VEC);
470 [ + + ]: 96513 : for(i=1;i<l;i++) gel(V,i) = gel(v,i);
471 : 7398 : return V;
472 : : }
473 : : /* shallow*/
474 : : INLINE GEN
475 : 54894 : vec_append(GEN V, GEN s)
476 : : {
477 : 54894 : long i, l2 = lg(V);
478 : 54894 : GEN res = cgetg(l2+1, typ(V));
479 [ + + ]: 90244 : for (i = 1; i < l2; ++i) gel(res, i) = gel(V,i);
480 : 54894 : gel(res,l2) = s; return res;
481 : : }
482 : : /* shallow*/
483 : : INLINE GEN
484 : 1680 : vec_setconst(GEN v, GEN x)
485 : : {
486 : 1680 : long i, l = lg(v);
487 [ + + ]: 6622 : for (i = 1; i < l; i++) gel(v,i) = x;
488 : 1680 : return v;
489 : : }
490 : : INLINE GEN
491 : 4200 : vecsmall_shorten(GEN v, long n)
492 : : {
493 : : long i;
494 : 4200 : GEN V = cgetg(n+1,t_VECSMALL);
495 [ + + ]: 19782 : for(i=1;i<=n;i++) V[i] = v[i];
496 : 4200 : return V;
497 : : }
498 : : INLINE GEN
499 : 476 : vecsmall_lengthen(GEN v, long n)
500 : : {
501 : 476 : long i, l = lg(v);
502 : 476 : GEN V = cgetg(n+1,t_VECSMALL);
503 [ + + ]: 43428 : for(i=1;i<l;i++) V[i] = v[i];
504 : 476 : return V;
505 : : }
506 : :
507 : : INLINE GEN
508 : 192778 : vec_to_vecsmall(GEN z)
509 : : {
510 : 192778 : long i, l = lg(z);
511 : 192778 : GEN x = cgetg(l, t_VECSMALL);
512 [ + + ]: 3150513 : for (i=1; i<l; i++) x[i] = itos(gel(z,i));
513 : 192778 : return x;
514 : : }
515 : : INLINE GEN
516 : 5452 : vecsmall_to_vec(GEN z)
517 : : {
518 : 5452 : long i, l = lg(z);
519 : 5452 : GEN x = cgetg(l,t_VEC);
520 [ + + ]: 17330 : for (i=1; i<l; i++) gel(x,i) = stoi(z[i]);
521 : 5452 : return x;
522 : : }
523 : : INLINE GEN
524 : 389892 : vecsmall_to_col(GEN z)
525 : : {
526 : 389892 : long i, l = lg(z);
527 : 389892 : GEN x = cgetg(l,t_COL);
528 [ + + ]: 2290742 : for (i=1; i<l; i++) gel(x,i) = stoi(z[i]);
529 : 389892 : return x;
530 : : }
531 : :
532 : : INLINE int
533 : 2586370 : vecsmall_lexcmp(GEN x, GEN y)
534 : : {
535 : : long lx,ly,l,i;
536 : 2586370 : lx = lg(x);
537 : 2586370 : ly = lg(y); l = minss(lx,ly);
538 [ + + ]: 14200241 : for (i=1; i<l; i++)
539 [ + + ][ + + ]: 13516530 : if (x[i] != y[i]) return x[i]<y[i]? -1: 1;
540 [ + - ]: 683711 : if (lx == ly) return 0;
541 [ # # ]: 2586370 : return (lx < ly)? -1 : 1;
542 : : }
543 : :
544 : : INLINE int
545 : 35046052 : vecsmall_prefixcmp(GEN x, GEN y)
546 : : {
547 : 35046052 : long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
548 [ + + ]: 111015089 : for (i=1; i<l; i++)
549 [ + + ][ + + ]: 100392822 : if (x[i] != y[i]) return x[i]<y[i]? -1: 1;
550 : 35046052 : return 0;
551 : : }
552 : :
553 : : /*Can be used on t_VEC, but coeffs not gcopy-ed*/
554 : : INLINE GEN
555 : 756 : vecsmall_prepend(GEN V, long s)
556 : : {
557 : 756 : long i, l2 = lg(V);
558 : 756 : GEN res = cgetg(l2+1, typ(V));
559 : 756 : res[1] = s;
560 [ + + ]: 1757 : for (i = 2; i <= l2; ++i) res[i] = V[i - 1];
561 : 756 : return res;
562 : : }
563 : :
564 : : INLINE GEN
565 : 352906 : vecsmall_append(GEN V, long s)
566 : : {
567 : 352906 : long i, l2 = lg(V);
568 : 352906 : GEN res = cgetg(l2+1, t_VECSMALL);
569 [ + + ]: 885571 : for (i = 1; i < l2; ++i) res[i] = V[i];
570 : 352906 : res[l2] = s; return res;
571 : : }
572 : :
573 : : INLINE GEN
574 : 156738 : vecsmall_concat(GEN u, GEN v)
575 : : {
576 : 156738 : long i, l1 = lg(u)-1, l2 = lg(v)-1;
577 : 156738 : GEN res = cgetg(l1+l2+1, t_VECSMALL);
578 [ + + ]: 985018 : for (i = 1; i <= l1; ++i) res[i] = u[i];
579 [ + + ]: 493299 : for (i = 1; i <= l2; ++i) res[i+l1] = v[i];
580 : 156738 : return res;
581 : : }
582 : :
583 : : /* return the number of indices where u and v are equal */
584 : : INLINE long
585 : 0 : vecsmall_coincidence(GEN u, GEN v)
586 : : {
587 : 0 : long i, s = 0, l = minss(lg(u),lg(v));
588 [ # # ]: 0 : for(i=1; i<l; i++)
589 [ # # ]: 0 : if(u[i] == v[i]) s++;
590 : 0 : return s;
591 : : }
592 : :
593 : : /* returns the first index i<=n such that x=v[i] if it exists, 0 otherwise */
594 : : INLINE long
595 : 0 : vecsmall_isin(GEN v, long x)
596 : : {
597 : 0 : long i, l = lg(v);
598 [ # # ]: 0 : for (i = 1; i < l; i++)
599 [ # # ]: 0 : if (v[i] == x) return i;
600 : 0 : return 0;
601 : : }
602 : :
603 : : INLINE long
604 : 84 : vecsmall_pack(GEN V, long base, long mod)
605 : : {
606 : 84 : long i, s = 0;
607 [ + + ]: 273 : for(i=1; i<lg(V); i++) s = (base*s + V[i]) % mod;
608 : 84 : return s;
609 : : }
610 : :
611 : : INLINE long
612 : 14 : vecsmall_indexmax(GEN x)
613 : : {
614 : 14 : long i, i0 = 1, t = x[1], lx = lg(x);
615 [ + + ]: 56 : for (i=2; i<lx; i++)
616 [ + + ]: 42 : if (x[i] > t) t = x[i0=i];
617 : 14 : return i0;
618 : : }
619 : :
620 : : INLINE long
621 : 1925 : vecsmall_max(GEN x)
622 : : {
623 : 1925 : long i, t = x[1], lx = lg(x);
624 [ + + ]: 6923 : for (i=2; i<lx; i++)
625 [ + + ]: 4998 : if (x[i] > t) t = x[i];
626 : 1925 : return t;
627 : : }
628 : :
629 : : INLINE long
630 : 14 : vecsmall_indexmin(GEN x)
631 : : {
632 : 14 : long i, i0 = 1, t = x[1], lx =lg(x);
633 [ + + ]: 56 : for (i=2; i<lx; i++)
634 [ - + ]: 42 : if (x[i] < t) t = x[i0=i];
635 : 14 : return i0;
636 : : }
637 : :
638 : : INLINE long
639 : 0 : vecsmall_min(GEN x)
640 : : {
641 : 0 : long i, t = x[1], lx =lg(x);
642 [ # # ]: 0 : for (i=2; i<lx; i++)
643 [ # # ]: 0 : if (x[i] < t) t = x[i];
644 : 0 : return t;
645 : : }
646 : :
647 : : INLINE int
648 : 2400919 : ZV_isscalar(GEN x)
649 : : {
650 : 2400919 : long l = lg(x);
651 [ + + ]: 8480629 : while (--l > 1)
652 [ + + ]: 8133328 : if (signe(gel(x, l))) return 0;
653 : 2400919 : return 1;
654 : : }
655 : : INLINE int
656 : 6288759 : QV_isscalar(GEN x)
657 : : {
658 : 6288759 : long lx = lg(x),i;
659 [ + + ]: 8696182 : for (i=2; i<lx; i++)
660 [ + + ]: 8401579 : if (!isintzero(gel(x, i))) return 0;
661 : 6288759 : return 1;
662 : : }
663 : : INLINE int
664 : 6251 : RgV_isscalar(GEN x)
665 : : {
666 : 6251 : long lx = lg(x),i;
667 [ + + ]: 14952 : for (i=2; i<lx; i++)
668 [ + + ]: 10178 : if (!gequal0(gel(x, i))) return 0;
669 : 6251 : return 1;
670 : : }
671 : : INLINE int
672 : 0 : RgX_isscalar(GEN x)
673 : : {
674 : : long i;
675 [ # # ]: 0 : for (i=lg(x)-1; i>2; i--)
676 [ # # ]: 0 : if (!gequal0(gel(x, i))) return 0;
677 : 0 : return 1;
678 : : }
679 : : INLINE long
680 [ + + ][ + + ]: 790225 : RgX_equal_var(GEN x, GEN y) { return varn(x) == varn(y) && RgX_equal(x,y); }
681 : :
682 : : INLINE int
683 : 651 : RgX_is_rational(GEN x)
684 : : {
685 : : long i;
686 [ + + ]: 9198 : for (i = lg(x)-1; i > 1; i--)
687 [ + + ]: 8813 : if (!is_rational_t(typ(gel(x,i)))) return 0;
688 : 651 : return 1;
689 : : }
690 : : INLINE int
691 : 54732140 : RgX_is_ZX(GEN x)
692 : : {
693 : : long i;
694 [ + + ]: 235226329 : for (i = lg(x)-1; i > 1; i--)
695 [ + + ]: 185611893 : if (typ(gel(x,i)) != t_INT) return 0;
696 : 54732140 : return 1;
697 : : }
698 : : INLINE int
699 : 5271 : RgX_is_QX(GEN x)
700 : : {
701 : 5271 : long k = lg(x)-1;
702 [ + + ]: 23897 : for ( ; k>1; k--)
703 [ + + ]: 18780 : if (!is_rational_t(typ(gel(x,k)))) return 0;
704 : 5271 : return 1;
705 : : }
706 : : INLINE int
707 : 14706211 : RgX_is_monomial(GEN x)
708 : : {
709 : : long i;
710 [ + + ]: 14706211 : if (!signe(x)) return 0;
711 [ + + ]: 23597012 : for (i=lg(x)-2; i>1; i--)
712 [ + + ]: 16299263 : if (!isexactzero(gel(x,i))) return 0;
713 : 14706211 : return 1;
714 : : }
715 : : INLINE int
716 : 1272850 : RgV_is_ZV(GEN x)
717 : : {
718 : : long i;
719 [ + + ]: 4674909 : for (i = lg(x)-1; i > 0; i--)
720 [ + + ]: 3402206 : if (typ(gel(x,i)) != t_INT) return 0;
721 : 1272850 : return 1;
722 : : }
723 : : INLINE int
724 : 0 : RgV_is_QV(GEN x)
725 : : {
726 : : long i;
727 [ # # ]: 0 : for (i = lg(x)-1; i > 0; i--)
728 [ # # ]: 0 : if (!is_rational_t(typ(gel(x,i)))) return 0;
729 : 0 : return 1;
730 : : }
731 : :
732 : : /********************************************************************/
733 : : /** **/
734 : : /** Dynamic arrays implementation **/
735 : : /** **/
736 : : /********************************************************************/
737 : : INLINE void **
738 : 202020163 : pari_stack_base(pari_stack *s) { return s->data; }
739 : :
740 : : INLINE void
741 : 21914 : pari_stack_init(pari_stack *s, size_t size, void **data)
742 : : {
743 : 21914 : s->data = data;
744 : 21914 : *data = NULL;
745 : 21914 : s->n = 0;
746 : 21914 : s->alloc = 0;
747 : 21914 : s->size = size;
748 : 21914 : }
749 : :
750 : : INLINE void
751 : 201997093 : pari_stack_alloc(pari_stack *s, long nb)
752 : : {
753 : 201997093 : void **sdat = pari_stack_base(s);
754 [ + + ]: 202049168 : if (s->n+nb <= s->alloc) return;
755 [ + + ]: 52075 : if (!s->alloc)
756 : 17500 : s->alloc = nb;
757 : : else
758 : : {
759 [ + + ]: 69255 : while (s->n+nb > s->alloc) s->alloc <<= 1;
760 : : }
761 : 52075 : *sdat = pari_realloc(*sdat,s->alloc*s->size);
762 : : }
763 : :
764 : : INLINE long
765 : 175773043 : pari_stack_new(pari_stack *s) { pari_stack_alloc(s, 1); return s->n++; }
766 : :
767 : : INLINE void
768 : 16005 : pari_stack_delete(pari_stack *s)
769 : : {
770 : 16005 : void **sdat = pari_stack_base(s);
771 [ + + ]: 16005 : if (*sdat) free(*sdat);
772 : 16005 : }
773 : :
774 : : INLINE void
775 : 7058 : pari_stack_pushp(pari_stack *s, void *u)
776 : : {
777 : 7058 : long n = pari_stack_new(s);
778 : 7058 : void **sdat =(void**) *pari_stack_base(s);
779 : 7058 : sdat[n] = u;
780 : 7058 : }
781 : :
782 : : /*******************************************************************/
783 : : /* */
784 : : /* EXTRACT */
785 : : /* */
786 : : /*******************************************************************/
787 : : INLINE GEN
788 : 1621247 : vecslice(GEN A, long y1, long y2)
789 : : {
790 : 1621247 : long i,lB = y2 - y1 + 2;
791 : 1621247 : GEN B = cgetg(lB, typ(A));
792 [ + + ]: 8464518 : for (i=1; i<lB; i++) B[i] = A[y1-1+i];
793 : 1621247 : return B;
794 : : }
795 : : INLINE GEN
796 : 85391 : vecslicepermute(GEN A, GEN p, long y1, long y2)
797 : : {
798 : 85391 : long i,lB = y2 - y1 + 2;
799 : 85391 : GEN B = cgetg(lB, typ(A));
800 [ + + ]: 4635124 : for (i=1; i<lB; i++) B[i] = A[p[y1-1+i]];
801 : 85391 : return B;
802 : : }
803 : : /* rowslice(rowpermute(A,p), x1, x2) */
804 : : INLINE GEN
805 : 19151 : rowslicepermute(GEN A, GEN p, long x1, long x2)
806 : : {
807 : 19151 : long i, lB = lg(A);
808 : 19151 : GEN B = cgetg(lB, typ(A));
809 [ + + ]: 104542 : for (i=1; i<lB; i++) gel(B,i) = vecslicepermute(gel(A,i),p,x1,x2);
810 : 19151 : return B;
811 : : }
812 : : INLINE GEN
813 : 47536 : rowslice(GEN A, long x1, long x2)
814 : : {
815 : 47536 : long i, lB = lg(A);
816 : 47536 : GEN B = cgetg(lB, typ(A));
817 [ + + ]: 416364 : for (i=1; i<lB; i++) gel(B,i) = vecslice(gel(A,i),x1,x2);
818 : 47536 : return B;
819 : : }
820 : :
821 : : /* shallow, remove coeff of index j */
822 : : INLINE GEN
823 : 1232 : vecsplice(GEN a, long j)
824 : : {
825 : 1232 : long i, k, l = lg(a);
826 : : GEN b;
827 [ - + ]: 1232 : if (l == 1) pari_err(e_MISC, "incorrect component in vecsplice");
828 : 1232 : b = cgetg(l-1, typ(a));
829 [ + + ]: 5936 : for (i = k = 1; i < l; i++)
830 [ + + ]: 4704 : if (i != j) gel(b, k++) = gel(a,i);
831 : 1232 : return b;
832 : : }
833 : : /* shallow */
834 : : INLINE GEN
835 : 336 : RgM_minor(GEN a, long i, long j)
836 : : {
837 : 336 : GEN b = vecsplice(a, j);
838 : 336 : long k, l = lg(b);
839 [ + + ]: 1232 : for (k = 1; k < l; k++) gel(b,k) = vecsplice(gel(b,k), i);
840 : 336 : return b;
841 : : }
842 : :
843 : : /* A[x0,] */
844 : : INLINE GEN
845 : 7929 : row(GEN A, long x0)
846 : : {
847 : 7929 : long i, lB = lg(A);
848 : 7929 : GEN B = cgetg(lB, t_VEC);
849 [ + + ]: 81116 : for (i=1; i<lB; i++) gel(B, i) = gcoeff(A, x0, i);
850 : 7929 : return B;
851 : : }
852 : : INLINE GEN
853 : 24102 : row_Flm(GEN A, long x0)
854 : : {
855 : 24102 : long i, lB = lg(A);
856 : 24102 : GEN B = cgetg(lB, t_VECSMALL);
857 [ + + ]: 253662 : for (i=1; i<lB; i++) B[i] = coeff(A, x0, i);
858 : 24102 : return B;
859 : : }
860 : : /* A[x0,] */
861 : : INLINE GEN
862 : 21 : rowcopy(GEN A, long x0)
863 : : {
864 : 21 : long i, lB = lg(A);
865 : 21 : GEN B = cgetg(lB, t_VEC);
866 [ + + ]: 63 : for (i=1; i<lB; i++) gel(B, i) = gcopy(gcoeff(A, x0, i));
867 : 21 : return B;
868 : : }
869 : : /* A[x0, x1..x2] */
870 : : INLINE GEN
871 : 2002 : row_i(GEN A, long x0, long x1, long x2)
872 : : {
873 : 2002 : long i, lB = x2 - x1 + 2;
874 : 2002 : GEN B = cgetg(lB, t_VEC);
875 [ + + ]: 5705 : for (i=x1; i<=x2; i++) gel(B, i) = gcoeff(A, x0, i);
876 : 2002 : return B;
877 : : }
878 : :
879 : : INLINE GEN
880 : 49 : vecreverse(GEN A)
881 : : {
882 : 49 : long i,l = lg(A);
883 : 49 : GEN B = cgetg(l, typ(A));
884 [ + + ]: 224 : for (i=1; i<l; i++) gel(B, i) = gel(A, l-i);
885 : 49 : return B;
886 : : }
887 : :
888 : : INLINE GEN
889 : 17367688 : vecsmallpermute(GEN A, GEN p) { return perm_mul(A, p); }
890 : :
891 : : INLINE GEN
892 : 4400880 : vecpermute(GEN A, GEN p)
893 : : {
894 : 4400880 : long i,lB = lg(p);
895 : 4400880 : GEN B = cgetg(lB, typ(A));
896 [ + + ]: 68582556 : for (i=1; i<lB; i++) gel(B, i) = gel(A, p[i]);
897 : 4400880 : return B;
898 : : }
899 : : INLINE GEN
900 : 125851 : rowpermute(GEN A, GEN p)
901 : : {
902 : 125851 : long i, lB = lg(A);
903 : 125851 : GEN B = cgetg(lB, typ(A));
904 [ + + ]: 1576779 : for (i=1; i<lB; i++)
905 [ + + ]: 1450928 : gel(B, i) = typ(gel(A,i)) == t_VECSMALL ? vecsmallpermute(gel(A, i), p):
906 : 1443271 : vecpermute(gel(A, i), p);
907 : 125851 : return B;
908 : : }
909 : : /*******************************************************************/
910 : : /* */
911 : : /* PERMUTATIONS */
912 : : /* */
913 : : /*******************************************************************/
914 : : /* identity permutation */
915 : : INLINE GEN
916 : 63560 : identity_perm(long n)
917 : : {
918 : 63560 : GEN perm = cgetg(n+1, t_VECSMALL);
919 : : long i;
920 [ + + ]: 2626701 : for (i = 1; i <= n; i++) perm[i] = i;
921 : 63560 : return perm;
922 : : }
923 : :
924 : : /* assume d <= n */
925 : : INLINE GEN
926 : 0 : cyclic_perm(long n, long d)
927 : : {
928 : 0 : GEN perm = cgetg(n+1, t_VECSMALL);
929 : : long i;
930 [ # # ]: 0 : for (i = 1; i <= n-d; i++) perm[i] = i+d;
931 [ # # ]: 0 : for ( ; i <= n; i++) perm[i] = i-n+d;
932 : 0 : return perm;
933 : : }
934 : :
935 : : /* Multiply (compose) two permutations */
936 : : INLINE GEN
937 : 17725058 : perm_mul(GEN s, GEN t)
938 : : {
939 : : GEN u;
940 : 17725058 : long i, l = lg(t);
941 : 17725058 : u = cgetg(l, t_VECSMALL);
942 [ + + ]: 86702276 : for (i = 1; i < l; i++) u[i] = s[ t[i] ];
943 : 17725058 : return u;
944 : : }
945 : : /* Compute the inverse (reciprocal) of a permutation. */
946 : : INLINE GEN
947 : 56 : perm_inv(GEN x)
948 : : {
949 : : long i, lx;
950 : 56 : GEN y = cgetg_copy(x, &lx);
951 [ + + ]: 945 : for (i=1; i<lx; i++) y[ x[i] ] = i;
952 : 56 : return y;
953 : : }
954 : : /* Return s*t*s^-1 */
955 : : INLINE GEN
956 : 35 : perm_conj(GEN s, GEN t)
957 : : {
958 : : long i, l;
959 : 35 : GEN v = cgetg_copy(s, &l);
960 [ + + ]: 875 : for (i = 1; i < l; i++) v[ s[i] ] = s[ t[i] ];
961 : 35 : return v;
962 : : }
963 : :
964 : : /*********************************************************************/
965 : : /* MALLOC/FREE WRAPPERS */
966 : : /*********************************************************************/
967 : : #define BLOCK_SIGALRM_START \
968 : : { \
969 : : int block=PARI_SIGINT_block; \
970 : : PARI_SIGINT_block = 2; \
971 : : MT_SIGINT_BLOCK(block);
972 : :
973 : : #define BLOCK_SIGINT_START \
974 : : { \
975 : : int block=PARI_SIGINT_block; \
976 : : PARI_SIGINT_block = 1; \
977 : : MT_SIGINT_BLOCK(block);
978 : :
979 : : #define BLOCK_SIGINT_END \
980 : : PARI_SIGINT_block = block; \
981 : : MT_SIGINT_UNBLOCK(block); \
982 : : if (!block && PARI_SIGINT_pending) \
983 : : { \
984 : : int sig = PARI_SIGINT_pending; \
985 : : PARI_SIGINT_pending = 0; \
986 : : raise(sig); \
987 : : } \
988 : : }
989 : :
990 : : INLINE void
991 : 36042798 : pari_free(void *pointer)
992 : : {
993 [ + + ]: 36042798 : BLOCK_SIGINT_START;
994 : 36042798 : free(pointer);
995 [ + + ][ - + ]: 36042798 : BLOCK_SIGINT_END;
[ + + ][ - + ]
996 : 36042798 : }
997 : : INLINE void*
998 : 102613625 : pari_malloc(size_t size)
999 : : {
1000 [ + - ]: 102613625 : if (size)
1001 : : {
1002 : : char *tmp;
1003 [ + - ]: 102613625 : BLOCK_SIGINT_START;
1004 : 102613625 : tmp = (char*)malloc(size);
1005 [ + - ][ - + ]: 102613625 : BLOCK_SIGINT_END;
[ + - ][ - + ]
1006 [ - + ]: 102613625 : if (!tmp) pari_err(e_MEM);
1007 : 102613625 : return tmp;
1008 : : }
1009 [ # # ]: 0 : if (DEBUGMEM) pari_warn(warner,"mallocing NULL object");
1010 : 102613625 : return NULL;
1011 : : }
1012 : : INLINE void*
1013 : 57178 : pari_realloc(void *pointer, size_t size)
1014 : : {
1015 : : char *tmp;
1016 : :
1017 [ + + ]: 57178 : BLOCK_SIGINT_START;
1018 [ + + ]: 57178 : if (!pointer) tmp = (char *) malloc(size);
1019 : 38208 : else tmp = (char *) realloc(pointer,size);
1020 [ + + ][ - + ]: 57178 : BLOCK_SIGINT_END;
[ + + ][ - + ]
1021 [ - + ]: 57178 : if (!tmp) pari_err(e_MEM);
1022 : 57178 : return tmp;
1023 : : }
1024 : : INLINE void*
1025 : 17095 : pari_calloc(size_t size)
1026 : : {
1027 : 17095 : void *t = pari_malloc(size);
1028 : 17095 : memset(t, 0, size); return t;
1029 : : }
1030 : : INLINE GEN
1031 : 2502 : cgetalloc(long t, size_t l)
1032 : : {
1033 : 2502 : GEN x = (GEN)pari_malloc(l * sizeof(long));
1034 : 2502 : x[0] = evaltyp(t) | evallg(l); return x;
1035 : : }
1036 : :
1037 : : /*******************************************************************/
1038 : : /* */
1039 : : /* GARBAGE COLLECTION */
1040 : : /* */
1041 : : /*******************************************************************/
1042 : : /* copy integer x as if we had avma = av */
1043 : : INLINE GEN
1044 : 771359793 : icopy_avma(GEN x, pari_sp av)
1045 : : {
1046 : 771359793 : long i = lgefint(x), lx = i;
1047 : 771359793 : GEN y = ((GEN)av) - i;
1048 [ + + ]: 5454351680 : while (--i > 0) y[i] = x[i];
1049 : 771359793 : y[0] = evaltyp(t_INT)|evallg(lx);
1050 : 771359793 : return y;
1051 : : }
1052 : : /* copy leaf x as if we had avma = av */
1053 : : INLINE GEN
1054 : 46952889 : leafcopy_avma(GEN x, pari_sp av)
1055 : : {
1056 : 46952889 : long i = lg(x);
1057 : 46952889 : GEN y = ((GEN)av) - i;
1058 [ + + ]: 306822926 : while (--i > 0) y[i] = x[i];
1059 : 46952889 : y[0] = x[0] & (~CLONEBIT);
1060 : 46952889 : return y;
1061 : : }
1062 : : INLINE GEN
1063 : 185332223 : gerepileuptoleaf(pari_sp av, GEN x)
1064 : : {
1065 : : long lx;
1066 : : GEN q;
1067 : :
1068 [ + + ][ + + ]: 185332223 : if (!isonstack(x) || (GEN)av<=x) { avma = av; return x; }
1069 : 185315078 : lx = lg(x);
1070 : 185315078 : q = ((GEN)av) - lx;
1071 : 185315078 : avma = (pari_sp)q;
1072 [ + + ]: 1750825346 : while (--lx >= 0) q[lx] = x[lx];
1073 : 185332223 : return q;
1074 : : }
1075 : : INLINE GEN
1076 : 533677203 : gerepileuptoint(pari_sp av, GEN x)
1077 : : {
1078 [ + + ][ + + ]: 533677203 : if (!isonstack(x) || (GEN)av<=x) { avma = av; return x; }
1079 : 483480479 : avma = (pari_sp)icopy_avma(x, av);
1080 : 533677203 : return (GEN)avma;
1081 : : }
1082 : : INLINE GEN
1083 : 370505560 : gerepileupto(pari_sp av, GEN x)
1084 : : {
1085 [ + + ][ + + ]: 370505560 : if (!isonstack(x) || (GEN)av<=x) { avma = av; return x; }
1086 [ + + + ]: 337921149 : switch(typ(x))
1087 : : { /* non-default = !is_recursive_t(tq) */
1088 : 62530238 : case t_INT: return gerepileuptoint(av, x);
1089 : : case t_REAL:
1090 : : case t_STR:
1091 : 53933220 : case t_VECSMALL: return gerepileuptoleaf(av,x);
1092 : : default:
1093 : : /* NB: x+i --> ((long)x) + i*sizeof(long) */
1094 : 370505560 : return gerepile(av, (pari_sp) (x+lg(x)), x);
1095 : : }
1096 : : }
1097 : :
1098 : : /* gerepileupto(av, gcopy(x)) */
1099 : : INLINE GEN
1100 : 20436209 : gerepilecopy(pari_sp av, GEN x)
1101 : : {
1102 [ + + ]: 20436209 : if (is_recursive_t(typ(x)))
1103 : : {
1104 : 18562686 : GENbin *p = copy_bin(x);
1105 : 18562686 : avma = av; return bin_copy(p);
1106 : : }
1107 : : else
1108 : : {
1109 : 1873523 : avma = av;
1110 [ + + ]: 1873523 : if (x < (GEN)av) {
1111 [ + + ]: 1782460 : if (x < (GEN)pari_mainstack->bot) new_chunk(lg(x));
1112 : 1782460 : x = leafcopy_avma(x, av);
1113 : 1782460 : avma = (pari_sp)x;
1114 : : } else
1115 : 91063 : x = leafcopy(x);
1116 : 20436209 : return x;
1117 : : }
1118 : : }
1119 : :
1120 : : /* Takes an array of pointers to GENs, of length n. Copies all
1121 : : * objects to contiguous locations and cleans up the stack between
1122 : : * av and avma. */
1123 : : INLINE void
1124 : 36326 : gerepilemany(pari_sp av, GEN* gptr[], int n)
1125 : : {
1126 : : int i;
1127 [ + + ]: 130147 : for (i=0; i<n; i++) *gptr[i] = (GEN)copy_bin(*gptr[i]);
1128 : 36326 : avma = av;
1129 [ + + ]: 130147 : for (i=0; i<n; i++) *gptr[i] = bin_copy((GENbin*)*gptr[i]);
1130 : 36326 : }
1131 : :
1132 : : INLINE void
1133 : 3447556 : gerepileall(pari_sp av, int n, ...)
1134 : : {
1135 : : int i;
1136 : 3447556 : va_list a; va_start(a, n);
1137 [ + - ]: 3447556 : if (n < 10)
1138 : : {
1139 : : GEN *gptr[10];
1140 [ + + ]: 10616905 : for (i=0; i<n; i++)
1141 [ + + ]: 7169349 : { gptr[i] = va_arg(a,GEN*); *gptr[i] = (GEN)copy_bin(*gptr[i]); }
1142 : 3447556 : avma = av;
1143 [ + + ]: 10616905 : for (--i; i>=0; i--) *gptr[i] = bin_copy((GENbin*)*gptr[i]);
1144 : :
1145 : : }
1146 : : else
1147 : : {
1148 : 0 : GEN **gptr = (GEN**) pari_malloc(n*sizeof(GEN*));
1149 [ # # ]: 0 : for (i=0; i<n; i++)
1150 [ # # ]: 0 : { gptr[i] = va_arg(a,GEN*); *gptr[i] = (GEN)copy_bin(*gptr[i]); }
1151 : 0 : avma = av;
1152 [ # # ]: 0 : for (--i; i>=0; i--) *gptr[i] = bin_copy((GENbin*)*gptr[i]);
1153 : 0 : pari_free(gptr);
1154 : : }
1155 : 3447556 : }
1156 : :
1157 : : INLINE void
1158 : 8 : gerepilecoeffs(pari_sp av, GEN x, int n)
1159 : : {
1160 : : int i;
1161 [ + + ]: 875 : for (i=0; i<n; i++) gel(x,i) = (GEN)copy_bin(gel(x,i));
1162 : 8 : avma = av;
1163 [ + + ]: 875 : for (i=0; i<n; i++) gel(x,i) = bin_copy((GENbin*)x[i]);
1164 : 8 : }
1165 : :
1166 : : /* p from copy_bin. Copy p->x back to stack, then destroy p */
1167 : : INLINE GEN
1168 : 25826723 : bin_copy(GENbin *p)
1169 : : {
1170 : : GEN x, y, base;
1171 : : long dx, len;
1172 : :
1173 [ + + ]: 25826723 : x = p->x; if (!x) { pari_free(p); return gen_0; }
1174 : 25818916 : len = p->len;
1175 : 25818916 : base= p->base; dx = x - base;
1176 : 25818916 : y = (GEN)memcpy((void*)new_chunk(len), (void*)GENbinbase(p), len*sizeof(long));
1177 : 25818916 : y += dx;
1178 [ - + ]: 25818916 : if (p->canon)
1179 : 0 : shiftaddress_canon(y, (y-x)*sizeof(long));
1180 : : else
1181 : 25818916 : shiftaddress(y, (y-x)*sizeof(long));
1182 : 25826723 : pari_free(p); return y;
1183 : : }
1184 : :
1185 : : INLINE GEN
1186 : 51645639 : GENbinbase(GENbin *p) { return (GEN)(p + 1); }
1187 : :
1188 : : INLINE void
1189 : 8800050 : cgiv(GEN x)
1190 : : {
1191 : 8800050 : pari_sp av = (pari_sp)(x+lg(x));
1192 [ + + ]: 8800050 : if (isonstack((GEN)av)) avma = av;
1193 : 8800050 : }
1194 : :
1195 : : INLINE void
1196 : 961131 : killblock(GEN x) { gunclone(x); }
1197 : :
1198 : : INLINE int
1199 [ + - ][ + + ]: 13985144 : is_universal_constant(GEN x) { return (x >= gen_0 && x <= ghalf); }
1200 : :
1201 : : /*******************************************************************/
1202 : : /* */
1203 : : /* CONVERSION / ASSIGNMENT */
1204 : : /* */
1205 : : /*******************************************************************/
1206 : : /* z is a type which may be a t_COMPLEX component (not a t_QUAD) */
1207 : : INLINE GEN
1208 : 1166484 : cxcompotor(GEN z, long prec)
1209 : : {
1210 [ + + + - ]: 1166484 : switch(typ(z))
1211 : : {
1212 : 772193 : case t_INT: return itor(z, prec);
1213 : 16653 : case t_FRAC: return fractor(z, prec);
1214 : 377638 : case t_REAL: return rtor(z, prec);
1215 : 1166484 : default: pari_err_TYPE("cxcompotor",z); return NULL; /* not reached */
1216 : : }
1217 : : }
1218 : : INLINE GEN
1219 : 582311 : cxtofp(GEN x, long prec)
1220 : 582311 : { retmkcomplex(cxcompotor(gel(x,1),prec), cxcompotor(gel(x,2),prec)); }
1221 : :
1222 : : INLINE double
1223 : 7825973 : gtodouble(GEN x)
1224 : : {
1225 [ + + ]: 7825973 : if (typ(x)!=t_REAL) {
1226 : 437411 : pari_sp av = avma;
1227 : 437411 : x = gtofp(x, DEFAULTPREC);
1228 [ - + ]: 437411 : if (typ(x)!=t_REAL) pari_err_TYPE("gtodouble [t_REAL expected]", x);
1229 : 437411 : avma = av;
1230 : : }
1231 : 7825973 : return rtodbl(x);
1232 : : }
1233 : : INLINE long
1234 : 27984714 : gtos(GEN x) {
1235 [ + + ]: 27984714 : if (typ(x) != t_INT) pari_err_TYPE("gtos [integer expected]",x);
1236 : 27984707 : return itos(x);
1237 : : }
1238 : :
1239 : : INLINE GEN
1240 : 1058683 : absfrac(GEN x)
1241 : : {
1242 : 1058683 : GEN y = cgetg(3, t_FRAC);
1243 : 1058683 : gel(y,1) = absi(gel(x,1));
1244 : 1058683 : gel(y,2) = icopy(gel(x,2)); return y;
1245 : : }
1246 : : INLINE GEN
1247 : 0 : absfrac_shallow(GEN x)
1248 [ # # ]: 0 : { return signe(gel(x,1))>0? x: mkfrac(negi(gel(x,1)), gel(x,2)); }
1249 : : INLINE GEN
1250 [ + + ]: 268401 : Q_abs(GEN x) { return (typ(x) == t_INT)? absi(x): absfrac(x); }
1251 : : INLINE GEN
1252 : 0 : Q_abs_shallow(GEN x)
1253 [ # # ]: 0 : { return (typ(x) == t_INT)? absi_shallow(x): absfrac_shallow(x); }
1254 : :
1255 : : /* Force z to be of type real/complex with floating point components */
1256 : : INLINE GEN
1257 : 5687404 : gtofp(GEN z, long prec)
1258 : : {
1259 [ + + + + : 5687404 : switch(typ(z))
- - ]
1260 : : {
1261 : 3538595 : case t_INT: return itor(z, prec);
1262 : 47528 : case t_FRAC: return fractor(z, prec);
1263 : 1542280 : case t_REAL: return rtor(z, prec);
1264 : : case t_COMPLEX: {
1265 : 559001 : GEN a = gel(z,1), b = gel(z,2);
1266 [ + + ]: 559001 : if (isintzero(b)) return cxcompotor(a, prec);
1267 [ + + ]: 557887 : if (isintzero(a)) {
1268 : 706 : GEN y = cgetg(3, t_COMPLEX);
1269 : 706 : b = cxcompotor(b, prec);
1270 : 706 : gel(y,1) = real_0_bit(expo(b) - prec2nbits(prec));
1271 : 706 : gel(y,2) = b; return y;
1272 : : }
1273 : 557181 : return cxtofp(z, prec);
1274 : : }
1275 : 0 : case t_QUAD: return quadtofp(z, prec);
1276 : 5687404 : default: pari_err_TYPE("gtofp",z); return NULL; /* not reached */
1277 : : }
1278 : : }
1279 : : /* Force z to be of type real / int */
1280 : : INLINE GEN
1281 : 22400 : gtomp(GEN z, long prec)
1282 : : {
1283 [ + + - - : 22400 : switch(typ(z))
- ]
1284 : : {
1285 : 14 : case t_INT: return z;
1286 : 22386 : case t_FRAC: return fractor(z, prec);
1287 : 0 : case t_REAL: return rtor(z, prec);
1288 : 0 : case t_QUAD: z = quadtofp(z, prec);
1289 [ # # ]: 0 : if (typ(z) == t_REAL) return z;
1290 : 22400 : default: pari_err_TYPE("gtomp",z); return NULL; /* not reached */
1291 : : }
1292 : : }
1293 : :
1294 : : INLINE GEN
1295 : 419673 : RgX_gtofp(GEN x, long prec)
1296 : : {
1297 : : long l;
1298 : 419673 : GEN y = cgetg_copy(x, &l);
1299 [ + + ]: 2692138 : while (--l > 1) gel(y,l) = gtofp(gel(x,l), prec);
1300 : 419673 : y[1] = x[1]; return y;
1301 : : }
1302 : : INLINE GEN
1303 : 124592 : RgC_gtofp(GEN x, long prec)
1304 : : {
1305 : 124592 : long l = lg(x);
1306 : 124592 : GEN y = cgetg(l, t_COL);
1307 [ + + ]: 1745049 : while (--l > 0) gel(y,l) = gtofp(gel(x,l), prec);
1308 : 124592 : return y;
1309 : : }
1310 : : INLINE GEN
1311 : 861 : RgM_gtofp(GEN x, long prec)
1312 : : {
1313 : : long l;
1314 : 861 : GEN y = cgetg_copy(x, &l);
1315 [ + + ]: 9131 : while (--l > 0) gel(y,l) = RgC_gtofp(gel(x,l), prec);
1316 : 861 : return y;
1317 : : }
1318 : : INLINE GEN
1319 : 560 : RgC_gtomp(GEN x, long prec)
1320 : : {
1321 : 560 : long l = lg(x);
1322 : 560 : GEN y = cgetg(l, t_COL);
1323 [ + + ]: 22960 : while (--l > 0) gel(y,l) = gtomp(gel(x,l), prec);
1324 : 560 : return y;
1325 : : }
1326 : : INLINE GEN
1327 : 14 : RgM_gtomp(GEN x, long prec)
1328 : : {
1329 : : long l;
1330 : 14 : GEN y = cgetg_copy(x, &l);
1331 [ + + ]: 574 : while (--l > 0) gel(y,l) = RgC_gtomp(gel(x,l), prec);
1332 : 14 : return y;
1333 : : }
1334 : :
1335 : : INLINE GEN
1336 : 8420 : RgX_fpnorml2(GEN x, long prec)
1337 : : {
1338 : 8420 : pari_sp av = avma;
1339 : 8420 : return gerepileupto(av, gnorml2(RgX_gtofp(x, prec)));
1340 : : }
1341 : : INLINE GEN
1342 : 116259 : RgC_fpnorml2(GEN x, long prec)
1343 : : {
1344 : 116259 : pari_sp av = avma;
1345 : 116259 : return gerepileupto(av, gnorml2(RgC_gtofp(x, prec)));
1346 : : }
1347 : : INLINE GEN
1348 : 567 : RgM_fpnorml2(GEN x, long prec)
1349 : : {
1350 : 567 : pari_sp av = avma;
1351 : 567 : return gerepileupto(av, gnorml2(RgM_gtofp(x, prec)));
1352 : : }
1353 : :
1354 : : /* y a t_REAL */
1355 : : INLINE void
1356 : 3210687 : affgr(GEN x, GEN y)
1357 : : {
1358 : : pari_sp av;
1359 [ + + + - : 3210687 : switch(typ(x)) {
- ]
1360 : 38 : case t_INT: affir(x,y); break;
1361 : 183828 : case t_REAL: affrr(x,y); break;
1362 : 3026821 : case t_FRAC: rdiviiz(gel(x,1),gel(x,2), y); break;
1363 : 0 : case t_QUAD: av = avma; affgr(quadtofp(x,realprec(y)), y); avma = av; break;
1364 : 0 : default: pari_err_TYPE2("=",x,y);
1365 : : }
1366 : 3210687 : }
1367 : :
1368 : : INLINE GEN
1369 : 26719 : affc_fixlg(GEN x, GEN res)
1370 : : {
1371 [ + + ]: 26719 : if (typ(x) == t_COMPLEX)
1372 : : {
1373 : 25200 : affrr_fixlg(gel(x,1), gel(res,1));
1374 : 25200 : affrr_fixlg(gel(x,2), gel(res,2));
1375 : : }
1376 : : else
1377 : : {
1378 : 1519 : avma = (pari_sp)(res+3);
1379 : 1519 : res = cgetr(realprec(gel(res,1)));
1380 : 1519 : affrr_fixlg(x, res);
1381 : : }
1382 : 26719 : return res;
1383 : : }
1384 : :
1385 : : INLINE GEN
1386 : 0 : trunc_safe(GEN x) { long e; return gcvtoi(x,&e); }
1387 : :
1388 : : /*******************************************************************/
1389 : : /* */
1390 : : /* LENGTH CONVERSIONS */
1391 : : /* */
1392 : : /*******************************************************************/
1393 : : INLINE long
1394 : 16527 : ndec2nlong(long x) { return 1 + (long)((x)*(LOG2_10/BITS_IN_LONG)); }
1395 : : INLINE long
1396 : 16527 : ndec2prec(long x) { return 2 + ndec2nlong(x); }
1397 : : /* Fast implementation of ceil(x / (8*sizeof(long))); typecast to (ulong)
1398 : : * to avoid overflow. Faster than 1 + ((x-1)>>TWOPOTBITS_IN_LONG)) :
1399 : : * addl, shrl instead of subl, sarl, addl */
1400 : : INLINE long
1401 : 531004 : nbits2nlong(long x) {
1402 : 531004 : return (long)(((ulong)x+BITS_IN_LONG-1) >> TWOPOTBITS_IN_LONG);
1403 : : }
1404 : :
1405 : : INLINE long
1406 : 249497720 : nbits2extraprec(long x) {
1407 : 249497720 : return (long)(((ulong)x+BITS_IN_LONG-1) >> TWOPOTBITS_IN_LONG);
1408 : : }
1409 : :
1410 : : /* Fast implementation of 2 + nbits2nlong(x) */
1411 : : INLINE long
1412 : 85901251 : nbits2prec(long x) {
1413 : 85901251 : return (long)(((ulong)x+3*BITS_IN_LONG-1) >> TWOPOTBITS_IN_LONG);
1414 : : }
1415 : : INLINE long
1416 : 2205745 : nbits2lg(long x) {
1417 : 2205745 : return (long)(((ulong)x+3*BITS_IN_LONG-1) >> TWOPOTBITS_IN_LONG);
1418 : : }
1419 : : /* ceil(x / sizeof(long)) */
1420 : : INLINE long
1421 : 8132871 : nchar2nlong(long x) {
1422 : 8132871 : return (long)(((ulong)x+sizeof(long)-1) >> (TWOPOTBITS_IN_LONG-3L));
1423 : : }
1424 : : INLINE long
1425 : 901881565 : bit_accuracy(long x) { return (x-2) * BITS_IN_LONG; }
1426 : : INLINE double
1427 : 87541 : bit_accuracy_mul(long x, double y) { return (x-2) * (BITS_IN_LONG*y); }
1428 : : INLINE double
1429 : 478065 : prec2nbits_mul(long x, double y) { return (x-2) * (BITS_IN_LONG*y); }
1430 : : INLINE long
1431 : 24572637 : bit_prec(GEN x) { return bit_accuracy(realprec(x)); }
1432 : : INLINE long
1433 : 49341601 : prec2nbits(long x) { return bit_accuracy(x); }
1434 : : INLINE long
1435 : 3754 : prec2ndec(long x) { return (long)prec2nbits_mul(x, LOG10_2); }
1436 : : INLINE long
1437 : 1563 : precdbl(long x) {return (x - 1) << 1;}
1438 : : INLINE long
1439 : 3326647716 : divsBIL(long n) { return n >> TWOPOTBITS_IN_LONG; }
1440 : : INLINE long
1441 : 3257593656 : remsBIL(long n) { return n & (BITS_IN_LONG-1); }
1442 : :
1443 : : /*********************************************************************/
1444 : : /** **/
1445 : : /** OPERATIONS MODULO m **/
1446 : : /** **/
1447 : : /*********************************************************************/
1448 : : /* Assume m > 0, more efficient if 0 <= a, b < m */
1449 : :
1450 : : INLINE GEN
1451 : 8864628 : Fp_red(GEN a, GEN m) { return modii(a, m); }
1452 : : INLINE GEN
1453 : 13425953 : Fp_add(GEN a, GEN b, GEN m)
1454 : : {
1455 : 13425953 : pari_sp av=avma;
1456 : 13425953 : GEN p = addii(a,b);
1457 : 13425953 : long s = signe(p);
1458 [ + + ]: 13425953 : if (!s) return p; /* = gen_0 */
1459 [ + + ]: 12936003 : if (s > 0) /* general case */
1460 : : {
1461 : 12749717 : GEN t = subii(p, m);
1462 : 12749717 : s = signe(t);
1463 [ + + ]: 12749717 : if (!s) { avma = av; return gen_0; }
1464 [ + + ]: 12501454 : if (s < 0) { avma = (pari_sp)p; return p; }
1465 [ + + ]: 3451195 : if (cmpii(t, m) < 0) return gerepileuptoint(av, t); /* general case ! */
1466 : 1016067 : p = remii(t, m);
1467 : : }
1468 : : else
1469 : 186286 : p = modii(p, m);
1470 : 13425953 : return gerepileuptoint(av, p);
1471 : : }
1472 : : INLINE GEN
1473 : 44511617 : Fp_sub(GEN a, GEN b, GEN m)
1474 : : {
1475 : 44511617 : pari_sp av=avma;
1476 : 44511617 : GEN p = subii(a,b);
1477 : 44511617 : long s = signe(p);
1478 [ + + ]: 44511617 : if (!s) return p; /* = gen_0 */
1479 [ + + ]: 43633995 : if (s > 0)
1480 : : {
1481 [ + + ]: 21538189 : if (cmpii(p, m) < 0) return p; /* general case ! */
1482 : 692495 : p = remii(p, m);
1483 : : }
1484 : : else
1485 : : {
1486 : 22095806 : GEN t = addii(p, m);
1487 [ - + ]: 22095806 : if (!s) { avma = av; return gen_0; }
1488 [ - + ]: 22095806 : if (s > 0) return gerepileuptoint(av, t); /* general case ! */
1489 : 22095806 : p = modii(t, m);
1490 : : }
1491 : 44511617 : return gerepileuptoint(av, p);
1492 : : }
1493 : : INLINE GEN
1494 : 8882551 : Fp_neg(GEN b, GEN m)
1495 : : {
1496 : 8882551 : pari_sp av = avma;
1497 : 8882551 : long s = signe(b);
1498 : : GEN p;
1499 [ + + ]: 8882551 : if (!s) return gen_0;
1500 [ + - ]: 6232206 : if (s > 0)
1501 : : {
1502 : 6232206 : p = subii(m, b);
1503 [ + + ]: 6232206 : if (signe(p) >= 0) return p; /* general case ! */
1504 : 23572 : p = modii(p, m);
1505 : : } else
1506 : 0 : p = remii(negi(b), m);
1507 : 8882551 : return gerepileuptoint(av, p);
1508 : : }
1509 : :
1510 : : INLINE GEN
1511 : 13619 : Fp_halve(GEN a, GEN p)
1512 : : {
1513 [ + + ]: 13619 : if (mpodd(a)) a = addii(a,p);
1514 : 13619 : return shifti(a,-1);
1515 : : }
1516 : :
1517 : : /* assume 0 <= u < p and ps2 = p>>1 */
1518 : : INLINE GEN
1519 : 1674875 : Fp_center(GEN u, GEN p, GEN ps2)
1520 [ + + ]: 1674875 : { return absi_cmp(u,ps2)<=0? icopy(u): subii(u,p); }
1521 : :
1522 : : /* x + y*z mod p */
1523 : : INLINE GEN
1524 : 5105154 : Fp_addmul(GEN x, GEN y, GEN z, GEN p)
1525 : : {
1526 : : pari_sp av;
1527 [ + + ][ + + ]: 5105154 : if (!signe(y) || !signe(z)) return Fp_red(x, p);
1528 [ + + ]: 5095534 : if (!signe(x)) return Fp_mul(z,y, p);
1529 : 4811410 : av = avma;
1530 : 5105154 : return gerepileuptoint(av, modii(addii(x, mulii(y,z)), p));
1531 : : }
1532 : :
1533 : : INLINE GEN
1534 : 16722464 : Fp_mul(GEN a, GEN b, GEN m)
1535 : : {
1536 : 16722464 : pari_sp av=avma;
1537 : : GEN p; /*HACK: assume modii use <=lg(p)+(lg(m)<<1) space*/
1538 : 16722464 : (void)new_chunk(lg(a)+lg(b)+(lg(m)<<1));
1539 : 16722464 : p = mulii(a,b);
1540 : 16722464 : avma = av; return modii(p,m);
1541 : : }
1542 : : INLINE GEN
1543 : 6353336 : Fp_sqr(GEN a, GEN m)
1544 : : {
1545 : 6353336 : pari_sp av=avma;
1546 : : GEN p; /*HACK: assume modii use <=lg(p)+(lg(m)<<1) space*/
1547 : 6353336 : (void)new_chunk((lg(a)+lg(m))<<1);
1548 : 6353336 : p = sqri(a);
1549 : 6353336 : avma = av; return modii(p,m);
1550 : : }
1551 : : INLINE GEN
1552 : 24322729 : Fp_mulu(GEN a, ulong b, GEN m)
1553 : : {
1554 : 24322729 : long l = lgefint(m);
1555 [ + + ]: 24322729 : if (l == 3)
1556 : : {
1557 : 19391176 : ulong mm = m[2];
1558 : 19391176 : return utoi( Fl_mul(umodiu(a, mm), b, mm) );
1559 : : } else {
1560 : 4931553 : pari_sp av = avma;
1561 : : GEN p; /*HACK: assume modii use <=lg(p)+(lg(m)<<1) space*/
1562 : 4931553 : (void)new_chunk(lg(a)+1+(l<<1));
1563 : 4931553 : p = muliu(a,b);
1564 : 24322729 : avma = av; return modii(p,m);
1565 : : }
1566 : : }
1567 : : INLINE GEN
1568 : 231 : Fp_muls(GEN a, long b, GEN m)
1569 : : {
1570 : 231 : long l = lgefint(m);
1571 [ + - ]: 231 : if (l == 3)
1572 : : {
1573 : 231 : ulong mm = m[2];
1574 [ + - ]: 231 : if (b < 0)
1575 : : {
1576 : 231 : ulong t = Fl_mul(umodiu(a, mm), -b, mm);
1577 [ + - ]: 231 : return t? utoipos(mm - t): gen_0;
1578 : : }
1579 : : else
1580 : 0 : return utoi( Fl_mul(umodiu(a, mm), b, mm) );
1581 : : } else {
1582 : 0 : pari_sp av = avma;
1583 : : GEN p; /*HACK: assume modii use <=lg(p)+(lg(m)<<1) space*/
1584 : 0 : (void)new_chunk(lg(a)+1+(l<<1));
1585 : 0 : p = mulis(a,b);
1586 : 231 : avma = av; return modii(p,m);
1587 : : }
1588 : : }
1589 : :
1590 : : INLINE GEN
1591 : 3326166 : Fp_inv(GEN a, GEN m)
1592 : : {
1593 : : GEN res;
1594 [ + + ]: 3326166 : if (! invmod(a,m,&res)) pari_err_INV("Fp_inv", mkintmod(res,m));
1595 : 3326074 : return res;
1596 : : }
1597 : : INLINE GEN
1598 : 271253 : Fp_invsafe(GEN a, GEN m)
1599 : : {
1600 : : GEN res;
1601 [ - + ]: 271253 : if (! invmod(a,m,&res)) return NULL;
1602 : 271253 : return res;
1603 : : }
1604 : : INLINE GEN
1605 : 1393855 : Fp_div(GEN a, GEN b, GEN m)
1606 : : {
1607 : 1393855 : pari_sp av=avma;
1608 : : GEN p; /*HACK: assume modii use <=lg(p)+(lg(m)<<1) space*/
1609 : 1393855 : (void)new_chunk(lg(a)+(lg(m)<<1));
1610 : 1393855 : p = mulii(a, Fp_inv(b,m));
1611 : 1393841 : avma = av; return modii(p,m);
1612 : : }
1613 : :
1614 : : INLINE GEN
1615 : 166371 : Flx_mulu(GEN x, ulong a, ulong p) { return Flx_Fl_mul(x,a%p,p); }
1616 : :
1617 : : /*******************************************************************/
1618 : : /* */
1619 : : /* ADDMULII / SUBMULII */
1620 : : /* */
1621 : : /*******************************************************************/
1622 : : /* x - y*z */
1623 : : INLINE GEN
1624 : 34566736 : submulii(GEN x, GEN y, GEN z)
1625 : : {
1626 : 34566736 : long lx = lgefint(x), ly, lz;
1627 : : pari_sp av;
1628 : : GEN t;
1629 [ + + ]: 34566736 : if (lx == 2) { t = mulii(z,y); togglesign(t); return t; }
1630 : 29392546 : ly = lgefint(y);
1631 [ + + ]: 29392546 : if (ly == 2) return icopy(x);
1632 : 28530076 : lz = lgefint(z);
1633 : 28530076 : av = avma; (void)new_chunk(lx+ly+lz); /* HACK */
1634 : 28530076 : t = mulii(z, y);
1635 : 34566736 : avma = av; return subii(x,t);
1636 : : }
1637 : : /* y*z - x */
1638 : : INLINE GEN
1639 : 2565306 : mulsubii(GEN y, GEN z, GEN x)
1640 : : {
1641 : 2565306 : long lx = lgefint(x), ly, lz;
1642 : : pari_sp av;
1643 : : GEN t;
1644 [ + + ]: 2565306 : if (lx == 2) return mulii(z,y);
1645 : 1634218 : ly = lgefint(y);
1646 [ + + ]: 1634218 : if (ly == 2) return negi(x);
1647 : 1551029 : lz = lgefint(z);
1648 : 1551029 : av = avma; (void)new_chunk(lx+ly+lz); /* HACK */
1649 : 1551029 : t = mulii(z, y);
1650 : 2565306 : avma = av; return subii(t,x);
1651 : : }
1652 : :
1653 : : /* x - u*y */
1654 : : INLINE GEN
1655 : 7000 : submuliu(GEN x, GEN y, ulong u)
1656 : : {
1657 : : pari_sp av;
1658 : 7000 : long ly = lgefint(y);
1659 [ - + ]: 7000 : if (ly == 2) return icopy(x);
1660 : 7000 : av = avma;
1661 : 7000 : (void)new_chunk(3+ly+lgefint(x)); /* HACK */
1662 : 7000 : y = mului(u,y);
1663 : 7000 : avma = av; return subii(x, y);
1664 : : }
1665 : : /* x + u*y */
1666 : : INLINE GEN
1667 : 7000 : addmuliu(GEN x, GEN y, ulong u)
1668 : : {
1669 : : pari_sp av;
1670 : 7000 : long ly = lgefint(y);
1671 [ - + ]: 7000 : if (ly == 2) return icopy(x);
1672 : 7000 : av = avma;
1673 : 7000 : (void)new_chunk(3+ly+lgefint(x)); /* HACK */
1674 : 7000 : y = mului(u,y);
1675 : 7000 : avma = av; return addii(x, y);
1676 : : }
1677 : : /* x - u*y */
1678 : : INLINE GEN
1679 : 253687168 : submuliu_inplace(GEN x, GEN y, ulong u)
1680 : : {
1681 : : pari_sp av;
1682 : 253687168 : long ly = lgefint(y);
1683 [ + + ]: 253687168 : if (ly == 2) return x;
1684 : 217808234 : av = avma;
1685 : 217808234 : (void)new_chunk(3+ly+lgefint(x)); /* HACK */
1686 : 217808234 : y = mului(u,y);
1687 : 253687168 : avma = av; return subii(x, y);
1688 : : }
1689 : : /* x + u*y */
1690 : : INLINE GEN
1691 : 253379553 : addmuliu_inplace(GEN x, GEN y, ulong u)
1692 : : {
1693 : : pari_sp av;
1694 : 253379553 : long ly = lgefint(y);
1695 [ + + ]: 253379553 : if (ly == 2) return x;
1696 : 218183871 : av = avma;
1697 : 218183871 : (void)new_chunk(3+ly+lgefint(x)); /* HACK */
1698 : 218183871 : y = mului(u,y);
1699 : 253379553 : avma = av; return addii(x, y);
1700 : : }
1701 : : /* ux + vy */
1702 : : INLINE GEN
1703 : 24430198 : lincombii(GEN u, GEN v, GEN x, GEN y)
1704 : : {
1705 : 24430198 : long lx = lgefint(x), ly;
1706 : : GEN p1, p2;
1707 : : pari_sp av;
1708 [ + + ]: 24430198 : if (lx == 2) return mulii(v,y);
1709 : 14141885 : ly = lgefint(y);
1710 [ + + ]: 14141885 : if (ly == 2) return mulii(u,x);
1711 : 13204574 : av = avma; (void)new_chunk(lx+ly+lgefint(u)+lgefint(v)); /* HACK */
1712 : 13204574 : p1 = mulii(u,x);
1713 : 13204574 : p2 = mulii(v,y);
1714 : 24430198 : avma = av; return addii(p1,p2);
1715 : : }
1716 : :
1717 : : /*******************************************************************/
1718 : : /* */
1719 : : /* GEN SUBTYPES */
1720 : : /* */
1721 : : /*******************************************************************/
1722 : :
1723 : : INLINE int
1724 : 812613582 : is_const_t(long t) { return (t < t_POLMOD); }
1725 : : INLINE int
1726 : 598460 : is_extscalar_t(long t) { return (t <= t_POL); }
1727 : : INLINE int
1728 : 520285 : is_intreal_t(long t) { return (t <= t_REAL); }
1729 : : INLINE int
1730 [ + + ][ + + ]: 295599889 : is_matvec_t(long t) { return (t >= t_VEC && t <= t_MAT); }
1731 : : INLINE int
1732 : 51091190 : is_noncalc_t(long tx) { return (tx) >= t_LIST; }
1733 : : INLINE int
1734 [ + + ][ + + ]: 76263 : is_rational_t(long t) { return (t == t_INT || t == t_FRAC); }
1735 : : INLINE int
1736 : 1680457540 : is_recursive_t(long t) { return lontyp[t]; }
1737 : : INLINE int
1738 : 146836733 : is_scalar_t(long t) { return (t < t_POL); }
1739 : : INLINE int
1740 [ + + ][ + + ]: 773260 : is_vec_t(long t) { return (t == t_VEC || t == t_COL); }
1741 : :
1742 : : /*******************************************************************/
1743 : : /* */
1744 : : /* TRANSCENDENTAL */
1745 : : /* */
1746 : : /*******************************************************************/
1747 : : INLINE GEN
1748 : 5505282 : sqrtr(GEN x) {
1749 : 5505282 : long s = signe(x);
1750 [ + + ]: 5505282 : if (s == 0) return real_0_bit(expo(x) >> 1);
1751 [ + + ]: 5472778 : if (s >= 0) return sqrtr_abs(x);
1752 : 5505282 : retmkcomplex(gen_0, sqrtr_abs(x));
1753 : : }
1754 : : /* x^(1/n) */
1755 : : INLINE GEN
1756 : 28944 : sqrtnr(GEN x, long n) { return mpexp(divrs(mplog(x), n)); }
1757 : :
1758 : : /*******************************************************************/
1759 : : /* */
1760 : : /* MISCELLANEOUS */
1761 : : /* */
1762 : : /*******************************************************************/
1763 [ + + ][ + + ]: 520187 : INLINE int ismpzero(GEN x) { return is_intreal_t(typ(x)) && !signe(x); }
1764 [ + + ][ + + ]: 285242868 : INLINE int isintzero(GEN x) { return typ(x) == t_INT && !signe(x); }
1765 [ + + ][ + + ]: 3982087 : INLINE int isint1(GEN x) { return typ(x)==t_INT && equali1(x); }
1766 [ # # ][ # # ]: 0 : INLINE int isintm1(GEN x){ return typ(x)==t_INT && equalim1(x);}
1767 : 155857016 : INLINE int equali1(GEN n)
1768 [ + + ][ + + ]: 155857016 : { return (ulong) n[1] == (evallgefint(3UL) | evalsigne(1)) && n[2] == 1; }
1769 : 50777 : INLINE int equalim1(GEN n)
1770 [ + + ][ + + ]: 50777 : { return (ulong) n[1] == (evallgefint(3UL) | evalsigne(-1)) && n[2] == 1; }
1771 : : /* works only for POSITIVE integers */
1772 : 754986355 : INLINE int is_pm1(GEN n)
1773 [ + + ][ + + ]: 754986355 : { return lgefint(n) == 3 && n[2] == 1; }
1774 : 102252457 : INLINE int is_bigint(GEN n)
1775 [ + + ][ + + ]: 102252457 : { long l = lgefint(n); return l > 3 || (l == 3 && (n[2] & HIGHBIT)); }
[ + + ]
1776 : :
1777 : 189620825 : INLINE int odd(long x) { return x & 1; }
1778 : 45693537 : INLINE int both_odd(long x, long y) { return x & y & 1; }
1779 : :
1780 : : INLINE int
1781 : 1098320086 : isonstack(GEN x)
1782 : 1098320086 : { return ((pari_sp)x >= pari_mainstack->bot
1783 [ + + ][ + + ]: 1098320086 : && (pari_sp)x < pari_mainstack->top); }
1784 : :
1785 : : /* assume 0 <= k <= BITS_IN_LONG. Return uniform random 0 <= x < (1<<k) */
1786 : : INLINE long
1787 : 8719539 : random_bits(long k) { return pari_rand() >> (BITS_IN_LONG - k); }
1788 : :
1789 : : /* assume x != 0 and x t_REAL, return an approximation to log2(|x|) */
1790 : : INLINE double
1791 : 16793781 : dbllog2r(GEN x)
1792 : 16793781 : { return log2((double)(ulong)x[2]) + (double)(expo(x) - (BITS_IN_LONG-1)); }
1793 : :
1794 : : INLINE GEN
1795 : 198639 : mul_content(GEN cx, GEN cy)
1796 : : {
1797 [ + + ]: 198639 : if (!cx) return cy;
1798 [ + + ]: 119987 : if (!cy) return cx;
1799 : 198639 : return gmul(cx,cy);
1800 : : }
1801 : : INLINE GEN
1802 : 158515 : mul_denom(GEN dx, GEN dy)
1803 : : {
1804 [ + + ]: 158515 : if (!dx) return dy;
1805 [ + + ]: 90237 : if (!dy) return dx;
1806 : 158515 : return mulii(dx,dy);
1807 : : }
1808 : :
1809 : : /* POLYNOMIALS */
1810 : : INLINE GEN
1811 [ + + ]: 17397454 : constant_term(GEN x) { return signe(x)? gel(x,2): gen_0; }
1812 : : INLINE GEN
1813 [ + - ]: 54454326 : leading_term(GEN x) { return lg(x) == 2? gen_0: gel(x,lg(x)-1); }
1814 : : INLINE ulong
1815 [ + - ]: 63644 : Flx_lead(GEN x) { return lg(x) == 2? 0: x[lg(x)-1]; }
1816 : : INLINE long
1817 : 1259258484 : degpol(GEN x) { return lg(x)-3; }
1818 : : INLINE long
1819 : 471161346 : lgpol(GEN x) { return lg(x)-2; }
1820 : : INLINE long
1821 : 23836110 : lgcols(GEN x) { return lg(gel(x,1)); }
1822 : : INLINE long
1823 : 13669921 : nbrows(GEN x) { return lg(gel(x,1))-1; }
1824 : : INLINE GEN
1825 : 7 : truecoeff(GEN x, long n) { return polcoeff0(x,n,-1); }
1826 : :
1827 : : INLINE GEN
1828 : 307047 : RgXQ_mul(GEN y, GEN x, GEN T) { return RgX_rem(RgX_mul(y, x), T); }
1829 : : INLINE GEN
1830 : 160301 : RgXQ_sqr(GEN x, GEN T) { return RgX_rem(RgX_sqr(x), T); }
1831 : :
1832 : : INLINE GEN
1833 : 86828 : ZXQ_mul(GEN y, GEN x, GEN T) { return ZX_rem(ZX_mul(y, x), T); }
1834 : : INLINE GEN
1835 : 13300 : ZXQ_sqr(GEN x, GEN T) { return ZX_rem(ZX_sqr(x), T); }
1836 : :
1837 : : INLINE GEN
1838 : 56912450 : RgX_copy(GEN x)
1839 : : {
1840 : : long lx, i;
1841 : 56912450 : GEN y = cgetg_copy(x, &lx); y[1] = x[1];
1842 [ + + ]: 204422833 : for (i = 2; i<lx; i++) gel(y,i) = gcopy(gel(x,i));
1843 : 56912450 : return y;
1844 : : }
1845 : : /* have to use ulong to avoid silly warnings from gcc "assuming signed
1846 : : * overflow does not occur" */
1847 : : INLINE GEN
1848 : 5005 : RgX_coeff(GEN x, long n)
1849 : : {
1850 : 5005 : ulong l = lg(x);
1851 [ + + ][ + + ]: 5005 : return (n < 0 || ((ulong)n+3) > l)? gen_0: gel(x,n+2);
1852 : : }
1853 : : INLINE GEN
1854 : 176645 : RgX_renormalize(GEN x) { return RgX_renormalize_lg(x, lg(x)); }
1855 : : INLINE GEN
1856 : 6051418 : RgX_div(GEN x, GEN y) { return RgX_divrem(x,y,NULL); }
1857 : : INLINE GEN
1858 : 1646631 : RgX_rem(GEN x, GEN y) { return RgX_divrem(x,y,ONLY_REM); }
1859 : : INLINE GEN
1860 : 0 : RgXQX_div(GEN x, GEN y, GEN T) { return RgXQX_divrem(x,y,T,NULL); }
1861 : : INLINE GEN
1862 : 10416 : RgXQX_rem(GEN x, GEN y, GEN T) { return RgXQX_divrem(x,y,T,ONLY_REM); }
1863 : : INLINE GEN
1864 : 631430 : FpX_div(GEN x, GEN y, GEN p) { return FpX_divrem(x,y,p, NULL); }
1865 : : INLINE GEN
1866 : 1362722 : Flx_div(GEN x, GEN y, ulong p) { return Flx_divrem(x,y,p, NULL); }
1867 : : INLINE GEN
1868 : 1016658 : F2x_div(GEN x, GEN y) { return F2x_divrem(x,y, NULL); }
1869 : : INLINE GEN
1870 : 0 : FpV_FpC_mul(GEN x, GEN y, GEN p) { return FpV_dotproduct(x,y,p); }
1871 : : INLINE GEN
1872 : 19633494 : pol0_Flx(long sv) { return mkvecsmall(sv); }
1873 : : INLINE GEN
1874 : 9403760 : pol1_Flx(long sv) { return mkvecsmall2(sv, 1); }
1875 : : INLINE GEN
1876 : 3134282 : polx_Flx(long sv) { return mkvecsmall3(sv, 0, 1); }
1877 : : INLINE GEN
1878 : 0 : zero_zx(long sv) { return zero_Flx(sv); }
1879 : : INLINE GEN
1880 : 0 : polx_zx(long sv) { return polx_Flx(sv); }
1881 : : INLINE GEN
1882 : 0 : zx_shift(GEN x, long n) { return Flx_shift(x,n); }
1883 : : INLINE GEN
1884 : 0 : zx_renormalize(GEN x, long l) { return Flx_renormalize(x,l); }
1885 : : INLINE GEN
1886 : 77 : zero_F2x(long sv) { return zero_Flx(sv); }
1887 : : INLINE GEN
1888 : 1689832 : pol0_F2x(long sv) { return pol0_Flx(sv); }
1889 : : INLINE GEN
1890 : 465198 : pol1_F2x(long sv) { return pol1_Flx(sv); }
1891 : : INLINE GEN
1892 : 176948 : polx_F2x(long sv) { return mkvecsmall2(sv, 2); }
1893 : : INLINE int
1894 : 1457 : F2x_equal1(GEN x) { return Flx_equal1(x); }
1895 : : INLINE int
1896 : 983293 : F2x_equal(GEN V, GEN W) { return Flx_equal(V,W); }
1897 : : INLINE GEN
1898 : 0 : F2v_copy(GEN x) { return leafcopy(x); }
1899 : : INLINE GEN
1900 : 996153 : Flv_copy(GEN x) { return leafcopy(x); }
1901 : : INLINE GEN
1902 : 33872861 : Flx_copy(GEN x) { return leafcopy(x); }
1903 : : INLINE GEN
1904 : 16475326 : vecsmall_copy(GEN x) { return leafcopy(x); }
1905 : : INLINE int
1906 [ + + ][ + + ]: 2712972 : Flx_equal1(GEN x) { return degpol(x)==0 && x[2] == 1; }
1907 : : INLINE int
1908 [ + + ][ + + ]: 11841 : ZX_equal1(GEN x) { return degpol(x)==0 && equali1(gel(x,2)); }
1909 : :
1910 : : INLINE GEN
1911 : 63016343 : ZX_renormalize(GEN x, long lx) { return ZXX_renormalize(x,lx); }
1912 : : INLINE GEN
1913 : 74083312 : FpX_renormalize(GEN x, long lx) { return ZXX_renormalize(x,lx); }
1914 : : INLINE GEN
1915 : 188796 : FpXX_renormalize(GEN x, long lx) { return ZXX_renormalize(x,lx); }
1916 : : INLINE GEN
1917 : 396828 : FpXQX_renormalize(GEN x, long lx) { return ZXX_renormalize(x,lx); }
1918 : : INLINE GEN
1919 : 25350653 : F2x_renormalize(GEN x, long lx) { return Flx_renormalize(x,lx); }
1920 : : INLINE GEN
1921 : 6034 : F2v_to_F2x(GEN x, long sv) {
1922 : 6034 : GEN y = leafcopy(x);
1923 : 6034 : y[1] = sv; F2x_renormalize(y, lg(y)); return y;
1924 : : }
1925 : :
1926 : : INLINE GEN
1927 : 0 : ZX_ZXY_resultant(GEN a, GEN b) { return ZX_ZXY_rnfequation(a,b,NULL); }
1928 : : INLINE long
1929 : 3360 : sturm(GEN x) { return sturmpart(x, NULL, NULL); }
1930 : : INLINE GEN
1931 : 24600 : resultant(GEN x, GEN y) { return resultant_all(x,y,NULL); }
1932 : :
1933 : : INLINE long
1934 : 2114 : gval(GEN x, long v) {
1935 : 2114 : pari_sp av = avma;
1936 : 2114 : long n = gvaluation(x, pol_x(v));
1937 : 2114 : avma = av; return n;
1938 : : }
1939 : :
1940 : : INLINE void
1941 : 482217 : RgX_shift_inplace_init(long v)
1942 [ + + ]: 482217 : { if (v) (void)cgetg(v, t_VECSMALL); }
1943 : : /* shift polynomial in place. assume v free cells have been left before x */
1944 : : INLINE GEN
1945 : 482217 : RgX_shift_inplace(GEN x, long v)
1946 : : {
1947 : : long i, lx;
1948 : : GEN y, z;
1949 [ + + ]: 482217 : if (!v) return x;
1950 : 254702 : lx = lg(x);
1951 [ - + ]: 254702 : if (lx == 2) return x;
1952 : 254702 : y = x + v;
1953 : 254702 : z = x + lx;
1954 : : /* stackdummy from normalizepol: move it up */
1955 [ - + ]: 254702 : if (lg(z) != v) x[lx + v] = z[0];
1956 [ + + ]: 4703199 : for (i = lx-1; i >= 2; i--) gel(y,i) = gel(x,i);
1957 [ + + ]: 679738 : for (i = v+1; i >= 2; i--) gel(x,i) = gen_0;
1958 : : /* leave x[1] alone: it is correct */
1959 : 482217 : x[0] = evaltyp(t_POL) | evallg(lx+v); return x;
1960 : : }
1961 : :
1962 : :
1963 : : /* LINEAR ALGEBRA */
1964 : : INLINE GEN
1965 : 4256 : zv_to_ZV(GEN x) { return vecsmall_to_vec(x); }
1966 : : INLINE GEN
1967 : 372112 : zc_to_ZC(GEN x) { return vecsmall_to_col(x); }
1968 : : INLINE GEN
1969 : 184442 : ZV_to_zv(GEN x) { return vec_to_vecsmall(x); }
1970 : : INLINE GEN
1971 : 0 : zx_to_zv(GEN x, long N) { return Flx_to_Flv(x,N); }
1972 : : INLINE GEN
1973 : 0 : zv_to_zx(GEN x, long sv) { return Flv_to_Flx(x,sv); }
1974 : : INLINE GEN
1975 : 0 : zm_to_zxV(GEN x, long sv) { return Flm_to_FlxV(x,sv); }
1976 : : INLINE GEN
1977 : 0 : zero_zm(long x, long y) { return zero_Flm(x,y); }
1978 : : INLINE GEN
1979 : 5679344 : zero_zv(long x) { return zero_Flv(x); }
1980 : : INLINE GEN
1981 : 91 : zm_transpose(GEN x) { return Flm_transpose(x); }
1982 : : INLINE GEN
1983 : 0 : zm_copy(GEN x) { return Flm_copy(x); }
1984 : : INLINE GEN
1985 : 796255 : zv_copy(GEN x) { return Flv_copy(x); }
1986 : : INLINE GEN
1987 : 0 : row_zm(GEN x, long i) { return row_Flm(x,i); }
1988 : :
1989 : : INLINE GEN
1990 : 851079 : ZC_hnfrem(GEN x, GEN y) { return ZC_hnfremdiv(x,y,NULL); }
1991 : : INLINE GEN
1992 : 25313 : ZM_hnfrem(GEN x, GEN y) { return ZM_hnfdivrem(x,y,NULL); }
1993 : : INLINE GEN
1994 : 1257826 : ZM_lll(GEN x, double D, long f) { return ZM_lll_norms(x,D,f,NULL); }
1995 : : INLINE void
1996 [ + + ]: 30739 : RgM_dimensions(GEN x, long *m, long *n) { *n = lg(x)-1; *m = *n? nbrows(x): 0; }
1997 : : INLINE GEN
1998 : 16547 : RgM_inv(GEN a) { return RgM_solve(a, NULL); }
1999 : : INLINE GEN
2000 : 5075447 : RgM_shallowcopy(GEN x)
2001 : : {
2002 : : long l;
2003 : 5075447 : GEN y = cgetg_copy(x, &l);
2004 [ + + ]: 26550449 : while (--l > 0) gel(y,l) = leafcopy(gel(x,l));
2005 : 5075447 : return y;
2006 : : }
2007 : : INLINE GEN
2008 : 1440 : F2m_copy(GEN x) { return RgM_shallowcopy(x); }
2009 : :
2010 : : INLINE GEN
2011 : 220683 : Flm_copy(GEN x) { return RgM_shallowcopy(x); }
2012 : :
2013 : : /* divisibility: return 1 if y[i] | x[i] for all i, 0 otherwise. Assume
2014 : : * x,y are ZV of the same length */
2015 : : INLINE int
2016 : 23184 : ZV_dvd(GEN x, GEN y)
2017 : : {
2018 : 23184 : long i, l = lg(x);
2019 [ + + ]: 36617 : for (i=1; i < l; i++)
2020 [ + + ]: 29498 : if ( ! dvdii( gel(x,i), gel(y,i) ) ) return 0;
2021 : 23184 : return 1;
2022 : : }
2023 : :
2024 : : /* Fq */
2025 : : INLINE GEN
2026 : 1664437 : Fq_red(GEN x, GEN T, GEN p)
2027 [ + + ]: 1664437 : { return typ(x)==t_INT? Fp_red(x,p): FpXQ_red(x,T,p); }
2028 : : INLINE GEN
2029 : 363 : gener_Fq_local(GEN T, GEN p, GEN L)
2030 : 363 : { return T? gener_FpXQ_local(T,p, L)
2031 [ + + ]: 363 : : pgener_Fp_local(p, L); }
2032 : :
2033 : : /* FpXQX */
2034 : : INLINE GEN
2035 : 0 : FpXQX_div(GEN x, GEN y, GEN T, GEN p) { return FpXQX_divrem(x, y, T, p, NULL); }
2036 : : INLINE GEN
2037 : 49172 : FlxqX_rem(GEN x, GEN y, GEN T, ulong p) { return FlxqX_divrem(x, y, T, p, ONLY_REM); }
2038 : : INLINE GEN
2039 : 4837 : FlxqX_div(GEN x, GEN y, GEN T, ulong p) { return FlxqX_divrem(x, y, T, p, NULL); }
2040 : :
2041 : : /* FqX */
2042 : : INLINE GEN
2043 [ + - ]: 2968 : FqX_red(GEN z, GEN T, GEN p) { return T? FpXQX_red(z, T, p): FpX_red(z, p); }
2044 : : INLINE GEN
2045 [ + + ]: 687988 : FqX_add(GEN x,GEN y,GEN T,GEN p) { return T? FpXX_add(x,y,p): FpX_add(x,y,p); }
2046 : : INLINE GEN
2047 [ + + ]: 3738 : FqX_neg(GEN x,GEN T,GEN p) { return T? FpXX_neg(x,p): FpX_neg(x,p); }
2048 : : INLINE GEN
2049 [ + + ]: 75621 : FqX_sub(GEN x,GEN y,GEN T,GEN p) { return T? FpXX_sub(x,y,p): FpX_sub(x,y,p); }
2050 : : INLINE GEN
2051 : 482732 : FqX_Fp_mul(GEN P, GEN u, GEN T, GEN p)
2052 [ + + ]: 482732 : { return T? FpXX_Fp_mul(P, u, p): FpX_Fp_mul(P, u, p); }
2053 : : INLINE GEN
2054 : 448944 : FqX_Fq_mul(GEN P, GEN U, GEN T, GEN p)
2055 [ + + ]: 448944 : { return typ(U)==t_INT ? FqX_Fp_mul(P, U, T, p): FpXQX_FpXQ_mul(P, U, T, p); }
2056 : : INLINE GEN
2057 : 30562 : FqX_mul(GEN x, GEN y, GEN T, GEN p)
2058 [ + + ]: 30562 : { return T? FpXQX_mul(x, y, T, p): FpX_mul(x, y, p); }
2059 : : INLINE GEN
2060 : 349872 : FqX_mulu(GEN x, ulong y, GEN T, GEN p)
2061 [ + + ]: 349872 : { return T? FpXX_mulu(x, y, p): FpX_mulu(x, y, p); }
2062 : : INLINE GEN
2063 : 1551 : FqX_sqr(GEN x, GEN T, GEN p)
2064 [ + + ]: 1551 : { return T? FpXQX_sqr(x, T, p): FpX_sqr(x, p); }
2065 : : INLINE GEN
2066 : 3217 : FqX_div(GEN x, GEN y, GEN T, GEN p)
2067 [ + + ]: 3217 : { return T? FpXQX_divrem(x,y,T,p,NULL): FpX_divrem(x,y,p,NULL); }
2068 : : INLINE GEN
2069 : 11356 : FqX_rem(GEN x, GEN y, GEN T, GEN p)
2070 [ + + ]: 11356 : { return T? FpXQX_rem(x,y,T,p): FpX_rem(x,y,p); }
2071 : : INLINE GEN
2072 : 0 : FqX_divrem(GEN x, GEN y, GEN T, GEN p, GEN *z)
2073 [ # # ]: 0 : { return T? FpXQX_divrem(x,y,T,p,z): FpX_divrem(x,y,p,z); }
2074 : : INLINE GEN
2075 : 10120 : FqX_gcd(GEN P,GEN Q,GEN T,GEN p)
2076 [ + + ]: 10120 : {return T? FpXQX_gcd(P,Q,T,p): FpX_gcd(P,Q,p);}
2077 : : INLINE GEN
2078 : 52737 : FqX_extgcd(GEN P,GEN Q,GEN T,GEN p, GEN *U, GEN *V)
2079 [ + + ]: 52737 : { return T? FpXQX_extgcd(P,Q,T,p,U,V): FpX_extgcd(P,Q,p,U,V); }
2080 : :
2081 : : /*FqXQ*/
2082 : : INLINE GEN
2083 : 0 : FqXQ_add(GEN x, GEN y, GEN S/*unused*/, GEN T, GEN p)
2084 [ # # ]: 0 : { (void)S; return T? FpXX_add(x,y,p): FpX_add(x,y,p); }
2085 : : INLINE GEN
2086 : 0 : FqXQ_sub(GEN x, GEN y, GEN S/*unused*/, GEN T, GEN p)
2087 [ # # ]: 0 : { (void)S; return T? FpXX_sub(x,y,p): FpX_sub(x,y,p); }
2088 : : INLINE GEN
2089 : 15624 : FqXQ_div(GEN x, GEN y, GEN S, GEN T, GEN p)
2090 [ + + ]: 15624 : { return T? FpXQXQ_div(x,y,S,T,p): FpXQ_div(x,y,S,p); }
2091 : : INLINE GEN
2092 : 0 : FqXQ_inv(GEN x, GEN S, GEN T, GEN p)
2093 [ # # ]: 0 : { return T? FpXQXQ_inv(x,S,T,p): FpXQ_inv(x,S,p); }
2094 : : INLINE GEN
2095 : 0 : FqXQ_invsafe(GEN x, GEN S, GEN T, GEN p)
2096 [ # # ]: 0 : { return T? FpXQXQ_invsafe(x,S,T,p): FpXQ_inv(x,S,p); }
2097 : : INLINE GEN
2098 : 36666 : FqXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN p)
2099 [ + + ]: 36666 : { return T? FpXQXQ_mul(x,y,S,T,p): FpXQ_mul(x,y,S,p); }
2100 : : INLINE GEN
2101 : 15911 : FqXQ_sqr(GEN x, GEN S, GEN T, GEN p)
2102 [ + + ]: 15911 : { return T? FpXQXQ_sqr(x,S,T,p): FpXQ_sqr(x,S,p); }
2103 : : INLINE GEN
2104 : 0 : FqXQ_pow(GEN x, GEN n, GEN S, GEN T, GEN p)
2105 [ # # ]: 0 : { return T? FpXQXQ_pow(x,n,S,T,p): FpXQ_pow(x,n,S,p); }
2106 : :
2107 : : /*FpXQ*/
2108 : : INLINE GEN
2109 : 0 : FpXQ_add(GEN x,GEN y,GEN T/*unused*/,GEN p)
2110 : 0 : { (void)T; return FpX_add(x,y,p); }
2111 : : INLINE GEN
2112 : 0 : FpXQ_sub(GEN x,GEN y,GEN T/*unused*/,GEN p)
2113 : 0 : { (void)T; return FpX_sub(x,y,p); }
2114 : :
2115 : : /*Flxq*/
2116 : : INLINE GEN
2117 : 0 : Flxq_add(GEN x,GEN y,GEN T/*unused*/,ulong p)
2118 : 0 : { (void)T; return Flx_add(x,y,p); }
2119 : : INLINE GEN
2120 : 0 : Flxq_sub(GEN x,GEN y,GEN T/*unused*/,ulong p)
2121 : 0 : { (void)T; return Flx_sub(x,y,p); }
2122 : :
2123 : : /* F2x */
2124 : :
2125 : : INLINE ulong
2126 : 59244485 : F2x_coeff(GEN x,long v)
2127 : : {
2128 : 59244485 : ulong u=(ulong)x[2+divsBIL(v)];
2129 : 59244485 : return (u>>remsBIL(v))&1UL;
2130 : : }
2131 : :
2132 : : INLINE void
2133 : 1534418 : F2x_clear(GEN x,long v)
2134 : : {
2135 : 1534418 : ulong* u=(ulong*)&x[2+divsBIL(v)];
2136 : 1534418 : *u&=~(1UL<<remsBIL(v));
2137 : 1534418 : }
2138 : :
2139 : : INLINE void
2140 : 17178936 : F2x_set(GEN x,long v)
2141 : : {
2142 : 17178936 : ulong* u=(ulong*)&x[2+divsBIL(v)];
2143 : 17178936 : *u|=1UL<<remsBIL(v);
2144 : 17178936 : }
2145 : :
2146 : : INLINE void
2147 : 321298 : F2x_flip(GEN x,long v)
2148 : : {
2149 : 321298 : ulong* u=(ulong*)&x[2+divsBIL(v)];
2150 : 321298 : *u^=1UL<<remsBIL(v);
2151 : 321298 : }
2152 : :
2153 : : /* F2v */
2154 : :
2155 : : INLINE ulong
2156 : 58891945 : F2v_coeff(GEN x,long v) { return F2x_coeff(x,v-1); }
2157 : :
2158 : : INLINE void
2159 : 1534418 : F2v_clear(GEN x,long v) { F2x_clear(x,v-1); }
2160 : :
2161 : : INLINE void
2162 : 10791446 : F2v_set(GEN x,long v) { F2x_set(x,v-1); }
2163 : :
2164 : : INLINE void
2165 : 321298 : F2v_flip(GEN x,long v) { F2x_flip(x,v-1); }
2166 : :
2167 : : /* F2m */
2168 : :
2169 : : INLINE ulong
2170 : 8029909 : F2m_coeff(GEN x, long a, long b) { return F2v_coeff(gel(x,b), a); }
2171 : :
2172 : : INLINE void
2173 : 0 : F2m_clear(GEN x, long a, long b) { F2v_clear(gel(x,b), a); }
2174 : :
2175 : : INLINE void
2176 : 1027412 : F2m_set(GEN x, long a, long b) { F2v_set(gel(x,b), a); }
2177 : :
2178 : : INLINE void
2179 : 321298 : F2m_flip(GEN x, long a, long b) { F2v_flip(gel(x,b), a); }
2180 : :
2181 : : /* ARITHMETIC */
2182 : : INLINE GEN
2183 : 273 : matpascal(long n) { return matqpascal(n, NULL); }
2184 : : INLINE long
2185 : 230567 : Z_issquare(GEN x) { return Z_issquareall(x, NULL); }
2186 : : INLINE long
2187 : 14 : Z_ispower(GEN x, ulong k) { return Z_ispowerall(x, k, NULL); }
2188 : : INLINE GEN
2189 : 2321106 : sqrti(GEN x) { return sqrtremi(x,NULL); }
2190 : : INLINE GEN
2191 : 1407721 : gaddgs(GEN y, long s) { return gaddsg(s,y); }
2192 : : INLINE int
2193 : 9765 : gcmpgs(GEN y, long s) { return -gcmpsg(s,y); }
2194 : : INLINE int
2195 : 5579 : gequalgs(GEN y, long s) { return gequalsg(s,y); }
2196 : : INLINE GEN
2197 : 0 : gmaxsg(long s, GEN y) { return gmaxgs(y,s); }
2198 : : INLINE GEN
2199 : 0 : gminsg(long s, GEN y) { return gmings(y,s); }
2200 : : INLINE GEN
2201 : 2009427 : gmulgs(GEN y, long s) { return gmulsg(s,y); }
2202 : : INLINE GEN
2203 : 365575 : gsubgs(GEN y, long s) { return gaddgs(y, -s); }
2204 : : INLINE GEN
2205 : 96226 : gdivsg(long s, GEN y) { return gdiv(stoi(s), y); }
2206 : :
2207 : : /* x t_COMPLEX */
2208 : : INLINE GEN
2209 : 9778154 : cxnorm(GEN x) { return gadd(gsqr(gel(x,1)), gsqr(gel(x,2))); }
2210 : : /* q t_QUAD */
2211 : : INLINE GEN
2212 : 1064 : quadnorm(GEN q)
2213 : : {
2214 : 1064 : GEN X = gel(q,1), b = gel(X,3), c = gel(X,2);
2215 : 1064 : GEN z, u = gel(q,3), v = gel(q,2);
2216 [ + + ][ + - ]: 1064 : if (typ(u) == t_INT && typ(v) == t_INT) /* generic case */
2217 : : {
2218 [ + + ]: 427 : z = signe(b)? mulii(v, addii(u,v)): sqri(v);
2219 : 427 : return addii(z, mulii(c, sqri(u)));
2220 : : }
2221 : : else
2222 : : {
2223 [ + - ]: 637 : z = signe(b)? gmul(v, gadd(u,v)): gsqr(v);
2224 : 1064 : return gadd(z, gmul(c, gsqr(u)));
2225 : : }
2226 : : }
2227 : : /* x a t_QUAD, return the associated discriminant */
2228 : : INLINE GEN
2229 : 182 : quad_disc(GEN x)
2230 : : {
2231 : 182 : GEN Q = gel(x,1), b = gel(Q,3), c = gel(Q,2), c4;
2232 [ + + ]: 182 : if (is_pm1(b))
2233 : : {
2234 : 154 : pari_sp av = avma; (void)new_chunk(lgefint(c) + 1);
2235 : 154 : c4 = shifti(c,2); avma = av; return subsi(1, c4);
2236 : : }
2237 : 182 : c4 = shifti(c,2); togglesign_safe(&c4); return c4;
2238 : : }
2239 : : INLINE GEN
2240 : 3622504 : qfb_disc3(GEN x, GEN y, GEN z) { return subii(sqri(y), shifti(mulii(x,z),2)); }
2241 : : INLINE GEN
2242 : 3552217 : qfb_disc(GEN x) { return qfb_disc3(gel(x,1), gel(x,2), gel(x,3)); }
2243 : :
2244 : : INLINE GEN
2245 : 109580 : sqrfrac(GEN x)
2246 : : {
2247 : 109580 : GEN z = cgetg(3,t_FRAC);
2248 : 109580 : gel(z,1) = sqri(gel(x,1));
2249 : 109580 : gel(z,2) = sqri(gel(x,2)); return z;
2250 : : }
2251 : :
2252 : : INLINE void
2253 : 3606251 : normalize_frac(GEN z) {
2254 [ + + ]: 3606251 : if (signe(gel(z,2)) < 0) { togglesign(gel(z,1)); setabssign(gel(z,2)); }
2255 : 3606251 : }
2256 : :
2257 : : INLINE GEN
2258 : 354905 : powii(GEN x, GEN n)
2259 : : {
2260 : 354905 : long ln = lgefint(n);
2261 [ + + ]: 354905 : if (ln == 3) {
2262 : : GEN z;
2263 [ + + ]: 353703 : if (signe(n) > 0) return powiu(x, n[2]);
2264 : 322 : z = cgetg(3, t_FRAC);
2265 : 322 : gel(z,1) = gen_1;
2266 : 322 : gel(z,2) = powiu(x, n[2]);
2267 : 322 : return z;
2268 : : }
2269 [ + - ]: 1202 : if (ln == 2) return gen_1; /* rare */
2270 : : /* should never happen */
2271 : 354905 : return powgi(x, n); /* overflow unless x = 0, 1, -1 */
2272 : : }
2273 : : INLINE GEN
2274 : 735 : powIs(long n) {
2275 [ + + + + ]: 735 : switch(n & 3)
2276 : : {
2277 : 7 : case 1: return mkcomplex(gen_0,gen_1);
2278 : 308 : case 2: return gen_m1;
2279 : 378 : case 3: return mkcomplex(gen_0,gen_m1);
2280 : : }
2281 : 735 : return gen_1;
2282 : : }
2283 : :
2284 : : /*******************************************************************/
2285 : : /* */
2286 : : /* ASSIGNMENTS */
2287 : : /* */
2288 : : /*******************************************************************/
2289 : 0 : INLINE void mpexpz(GEN x, GEN z)
2290 : 0 : { pari_sp av = avma; gaffect(mpexp(x), z); avma = av; }
2291 : 0 : INLINE void mplogz(GEN x, GEN z)
2292 : 0 : { pari_sp av = avma; gaffect(mplog(x), z); avma = av; }
2293 : 0 : INLINE void mpcosz(GEN x, GEN z)
2294 : 0 : { pari_sp av = avma; gaffect(mpcos(x), z); avma = av; }
2295 : 0 : INLINE void mpsinz(GEN x, GEN z)
2296 : 0 : { pari_sp av = avma; gaffect(mpsin(x), z); avma = av; }
2297 : 0 : INLINE void gnegz(GEN x, GEN z)
2298 : 0 : { pari_sp av = avma; gaffect(gneg(x), z); avma = av; }
2299 : 0 : INLINE void gabsz(GEN x, long prec, GEN z)
2300 : 0 : { pari_sp av = avma; gaffect(gabs(x,prec), z); avma = av; }
2301 : 46636 : INLINE void gaddz(GEN x, GEN y, GEN z)
2302 : 46636 : { pari_sp av = avma; gaffect(gadd(x,y), z); avma = av; }
2303 : 0 : INLINE void gsubz(GEN x, GEN y, GEN z)
2304 : 0 : { pari_sp av = avma; gaffect(gsub(x,y), z); avma = av; }
2305 : 23346 : INLINE void gmulz(GEN x, GEN y, GEN z)
2306 : 23346 : { pari_sp av = avma; gaffect(gmul(x,y), z); avma = av; }
2307 : 0 : INLINE void gdivz(GEN x, GEN y, GEN z)
2308 : 0 : { pari_sp av = avma; gaffect(gdiv(x,y), z); avma = av; }
2309 : 0 : INLINE void gdiventz(GEN x, GEN y, GEN z)
2310 : 0 : { pari_sp av = avma; gaffect(gdivent(x,y), z); avma = av; }
2311 : 0 : INLINE void gmodz(GEN x, GEN y, GEN z)
2312 : 0 : { pari_sp av = avma; gaffect(gmod(x,y), z); avma = av; }
2313 : 0 : INLINE void gmul2nz(GEN x, long s, GEN z)
2314 : 0 : { pari_sp av = avma; gaffect(gmul2n(x,s), z); avma = av; }
2315 : 0 : INLINE void gshiftz(GEN x, long s, GEN z)
2316 : 0 : { pari_sp av = avma; gaffect(gshift(x,s), z); avma = av; }
2317 : :
2318 : : /*******************************************************************/
2319 : : /* */
2320 : : /* ELLIPTIC CURVES */
2321 : : /* */
2322 : : /*******************************************************************/
2323 : 1952168 : INLINE GEN ell_get_a1(GEN e) { return gel(e,1); }
2324 : 1406980 : INLINE GEN ell_get_a2(GEN e) { return gel(e,2); }
2325 : 1969150 : INLINE GEN ell_get_a3(GEN e) { return gel(e,3); }
2326 : 2020292 : INLINE GEN ell_get_a4(GEN e) { return gel(e,4); }
2327 : 2430380 : INLINE GEN ell_get_a6(GEN e) { return gel(e,5); }
2328 : 1994421 : INLINE GEN ell_get_b2(GEN e) { return gel(e,6); }
2329 : 434415 : INLINE GEN ell_get_b4(GEN e) { return gel(e,7); }
2330 : 825596 : INLINE GEN ell_get_b6(GEN e) { return gel(e,8); }
2331 : 687449 : INLINE GEN ell_get_b8(GEN e) { return gel(e,9); }
2332 : 4540886 : INLINE GEN ell_get_c4(GEN e) { return gel(e,10); }
2333 : 4900182 : INLINE GEN ell_get_c6(GEN e) { return gel(e,11); }
2334 : 6159846 : INLINE GEN ell_get_disc(GEN e) { return gel(e,12); }
2335 : 830872 : INLINE GEN ell_get_j(GEN e) { return gel(e,13); }
2336 : 6267233 : INLINE long ell_get_type(GEN e) { return mael(e,14,1); }
2337 : 575057 : INLINE GEN ellff_get_field(GEN x) { return gmael(x, 15, 1); }
2338 : 255318 : INLINE GEN ellff_get_a4a6(GEN x) { return gmael(x, 15, 2); }
2339 : 336 : INLINE GEN ellQp_get_zero(GEN x) { return gmael(x, 15, 1); }
2340 : 84 : INLINE long ellQp_get_prec(GEN E) { GEN z = ellQp_get_zero(E); return valp(z); }
2341 : 245 : INLINE GEN ellQp_get_p(GEN E) { GEN z = ellQp_get_zero(E); return gel(z,2); }
2342 : 217 : INLINE long ellR_get_prec(GEN x) { return nbits2prec(mael3(x, 15, 1, 1)); }
2343 : 529 : INLINE long ellR_get_sign(GEN x) { return mael3(x, 15, 1, 2); }
2344 : :
2345 : 29933713 : INLINE int ell_is_inf(GEN z) { return lg(z) == 2; }
2346 : 465428 : INLINE GEN ellinf(void) { return mkvec(gen_0); }
2347 : :
2348 : : /*******************************************************************/
2349 : : /* */
2350 : : /* ALGEBRAIC NUMBER THEORY */
2351 : : /* */
2352 : : /*******************************************************************/
2353 : 15318625 : INLINE GEN pr_get_p(GEN pr) { return gel(pr,1); }
2354 : 1911257 : INLINE GEN pr_get_gen(GEN pr){ return gel(pr,2); }
2355 : : /* .[2] instead of itos works: e and f are small positive integers */
2356 : 1066614 : INLINE long pr_get_e(GEN pr) { return gel(pr,3)[2]; }
2357 : 8013953 : INLINE long pr_get_f(GEN pr) { return gel(pr,4)[2]; }
2358 : 12415054 : INLINE GEN pr_get_tau(GEN pr){ return gel(pr,5); }
2359 : : INLINE int
2360 : 556443 : pr_is_inert(GEN P) { return pr_get_f(P) == lg(pr_get_gen(P))-1; }
2361 : : INLINE GEN
2362 : 75877 : pr_norm(GEN pr) { return powiu(pr_get_p(pr), pr_get_f(pr)); }
2363 : :
2364 : : /* assume nf a genuine nf */
2365 : : INLINE long
2366 : 3022 : nf_get_varn(GEN nf) { return varn(gel(nf,1)); }
2367 : : INLINE GEN
2368 : 5844588 : nf_get_pol(GEN nf) { return gel(nf,1); }
2369 : : INLINE long
2370 : 2647822 : nf_get_degree(GEN nf) { return degpol( nf_get_pol(nf) ); }
2371 : : INLINE long
2372 : 1241402 : nf_get_r1(GEN nf) { GEN x = gel(nf,2); return itou(gel(x,1)); }
2373 : : INLINE long
2374 : 273 : nf_get_r2(GEN nf) { GEN x = gel(nf,2); return itou(gel(x,2)); }
2375 : : INLINE GEN
2376 : 17421 : nf_get_disc(GEN nf) { return gel(nf,3); }
2377 : : INLINE GEN
2378 : 437859 : nf_get_index(GEN nf) { return gel(nf,4); }
2379 : : INLINE GEN
2380 : 1167881 : nf_get_M(GEN nf) { return gmael(nf,5,1); }
2381 : : INLINE GEN
2382 : 37903 : nf_get_G(GEN nf) { return gmael(nf,5,2); }
2383 : : INLINE GEN
2384 : 379114 : nf_get_roundG(GEN nf) { return gmael(nf,5,3); }
2385 : : INLINE GEN
2386 : 721 : nf_get_Tr(GEN nf) { return gmael(nf,5,4); }
2387 : : INLINE GEN
2388 : 714 : nf_get_diff(GEN nf) { return gmael(nf,5,5); }
2389 : : INLINE GEN
2390 : 40491 : nf_get_roots(GEN nf) { return gel(nf,6); }
2391 : : INLINE GEN
2392 : 6329705 : nf_get_zk(GEN nf) { return gel(nf,7); }
2393 : : INLINE GEN
2394 : 1242319 : nf_get_invzk(GEN nf) { return gel(nf,8); }
2395 : : INLINE void
2396 : 3388 : nf_get_sign(GEN nf, long *r1, long *r2)
2397 : : {
2398 : 3388 : GEN x = gel(nf,2);
2399 : 3388 : *r1 = itou(gel(x,1));
2400 : 3388 : *r2 = itou(gel(x,2));
2401 : 3388 : }
2402 : :
2403 : : INLINE GEN
2404 : 7888 : abgrp_get_no(GEN x) { return gel(x,1); }
2405 : : INLINE GEN
2406 : 1128510 : abgrp_get_cyc(GEN x) { return gel(x,2); }
2407 : : INLINE GEN
2408 : 279629 : abgrp_get_gen(GEN x) { return gel(x,3); }
2409 : : INLINE GEN
2410 : 1111705 : bnf_get_nf(GEN bnf) { return gel(bnf,7); }
2411 : : INLINE GEN
2412 : 567446 : bnf_get_clgp(GEN bnf) { return gmael(bnf,8,1); }
2413 : : INLINE GEN
2414 : 609 : bnf_get_no(GEN bnf) { return abgrp_get_no(bnf_get_clgp(bnf)); }
2415 : : INLINE GEN
2416 : 292904 : bnf_get_cyc(GEN bnf) { return abgrp_get_cyc(bnf_get_clgp(bnf)); }
2417 : : INLINE GEN
2418 : 273786 : bnf_get_gen(GEN bnf) { return abgrp_get_gen(bnf_get_clgp(bnf)); }
2419 : : INLINE GEN
2420 : 364 : bnf_get_reg(GEN bnf) { return gmael(bnf,8,2); }
2421 : : INLINE GEN
2422 : 449686 : bnf_get_logfu(GEN bnf) { return gel(bnf,3); }
2423 : : INLINE GEN
2424 : 5619 : bnf_get_tuU(GEN bnf) { return gmael3(bnf,8,4,2); }
2425 : : INLINE long
2426 : 7152 : bnf_get_tuN(GEN bnf) { return gmael3(bnf,8,4,1)[2]; }
2427 : : INLINE GEN
2428 : 6109 : bnf_get_fu(GEN bnf) {
2429 : 6109 : GEN fu = bnf_get_fu_nocheck(bnf);
2430 [ - + ]: 6109 : if (typ(fu) == t_MAT) pari_err(e_MISC,"missing units in bnf");
2431 : 6109 : return fu;
2432 : : }
2433 : : INLINE GEN
2434 : 11295 : bnf_get_fu_nocheck(GEN bnf) { return gmael(bnf,8,5); }
2435 : :
2436 : : INLINE GEN
2437 : 449487 : bnr_get_bnf(GEN bnr) { return gel(bnr,1); }
2438 : : INLINE GEN
2439 : 223799 : bnr_get_bid(GEN bnr) { return gel(bnr,2); }
2440 : : INLINE GEN
2441 : 8695 : bnr_get_mod(GEN bnr) { return gmael(bnr,2,1); }
2442 : : INLINE GEN
2443 : 1918 : bnr_get_nf(GEN bnr) { return gmael(bnr,1,7); }
2444 : : INLINE GEN
2445 : 247524 : bnr_get_clgp(GEN bnr) { return gel(bnr,5); }
2446 : : INLINE GEN
2447 : 7279 : bnr_get_no(GEN bnr) { return abgrp_get_no(bnr_get_clgp(bnr)); }
2448 : : INLINE GEN
2449 : 238882 : bnr_get_cyc(GEN bnr) { return abgrp_get_cyc(bnr_get_clgp(bnr)); }
2450 : : INLINE GEN
2451 : 63 : bnr_get_gen_nocheck(GEN bnr) { return abgrp_get_gen(bnr_get_clgp(bnr)); }
2452 : : INLINE GEN
2453 : 1300 : bnr_get_gen(GEN bnr) {
2454 : 1300 : GEN G = bnr_get_clgp(bnr);
2455 [ - + ]: 1300 : if (lg(G) != 4)
2456 : 0 : pari_err(e_MISC,"missing bnr generators: please use bnrinit(,,1)");
2457 : 1300 : return gel(G,3);
2458 : : }
2459 : :
2460 : : INLINE GEN
2461 : 360287 : bid_get_mod(GEN bid) { return gel(bid,1); }
2462 : : INLINE GEN
2463 : 93113 : bid_get_ideal(GEN bid) { return gmael(bid,1,1); }
2464 : : INLINE GEN
2465 : 129081 : bid_get_arch(GEN bid) { return gmael(bid,1,2); }
2466 : : INLINE GEN
2467 : 601468 : bid_get_grp(GEN bid) { return gel(bid,2); }
2468 : : INLINE GEN
2469 : 0 : bid_get_no(GEN bid) { return abgrp_get_no(bid_get_grp(bid)); }
2470 : : INLINE GEN
2471 : 595688 : bid_get_cyc(GEN bid) { return abgrp_get_cyc(bid_get_grp(bid)); }
2472 : : INLINE GEN
2473 : 0 : bid_get_gen_nocheck(GEN bid) { return abgrp_get_gen(bid_get_grp(bid)); }
2474 : : INLINE GEN
2475 : 4744 : bid_get_gen(GEN bid) {
2476 : 4744 : GEN G = bid_get_grp(bid);
2477 [ - + ]: 4744 : if (lg(G) != 4) pari_err(e_MISC,"missing bid generators. Use idealstar(,,2)");
2478 : 4744 : return abgrp_get_gen(G);
2479 : : }
2480 : : INLINE GEN
2481 : 868 : gal_get_pol(GEN gal) { return gel(gal,1); }
2482 : : INLINE GEN
2483 : 924 : gal_get_p(GEN gal) { return gmael(gal,2,1); }
2484 : : INLINE GEN
2485 : 42 : gal_get_e(GEN gal) { return gmael(gal,2,2); }
2486 : : INLINE GEN
2487 : 1519 : gal_get_mod(GEN gal) { return gmael(gal,2,3); }
2488 : : INLINE GEN
2489 : 1876 : gal_get_roots(GEN gal) { return gel(gal,3); }
2490 : : INLINE GEN
2491 : 1533 : gal_get_invvdm(GEN gal) { return gel(gal,4); }
2492 : : INLINE GEN
2493 : 1533 : gal_get_den(GEN gal) { return gel(gal,5); }
2494 : : INLINE GEN
2495 : 791 : gal_get_group(GEN gal) { return gel(gal,6); }
2496 : : INLINE GEN
2497 : 875 : gal_get_gen(GEN gal) { return gel(gal,7); }
2498 : : INLINE GEN
2499 : 413 : gal_get_orders(GEN gal) { return gel(gal,8); }
2500 : :
2501 : : /* assume rnf a genuine rnf */
2502 : : INLINE long
2503 : 917 : rnf_get_degree(GEN rnf) { return degpol(rnf_get_pol(rnf)); }
2504 : : INLINE long
2505 : 539 : rnf_get_nfdegree(GEN rnf) { return degpol(nf_get_pol(rnf_get_nf(rnf))); }
2506 : : INLINE long
2507 : 182 : rnf_get_absdegree(GEN rnf) { return degpol(gmael(rnf,11,1)); }
2508 : : INLINE GEN
2509 : 4942 : rnf_get_nf(GEN rnf) { return gel(rnf,10); }
2510 : : INLINE void
2511 : 735 : rnf_get_nfzk(GEN rnf, GEN *b, GEN *cb) {*b=gmael(rnf,2,1); *cb=gmael(rnf,2,2);}
2512 : : INLINE GEN
2513 : 1820 : rnf_get_polabs(GEN rnf) { return gmael(rnf,11,1); }
2514 : : INLINE GEN
2515 : 7077 : rnf_get_pol(GEN rnf) { return gel(rnf,1); }
2516 : : INLINE GEN
2517 : 140 : rnf_get_disc(GEN rnf) { return gel(rnf,3); }
2518 : : INLINE GEN
2519 : 105 : rnf_get_index(GEN rnf) { return gel(rnf,4); }
2520 : : INLINE long
2521 : 0 : rnf_get_varn(GEN rnf) { return varn(gel(rnf,1)); }
2522 : : INLINE GEN
2523 : 4634 : rnf_get_nfpol(GEN rnf) { return gmael(rnf,10,1); }
2524 : : INLINE long
2525 : 56 : rnf_get_nfvarn(GEN rnf) { return varn(gmael(rnf,10,1)); }
2526 : : INLINE GEN
2527 : 1925 : rnf_get_zk(GEN rnf) { return gel(rnf,7); }
2528 : : INLINE GEN
2529 : 1344 : rnf_get_map(GEN rnf) { return gel(rnf,11); }
2530 : : INLINE GEN
2531 : 1057 : rnf_get_invzk(GEN rnf) { return gel(rnf,8); }
2532 : :
2533 : : /* I integral (not necessarily HNF), G ZM, rounded Cholesky form of a weighted
2534 : : * T2 matrix. Return m in I with T2(m) small */
2535 : : INLINE GEN
2536 : 142592 : idealpseudomin(GEN I, GEN G)
2537 : : {
2538 : 142592 : GEN u = ZM_lll(ZM_mul(G, I), 0.99, LLL_IM);
2539 : 142592 : return ZM_ZC_mul(I, gel(u,1));
2540 : : }
2541 : : /* I, G as in idealpseudomin. Return an irrational m in I with T2(m) small */
2542 : : INLINE GEN
2543 : 276866 : idealpseudomin_nonscalar(GEN I, GEN G)
2544 : : {
2545 : 276866 : GEN u = ZM_lll(ZM_mul(G, I), 0.99, LLL_IM);
2546 : 276866 : GEN m = ZM_ZC_mul(I, gel(u,1));
2547 [ + + ][ + - ]: 276866 : if (ZV_isscalar(m) && lg(u) > 2) m = ZM_ZC_mul(I, gel(u,2));
2548 : 276866 : return m;
2549 : : }
2550 : :
2551 : : INLINE GEN
2552 : 308 : idealred_elt(GEN nf, GEN I) {
2553 : 308 : pari_sp av = avma;
2554 : 308 : GEN u = idealpseudomin(I, nf_get_roundG(nf));
2555 : 308 : return gerepileupto(av, u);
2556 : : }
2557 : : INLINE GEN
2558 : 141720 : idealred(GEN nf, GEN I) { return idealred0(nf, I, NULL); }
2559 : :
2560 : : /*******************************************************************/
2561 : : /* */
2562 : : /* CLOSURES */
2563 : : /* */
2564 : : /*******************************************************************/
2565 : 87273213 : INLINE long closure_arity(GEN C) { return ((ulong)C[1])&ARITYBITS; }
2566 : 10899343 : INLINE long closure_is_variadic(GEN C) { return !!(((ulong)C[1])&VARARGBITS); }
2567 : 76366563 : INLINE const char *closure_codestr(GEN C) { return GSTR(gel(C,2))-1; }
2568 : 0 : INLINE GEN closure_get_code(GEN C) { return gel(C,2); }
2569 : 76366563 : INLINE GEN closure_get_oper(GEN C) { return gel(C,3); }
2570 : 76363391 : INLINE GEN closure_get_data(GEN C) { return gel(C,4); }
2571 : 3324 : INLINE GEN closure_get_dbg(GEN C) { return gel(C,5); }
2572 : 7229 : INLINE GEN closure_get_text(GEN C) { return gel(C,6); }
2573 : 1022 : INLINE GEN closure_get_frame(GEN C) { return gel(C,7); }
2574 : :
2575 : : /*******************************************************************/
2576 : : /* */
2577 : : /* ERRORS */
2578 : : /* */
2579 : : /*******************************************************************/
2580 : : INLINE long
2581 : 20670 : err_get_num(GEN e) { return e[1]; }
2582 : : INLINE GEN
2583 : 77 : err_get_compo(GEN e, long i) { return gel(e, i+1); }
2584 : :
2585 : : INLINE void
2586 : 0 : pari_err_BUG(const char *f) { pari_err(e_BUG,f); }
2587 : : INLINE void
2588 : 7 : pari_err_CONSTPOL(const char *f) { pari_err(e_CONSTPOL, f); }
2589 : : INLINE void
2590 : 42 : pari_err_COPRIME(const char *f, GEN x, GEN y) { pari_err(e_COPRIME, f,x,y); }
2591 : : INLINE void
2592 : 177 : pari_err_DIM(const char *f) { pari_err(e_DIM, f); }
2593 : : INLINE void
2594 : 0 : pari_err_FILE(const char *f, const char *g) { pari_err(e_FILE, f,g); }
2595 : : INLINE void
2596 : 7 : pari_err_FLAG(const char *f) { pari_err(e_FLAG,f); }
2597 : : INLINE void
2598 : 112 : pari_err_IMPL(const char *f) { pari_err(e_IMPL,f); }
2599 : : INLINE void
2600 : 651 : pari_err_INV(const char *f, GEN x) { pari_err(e_INV,f,x); }
2601 : : INLINE void
2602 : 14 : pari_err_IRREDPOL(const char *f, GEN x) { pari_err(e_IRREDPOL, f,x); }
2603 : : INLINE void
2604 : 1157 : pari_err_DOMAIN(const char *f, const char *v, const char *op, GEN l, GEN x) { pari_err(e_DOMAIN, f,v,op,l,x); }
2605 : : INLINE void
2606 : 203 : pari_err_COMPONENT(const char *f, const char *op, GEN l, GEN x) { pari_err(e_COMPONENT, f,op,l,x); }
2607 : : INLINE void
2608 : 0 : pari_err_MAXPRIME(ulong c) { pari_err(e_MAXPRIME, c); }
2609 : : INLINE void
2610 : 308 : pari_err_OP(const char *f, GEN x, GEN y) { pari_err(e_OP, f,x,y); }
2611 : : INLINE void
2612 : 44 : pari_err_OVERFLOW(const char *f) { pari_err(e_OVERFLOW, f); }
2613 : : INLINE void
2614 : 225 : pari_err_PREC(const char *f) { pari_err(e_PREC,f); }
2615 : : INLINE void
2616 : 0 : pari_err_PACKAGE(const char *f) { pari_err(e_PACKAGE,f); }
2617 : : INLINE void
2618 : 35 : pari_err_PRIME(const char *f, GEN x) { pari_err(e_PRIME, f,x); }
2619 : : INLINE void
2620 : 707 : pari_err_MODULUS(const char *f, GEN x, GEN y) { pari_err(e_MODULUS, f,x,y); }
2621 : : INLINE void
2622 : 21 : pari_err_ROOTS0(const char *f) { pari_err(e_ROOTS0, f); }
2623 : : INLINE void
2624 : 70 : pari_err_SQRTN(const char *f, GEN x) { pari_err(e_SQRTN, f,x); }
2625 : : INLINE void
2626 : 10364 : pari_err_TYPE(const char *f, GEN x) { pari_err(e_TYPE, f,x); }
2627 : : INLINE void
2628 : 2786 : pari_err_TYPE2(const char *f, GEN x, GEN y) { pari_err(e_TYPE2, f,x,y); }
2629 : : INLINE void
2630 : 490 : pari_err_VAR(const char *f, GEN x, GEN y) { pari_err(e_VAR, f,x,y); }
2631 : : INLINE void
2632 : 63 : pari_err_PRIORITY(const char *f, GEN x, const char *op, long v)
2633 : 63 : { pari_err(e_PRIORITY, f,x,op,v); }
|
