Line data Source code
1 : #line 2 "../src/kernel/none/mp_indep.c"
2 : /* Copyright (C) 2000 The PARI group.
3 :
4 : This file is part of the PARI/GP package.
5 :
6 : PARI/GP is free software; you can redistribute it and/or modify it under the
7 : terms of the GNU General Public License as published by the Free Software
8 : Foundation; either version 2 of the License, or (at your option) any later
9 : version. It is distributed in the hope that it will be useful, but WITHOUT
10 : ANY WARRANTY WHATSOEVER.
11 :
12 : Check the License for details. You should have received a copy of it, along
13 : with the package; see the file 'COPYING'. If not, write to the Free Software
14 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
15 :
16 : /* Find c such that 1=c*b mod 2^BITS_IN_LONG, assuming b odd (unchecked) */
17 : ulong
18 60679300 : invmod2BIL(ulong b)
19 : {
20 : static int tab[] = { 0, 0, 0, 8, 0, 8, 0, 0 };
21 60679300 : ulong x = b + tab[b & 7]; /* b^(-1) mod 2^4 */
22 :
23 : /* Newton applied to 1/x - b = 0 */
24 : #ifdef LONG_IS_64BIT
25 60679300 : x = x*(2-b*x); /* one more pass necessary */
26 : #endif
27 60679300 : x = x*(2-b*x);
28 60679300 : x = x*(2-b*x); return x*(2-b*x);
29 : }
30 :
31 : void
32 1358215627 : affrr(GEN x, GEN y)
33 : {
34 1358215627 : long i, lx, ly = lg(y);
35 1358215627 : if (!signe(x))
36 : {
37 126528 : y[1] = evalexpo(minss(expo(x), -bit_accuracy(ly)));
38 126528 : return;
39 : }
40 1358089099 : y[1] = x[1]; lx = lg(x);
41 1358089099 : if (lx <= ly)
42 : {
43 7303705310 : for (i=2; i<lx; i++) y[i]=x[i];
44 1302425008 : for ( ; i<ly; i++) y[i]=0;
45 1144985122 : return;
46 : }
47 1142541561 : for (i=2; i<ly; i++) y[i]=x[i];
48 : /* lx > ly: round properly */
49 213103977 : if (x[ly] & HIGHBIT) roundr_up_ip(y, ly);
50 : }
51 :
52 : GEN
53 62574405 : trunc2nr(GEN x, long n)
54 : {
55 : long ex;
56 62574405 : if (!signe(x)) return gen_0;
57 62133583 : ex = expo(x) + n; if (ex < 0) return gen_0;
58 59566353 : return mantissa2nr(x, ex - bit_prec(x) + 1);
59 : }
60 :
61 : /* x a t_REAL, x = i/2^e, i a t_INT */
62 : GEN
63 52651961 : mantissa_real(GEN x, long *e)
64 : {
65 52651961 : *e = bit_prec(x)-1-expo(x);
66 52651737 : return mantissa2nr(x, 0);
67 : }
68 :
69 : GEN
70 917064917 : mului(ulong x, GEN y)
71 : {
72 917064917 : long s = signe(y);
73 : GEN z;
74 :
75 917064917 : if (!s || !x) return gen_0;
76 765104701 : z = muluispec(x, y+2, lgefint(y)-2);
77 764773079 : setsigne(z,s); return z;
78 : }
79 :
80 : GEN
81 603709715 : mulsi(long x, GEN y)
82 : {
83 603709715 : long s = signe(y);
84 : GEN z;
85 :
86 603709715 : if (!s || !x) return gen_0;
87 360686555 : if (x<0) { s = -s; x = -x; }
88 360686555 : z = muluispec((ulong)x, y+2, lgefint(y)-2);
89 360681927 : setsigne(z,s); return z;
90 : }
91 :
92 : GEN
93 201097431 : mulss(long x, long y)
94 : {
95 : ulong p1;
96 : LOCAL_HIREMAINDER;
97 :
98 201097431 : if (!x || !y) return gen_0;
99 200761995 : if (x<0) {
100 413722 : x = -x;
101 413722 : if (y<0) { y = -y; p1 = mulll(x,y); return uutoi(hiremainder, p1); }
102 299303 : p1 = mulll(x,y); return uutoineg(hiremainder, p1);
103 : } else {
104 200348273 : if (y<0) { y = -y; p1 = mulll(x,y); return uutoineg(hiremainder, p1); }
105 200341938 : p1 = mulll(x,y); return uutoi(hiremainder, p1);
106 : }
107 : }
108 : GEN
109 1506070 : sqrs(long x)
110 : {
111 : ulong p1;
112 : LOCAL_HIREMAINDER;
113 :
114 1506070 : if (!x) return gen_0;
115 1504299 : if (x<0) x = -x;
116 1504299 : p1 = mulll(x,x); return uutoi(hiremainder, p1);
117 : }
118 : GEN
119 4408528076 : muluu(ulong x, ulong y)
120 : {
121 : ulong p1;
122 : LOCAL_HIREMAINDER;
123 :
124 4408528076 : if (!x || !y) return gen_0;
125 4409311713 : p1 = mulll(x,y); return uutoi(hiremainder, p1);
126 : }
127 : GEN
128 606514324 : sqru(ulong x)
129 : {
130 : ulong p1;
131 : LOCAL_HIREMAINDER;
132 :
133 606514324 : if (!x) return gen_0;
134 606181395 : p1 = mulll(x,x); return uutoi(hiremainder, p1);
135 : }
136 :
137 : /* assume x > 1, y != 0. Return u * y with sign s */
138 : static GEN
139 701764151 : mulur_2(ulong x, GEN y, long s)
140 : {
141 701764151 : long m, sh, i, lx = lg(y), e = expo(y);
142 701764151 : GEN z = cgetg(lx, t_REAL);
143 : ulong garde;
144 : LOCAL_HIREMAINDER;
145 :
146 700525901 : y--; garde = mulll(x,y[lx]);
147 3674127109 : for (i=lx-1; i>=3; i--) z[i]=addmul(x,y[i]);
148 700525901 : z[2]=hiremainder; /* != 0 since y normalized and |x| > 1 */
149 700525901 : sh = bfffo(hiremainder); m = BITS_IN_LONG-sh;
150 700525901 : if (sh) shift_left(z,z, 2,lx-1, garde,sh);
151 702614512 : z[1] = evalsigne(s) | evalexpo(m+e);
152 704048887 : if ((garde << sh) & HIGHBIT) roundr_up_ip(z, lx);
153 703836905 : return z;
154 : }
155 :
156 : INLINE GEN
157 473673 : mul0r(GEN x)
158 : {
159 473673 : long l = realprec(x), e = expo(x);
160 473673 : e = (l > 0)? e - l: (e < 0? 2*e: 0);
161 473673 : return real_0_bit(e);
162 : }
163 : /* lg(x) > 2 */
164 : INLINE GEN
165 186460 : div0r(GEN x) {
166 186460 : long l = realprec(x), e = expo(x);
167 186460 : return real_0_bit(-l - e);
168 : }
169 :
170 : GEN
171 116557708 : mulsr(long x, GEN y)
172 : {
173 : long s;
174 :
175 116557708 : if (!x) return mul0r(y);
176 116557666 : s = signe(y);
177 116557666 : if (!s)
178 : {
179 228331 : if (x < 0) x = -x;
180 228331 : return real_0_bit( expo(y) + expu(x) );
181 : }
182 116329335 : if (x==1) return rcopy(y);
183 107632710 : if (x==-1) return negr(y);
184 104520380 : if (x < 0)
185 34720162 : return mulur_2((ulong)-x, y, -s);
186 : else
187 69800218 : return mulur_2((ulong)x, y, s);
188 : }
189 :
190 : GEN
191 919276554 : mulur(ulong x, GEN y)
192 : {
193 : long s;
194 :
195 919276554 : if (!x) return mul0r(y);
196 919276547 : s = signe(y);
197 919276547 : if (!s) return real_0_bit( expo(y) + expu(x) );
198 911970527 : if (x==1) return rcopy(y);
199 596931459 : return mulur_2(x, y, s);
200 : }
201 :
202 : INLINE void
203 3552206033 : mulrrz_end(GEN z, GEN hi, long lz, long sz, long ez, ulong garde)
204 : {
205 : long i;
206 3552206033 : if (hi[2] < 0)
207 : {
208 1645086287 : if (z != hi)
209 1720754221 : for (i=2; i<lz ; i++) z[i] = hi[i];
210 1645086287 : ez++;
211 : }
212 : else
213 : {
214 1907119746 : shift_left(z,hi,2,lz-1, garde, 1);
215 1910454032 : garde <<= 1;
216 : }
217 3555540319 : if (garde & HIGHBIT)
218 : { /* round to nearest */
219 1741706409 : i = lz; do ((ulong*)z)[--i]++; while (i>1 && z[i]==0);
220 1724134155 : if (i == 1) { z[2] = (long)HIGHBIT; ez++; }
221 : }
222 3555540319 : z[1] = evalsigne(sz)|evalexpo(ez);
223 3550664651 : }
224 : /* mulrrz_end for lz = 3, minor simplifications. z[2]=hiremainder from mulll */
225 : INLINE void
226 770772466 : mulrrz_3end(GEN z, long sz, long ez, ulong garde)
227 : {
228 770772466 : if (z[2] < 0)
229 : { /* z2 < (2^BIL-1)^2 / 2^BIL, hence z2+1 != 0 */
230 361899145 : if (garde & HIGHBIT) z[2]++; /* round properly */
231 361899145 : ez++;
232 : }
233 : else
234 : {
235 408873321 : uel(z,2) = (uel(z,2)<<1) | (garde>>(BITS_IN_LONG-1));
236 408873321 : if (garde & (1UL<<(BITS_IN_LONG-2)))
237 : {
238 167984832 : uel(z,2)++; /* round properly, z2+1 can overflow */
239 167984832 : if (!uel(z,2)) { uel(z,2) = HIGHBIT; ez++; }
240 : }
241 : }
242 770772466 : z[1] = evalsigne(sz)|evalexpo(ez);
243 770774277 : }
244 :
245 : /* set z <-- x^2 != 0, floating point multiplication.
246 : * lz = lg(z) = lg(x) */
247 : INLINE void
248 559218358 : sqrz_i(GEN z, GEN x, long lz)
249 : {
250 559218358 : long ez = 2*expo(x);
251 : long i, j, lzz, p1;
252 : ulong garde;
253 : GEN x1;
254 : LOCAL_HIREMAINDER;
255 : LOCAL_OVERFLOW;
256 :
257 559218358 : if (lz > prec2lg(SQRR_SQRI_LIMIT))
258 : {
259 41198567 : pari_sp av = avma;
260 41198567 : GEN hi = sqrispec_mirror(x+2, lz-2);
261 41549935 : mulrrz_end(z, hi, lz, 1, ez, hi[lz]);
262 41532526 : set_avma(av); return;
263 : }
264 517919329 : if (lz == 3)
265 : {
266 121026413 : garde = mulll(x[2],x[2]);
267 121026413 : z[2] = hiremainder;
268 121026413 : mulrrz_3end(z, 1, ez, garde);
269 121004750 : return;
270 : }
271 :
272 396892916 : lzz = lz-1; p1 = x[lzz];
273 396892916 : if (p1)
274 : {
275 360927485 : (void)mulll(p1,x[3]);
276 360927485 : garde = addmul(p1,x[2]);
277 360927485 : z[lzz] = hiremainder;
278 : }
279 : else
280 : {
281 35965431 : garde = 0;
282 35965431 : z[lzz] = 0;
283 : }
284 1837211352 : for (j=lz-2, x1=x-j; j>=3; j--)
285 : {
286 1440318436 : p1 = x[j]; x1++;
287 1440318436 : if (p1)
288 : {
289 1413255634 : (void)mulll(p1,x1[lz+1]);
290 1413255634 : garde = addll(addmul(p1,x1[lz]), garde);
291 7223844454 : for (i=lzz; i>j; i--)
292 : {
293 5810588820 : hiremainder += overflow;
294 5810588820 : z[i] = addll(addmul(p1,x1[i]), z[i]);
295 : }
296 1413255634 : z[j] = hiremainder+overflow;
297 : }
298 27062802 : else z[j]=0;
299 : }
300 396892916 : p1 = x[2]; x1++;
301 396892916 : garde = addll(mulll(p1,x1[lz]), garde);
302 2239642141 : for (i=lzz; i>2; i--)
303 : {
304 1842749225 : hiremainder += overflow;
305 1842749225 : z[i] = addll(addmul(p1,x1[i]), z[i]);
306 : }
307 396892916 : z[2] = hiremainder+overflow;
308 396892916 : mulrrz_end(z, z, lz, 1, ez, garde);
309 : }
310 :
311 : /* lz "large" = lg(y) = lg(z), lg(x) > lz if flag = 1 and >= if flag = 0 */
312 : INLINE void
313 54415513 : mulrrz_int(GEN z, GEN x, GEN y, long lz, long flag, long sz)
314 : {
315 54415513 : pari_sp av = avma;
316 54415513 : GEN hi = muliispec_mirror(y+2, x+2, lz+flag-2, lz-2);
317 54415513 : mulrrz_end(z, hi, lz, sz, expo(x)+expo(y), hi[lz]);
318 54415513 : set_avma(av);
319 54415513 : }
320 :
321 : /* lz = 3 */
322 : INLINE void
323 650903891 : mulrrz_3(GEN z, GEN x, GEN y, long flag, long sz)
324 : {
325 : ulong garde;
326 : LOCAL_HIREMAINDER;
327 650903891 : if (flag)
328 : {
329 77787396 : (void)mulll(x[2],y[3]);
330 77787396 : garde = addmul(x[2],y[2]);
331 : }
332 : else
333 573116495 : garde = mulll(x[2],y[2]);
334 650903891 : z[2] = hiremainder;
335 650903891 : mulrrz_3end(z, sz, expo(x)+expo(y), garde);
336 651079735 : }
337 :
338 : /* set z <-- x*y, floating point multiplication. Trailing 0s for x are
339 : * treated efficiently (important application: mulir).
340 : * lz = lg(z) = lg(x) <= ly <= lg(y), sz = signe(z). flag = lg(x) < lg(y) */
341 : INLINE void
342 3698373609 : mulrrz_i(GEN z, GEN x, GEN y, long lz, long flag, long sz)
343 : {
344 : long ez, i, j, lzz, p1;
345 : ulong garde;
346 : GEN y1;
347 : LOCAL_HIREMAINDER;
348 : LOCAL_OVERFLOW;
349 :
350 3698373609 : if (x == y) { sqrz_i(z,x,lz); return; }
351 3698373609 : if (lz > prec2lg(MULRR_MULII_LIMIT)) { mulrrz_int(z,x,y,lz,flag,sz); return; }
352 3647791684 : if (lz == 3) { mulrrz_3(z,x,y,flag,sz); return; }
353 2996850650 : ez = expo(x) + expo(y);
354 2996850650 : if (flag) { (void)mulll(x[2],y[lz]); garde = hiremainder; } else garde = 0;
355 2996850650 : lzz=lz-1; p1=x[lzz];
356 2996850650 : if (p1)
357 : {
358 2795157905 : (void)mulll(p1,y[3]);
359 2795157905 : garde = addll(addmul(p1,y[2]), garde);
360 2795157905 : z[lzz] = overflow+hiremainder;
361 : }
362 201692745 : else z[lzz]=0;
363 13476964961 : for (j=lz-2, y1=y-j; j>=3; j--)
364 : {
365 10480114311 : p1 = x[j]; y1++;
366 10480114311 : if (p1)
367 : {
368 10179817764 : (void)mulll(p1,y1[lz+1]);
369 10179817764 : garde = addll(addmul(p1,y1[lz]), garde);
370 61817431438 : for (i=lzz; i>j; i--)
371 : {
372 51637613674 : hiremainder += overflow;
373 51637613674 : z[i] = addll(addmul(p1,y1[i]), z[i]);
374 : }
375 10179817764 : z[j] = hiremainder+overflow;
376 : }
377 300296547 : else z[j]=0;
378 : }
379 2996850650 : p1 = x[2]; y1++;
380 2996850650 : garde = addll(mulll(p1,y1[lz]), garde);
381 16530921339 : for (i=lzz; i>2; i--)
382 : {
383 13534070689 : hiremainder += overflow;
384 13534070689 : z[i] = addll(addmul(p1,y1[i]), z[i]);
385 : }
386 2996850650 : z[2] = hiremainder+overflow;
387 2996850650 : mulrrz_end(z, z, lz, sz, ez, garde);
388 : }
389 :
390 : GEN
391 3942906021 : mulrr(GEN x, GEN y)
392 : {
393 : long flag, ly, lz, sx, sy;
394 : GEN z;
395 :
396 3942906021 : if (x == y) return sqrr(x);
397 3941293424 : sx = signe(x); if (!sx) return real_0_bit(expo(x) + expo(y));
398 3677619251 : sy = signe(y); if (!sy) return real_0_bit(expo(x) + expo(y));
399 3644089491 : if (sy < 0) sx = -sx;
400 3644089491 : lz = lg(x);
401 3644089491 : ly = lg(y);
402 3644089491 : if (lz > ly) { lz = ly; swap(x, y); flag = 1; } else flag = (lz != ly);
403 3644089491 : z = cgetg(lz, t_REAL);
404 3637849118 : mulrrz_i(z, x,y, lz,flag, sx);
405 3646976523 : return z;
406 : }
407 :
408 : GEN
409 591669229 : sqrr(GEN x)
410 : {
411 591669229 : long lz, sx = signe(x);
412 : GEN z;
413 :
414 591669229 : if (!sx) return real_0_bit(2*expo(x));
415 559902981 : lz = lg(x); z = cgetg(lz, t_REAL);
416 559238412 : sqrz_i(z, x, lz);
417 560173642 : return z;
418 : }
419 :
420 : GEN
421 978049101 : mulir(GEN x, GEN y)
422 : {
423 978049101 : long sx = signe(x), sy;
424 978049101 : if (!sx) return mul0r(y);
425 977575475 : if (lgefint(x) == 3) {
426 867079085 : GEN z = mulur(uel(x,2), y);
427 868696994 : if (sx < 0) togglesign(z);
428 868382216 : return z;
429 : }
430 110496390 : sy = signe(y);
431 110496390 : if (!sy) return real_0_bit(expi(x) + expo(y));
432 109811668 : if (sy < 0) sx = -sx;
433 : {
434 109811668 : long lz = lg(y), lx = lgefint(x);
435 109811668 : GEN hi, z = cgetg(lz, t_REAL);
436 109097908 : pari_sp av = avma;
437 109097908 : if (lx < (lz>>1) || (lx < lz && lz > prec2lg(MULRR_MULII_LIMIT)))
438 : { /* size mantissa of x < half size of mantissa z, or lx < lz so large
439 : * that mulrr will call mulii anyway: mulii */
440 47692650 : x = itor(x, lg2prec(lx));
441 47384848 : hi = muliispec_mirror(y+2, x+2, lz-2, lx-2);
442 49145475 : mulrrz_end(z, hi, lz, sx, expo(x)+expo(y), hi[lz]);
443 : }
444 : else /* dubious: complete x with 0s and call mulrr */
445 61376953 : mulrrz_i(z, itor(x, lg2prec(lz)), y, lz, 0, sx);
446 110871756 : set_avma(av); return z;
447 : }
448 : }
449 :
450 : /* x + y*z, generic. If lgefint(z) <= 3, caller should use faster variants */
451 : static GEN
452 90938160 : addmulii_gen(GEN x, GEN y, GEN z, long lz)
453 : {
454 90938160 : long lx = lgefint(x), ly;
455 : pari_sp av;
456 : GEN t;
457 90938160 : if (lx == 2) return mulii(z,y);
458 88132185 : ly = lgefint(y);
459 88132185 : if (ly == 2) return icopy(x); /* y = 0, wasteful copy */
460 87522306 : av = avma; (void)new_chunk(lx+ly+lz); /*HACK*/
461 87523581 : t = mulii(z, y);
462 87518515 : set_avma(av); return addii(t,x);
463 : }
464 : /* x + y*z, lgefint(z) == 3 */
465 : static GEN
466 466778837 : addmulii_lg3(GEN x, GEN y, GEN z)
467 : {
468 466778837 : long s = signe(z), lx, ly;
469 466778837 : ulong w = z[2];
470 : pari_sp av;
471 : GEN t;
472 466778837 : if (w == 1) return (s > 0)? addii(x,y): subii(x,y); /* z = +- 1 */
473 385146065 : lx = lgefint(x);
474 385146065 : ly = lgefint(y);
475 385146065 : if (lx == 2)
476 : { /* x = 0 */
477 71286609 : if (ly == 2) return gen_0;
478 39526614 : t = muluispec(w, y+2, ly-2);
479 39526972 : if (signe(y) < 0) s = -s;
480 39526972 : setsigne(t, s); return t;
481 : }
482 313859456 : if (ly == 2) return icopy(x); /* y = 0, wasteful copy */
483 273285281 : av = avma; (void)new_chunk(1+lx+ly);/*HACK*/
484 273432757 : t = muluispec(w, y+2, ly-2);
485 273384263 : if (signe(y) < 0) s = -s;
486 273384263 : setsigne(t, s);
487 273384263 : set_avma(av); return addii(x,t);
488 : }
489 : /* x + y*z */
490 : GEN
491 166918130 : addmulii(GEN x, GEN y, GEN z)
492 : {
493 166918130 : long lz = lgefint(z);
494 166918130 : switch(lz)
495 : {
496 740447 : case 2: return icopy(x); /* z = 0, wasteful copy */
497 126025865 : case 3: return addmulii_lg3(x, y, z);
498 40151818 : default:return addmulii_gen(x, y, z, lz);
499 : }
500 : }
501 : /* x + y*z, returns x itself and not a copy when y*z = 0 */
502 : GEN
503 1568061860 : addmulii_inplace(GEN x, GEN y, GEN z)
504 : {
505 : long lz;
506 1568061860 : if (lgefint(y) == 2) return x;
507 391351541 : lz = lgefint(z);
508 391351541 : switch(lz)
509 : {
510 18016 : case 2: return x;
511 340779801 : case 3: return addmulii_lg3(x, y, z);
512 50553724 : default:return addmulii_gen(x, y, z, lz);
513 : }
514 : }
515 :
516 : /* written by Bruno Haible following an idea of Robert Harley */
517 : long
518 2200456116 : vals(ulong z)
519 : {
520 : static char tab[64]={-1,0,1,12,2,6,-1,13,3,-1,7,-1,-1,-1,-1,14,10,4,-1,-1,8,-1,-1,25,-1,-1,-1,-1,-1,21,27,15,31,11,5,-1,-1,-1,-1,-1,9,-1,-1,24,-1,-1,20,26,30,-1,-1,-1,-1,23,-1,19,29,-1,22,18,28,17,16,-1};
521 : #ifdef LONG_IS_64BIT
522 : long s;
523 : #endif
524 :
525 2200456116 : if (!z) return -1;
526 : #ifdef LONG_IS_64BIT
527 1975647754 : if (! (z&0xffffffff)) { s = 32; z >>=32; } else s = 0;
528 : #endif
529 2200456116 : z |= ~z + 1;
530 2200456116 : z += z << 4;
531 2200456116 : z += z << 6;
532 2200456116 : z ^= z << 16; /* or z -= z<<16 */
533 : #ifdef LONG_IS_64BIT
534 1975647754 : return s + tab[(z&0xffffffff)>>26];
535 : #else
536 224808362 : return tab[z>>26];
537 : #endif
538 : }
539 :
540 : GEN
541 168 : divsi(long x, GEN y)
542 : {
543 168 : long p1, s = signe(y);
544 : LOCAL_HIREMAINDER;
545 :
546 168 : if (!s) pari_err_INV("divsi",gen_0);
547 168 : if (!x || lgefint(y)>3 || ((long)y[2])<0) return gen_0;
548 168 : hiremainder=0; p1=divll(labs(x),y[2]);
549 168 : if (x<0) { hiremainder = -((long)hiremainder); p1 = -p1; }
550 168 : if (s<0) p1 = -p1;
551 168 : return stoi(p1);
552 : }
553 :
554 : GEN
555 3494916 : divir(GEN x, GEN y)
556 : {
557 : GEN z;
558 3494916 : long ly = lg(y), lx = lgefint(x);
559 : pari_sp av;
560 :
561 3494916 : if (ly == 2) pari_err_INV("divir",y);
562 3494920 : if (lx == 2) return div0r(y);
563 3308461 : if (lx == 3) {
564 1961652 : z = divur(x[2], y);
565 1961649 : if (signe(x) < 0) togglesign(z);
566 1961649 : return z;
567 : }
568 1346809 : z = cgetg(ly, t_REAL); av = avma;
569 1346809 : affrr(divrr(itor(x, lg2prec(ly+1)), y), z);
570 1346809 : set_avma(av); return z;
571 : }
572 :
573 : GEN
574 2494741 : divur(ulong x, GEN y)
575 : {
576 : pari_sp av;
577 2494741 : long p = realprec(y);
578 : GEN z;
579 :
580 2494741 : if (p == 0) pari_err_INV("divur",y);
581 2494741 : if (!x) return div0r(y);
582 2494741 : if (p > INVNEWTON_LIMIT) {
583 183 : av = avma; z = invr(y);
584 183 : if (x == 1) return z;
585 183 : return gerepileuptoleaf(av, mulur(x, z));
586 : }
587 2494558 : z = cgetr(p); av = avma;
588 2494543 : affrr(divrr(utor(x, p + BITS_IN_LONG), y), z);
589 2494548 : set_avma(av); return z;
590 : }
591 :
592 : GEN
593 798 : divsr(long x, GEN y)
594 : {
595 : pari_sp av;
596 798 : long p = realprec(y);
597 : GEN z;
598 :
599 798 : if (p == 0) pari_err_INV("divsr",y);
600 798 : if (!x) return div0r(y);
601 798 : if (p > INVNEWTON_LIMIT) {
602 0 : av = avma; z = invr(y);
603 0 : if (x == 1) return z;
604 0 : if (x ==-1) { togglesign(z); return z; }
605 0 : return gerepileuptoleaf(av, mulsr(x, z));
606 : }
607 798 : z = cgetr(p); av = avma;
608 798 : affrr(divrr(stor(x,p + BITS_IN_LONG), y), z);
609 798 : set_avma(av); return z;
610 : }
611 :
612 : /* returns 1/y, assume y != 0 */
613 : static GEN
614 62397745 : invr_basecase(GEN y)
615 : {
616 62397745 : long p = realprec(y);
617 62397745 : GEN z = cgetr(p);
618 62388912 : pari_sp av = avma;
619 62388912 : affrr(divrr(real_1(p + BITS_IN_LONG), y), z);
620 62394264 : set_avma(av); return z;
621 : }
622 : /* returns 1/b, Newton iteration */
623 : GEN
624 62397951 : invr(GEN b)
625 : {
626 62397951 : const long s = 6;
627 62397951 : long i, p, l = lg(b);
628 : GEN x, a;
629 : ulong mask;
630 :
631 62397951 : if (l <= maxss(prec2lg(INVNEWTON_LIMIT), (1L<<s) + 2)) {
632 62393567 : if (l == 2) pari_err_INV("invr",b);
633 62393567 : return invr_basecase(b);
634 : }
635 4294 : mask = quadratic_prec_mask(l-2);
636 30058 : for(i=0, p=1; i<s; i++) { p <<= 1; if (mask & 1) p--; mask >>= 1; }
637 4294 : x = cgetg(l, t_REAL);
638 4294 : a = rcopy(b); a[1] = _evalexpo(0) | evalsigne(1);
639 4294 : affrr(invr_basecase(rtor(a, lg2prec(p+2))), x);
640 13747 : while (mask > 1)
641 : {
642 9453 : p <<= 1; if (mask & 1) p--;
643 9453 : mask >>= 1;
644 9453 : setlg(a, p + 2);
645 9453 : setlg(x, p + 2);
646 : /* TODO: mulrr(a,x) should be a half product (the higher half is known).
647 : * mulrr(x, ) already is */
648 9453 : affrr(addrr(x, mulrr(x, subsr(1, mulrr(a,x)))), x);
649 9453 : set_avma((pari_sp)a);
650 : }
651 4294 : x[1] = (b[1] & SIGNBITS) | evalexpo(expo(x)-expo(b));
652 4294 : set_avma((pari_sp)x); return x;
653 : }
654 :
655 : GEN
656 2561196961 : modii(GEN x, GEN y)
657 : {
658 2561196961 : switch(signe(x))
659 : {
660 484582095 : case 0: return gen_0;
661 1544392625 : case 1: return remii(x,y);
662 532222241 : default:
663 : {
664 532222241 : pari_sp av = avma;
665 532222241 : (void)new_chunk(lgefint(y));
666 536936683 : x = remii(x,y); set_avma(av);
667 536987848 : if (x==gen_0) return x;
668 495868175 : return subiispec(y+2,x+2,lgefint(y)-2,lgefint(x)-2);
669 : }
670 : }
671 : }
672 :
673 : void
674 782235 : modiiz(GEN x, GEN y, GEN z)
675 : {
676 782235 : const pari_sp av = avma;
677 782235 : affii(modii(x,y),z); set_avma(av);
678 782198 : }
679 :
680 : GEN
681 9809399 : divrs(GEN x, long y)
682 : {
683 : GEN z;
684 9809399 : if (y < 0)
685 : {
686 5758088 : z = divru(x, (ulong)-y);
687 5758064 : togglesign(z);
688 : }
689 : else
690 4051311 : z = divru(x, (ulong)y);
691 9809367 : return z;
692 : }
693 :
694 : GEN
695 1095299142 : divru(GEN x, ulong y)
696 : {
697 1095299142 : long i, lx, sh, e, s = signe(x);
698 : ulong garde;
699 : GEN z;
700 : LOCAL_HIREMAINDER;
701 :
702 1095299142 : if (!y) pari_err_INV("divru",gen_0);
703 1095381632 : if (!s) return real_0_bit(expo(x) - expu(y));
704 1094743152 : if (!(y & (y-1))) /* power of 2 */
705 : {
706 92144153 : if (y == 1) return rcopy(x);
707 89430582 : return shiftr(x, -expu(y));
708 : }
709 1002598999 : e = expo(x);
710 1002598999 : lx = lg(x);
711 1002598999 : z = cgetg(lx, t_REAL);
712 1001228957 : if (lx == 3)
713 : {
714 160104523 : if (y <= uel(x,2))
715 : {
716 160104253 : hiremainder = 0;
717 160104253 : z[2] = divll(x[2],y);
718 : /* we may have hiremainder != 0 ==> garde */
719 160104253 : garde = divll(0,y);
720 : }
721 : else
722 : {
723 270 : hiremainder = x[2];
724 270 : z[2] = divll(0,y);
725 270 : garde = hiremainder;
726 270 : e -= BITS_IN_LONG;
727 : }
728 : }
729 : else
730 : {
731 841124434 : ulong yp = get_Fl_red(y);
732 842045323 : if (y <= uel(x,2))
733 : {
734 842050972 : hiremainder = 0;
735 7257883443 : for (i=2; i<lx; i++) z[i] = divll_pre(x[i],y,yp);
736 : /* we may have hiremainder != 0 ==> garde */
737 847900406 : garde = divll_pre(0,y,yp);
738 : }
739 : else
740 : {
741 3231 : long l = lx-1;
742 3231 : hiremainder = x[2];
743 56821 : for (i=2; i<l; i++) z[i] = divll_pre(x[i+1],y,yp);
744 3231 : z[i] = divll_pre(0,y,yp);
745 3765 : garde = hiremainder;
746 3765 : e -= BITS_IN_LONG;
747 : }
748 : }
749 1004835146 : sh=bfffo(z[2]); /* z[2] != 0 */
750 1004835146 : if (sh) shift_left(z,z, 2,lx-1, garde,sh);
751 1005201175 : z[1] = evalsigne(s) | evalexpo(e-sh);
752 1003921074 : if ((garde << sh) & HIGHBIT) roundr_up_ip(z, lx);
753 1003927418 : return z;
754 : }
755 :
756 : GEN
757 132163608 : truedvmdii(GEN x, GEN y, GEN *z)
758 : {
759 : pari_sp av;
760 : GEN r, q, *gptr[2];
761 132163608 : if (!is_bigint(y)) return truedvmdis(x, itos(y), z);
762 5300940 : if (z == ONLY_REM) return modii(x,y);
763 :
764 5300940 : av = avma;
765 5300940 : q = dvmdii(x,y,&r); /* assume that r is last on stack */
766 5300939 : switch(signe(r))
767 : {
768 703284 : case 0:
769 703284 : if (z) *z = gen_0;
770 703284 : return q;
771 3564330 : case 1:
772 3564330 : if (z) *z = r; else cgiv(r);
773 3564329 : return q;
774 1033325 : case -1: break;
775 : }
776 1033325 : q = addis(q, -signe(y));
777 1033325 : if (!z) return gerepileuptoint(av, q);
778 :
779 857169 : *z = subiispec(y+2,r+2, lgefint(y)-2,lgefint(r)-2);
780 857168 : gptr[0]=&q; gptr[1]=z; gerepilemanysp(av,(pari_sp)r,gptr,2);
781 857150 : return q;
782 : }
783 : GEN
784 129019312 : truedvmdis(GEN x, long y, GEN *z)
785 : {
786 129019312 : pari_sp av = avma;
787 : long r;
788 : GEN q;
789 :
790 129019312 : if (z == ONLY_REM) return modis(x, y);
791 129019312 : q = divis_rem(x,y,&r);
792 :
793 128999342 : if (r >= 0)
794 : {
795 117439467 : if (z) *z = utoi(r);
796 117437855 : return q;
797 : }
798 11559875 : q = gerepileuptoint(av, addis(q, (y < 0)? 1: -1));
799 11571243 : if (z) *z = utoi(r + labs(y));
800 11571206 : return q;
801 : }
802 : GEN
803 6202031 : truedvmdsi(long x, GEN y, GEN *z)
804 : {
805 : long q, r;
806 6202031 : if (z == ONLY_REM) return modsi(x, y);
807 6202031 : q = sdivsi_rem(x,y,&r);
808 6202031 : if (r >= 0) {
809 6202031 : if (z) *z = utoi(r);
810 6202031 : return stoi(q);
811 : }
812 0 : q = q - signe(y);
813 0 : if (!z) return stoi(q);
814 :
815 0 : *z = subiuspec(y+2,(ulong)-r, lgefint(y)-2);
816 0 : return stoi(q);
817 : }
818 :
819 : /* 2^n = shifti(gen_1, n) */
820 : GEN
821 102198247 : int2n(long n) {
822 : long i, m, l;
823 : GEN z;
824 102198247 : if (n < 0) return gen_0;
825 102179325 : if (n == 0) return gen_1;
826 :
827 98535534 : l = dvmdsBIL(n, &m) + 3;
828 98535406 : z = cgetipos(l);
829 539626566 : for (i = 2; i < l; i++) z[i] = 0;
830 98503984 : *int_MSW(z) = 1UL << m; return z;
831 : }
832 : /* To avoid problems when 2^(BIL-1) < n. Overflow cleanly, where int2n
833 : * returns gen_0 */
834 : GEN
835 25543414 : int2u(ulong n) {
836 : ulong i, m, l;
837 : GEN z;
838 25543414 : if (n == 0) return gen_1;
839 :
840 25543414 : l = dvmduBIL(n, &m) + 3;
841 25543830 : z = cgetipos(l);
842 51467597 : for (i = 2; i < l; i++) z[i] = 0;
843 25541652 : *int_MSW(z) = 1UL << m; return z;
844 : }
845 : /* 2^n - 1 */
846 : GEN
847 7644 : int2um1(ulong n) {
848 : ulong i, m, l;
849 : GEN z;
850 7644 : if (n == 0) return gen_0;
851 :
852 7644 : l = dvmduBIL(n, &m);
853 7644 : l += m? 3: 2;
854 7644 : z = cgetipos(l);
855 15427 : for (i = 2; i < l; i++) z[i] = ~0UL;
856 7644 : if (m) *int_MSW(z) = (1UL << m) - 1;
857 7644 : return z;
858 : }
859 :
860 : GEN
861 2230117408 : shifti(GEN x, long n)
862 : {
863 2230117408 : long s = signe(x);
864 : GEN y;
865 :
866 2230117408 : if(s == 0) return gen_0;
867 1928233318 : y = shiftispec(x + 2, lgefint(x) - 2, n);
868 1928314853 : if (signe(y)) setsigne(y, s);
869 1928314853 : return y;
870 : }
871 :
872 : /* actual operations will take place on a+2 and b+2: we strip the codewords */
873 : GEN
874 20670612953 : mulii(GEN a,GEN b)
875 : {
876 : long sa,sb;
877 : GEN z;
878 :
879 20670612953 : sa=signe(a); if (!sa) return gen_0;
880 14023240241 : sb=signe(b); if (!sb) return gen_0;
881 10308554317 : if (sb<0) sa = -sa;
882 10308554317 : z = muliispec(a+2,b+2, lgefint(a)-2,lgefint(b)-2);
883 10338656515 : setsigne(z,sa); return z;
884 : }
885 :
886 : GEN
887 1829841640 : sqri(GEN a) { return sqrispec(a+2, lgefint(a)-2); }
888 :
889 : /* sqrt()'s result may be off by 1 when a is not representable exactly as a
890 : * double [64bit machine] */
891 : ulong
892 228448252 : usqrt(ulong a)
893 : {
894 228448252 : ulong x = (ulong)sqrt((double)a);
895 : #ifdef LONG_IS_64BIT
896 195667092 : if (x > LOWMASK || x*x > a) x--;
897 : #endif
898 228448252 : return x;
899 : }
900 :
901 : /********************************************************************/
902 : /** **/
903 : /** EXPONENT / CONVERSION t_REAL --> double **/
904 : /** **/
905 : /********************************************************************/
906 :
907 : #ifdef LONG_IS_64BIT
908 : long
909 22291673 : dblexpo(double x)
910 : {
911 : union { double f; ulong i; } fi;
912 22291673 : const int mant_len = 52; /* mantissa bits (excl. hidden bit) */
913 22291673 : const int exp_mid = 0x3ff;/* exponent bias */
914 :
915 22291673 : if (x==0.) return -exp_mid;
916 22291661 : fi.f = x;
917 22291661 : return ((fi.i & (HIGHBIT-1)) >> mant_len) - exp_mid;
918 : }
919 :
920 : ulong
921 0 : dblmantissa(double x)
922 : {
923 : union { double f; ulong i; } fi;
924 0 : const int expo_len = 11; /* number of bits of exponent */
925 :
926 0 : if (x==0.) return 0;
927 0 : fi.f = x;
928 0 : return (fi.i << expo_len) | HIGHBIT;
929 : }
930 :
931 : GEN
932 11508918 : dbltor(double x)
933 : {
934 : GEN z;
935 : long e;
936 : union { double f; ulong i; } fi;
937 11508918 : const int mant_len = 52; /* mantissa bits (excl. hidden bit) */
938 11508918 : const int exp_mid = 0x3ff;/* exponent bias */
939 11508918 : const int expo_len = 11; /* number of bits of exponent */
940 :
941 11508918 : if (x==0.) return real_0_bit(-exp_mid);
942 11503598 : fi.f = x; z = cgetr(DEFAULTPREC);
943 : {
944 11501691 : const ulong a = fi.i;
945 : ulong A;
946 11501691 : e = ((a & (HIGHBIT-1)) >> mant_len) - exp_mid;
947 11501691 : if (e == exp_mid+1) pari_err_OVERFLOW("dbltor [NaN or Infinity]");
948 11501677 : A = a << expo_len;
949 11501677 : if (e == -exp_mid)
950 : { /* unnormalized values */
951 0 : int sh = bfffo(A);
952 0 : e -= sh-1;
953 0 : z[2] = A << sh;
954 : }
955 : else
956 11501677 : z[2] = HIGHBIT | A;
957 11501677 : z[1] = _evalexpo(e) | evalsigne(x<0? -1: 1);
958 : }
959 11501677 : return z;
960 : }
961 :
962 : double
963 247501118 : rtodbl(GEN x)
964 : {
965 247501118 : long ex,s=signe(x);
966 : ulong a;
967 : union { double f; ulong i; } fi;
968 247501118 : const int mant_len = 52; /* mantissa bits (excl. hidden bit) */
969 247501118 : const int exp_mid = 0x3ff;/* exponent bias */
970 247501118 : const int expo_len = 11; /* number of bits of exponent */
971 :
972 247501118 : if (!s || (ex=expo(x)) < - exp_mid) return 0.0;
973 :
974 : /* start by rounding to closest */
975 218809234 : a = (x[2] & (HIGHBIT-1)) + 0x400;
976 218809234 : if (a & HIGHBIT) { ex++; a=0; }
977 218809234 : if (ex >= exp_mid) pari_err_OVERFLOW("t_REAL->double conversion");
978 218806600 : fi.i = ((ex + exp_mid) << mant_len) | (a >> expo_len);
979 218806600 : if (s<0) fi.i |= HIGHBIT;
980 218806600 : return fi.f;
981 : }
982 :
983 : #else /* LONG_IS_64BIT */
984 :
985 : #if PARI_DOUBLE_FORMAT == 1
986 : # define INDEX0 1
987 : # define INDEX1 0
988 : #elif PARI_DOUBLE_FORMAT == 0
989 : # define INDEX0 0
990 : # define INDEX1 1
991 : #endif
992 :
993 : long
994 3746521 : dblexpo(double x)
995 : {
996 : union { double f; ulong i[2]; } fi;
997 3746521 : const int mant_len = 52; /* mantissa bits (excl. hidden bit) */
998 3746521 : const int exp_mid = 0x3ff;/* exponent bias */
999 3746521 : const int shift = mant_len-32;
1000 :
1001 3746521 : if (x==0.) return -exp_mid;
1002 3746519 : fi.f = x;
1003 : {
1004 3746519 : const ulong a = fi.i[INDEX0];
1005 3746519 : return ((a & (HIGHBIT-1)) >> shift) - exp_mid;
1006 : }
1007 : }
1008 :
1009 : ulong
1010 0 : dblmantissa(double x)
1011 : {
1012 : union { double f; ulong i[2]; } fi;
1013 0 : const int expo_len = 11; /* number of bits of exponent */
1014 :
1015 0 : if (x==0.) return 0;
1016 0 : fi.f = x;
1017 : {
1018 0 : const ulong a = fi.i[INDEX0];
1019 0 : const ulong b = fi.i[INDEX1];
1020 0 : return HIGHBIT | b >> (BITS_IN_LONG-expo_len) | (a << expo_len);
1021 : }
1022 : }
1023 :
1024 : GEN
1025 1880387 : dbltor(double x)
1026 : {
1027 : GEN z;
1028 : long e;
1029 : union { double f; ulong i[2]; } fi;
1030 1880387 : const int mant_len = 52; /* mantissa bits (excl. hidden bit) */
1031 1880387 : const int exp_mid = 0x3ff;/* exponent bias */
1032 1880387 : const int expo_len = 11; /* number of bits of exponent */
1033 1880387 : const int shift = mant_len-32;
1034 :
1035 1880387 : if (x==0.) return real_0_bit(-exp_mid);
1036 1879513 : fi.f = x; z = cgetr(DEFAULTPREC);
1037 : {
1038 1879513 : const ulong a = fi.i[INDEX0];
1039 1879513 : const ulong b = fi.i[INDEX1];
1040 : ulong A, B;
1041 1879513 : e = ((a & (HIGHBIT-1)) >> shift) - exp_mid;
1042 1879513 : if (e == exp_mid+1) pari_err_OVERFLOW("dbltor [NaN or Infinity]");
1043 1879513 : A = b >> (BITS_IN_LONG-expo_len) | (a << expo_len);
1044 1879513 : B = b << expo_len;
1045 1879513 : if (e == -exp_mid)
1046 : { /* unnormalized values */
1047 : int sh;
1048 0 : if (A)
1049 : {
1050 0 : sh = bfffo(A);
1051 0 : e -= sh-1;
1052 0 : z[2] = (A << sh) | (B >> (32-sh));
1053 0 : z[3] = B << sh;
1054 : }
1055 : else
1056 : {
1057 0 : sh = bfffo(B); /* B != 0 */
1058 0 : e -= sh-1 + 32;
1059 0 : z[2] = B << sh;
1060 0 : z[3] = 0;
1061 : }
1062 : }
1063 : else
1064 : {
1065 1879513 : z[3] = B;
1066 1879513 : z[2] = HIGHBIT | A;
1067 : }
1068 1879513 : z[1] = _evalexpo(e) | evalsigne(x<0? -1: 1);
1069 : }
1070 1879513 : return z;
1071 : }
1072 :
1073 : double
1074 40554418 : rtodbl(GEN x)
1075 : {
1076 40554418 : long ex,s=signe(x),lx=lg(x);
1077 : ulong a,b,k;
1078 : union { double f; ulong i[2]; } fi;
1079 40554418 : const int mant_len = 52; /* mantissa bits (excl. hidden bit) */
1080 40554418 : const int exp_mid = 0x3ff;/* exponent bias */
1081 40554418 : const int expo_len = 11; /* number of bits of exponent */
1082 40554418 : const int shift = mant_len-32;
1083 :
1084 40554418 : if (!s || (ex=expo(x)) < - exp_mid) return 0.0;
1085 :
1086 : /* start by rounding to closest */
1087 35719456 : a = x[2] & (HIGHBIT-1);
1088 35719456 : if (lx > 3)
1089 : {
1090 35592421 : b = x[3] + 0x400UL; if (b < 0x400UL) a++;
1091 35592421 : if (a & HIGHBIT) { ex++; a=0; }
1092 : }
1093 127035 : else b = 0;
1094 35719456 : if (ex >= exp_mid) pari_err_OVERFLOW("t_REAL->double conversion");
1095 35719456 : ex += exp_mid;
1096 35719456 : k = (a >> expo_len) | (ex << shift);
1097 35719456 : if (s<0) k |= HIGHBIT;
1098 35719456 : fi.i[INDEX0] = k;
1099 35719456 : fi.i[INDEX1] = (a << (BITS_IN_LONG-expo_len)) | (b >> expo_len);
1100 35719456 : return fi.f;
1101 : }
1102 : #endif /* LONG_IS_64BIT */
1103 :
|
