1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 * gmpy2_mpz_misc.c *
3 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
4 * Python interface to the GMP or MPIR, MPFR, and MPC multiple precision *
5 * libraries. *
6 * *
7 * Copyright 2000 - 2009 Alex Martelli *
8 * *
9 * Copyright 2008 - 2021 Case Van Horsen *
10 * *
11 * This file is part of GMPY2. *
12 * *
13 * GMPY2 is free software: you can redistribute it and/or modify it under *
14 * the terms of the GNU Lesser General Public License as published by the *
15 * Free Software Foundation, either version 3 of the License, or (at your *
16 * option) any later version. *
17 * *
18 * GMPY2 is distributed in the hope that it will be useful, but WITHOUT *
19 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or *
20 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public *
21 * License for more details. *
22 * *
23 * You should have received a copy of the GNU Lesser General Public *
24 * License along with GMPY2; if not, see <http://www.gnu.org/licenses/> *
25 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
26
27 /* return number-of-digits for an mpz in requested base, default 10 */
28 PyDoc_STRVAR(GMPy_doc_mpz_method_num_digits,
29 "x.num_digits([base]) -> int\n\n"
30 "Return length of string representing the absolute value of x in\n"
31 "the given base. Values for base can range between 2 and 62. The\n"
32 "value returned may be 1 too large.");
33
34 PyDoc_STRVAR(GMPy_doc_mpz_function_num_digits,
35 "num_digits(x[, base]) -> int\n\n"
36 "Return length of string representing the absolute value of x in\n"
37 "the given base. Values for base can range between 2 and 62. The\n"
38 "value returned may be 1 too large.");
39
40 static PyObject *
GMPy_MPZ_Method_NumDigits(PyObject * self,PyObject * args)41 GMPy_MPZ_Method_NumDigits(PyObject *self, PyObject *args)
42 {
43 long base = 10;
44 PyObject *result;
45
46 if (PyTuple_GET_SIZE(args) == 1) {
47 base = PyIntOrLong_AsLong(PyTuple_GET_ITEM(args, 0));
48 if (base == -1 && PyErr_Occurred()) {
49 return NULL;
50 }
51 }
52
53 if ((base < 2) || (base > 62)) {
54 VALUE_ERROR("base must be in the interval [2, 62]");
55 return NULL;
56 }
57
58 result = PyIntOrLong_FromSize_t(mpz_sizeinbase(MPZ(self), (int)base));
59 return result;
60 }
61
62 static PyObject *
GMPy_MPZ_Function_NumDigits(PyObject * self,PyObject * args)63 GMPy_MPZ_Function_NumDigits(PyObject *self, PyObject *args)
64 {
65 long base = 10;
66 Py_ssize_t argc;
67 MPZ_Object *temp;
68 PyObject *result;
69
70 argc = PyTuple_GET_SIZE(args);
71 if (argc == 0 || argc > 2) {
72 TYPE_ERROR("num_digits() requires 'mpz',['int'] arguments");
73 return NULL;
74 }
75
76 if (argc == 2) {
77 base = PyIntOrLong_AsLong(PyTuple_GET_ITEM(args, 1));
78 if (base == -1 && PyErr_Occurred()) {
79 return NULL;
80 }
81 }
82
83 if ((base < 2) || (base > 62)) {
84 VALUE_ERROR("base must be in the interval [2, 62]");
85 return NULL;
86 }
87
88 if (!(temp = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL))) {
89 return NULL;
90 }
91
92 result = PyIntOrLong_FromSize_t(mpz_sizeinbase(temp->z, (int)base));
93 Py_DECREF((PyObject*)temp);
94 return result;
95 }
96
97 PyDoc_STRVAR(GMPy_doc_mpz_function_iroot,
98 "iroot(x,n) -> (number, boolean)\n\n"
99 "Return the integer n-th root of x and boolean value that is True\n"
100 "iff the root is exact. x >= 0. n > 0.");
101
102 static PyObject *
GMPy_MPZ_Function_Iroot(PyObject * self,PyObject * args)103 GMPy_MPZ_Function_Iroot(PyObject *self, PyObject *args)
104 {
105 unsigned long n;
106 int exact;
107 MPZ_Object *root = NULL, *tempx = NULL;
108 PyObject *result = NULL;
109
110 if ((PyTuple_GET_SIZE(args) != 2) ||
111 ((!IS_INTEGER(PyTuple_GET_ITEM(args, 0))) ||
112 (!IS_INTEGER(PyTuple_GET_ITEM(args, 1))))) {
113
114 TYPE_ERROR("iroot() requires 'int','int' arguments");
115 return NULL;
116 }
117
118 n = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 1));
119 if ((n == 0) || ((n == (unsigned long)(-1)) && PyErr_Occurred())) {
120 VALUE_ERROR("n must be > 0");
121 return NULL;
122 }
123
124 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL))) {
125 /* LCOV_EXCL_START */
126 return NULL;
127 /* LCOV_EXCL_STOP */
128 }
129
130 if (mpz_sgn(tempx->z) < 0) {
131 VALUE_ERROR("iroot() of negative number");
132 Py_DECREF((PyObject*)tempx);
133 return NULL;
134 }
135
136 if (!(result = PyTuple_New(2)) ||
137 !(root = GMPy_MPZ_New(NULL))) {
138
139 /* LCOV_EXCL_START */
140 Py_DECREF((PyObject*)tempx);
141 Py_XDECREF((PyObject*)root);
142 Py_XDECREF(result);
143 return NULL;
144 /* LCOV_EXCL_STOP */
145 }
146
147 exact = mpz_root(root->z, tempx->z, n);
148 Py_DECREF((PyObject*)tempx);
149
150 PyTuple_SET_ITEM(result, 0, (PyObject*)root);
151 PyTuple_SET_ITEM(result, 1, (PyObject*)PyBool_FromLong(exact));
152 return result;
153 }
154
155 PyDoc_STRVAR(GMPy_doc_mpz_function_iroot_rem,
156 "iroot_rem(x,n) -> (number, number)\n\n"
157 "Return a 2-element tuple (y,r), such that y is the integer n-th\n"
158 "root of x and x=y**n + r. x >= 0. n > 0.");
159
160 static PyObject *
GMPy_MPZ_Function_IrootRem(PyObject * self,PyObject * args)161 GMPy_MPZ_Function_IrootRem(PyObject *self, PyObject *args)
162 {
163 unsigned long n;
164 MPZ_Object *root = NULL, *rem = NULL, *tempx = NULL;
165 PyObject *result = NULL;
166
167 if ((PyTuple_GET_SIZE(args) != 2) ||
168 ((!IS_INTEGER(PyTuple_GET_ITEM(args, 0))) ||
169 (!IS_INTEGER(PyTuple_GET_ITEM(args, 1))))) {
170
171 TYPE_ERROR("iroot_rem() requires 'int','int' arguments");
172 return NULL;
173 }
174
175 n = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 1));
176 if ((n == 0) || ((n == (unsigned long)(-1)) && PyErr_Occurred())) {
177 VALUE_ERROR("n must be > 0");
178 return NULL;
179 }
180
181 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL))) {
182 /* LCOV_EXCL_START */
183 return NULL;
184 /* LCOV_EXCL_STOP */
185 }
186
187 if (mpz_sgn(tempx->z) < 0) {
188 VALUE_ERROR("iroot_rem() of negative number");
189 Py_DECREF((PyObject*)tempx);
190 return NULL;
191 }
192
193 if (!(result = PyTuple_New(2)) ||
194 !(root = GMPy_MPZ_New(NULL)) ||
195 !(rem = GMPy_MPZ_New(NULL))) {
196
197 /* LCOV_EXCL_START */
198 Py_DECREF((PyObject*)tempx);
199 Py_XDECREF(result);
200 Py_XDECREF((PyObject*)root);
201 Py_XDECREF((PyObject*)rem);
202 return NULL;
203 /* LCOV_EXCL_STOP */
204 }
205
206 mpz_rootrem(root->z, rem->z, tempx->z, n);
207 Py_DECREF((PyObject*)tempx);
208
209 PyTuple_SET_ITEM(result, 0, (PyObject*)root);
210 PyTuple_SET_ITEM(result, 1, (PyObject*)rem);
211 return result;
212 }
213
214 PyDoc_STRVAR(GMPy_doc_mpz_method_ceil, "Ceiling of an mpz returns itself.");
215
216 static PyObject *
GMPy_MPZ_Method_Ceil(PyObject * self,PyObject * other)217 GMPy_MPZ_Method_Ceil(PyObject *self, PyObject *other)
218 {
219 Py_INCREF(self);
220 return self;
221 }
222
223 PyDoc_STRVAR(GMPy_doc_mpz_method_floor, "Floor of an mpz returns itself.");
224
225 static PyObject *
GMPy_MPZ_Method_Floor(PyObject * self,PyObject * other)226 GMPy_MPZ_Method_Floor(PyObject *self, PyObject *other)
227 {
228 Py_INCREF(self);
229 return self;
230 }
231
232 PyDoc_STRVAR(GMPy_doc_mpz_method_trunc, "Truncating an mpz returns itself.");
233
234 static PyObject *
GMPy_MPZ_Method_Trunc(PyObject * self,PyObject * other)235 GMPy_MPZ_Method_Trunc(PyObject *self, PyObject *other)
236 {
237 Py_INCREF(self);
238 return self;
239 }
240
241 PyDoc_STRVAR(GMPy_doc_mpz_method_round, "Round an mpz to power of 10.");
242
243 static PyObject *
GMPy_MPZ_Method_Round(PyObject * self,PyObject * args)244 GMPy_MPZ_Method_Round(PyObject *self, PyObject *args)
245 {
246 Py_ssize_t round_digits;
247 MPZ_Object *result;
248 mpz_t temp, rem;
249
250 if (PyTuple_GET_SIZE(args) == 0) {
251 Py_INCREF(self);
252 return self;
253 }
254
255 round_digits = GMPy_Integer_AsSsize_t(PyTuple_GET_ITEM(args, 0));
256 if (round_digits == -1 && PyErr_Occurred()) {
257 TYPE_ERROR("__round__() requires 'int' argument");
258 return NULL;
259 }
260
261 if (round_digits >= 0) {
262 Py_INCREF(self);
263 return self;
264 }
265
266 /* We can now assume round_digits > 0. */
267 round_digits = -round_digits;
268
269 if ((result = GMPy_MPZ_New(NULL))) {
270 if ((unsigned)round_digits >= mpz_sizeinbase(MPZ(self), 10)) {
271 mpz_set_ui(result->z, 0);
272 }
273 else {
274 mpz_init(temp);
275 mpz_init(rem);
276 mpz_ui_pow_ui(temp, 10, round_digits);
277 mpz_fdiv_qr(result->z, rem, MPZ(self), temp);
278 mpz_mul_2exp(rem, rem, 1);
279 if (mpz_cmp(rem, temp) > 0) {
280 mpz_add_ui(result->z, result->z, 1);
281 }
282 else if (mpz_cmp(rem, temp) == 0) {
283 if (mpz_odd_p(result->z)) {
284 mpz_add_ui(result->z, result->z, 1);
285 }
286 }
287 mpz_mul(result->z, result->z, temp);
288 mpz_clear(rem);
289 mpz_clear(temp);
290 }
291 }
292
293 return (PyObject*)result;
294 }
295
296 static int
GMPy_MPZ_NonZero_Slot(MPZ_Object * self)297 GMPy_MPZ_NonZero_Slot(MPZ_Object *self)
298 {
299 return mpz_sgn(self->z) != 0;
300 }
301
302 #if PY_MAJOR_VERSION < 3
303
304 /* hex/oct formatting (mpz-only) */
305
306 static PyObject *
GMPy_MPZ_Oct_Slot(MPZ_Object * self)307 GMPy_MPZ_Oct_Slot(MPZ_Object *self)
308 {
309 return GMPy_PyStr_From_MPZ(self, 8, 0, NULL);
310 }
311
312 static PyObject *
GMPy_MPZ_Hex_Slot(MPZ_Object * self)313 GMPy_MPZ_Hex_Slot(MPZ_Object *self)
314 {
315 return GMPy_PyStr_From_MPZ(self, 16, 0, NULL);
316 }
317 #endif
318
319 /* Miscellaneous gmpy functions */
320
321 PyDoc_STRVAR(GMPy_doc_mpz_function_gcd,
322 "gcd(*integers) -> mpz\n\n"
323 "Return the greatest common divisor of integers.");
324
325 static PyObject *
GMPy_MPZ_Function_GCD(PyObject * self,PyObject * args)326 GMPy_MPZ_Function_GCD(PyObject *self, PyObject *args)
327 {
328 PyObject *arg;
329 MPZ_Object *result = NULL, *tempa = NULL;
330 CTXT_Object *context = NULL;
331 Py_ssize_t i, nargs;
332
333 CHECK_CONTEXT(context);
334
335 if (!(result = GMPy_MPZ_New(NULL))) {
336 /* LCOV_EXCL_START */
337 return NULL;
338 /* LCOV_EXCL_STOP */
339 }
340
341 nargs = PyTuple_Size(args);
342
343 for (i = 0; i < nargs; i++) {
344 arg = PyTuple_GET_ITEM(args, i);
345
346 if MPZ_Check(arg) {
347 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
348 mpz_gcd(result->z, MPZ(arg), result->z);
349 GMPY_MAYBE_END_ALLOW_THREADS(context);\
350 } else {
351 if (!(tempa = GMPy_MPZ_From_Integer(arg, NULL))) {
352 TYPE_ERROR("gcd() requires 'mpz' arguments");
353 Py_XDECREF((PyObject*)tempa);
354 Py_DECREF((PyObject*)result);
355 return NULL;
356 }
357
358 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
359 mpz_gcd(result->z, tempa->z, result->z);
360 GMPY_MAYBE_END_ALLOW_THREADS(context);
361 Py_DECREF((PyObject*)tempa);
362 }
363 }
364 return (PyObject*)result;
365 }
366
367 PyDoc_STRVAR(GMPy_doc_mpz_function_lcm,
368 "lcm(*integers) -> mpz\n\n"
369 "Return the lowest common multiple of integers.");
370
371 static PyObject *
GMPy_MPZ_Function_LCM(PyObject * self,PyObject * args)372 GMPy_MPZ_Function_LCM(PyObject *self, PyObject *args)
373 {
374 PyObject *arg;
375 MPZ_Object *result = NULL, *tempa = NULL;
376 CTXT_Object *context = NULL;
377 Py_ssize_t i, nargs;
378
379 CHECK_CONTEXT(context);
380
381 if (!(result = GMPy_MPZ_New(NULL))) {
382 /* LCOV_EXCL_START */
383 return NULL;
384 /* LCOV_EXCL_STOP */
385 }
386
387 mpz_set_ui(result->z, 1);
388 nargs = PyTuple_Size(args);
389
390 for (i = 0; i < nargs; i++) {
391 arg = PyTuple_GET_ITEM(args, i);
392
393 if MPZ_Check(arg) {
394 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
395 mpz_lcm(result->z, MPZ(arg), result->z);
396 GMPY_MAYBE_END_ALLOW_THREADS(context);
397 } else {
398 if (!(tempa = GMPy_MPZ_From_Integer(arg, NULL))) {
399 TYPE_ERROR("lcm() requires 'mpz' arguments");
400 Py_XDECREF((PyObject*)tempa);
401 Py_DECREF((PyObject*)result);
402 return NULL;
403 }
404
405 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
406 mpz_lcm(result->z, tempa->z, result->z);
407 GMPY_MAYBE_END_ALLOW_THREADS(context);
408 Py_DECREF((PyObject*)tempa);
409 }
410 }
411 return (PyObject*)result;
412 }
413
414 PyDoc_STRVAR(GMPy_doc_mpz_function_gcdext,
415 "gcdext(a, b) - > tuple\n\n"
416 "Return a 3-element tuple (g,s,t) such that\n"
417 " g == gcd(a,b) and g == a*s + b*t");
418
419 static PyObject *
GMPy_MPZ_Function_GCDext(PyObject * self,PyObject * args)420 GMPy_MPZ_Function_GCDext(PyObject *self, PyObject *args)
421 {
422 PyObject *arg0, *arg1, *result = NULL;
423 MPZ_Object *g = NULL, *s = NULL, *t = NULL, *tempa = NULL, *tempb = NULL;
424 CTXT_Object *context = NULL;
425
426 CHECK_CONTEXT(context);
427
428 if(PyTuple_GET_SIZE(args) != 2) {
429 TYPE_ERROR("gcdext() requires 'mpz','mpz' arguments");
430 return NULL;
431 }
432
433 if (!(result = PyTuple_New(3)) ||
434 !(g = GMPy_MPZ_New(NULL)) ||
435 !(s = GMPy_MPZ_New(NULL)) ||
436 !(t = GMPy_MPZ_New(NULL))) {
437
438 /* LCOV_EXCL_START */
439 Py_XDECREF((PyObject*)g);
440 Py_XDECREF((PyObject*)s);
441 Py_XDECREF((PyObject*)t);
442 Py_XDECREF(result);
443 return NULL;
444 /* LCOV_EXCL_STOP */
445 }
446
447 arg0 = PyTuple_GET_ITEM(args, 0);
448 arg1 = PyTuple_GET_ITEM(args, 1);
449
450 if (MPZ_Check(arg0) && MPZ_Check(arg1)) {
451 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
452 mpz_gcdext(g->z, s->z, t->z, MPZ(arg0), MPZ(arg1));
453 GMPY_MAYBE_END_ALLOW_THREADS(context);
454 }
455 else {
456 if(!(tempa = GMPy_MPZ_From_Integer(arg0, NULL)) ||
457 !(tempb = GMPy_MPZ_From_Integer(arg1, NULL))) {
458
459 TYPE_ERROR("gcdext() requires 'mpz','mpz' arguments");
460 Py_XDECREF((PyObject*)tempa);
461 Py_XDECREF((PyObject*)tempb);
462 Py_DECREF((PyObject*)g);
463 Py_DECREF((PyObject*)s);
464 Py_DECREF((PyObject*)t);
465 Py_DECREF(result);
466 return NULL;
467 }
468 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
469 mpz_gcdext(g->z, s->z, t->z, tempa->z, tempb->z);
470 GMPY_MAYBE_END_ALLOW_THREADS(context);
471 Py_DECREF((PyObject*)tempa);
472 Py_DECREF((PyObject*)tempb);
473 }
474 PyTuple_SET_ITEM(result, 0, (PyObject*)g);
475 PyTuple_SET_ITEM(result, 1, (PyObject*)s);
476 PyTuple_SET_ITEM(result, 2, (PyObject*)t);
477 return result;
478 }
479
480 PyDoc_STRVAR(GMPy_doc_mpz_function_divm,
481 "divm(a, b, m) -> mpz\n\n"
482 "Return x such that b*x == a mod m. Raises a ZeroDivisionError\n"
483 "exception if no such value x exists.");
484
485 static PyObject *
GMPy_MPZ_Function_Divm(PyObject * self,PyObject * args)486 GMPy_MPZ_Function_Divm(PyObject *self, PyObject *args)
487 {
488 MPZ_Object *result = NULL, *num = NULL, *den = NULL, *mod = NULL;
489 mpz_t numz, denz, modz, gcdz;
490 int ok = 0;
491 CTXT_Object *context = NULL;
492
493 CHECK_CONTEXT(context);
494
495 if (PyTuple_GET_SIZE(args) != 3) {
496 TYPE_ERROR("divm() requires 'mpz','mpz','mpz' arguments");
497 return NULL;
498 }
499
500 if (!(result = GMPy_MPZ_New(NULL))) {
501 /* LCOV_EXCL_START */
502 return NULL;
503 /* LCOV_EXCL_STOP */
504 }
505
506 if (!(num = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL)) ||
507 !(den = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 1), NULL)) ||
508 !(mod = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 2), NULL))) {
509
510 TYPE_ERROR("divm() requires 'mpz','mpz','mpz' arguments");
511 Py_XDECREF((PyObject*)num);
512 Py_XDECREF((PyObject*)den);
513 Py_XDECREF((PyObject*)mod);
514 Py_DECREF((PyObject*)result);
515 return NULL;
516 }
517
518 /* Make copies so we don't destroy the input. */
519 mpz_init(numz);
520 mpz_init(denz);
521 mpz_init(modz);
522 mpz_set(numz, num->z);
523 mpz_set(denz, den->z);
524 mpz_set(modz, mod->z);
525 Py_DECREF((PyObject*)num);
526 Py_DECREF((PyObject*)den);
527 Py_DECREF((PyObject*)mod);
528
529
530 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
531 ok = mpz_invert(result->z, denz, modz);
532 GMPY_MAYBE_END_ALLOW_THREADS(context);
533
534 if (!ok) {
535 /* last-ditch attempt: do num, den AND mod have a gcd>1 ? */
536 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
537 mpz_init(gcdz);
538 mpz_gcd(gcdz, numz, denz);
539 mpz_gcd(gcdz, gcdz, modz);
540 mpz_divexact(numz, numz, gcdz);
541 mpz_divexact(denz, denz, gcdz);
542 mpz_divexact(modz, modz, gcdz);
543 mpz_clear(gcdz);
544 ok = mpz_invert(result->z, denz, modz);
545 GMPY_MAYBE_END_ALLOW_THREADS(context);
546 }
547
548 if (ok) {
549 GMPY_MAYBE_BEGIN_ALLOW_THREADS(context);
550 mpz_mul(result->z, result->z, numz);
551 mpz_mod(result->z, result->z, modz);
552 mpz_clear(numz);
553 mpz_clear(denz);
554 mpz_clear(modz);
555 GMPY_MAYBE_END_ALLOW_THREADS(context);
556 return (PyObject*)result;
557 }
558 else {
559 ZERO_ERROR("not invertible");
560 mpz_clear(numz);
561 mpz_clear(denz);
562 mpz_clear(modz);
563 Py_DECREF((PyObject*)result);
564 return NULL;
565 }
566 }
567
568 PyDoc_STRVAR(GMPy_doc_mpz_function_fac,
569 "fac(n) -> mpz\n\n"
570 "Return the exact factorial of n.\n\n"
571 "See factorial(n) to get the floating-point approximation.");
572
573 static PyObject *
GMPy_MPZ_Function_Fac(PyObject * self,PyObject * other)574 GMPy_MPZ_Function_Fac(PyObject *self, PyObject *other)
575 {
576 MPZ_Object *result = NULL;
577 unsigned long n;
578
579 n = GMPy_Integer_AsUnsignedLong(other);
580 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
581 return NULL;
582 }
583
584 if ((result = GMPy_MPZ_New(NULL))) {
585 mpz_fac_ui(result->z, n);
586 }
587 return (PyObject*)result;
588 }
589
590 PyDoc_STRVAR(GMPy_doc_mpz_function_double_fac,
591 "double_fac(n) -> mpz\n\n"
592 "Return the exact double factorial (n!!) of n. The double\n"
593 "factorial is defined as n*(n-2)*(n-4)...");
594
595 static PyObject *
GMPy_MPZ_Function_DoubleFac(PyObject * self,PyObject * other)596 GMPy_MPZ_Function_DoubleFac(PyObject *self, PyObject *other)
597 {
598 MPZ_Object *result = NULL;
599 unsigned long n;
600
601 n = GMPy_Integer_AsUnsignedLong(other);
602 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
603 return NULL;
604 }
605
606 if ((result = GMPy_MPZ_New(NULL))) {
607 mpz_2fac_ui(result->z, n);
608 }
609 return (PyObject*)result;
610 }
611
612 PyDoc_STRVAR(GMPy_doc_mpz_function_primorial,
613 "primorial(n) -> mpz\n\n"
614 "Return the product of all positive prime numbers less than or"
615 "equal to n.");
616
617 static PyObject *
GMPy_MPZ_Function_Primorial(PyObject * self,PyObject * other)618 GMPy_MPZ_Function_Primorial(PyObject *self, PyObject *other)
619 {
620 MPZ_Object *result = NULL;
621 unsigned long n;
622
623 n = GMPy_Integer_AsUnsignedLong(other);
624 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
625 return NULL;
626 }
627
628 if ((result = GMPy_MPZ_New(NULL))) {
629 mpz_primorial_ui(result->z, n);
630 }
631 return (PyObject*)result;
632 }
633
634 PyDoc_STRVAR(GMPy_doc_mpz_function_multi_fac,
635 "multi_fac(n,m) -> mpz\n\n"
636 "Return the exact m-multi factorial of n. The m-multi"
637 "factorial is defined as n*(n-m)*(n-2m)...");
638
639 static PyObject *
GMPy_MPZ_Function_MultiFac(PyObject * self,PyObject * args)640 GMPy_MPZ_Function_MultiFac(PyObject *self, PyObject *args)
641 {
642 MPZ_Object *result = NULL;
643 unsigned long n, m;
644
645 if (PyTuple_GET_SIZE(args) != 2) {
646 TYPE_ERROR("multi_fac() requires 2 integer arguments");
647 return NULL;
648 }
649
650 n = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 0));
651 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
652 return NULL;
653 }
654
655 m = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 1));
656 if (m == (unsigned long)(-1) && PyErr_Occurred()) {
657 return NULL;
658 }
659
660 if ((result = GMPy_MPZ_New(NULL))) {
661 mpz_mfac_uiui(result->z, n, m);
662 }
663 return (PyObject*)result;
664 }
665
666 PyDoc_STRVAR(GMPy_doc_mpz_function_fib,
667 "fib(n) -> mpz\n\n"
668 "Return the n-th Fibonacci number.");
669
670 static PyObject *
GMPy_MPZ_Function_Fib(PyObject * self,PyObject * other)671 GMPy_MPZ_Function_Fib(PyObject *self, PyObject *other)
672 {
673 MPZ_Object *result = NULL;
674 unsigned long n;
675
676 n = GMPy_Integer_AsUnsignedLong(other);
677 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
678 return NULL;
679 }
680 if ((result = GMPy_MPZ_New(NULL))) {
681 mpz_fib_ui(result->z, n);
682 }
683 return (PyObject*)result;
684 }
685
686 PyDoc_STRVAR(GMPy_doc_mpz_function_fib2,
687 "fib2(n) -> tuple\n\n"
688 "Return a 2-tuple with the (n-1)-th and n-th Fibonacci numbers.");
689
690 static PyObject *
GMPy_MPZ_Function_Fib2(PyObject * self,PyObject * other)691 GMPy_MPZ_Function_Fib2(PyObject *self, PyObject *other)
692 {
693 PyObject *result = NULL;
694 MPZ_Object *fib1 = NULL, *fib2 = NULL;
695 unsigned long n;
696
697 n = GMPy_Integer_AsUnsignedLong(other);
698 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
699 return NULL;
700 }
701
702 if (!(result = PyTuple_New(2)) ||
703 !(fib1 = GMPy_MPZ_New(NULL)) ||
704 !(fib2 = GMPy_MPZ_New(NULL))) {
705
706 /* LCOV_EXCL_START */
707 Py_XDECREF(result);
708 Py_XDECREF((PyObject*)fib1);
709 Py_XDECREF((PyObject*)fib2);
710 result = NULL;
711 /* LCOV_EXCL_STOP */
712 }
713
714 mpz_fib2_ui(fib1->z, fib2->z, n);
715 PyTuple_SET_ITEM(result, 0, (PyObject*)fib1);
716 PyTuple_SET_ITEM(result, 1, (PyObject*)fib2);
717 return (PyObject*)result;
718 }
719
720 PyDoc_STRVAR(GMPy_doc_mpz_function_lucas,
721 "lucas(n) -> mpz\n\n"
722 "Return the n-th Lucas number.");
723
724 static PyObject *
GMPy_MPZ_Function_Lucas(PyObject * self,PyObject * other)725 GMPy_MPZ_Function_Lucas(PyObject *self, PyObject *other)
726 {
727 MPZ_Object *result = NULL;
728 unsigned long n;
729
730 n = GMPy_Integer_AsUnsignedLong(other);
731 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
732 return NULL;
733 }
734
735 if ((result = GMPy_MPZ_New(NULL))) {
736 mpz_lucnum_ui(result->z, n);
737 }
738 return (PyObject*)result;
739 }
740
741 PyDoc_STRVAR(GMPy_doc_mpz_function_lucas2,
742 "lucas2(n) -> tuple\n\n"
743 "Return a 2-tuple with the (n-1)-th and n-th Lucas numbers.");
744
745 static PyObject *
GMPy_MPZ_Function_Lucas2(PyObject * self,PyObject * other)746 GMPy_MPZ_Function_Lucas2(PyObject *self, PyObject *other)
747 {
748 PyObject *result = NULL;
749 MPZ_Object *luc1 = NULL, *luc2 = NULL;
750 unsigned long n;
751
752 n = GMPy_Integer_AsUnsignedLong(other);
753 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
754 return NULL;
755 }
756
757 if (!(result = PyTuple_New(2)) ||
758 !(luc1 = GMPy_MPZ_New(NULL)) ||
759 !(luc2 = GMPy_MPZ_New(NULL))) {
760
761 /* LCOV_EXCL_START */
762 Py_XDECREF(result);
763 Py_XDECREF((PyObject*)luc1);
764 Py_XDECREF((PyObject*)luc2);
765 result = NULL;
766 /* LCOV_EXCL_STOP */
767 }
768
769 mpz_lucnum2_ui(luc1->z, luc2->z, n);
770 PyTuple_SET_ITEM(result, 0, (PyObject*)luc1);
771 PyTuple_SET_ITEM(result, 1, (PyObject*)luc2);
772 return result;
773 }
774
775 PyDoc_STRVAR(GMPy_doc_mpz_function_bincoef,
776 "bincoef(n, k) -> mpz\n\n"
777 "Return the binomial coefficient ('n choose k'). k >= 0.");
778
779 PyDoc_STRVAR(GMPy_doc_mpz_function_comb,
780 "comb(n, k) -> mpz\n\n"
781 "Return the number of combinations of 'n things, taking k at a\n"
782 "time'. k >= 0. Same as bincoef(n, k)");
783
784 static PyObject *
GMPy_MPZ_Function_Bincoef(PyObject * self,PyObject * args)785 GMPy_MPZ_Function_Bincoef(PyObject *self, PyObject *args)
786 {
787 MPZ_Object *result = NULL, *tempx;
788 unsigned long n, k;
789
790 if (PyTuple_GET_SIZE(args) != 2) {
791 TYPE_ERROR("bincoef() requires two integer arguments");
792 return NULL;
793 }
794
795 if (!(result = GMPy_MPZ_New(NULL))) {
796 /* LCOV_EXCL_START */
797 return NULL;
798 /* LCOV_EXCL_STOP */
799 }
800
801 k = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 1));
802 if (k == (unsigned long)(-1) && PyErr_Occurred()) {
803 Py_DECREF((PyObject*)result);
804 return NULL;
805 }
806
807 n = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 0));
808 if (n == (unsigned long)(-1) && PyErr_Occurred()) {
809 /* Since we plan to skip the else clause and continue,
810 * we need to clear the error since we aren't acting on it.
811 */
812 PyErr_Clear();
813 }
814 else {
815 /* Use mpz_bin_uiui which should be faster. */
816 mpz_bin_uiui(result->z, n, k);
817 return (PyObject*)result;
818 }
819
820 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL))) {
821 Py_DECREF((PyObject*)result);
822 return NULL;
823 }
824
825 mpz_bin_ui(result->z, tempx->z, k);
826 Py_DECREF((PyObject*)tempx);
827 return (PyObject*)result;
828 }
829
830 PyDoc_STRVAR(GMPy_doc_mpz_function_isqrt,
831 "isqrt(x) -> mpz\n\n"
832 "Return the integer square root of an integer x. x >= 0.");
833
834 static PyObject *
GMPy_MPZ_Function_Isqrt(PyObject * self,PyObject * other)835 GMPy_MPZ_Function_Isqrt(PyObject *self, PyObject *other)
836 {
837 MPZ_Object *result;
838
839 if (CHECK_MPZANY(other)) {
840 if (mpz_sgn(MPZ(other)) < 0) {
841 VALUE_ERROR("isqrt() of negative number");
842 return NULL;
843 }
844 if ((result = GMPy_MPZ_New(NULL))) {
845 mpz_sqrt(result->z, MPZ(other));
846 }
847 }
848 else {
849 if (!(result = GMPy_MPZ_From_Integer(other, NULL))) {
850 TYPE_ERROR("isqrt() requires 'mpz' argument");
851 return NULL;
852 }
853 if (mpz_sgn(result->z) < 0) {
854 VALUE_ERROR("isqrt() of negative number");
855 Py_DECREF((PyObject*)result);
856 return NULL;
857 }
858 mpz_sqrt(result->z, result->z);
859 }
860 return (PyObject*)result;
861 }
862
863 PyDoc_STRVAR(GMPy_doc_mpz_function_isqrt_rem,
864 "isqrt_rem(x) -> tuple\n\n"
865 "Return a 2-element tuple (s,t) such that s=isqrt(x) and t=x-s*s.\n"
866 "x >=0.");
867
868 static PyObject *
GMPy_MPZ_Function_IsqrtRem(PyObject * self,PyObject * other)869 GMPy_MPZ_Function_IsqrtRem(PyObject *self, PyObject *other)
870 {
871 MPZ_Object *root = NULL, *rem = NULL, *temp = NULL;
872 PyObject *result;
873
874 if (!(temp = GMPy_MPZ_From_Integer(other, NULL))) {
875 TYPE_ERROR("isqrt_rem() requires 'mpz' argument");
876 return NULL;
877 }
878
879 if (mpz_sgn(temp->z) < 0) {
880 VALUE_ERROR("isqrt_rem() of negative number");
881 Py_DECREF((PyObject*)temp);
882 return NULL;
883 }
884
885 if (!(result = PyTuple_New(2)) ||
886 !(root = GMPy_MPZ_New(NULL)) ||
887 !(rem = GMPy_MPZ_New(NULL))) {
888
889 /* LCOV_EXCL_START */
890 Py_DECREF((PyObject*)temp);
891 Py_XDECREF(result);
892 Py_XDECREF((PyObject*)root);
893 Py_XDECREF((PyObject*)rem);
894 return NULL;
895 /* LCOV_EXCL_STOP */
896 }
897
898 mpz_sqrtrem(root->z, rem->z, temp->z);
899 Py_DECREF((PyObject*)temp);
900 PyTuple_SET_ITEM(result, 0, (PyObject*)root);
901 PyTuple_SET_ITEM(result, 1, (PyObject*)rem);
902 return result;
903 }
904
905 PyDoc_STRVAR(GMPy_doc_mpz_function_remove,
906 "remove(x, f) -> tuple\n\n"
907 "Return a 2-element tuple (y,m) such that x=y*(f**m) and f does\n"
908 "not divide y. Remove the factor f from x as many times as\n"
909 "possible. m is the multiplicity f in x. f > 1.");
910
911 static PyObject *
GMPy_MPZ_Function_Remove(PyObject * self,PyObject * args)912 GMPy_MPZ_Function_Remove(PyObject *self, PyObject *args)
913 {
914 MPZ_Object *result = NULL, *tempx = NULL, *tempf = NULL;
915 PyObject *x, *f;
916 size_t multiplicity;
917
918 if (PyTuple_GET_SIZE(args) != 2) {
919 TYPE_ERROR("remove() requires 'mpz','mpz' arguments");
920 return NULL;
921 }
922
923 if (!(result = GMPy_MPZ_New(NULL))) {
924 /* LCOV_EXCL_START */
925 return NULL;
926 /* LCOV_EXCL_STOP */
927 }
928
929 x = PyTuple_GET_ITEM(args, 0);
930 f = PyTuple_GET_ITEM(args, 1);
931
932 if (MPZ_Check(x) && MPZ_Check(f)) {
933 if (mpz_cmp_si(MPZ(f), 2) < 0) {
934 VALUE_ERROR("factor must be > 1");
935 Py_DECREF((PyObject*)result);
936 return NULL;
937 }
938 multiplicity = mpz_remove(result->z, MPZ(x), MPZ(f));
939 return Py_BuildValue("(Nk)", result, multiplicity);
940 }
941 else {
942
943
944 if (!(tempx = GMPy_MPZ_From_Integer(x, NULL)) ||
945 !(tempf = GMPy_MPZ_From_Integer(f, NULL))) {
946
947 TYPE_ERROR("remove() requires 'mpz','mpz' arguments");
948 Py_XDECREF((PyObject*)tempx);
949 Py_XDECREF((PyObject*)tempf);
950 Py_DECREF((PyObject*)result);
951 return NULL;
952 }
953 if (mpz_cmp_si(MPZ(tempf), 2) < 0) {
954 VALUE_ERROR("factor must be > 1");
955 Py_DECREF((PyObject*)tempx);
956 Py_DECREF((PyObject*)tempf);
957 Py_DECREF((PyObject*)result);
958 return NULL;
959 }
960 multiplicity = mpz_remove(result->z, tempx->z, tempf->z);
961 Py_DECREF((PyObject*)tempx);
962 Py_DECREF((PyObject*)tempf);
963 return Py_BuildValue("(Nk)", result, multiplicity);
964 }
965 }
966
967 PyDoc_STRVAR(GMPy_doc_mpz_function_invert,
968 "invert(x, m) -> mpz\n\n"
969 "Return y such that x*y == 1 modulo m. Raises ZeroDivisionError if no\n"
970 "inverse exists.");
971
972 static PyObject *
GMPy_MPZ_Function_Invert(PyObject * self,PyObject * args)973 GMPy_MPZ_Function_Invert(PyObject *self, PyObject *args)
974 {
975 PyObject *x, *y;
976 MPZ_Object *result = NULL, *tempx = NULL, *tempy = NULL;
977 int success;
978
979 if (PyTuple_GET_SIZE(args) != 2) {
980 TYPE_ERROR("invert() requires 'mpz','mpz' arguments");
981 return NULL;
982 }
983
984 if (!(result = GMPy_MPZ_New(NULL))) {
985 /* LCOV_EXCL_START */
986 return NULL;
987 /* LCOV_EXCL_STOP */
988 }
989
990 x = PyTuple_GET_ITEM(args, 0);
991 y = PyTuple_GET_ITEM(args, 1);
992
993 if (MPZ_Check(x) && MPZ_Check(y)) {
994 if (mpz_sgn(MPZ(y)) == 0) {
995 ZERO_ERROR("invert() division by 0");
996 Py_DECREF((PyObject*)result);
997 return NULL;
998 }
999 success = mpz_invert(result->z, MPZ(x), MPZ(y));
1000 if (!success) {
1001 ZERO_ERROR("invert() no inverse exists");
1002 Py_DECREF((PyObject*)result);
1003 return NULL;
1004 }
1005 }
1006 else {
1007
1008
1009 if (!(tempx = GMPy_MPZ_From_Integer(x, NULL)) ||
1010 !(tempy = GMPy_MPZ_From_Integer(y, NULL))) {
1011
1012 TYPE_ERROR("invert() requires 'mpz','mpz' arguments");
1013 Py_XDECREF((PyObject*)tempx);
1014 Py_XDECREF((PyObject*)tempy);
1015 Py_DECREF((PyObject*)result);
1016 return NULL;
1017 }
1018 if (mpz_sgn(tempy->z) == 0) {
1019 ZERO_ERROR("invert() division by 0");
1020 Py_DECREF((PyObject*)tempx);
1021 Py_DECREF((PyObject*)tempy);
1022 Py_DECREF(result);
1023 return NULL;
1024 }
1025 success = mpz_invert(result->z, tempx->z, tempy->z);
1026 Py_DECREF((PyObject*)tempx);
1027 Py_DECREF((PyObject*)tempy);
1028 if (!success) {
1029 ZERO_ERROR("invert() no inverse exists");
1030 Py_DECREF((PyObject*)result);
1031 return NULL;
1032 }
1033 }
1034 return (PyObject*)result;
1035 }
1036
1037 PyDoc_STRVAR(GMPy_doc_mpz_function_divexact,
1038 "divexact(x, y) -> mpz\n\n"
1039 "Return the quotient of x divided by y. Faster than standard\n"
1040 "division but requires the remainder is zero!");
1041
1042 static PyObject *
GMPy_MPZ_Function_Divexact(PyObject * self,PyObject * args)1043 GMPy_MPZ_Function_Divexact(PyObject *self, PyObject *args)
1044 {
1045 PyObject *x, *y;
1046 MPZ_Object *result, *tempx= NULL, *tempy = NULL;
1047
1048 if(PyTuple_GET_SIZE(args) != 2) {
1049 TYPE_ERROR("divexact() requires 'mpz','mpz' arguments");
1050 return NULL;
1051 }
1052
1053 if (!(result = GMPy_MPZ_New(NULL))) {
1054 /* LCOV_EXCL_START */
1055 return NULL;
1056 /* LCOV_EXCL_STOP */
1057 }
1058
1059 x = PyTuple_GET_ITEM(args, 0);
1060 y = PyTuple_GET_ITEM(args, 1);
1061
1062 if (MPZ_Check(x) && MPZ_Check(y)) {
1063 if (mpz_sgn(MPZ(y)) == 0) {
1064 ZERO_ERROR("divexact() division by 0");
1065 Py_DECREF((PyObject*)result);
1066 return NULL;
1067 }
1068 mpz_divexact(result->z, MPZ(x), MPZ(y));
1069 }
1070 else {
1071 if (!(tempx = GMPy_MPZ_From_Integer(x, NULL)) ||
1072 !(tempy = GMPy_MPZ_From_Integer(y, NULL))) {
1073
1074 TYPE_ERROR("divexact() requires 'mpz','mpz' arguments");
1075 Py_XDECREF((PyObject*)tempx);
1076 Py_XDECREF((PyObject*)tempy);
1077 Py_DECREF((PyObject*)result);
1078 return NULL;
1079 }
1080 if (mpz_sgn(MPZ(tempy)) == 0) {
1081 ZERO_ERROR("divexact() division by 0");
1082 Py_DECREF((PyObject*)tempx);
1083 Py_DECREF((PyObject*)tempy);
1084 Py_DECREF((PyObject*)result);
1085 return NULL;
1086 }
1087 mpz_divexact(result->z, tempx->z, tempy->z);
1088 Py_DECREF((PyObject*)tempx);
1089 Py_DECREF((PyObject*)tempy);
1090 }
1091 return (PyObject*)result;
1092 }
1093
1094 PyDoc_STRVAR(GMPy_doc_mpz_function_is_square,
1095 "is_square(x) -> bool\n\n"
1096 "Returns True if x is a perfect square, else return False.");
1097
1098 static PyObject *
GMPy_MPZ_Function_IsSquare(PyObject * self,PyObject * other)1099 GMPy_MPZ_Function_IsSquare(PyObject *self, PyObject *other)
1100 {
1101 int res;
1102 MPZ_Object *tempx;
1103
1104 if (MPZ_Check(other)) {
1105 res = mpz_perfect_square_p(MPZ(other));
1106 }
1107 else {
1108 if (!(tempx = GMPy_MPZ_From_Integer(other, NULL))) {
1109 TYPE_ERROR("is_square() requires 'mpz' argument");
1110 return NULL;
1111 }
1112 else {
1113 res = mpz_perfect_square_p(tempx->z);
1114 Py_DECREF((PyObject*)tempx);
1115 }
1116 }
1117
1118 if (res)
1119 Py_RETURN_TRUE;
1120 else
1121 Py_RETURN_FALSE;
1122 }
1123
1124 PyDoc_STRVAR(GMPy_doc_mpz_method_is_square,
1125 "x.is_square() -> bool\n\n"
1126 "Returns True if x is a perfect square, else return False.");
1127
1128 static PyObject *
GMPy_MPZ_Method_IsSquare(PyObject * self,PyObject * other)1129 GMPy_MPZ_Method_IsSquare(PyObject *self, PyObject *other)
1130 {
1131 int res;
1132
1133 res = mpz_perfect_square_p(MPZ(self));
1134
1135 if (res)
1136 Py_RETURN_TRUE;
1137 else
1138 Py_RETURN_FALSE;
1139 }
1140
1141 PyDoc_STRVAR(GMPy_doc_mpz_function_is_divisible,
1142 "is_divisible(x, d) -> bool\n\n"
1143 "Returns True if x is divisible by d, else return False.");
1144
1145 static PyObject *
GMPy_MPZ_Function_IsDivisible(PyObject * self,PyObject * args)1146 GMPy_MPZ_Function_IsDivisible(PyObject *self, PyObject *args)
1147 {
1148 unsigned long temp;
1149 int res = 0;
1150 MPZ_Object *tempx, *tempd;
1151
1152 if (PyTuple_GET_SIZE(args) != 2) {
1153 TYPE_ERROR("is_divisible() requires 2 integer arguments");
1154 return NULL;
1155 }
1156
1157 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL))) {
1158 return NULL;
1159 }
1160
1161 temp = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 1));
1162 if (temp == (unsigned long)-1 && PyErr_Occurred()) {
1163 PyErr_Clear();
1164 /* Implement mpz_divisible_p here. */
1165
1166 if (!(tempd = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 1), NULL))) {
1167 TYPE_ERROR("is_divisible() requires 2 integer arguments");
1168 Py_DECREF((PyObject*)tempx);
1169 return NULL;
1170 }
1171
1172 res = mpz_divisible_p(tempx->z, tempd->z);
1173 Py_DECREF((PyObject*)tempx);
1174 Py_DECREF((PyObject*)tempd);
1175 }
1176 else {
1177 /* Implement mpz_divisible_ui_p here. */
1178
1179 res = mpz_divisible_ui_p(tempx->z, temp);
1180 Py_DECREF((PyObject*)tempx);
1181 }
1182 if (res)
1183 Py_RETURN_TRUE;
1184 else
1185 Py_RETURN_FALSE;
1186 }
1187
1188 PyDoc_STRVAR(GMPy_doc_mpz_method_is_divisible,
1189 "x.is_divisible(d) -> bool\n\n"
1190 "Returns True if x is divisible by d, else return False.");
1191
1192 static PyObject *
GMPy_MPZ_Method_IsDivisible(PyObject * self,PyObject * other)1193 GMPy_MPZ_Method_IsDivisible(PyObject *self, PyObject *other)
1194 {
1195 unsigned long temp;
1196 int res;
1197 MPZ_Object *tempd;
1198
1199 temp = GMPy_Integer_AsUnsignedLong(other);
1200 if (temp == (unsigned long)-1 && PyErr_Occurred()) {
1201 PyErr_Clear();
1202 /* Implement mpz_divisible_p here. */
1203
1204 if (!(tempd = GMPy_MPZ_From_Integer(other, NULL))) {
1205 TYPE_ERROR("is_divisible() requires 2 integer arguments");
1206 return NULL;
1207 }
1208
1209 res = mpz_divisible_p(MPZ(self), tempd->z);
1210 Py_DECREF((PyObject*)tempd);
1211 }
1212 else {
1213 /* Implement mpz_divisible_ui_p here. */
1214
1215 res = mpz_divisible_ui_p(MPZ(self), temp);
1216 }
1217 if (res)
1218 Py_RETURN_TRUE;
1219 else
1220 Py_RETURN_FALSE;
1221 }
1222
1223 PyDoc_STRVAR(GMPy_doc_mpz_function_is_congruent,
1224 "is_congruent(x, y, m) -> bool\n\n"
1225 "Returns True if x is congruent to y modulo m, else return False.");
1226
1227 static PyObject *
GMPy_MPZ_Function_IsCongruent(PyObject * self,PyObject * args)1228 GMPy_MPZ_Function_IsCongruent(PyObject *self, PyObject *args)
1229 {
1230 int res;
1231 MPZ_Object *tempx = NULL, *tempy = NULL, *tempm = NULL;
1232
1233 if (PyTuple_GET_SIZE(args) != 3) {
1234 TYPE_ERROR("is_congruent() requires 3 integer arguments");
1235 return NULL;
1236 }
1237
1238 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL)) ||
1239 !(tempy = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 1), NULL)) ||
1240 !(tempm = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 2), NULL))) {
1241
1242 Py_XDECREF((PyObject*)tempx);
1243 Py_XDECREF((PyObject*)tempy);
1244 Py_XDECREF((PyObject*)tempm);
1245 TYPE_ERROR("is_congruent() requires 3 integer arguments");
1246 return NULL;
1247 }
1248
1249 res = mpz_congruent_p(tempx->z, tempy->z, tempm->z);
1250 Py_DECREF((PyObject*)tempx);
1251 Py_DECREF((PyObject*)tempy);
1252 Py_DECREF((PyObject*)tempm);
1253 if (res)
1254 Py_RETURN_TRUE;
1255 else
1256 Py_RETURN_FALSE;
1257 }
1258
1259 PyDoc_STRVAR(GMPy_doc_mpz_method_is_congruent,
1260 "x.is_congruent(y, m) -> bool\n\n"
1261 "Returns True if x is congruent to y modulo m, else return False.");
1262
1263 static PyObject *
GMPy_MPZ_Method_IsCongruent(PyObject * self,PyObject * args)1264 GMPy_MPZ_Method_IsCongruent(PyObject *self, PyObject *args)
1265 {
1266 int res;
1267 MPZ_Object *tempy = NULL, *tempm = NULL;
1268
1269 if (PyTuple_GET_SIZE(args) != 2) {
1270 TYPE_ERROR("is_congruent() requires 2 integer arguments");
1271 return NULL;
1272 }
1273
1274 if (!(tempy = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL)) ||
1275 !(tempm = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 1), NULL))) {
1276
1277 Py_XDECREF((PyObject*)tempy);
1278 Py_XDECREF((PyObject*)tempm);
1279 TYPE_ERROR("is_congruent() requires 2 integer arguments");
1280 return NULL;
1281 }
1282
1283 res = mpz_congruent_p(MPZ(self), tempy->z, tempm->z);
1284 Py_DECREF((PyObject*)tempy);
1285 Py_DECREF((PyObject*)tempm);
1286 if (res)
1287 Py_RETURN_TRUE;
1288 else
1289 Py_RETURN_FALSE;
1290 }
1291
1292 PyDoc_STRVAR(GMPy_doc_mpz_function_is_power,
1293 "is_power(x) -> bool\n\n"
1294 "Return True if x is a perfect power (there exists a y and an\n"
1295 "n > 1, such that x=y**n), else return False.");
1296
1297 static PyObject *
GMPy_MPZ_Function_IsPower(PyObject * self,PyObject * other)1298 GMPy_MPZ_Function_IsPower(PyObject *self, PyObject *other)
1299 {
1300 int res;
1301 MPZ_Object* tempx;
1302
1303 if (MPZ_Check(other)) {
1304 res = mpz_perfect_power_p(MPZ(other));
1305 }
1306 else {
1307 if (!(tempx = GMPy_MPZ_From_Integer(other, NULL))) {
1308 TYPE_ERROR("is_power() requires 'mpz' argument");
1309 return NULL;
1310 }
1311 else {
1312 res = mpz_perfect_power_p(tempx->z);
1313 Py_DECREF((PyObject*)tempx);
1314 }
1315 }
1316
1317 if (res)
1318 Py_RETURN_TRUE;
1319 else
1320 Py_RETURN_FALSE;
1321 }
1322
1323 PyDoc_STRVAR(GMPy_doc_mpz_method_is_power,
1324 "x.is_power() -> bool\n\n"
1325 "Return True if x is a perfect power (there exists a y and an\n"
1326 "n > 1, such that x=y**n), else return False.");
1327
1328 static PyObject *
GMPy_MPZ_Method_IsPower(PyObject * self,PyObject * other)1329 GMPy_MPZ_Method_IsPower(PyObject *self, PyObject *other)
1330 {
1331 int res;
1332
1333 res = mpz_perfect_power_p(MPZ(self));
1334
1335 if (res)
1336 Py_RETURN_TRUE;
1337 else
1338 Py_RETURN_FALSE;
1339 }
1340
1341 PyDoc_STRVAR(GMPy_doc_mpz_function_is_prime,
1342 "is_prime(x[, n=25]) -> bool\n\n"
1343 "Return True if x is _probably_ prime, else False if x is\n"
1344 "definitely composite. x is checked for small divisors and up\n"
1345 "to n Miller-Rabin tests are performed.");
1346
1347 static PyObject *
GMPy_MPZ_Function_IsPrime(PyObject * self,PyObject * args)1348 GMPy_MPZ_Function_IsPrime(PyObject *self, PyObject *args)
1349 {
1350 int i;
1351 unsigned long reps = 25;
1352 MPZ_Object* tempx;
1353 Py_ssize_t argc;
1354
1355 argc = PyTuple_GET_SIZE(args);
1356
1357 if (argc == 0 || argc > 2) {
1358 TYPE_ERROR("is_prime() requires 'mpz'[,'int'] arguments");
1359 return NULL;
1360 }
1361
1362 if (PyTuple_GET_SIZE(args) == 2) {
1363 reps = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 1));
1364 if (reps == (unsigned long)(-1) && PyErr_Occurred()) {
1365 return NULL;
1366 }
1367 /* Silently limit n to a reasonable value. */
1368 if (reps > 1000) {
1369 reps = 1000;
1370 }
1371 }
1372
1373 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL))) {
1374 return NULL;
1375 }
1376
1377 i = mpz_probab_prime_p(tempx->z, (int)reps);
1378 Py_DECREF((PyObject*)tempx);
1379
1380 if (i)
1381 Py_RETURN_TRUE;
1382 else
1383 Py_RETURN_FALSE;
1384 }
1385
1386 PyDoc_STRVAR(GMPy_doc_mpz_method_is_prime,
1387 "x.is_prime([n=25]) -> bool\n\n"
1388 "Return True if x is _probably_ prime, else False if x is\n"
1389 "definitely composite. x is checked for small divisors and up\n"
1390 "to n Miller-Rabin tests are performed.");
1391
1392 static PyObject *
GMPy_MPZ_Method_IsPrime(PyObject * self,PyObject * args)1393 GMPy_MPZ_Method_IsPrime(PyObject *self, PyObject *args)
1394 {
1395 int i;
1396 unsigned long reps = 25;
1397 Py_ssize_t argc;
1398
1399 argc = PyTuple_GET_SIZE(args);
1400
1401 if (argc > 1) {
1402 TYPE_ERROR("is_prime() takes at most 1 argument");
1403 return NULL;
1404 }
1405
1406 if (PyTuple_GET_SIZE(args) == 1) {
1407 reps = GMPy_Integer_AsUnsignedLong(PyTuple_GET_ITEM(args, 0));
1408 if (reps == (unsigned long)(-1) && PyErr_Occurred()) {
1409 return NULL;
1410 }
1411 /* Silently limit n to a reasonable value. */
1412 if (reps > 1000) {
1413 reps = 1000;
1414 }
1415 }
1416
1417 i = mpz_probab_prime_p(MPZ(self), (int)reps);
1418
1419 if (i)
1420 Py_RETURN_TRUE;
1421 else
1422 Py_RETURN_FALSE;
1423 }
1424
1425 PyDoc_STRVAR(GMPy_doc_mpz_function_next_prime,
1426 "next_prime(x) -> mpz\n\n"
1427 "Return the next _probable_ prime number > x.");
1428
1429 static PyObject *
GMPy_MPZ_Function_NextPrime(PyObject * self,PyObject * other)1430 GMPy_MPZ_Function_NextPrime(PyObject *self, PyObject *other)
1431 {
1432 MPZ_Object *result;
1433
1434 if(MPZ_Check(other)) {
1435 if(!(result = GMPy_MPZ_New(NULL))) {
1436 /* LCOV_EXCL_START */
1437 return NULL;
1438 /* LCOV_EXCL_STOP */
1439 }
1440 mpz_nextprime(result->z, MPZ(other));
1441 }
1442 else {
1443 if (!(result = GMPy_MPZ_From_Integer(other, NULL))) {
1444 TYPE_ERROR("next_prime() requires 'mpz' argument");
1445 return NULL;
1446 }
1447 else {
1448 mpz_nextprime(result->z, result->z);
1449 }
1450 }
1451 return (PyObject*)result;
1452 }
1453
1454 PyDoc_STRVAR(GMPy_doc_mpz_function_jacobi,
1455 "jacobi(x, y) -> mpz\n\n"
1456 "Return the Jacobi symbol (x|y). y must be odd and >0.");
1457
1458 static PyObject *
GMPy_MPZ_Function_Jacobi(PyObject * self,PyObject * args)1459 GMPy_MPZ_Function_Jacobi(PyObject *self, PyObject *args)
1460 {
1461 MPZ_Object *tempx = NULL, *tempy = NULL;
1462 long res;
1463
1464 if (PyTuple_GET_SIZE(args) != 2) {
1465 TYPE_ERROR("jacobi() requires 'mpz','mpz' arguments");
1466 return NULL;
1467 }
1468
1469 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL)) ||
1470 !(tempy = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 1), NULL))) {
1471
1472 Py_XDECREF((PyObject*)tempx);
1473 Py_XDECREF((PyObject*)tempy);
1474 return NULL;
1475 }
1476
1477 if (mpz_sgn(tempy->z) <= 0 || mpz_even_p(tempy->z)) {
1478 VALUE_ERROR("y must be odd and >0");
1479 Py_DECREF((PyObject*)tempx);
1480 Py_DECREF((PyObject*)tempy);
1481 return NULL;
1482 }
1483
1484 res = (long)(mpz_jacobi(tempx->z, tempy->z));
1485 Py_DECREF((PyObject*)tempx);
1486 Py_DECREF((PyObject*)tempy);
1487 return PyIntOrLong_FromLong(res);
1488 }
1489
1490 PyDoc_STRVAR(GMPy_doc_mpz_function_legendre,
1491 "legendre(x, y) -> mpz\n\n"
1492 "Return the Legendre symbol (x|y). y is assumed to be an odd prime.");
1493
1494 static PyObject *
GMPy_MPZ_Function_Legendre(PyObject * self,PyObject * args)1495 GMPy_MPZ_Function_Legendre(PyObject *self, PyObject *args)
1496 {
1497 MPZ_Object *tempx = NULL, *tempy = NULL;
1498 long res;
1499
1500 if (PyTuple_GET_SIZE(args) != 2) {
1501 TYPE_ERROR("legendre() requires 'mpz','mpz' arguments");
1502 return NULL;
1503 }
1504
1505 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL)) ||
1506 !(tempy = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 1), NULL))) {
1507
1508 Py_XDECREF((PyObject*)tempx);
1509 Py_XDECREF((PyObject*)tempy);
1510 return NULL;
1511 }
1512
1513 if (mpz_sgn(tempy->z) <= 0 || mpz_even_p(tempy->z)) {
1514 VALUE_ERROR("y must be odd, prime, and >0");
1515 Py_DECREF((PyObject*)tempx);
1516 Py_DECREF((PyObject*)tempy);
1517 return NULL;
1518 }
1519
1520 res = (long)(mpz_legendre(tempx->z, tempy->z));
1521 Py_DECREF((PyObject*)tempx);
1522 Py_DECREF((PyObject*)tempy);
1523 return PyIntOrLong_FromLong(res);
1524 }
1525
1526 PyDoc_STRVAR(GMPy_doc_mpz_function_kronecker,
1527 "kronecker(x, y) -> mpz\n\n"
1528 "Return the Kronecker-Jacobi symbol (x|y).");
1529
1530 static PyObject *
GMPy_MPZ_Function_Kronecker(PyObject * self,PyObject * args)1531 GMPy_MPZ_Function_Kronecker(PyObject *self, PyObject *args)
1532 {
1533 MPZ_Object *tempx = NULL, *tempy = NULL;
1534 long res;
1535
1536 if (PyTuple_GET_SIZE(args) != 2) {
1537 TYPE_ERROR("kronecker() requires 'mpz','mpz' arguments");
1538 return NULL;
1539 }
1540
1541 if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL)) ||
1542 !(tempy = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 1), NULL))) {
1543
1544 Py_XDECREF((PyObject*)tempx);
1545 Py_XDECREF((PyObject*)tempy);
1546 return NULL;
1547 }
1548
1549 res = (long)(mpz_kronecker(tempx->z, tempy->z));
1550 Py_DECREF((PyObject*)tempx);
1551 Py_DECREF((PyObject*)tempy);
1552 return PyIntOrLong_FromLong(res);
1553 }
1554
1555 PyDoc_STRVAR(GMPy_doc_mpz_function_is_even,
1556 "is_even(x) -> bool\n\n"
1557 "Return True if x is even, False otherwise.");
1558
1559 static PyObject *
GMPy_MPZ_Function_IsEven(PyObject * self,PyObject * other)1560 GMPy_MPZ_Function_IsEven(PyObject *self, PyObject *other)
1561 {
1562 int res;
1563 MPZ_Object *tempx;
1564
1565 if (MPZ_Check(other)) {
1566 res = mpz_even_p(MPZ(other));
1567 }
1568 else {
1569 if (!(tempx = GMPy_MPZ_From_Integer(other, NULL))) {
1570 TYPE_ERROR("is_even() requires 'mpz' argument");
1571 return NULL;
1572 }
1573 else {
1574 res = mpz_even_p(tempx->z);
1575 Py_DECREF((PyObject*)tempx);
1576 }
1577 }
1578
1579 if (res)
1580 Py_RETURN_TRUE;
1581 else
1582 Py_RETURN_FALSE;
1583 }
1584
1585 PyDoc_STRVAR(GMPy_doc_mpz_method_is_even,
1586 "x.is_even() -> bool\n\n"
1587 "Return True if x is even, False otherwise.");
1588
1589 static PyObject *
GMPy_MPZ_Method_IsEven(PyObject * self,PyObject * other)1590 GMPy_MPZ_Method_IsEven(PyObject *self, PyObject *other)
1591 {
1592 int res;
1593
1594 res = mpz_even_p(MPZ(self));
1595
1596 if (res)
1597 Py_RETURN_TRUE;
1598 else
1599 Py_RETURN_FALSE;
1600 }
1601
1602 PyDoc_STRVAR(GMPy_doc_mpz_function_is_odd,
1603 "is_odd(x) -> bool\n\n"
1604 "Return True if x is odd, False otherwise.");
1605
1606 static PyObject *
GMPy_MPZ_Function_IsOdd(PyObject * self,PyObject * other)1607 GMPy_MPZ_Function_IsOdd(PyObject *self, PyObject *other)
1608 {
1609 int res;
1610 MPZ_Object *tempx;
1611
1612 if (CHECK_MPZANY(other)) {
1613 res = mpz_odd_p(MPZ(other));
1614 }
1615 else {
1616 if (!(tempx = GMPy_MPZ_From_Integer(other, NULL))) {
1617 TYPE_ERROR("is_odd() requires 'mpz' argument");
1618 return NULL;
1619 }
1620 else {
1621 res = mpz_odd_p(tempx->z);
1622 Py_DECREF((PyObject*)tempx);
1623 }
1624 }
1625
1626 if (res)
1627 Py_RETURN_TRUE;
1628 else
1629 Py_RETURN_FALSE;
1630 }
1631
1632 PyDoc_STRVAR(GMPy_doc_mpz_method_is_odd,
1633 "x.is_odd() -> bool\n\n"
1634 "Return True if x is odd, False otherwise.");
1635
1636 static PyObject *
GMPy_MPZ_Method_IsOdd(PyObject * self,PyObject * other)1637 GMPy_MPZ_Method_IsOdd(PyObject *self, PyObject *other)
1638 {
1639 int res;
1640
1641 res = mpz_odd_p(MPZ(self));
1642
1643 if (res)
1644 Py_RETURN_TRUE;
1645 else
1646 Py_RETURN_FALSE;
1647 }
1648
1649 /*
1650 * Add mapping support to mpz objects.
1651 */
1652
1653 static Py_ssize_t
GMPy_MPZ_Method_Length(MPZ_Object * self)1654 GMPy_MPZ_Method_Length(MPZ_Object *self)
1655 {
1656 return mpz_sizeinbase(self->z, 2);
1657 }
1658
1659 static PyObject *
GMPy_MPZ_Method_SubScript(MPZ_Object * self,PyObject * item)1660 GMPy_MPZ_Method_SubScript(MPZ_Object *self, PyObject *item)
1661 {
1662 if (PyIndex_Check(item)) {
1663 Py_ssize_t i;
1664
1665 i = PyIntOrLong_AsSsize_t(item);
1666 if (i == -1 && PyErr_Occurred()) {
1667 INDEX_ERROR("argument too large to convert to an index");
1668 return NULL;
1669 }
1670 if (i < 0) {
1671 i += mpz_sizeinbase(self->z, 2);
1672 }
1673 return PyIntOrLong_FromLong(mpz_tstbit(self->z, i));
1674 }
1675 else if (PySlice_Check(item)) {
1676 Py_ssize_t start, stop, step, slicelength, cur, i;
1677 MPZ_Object *result;
1678
1679 #if PY_VERSION_HEX > 0x030200A4
1680 if (PySlice_GetIndicesEx(item,
1681 mpz_sizeinbase(self->z, 2),
1682 &start, &stop, &step, &slicelength) < 0) {
1683 return NULL;
1684 }
1685 #else
1686 if (PySlice_GetIndicesEx((PySliceObject*)item,
1687 mpz_sizeinbase(self->z, 2),
1688 &start, &stop, &step, &slicelength) < 0) {
1689 return NULL;
1690 }
1691 #endif
1692
1693 if ((step < 0 && start < stop) || (step > 0 && start > stop)) {
1694 stop = start;
1695 }
1696
1697 if (!(result = GMPy_MPZ_New(NULL))) {
1698 return NULL;
1699 }
1700
1701 mpz_set_ui(result->z, 0);
1702 if (slicelength > 0) {
1703 for (cur = start, i = 0; i < slicelength; cur += step, i++) {
1704 if(mpz_tstbit(self->z, cur)) {
1705 mpz_setbit(result->z, i);
1706 }
1707 }
1708 }
1709 return (PyObject*)result;
1710 }
1711 else {
1712 TYPE_ERROR("bit positions must be integers");
1713 return NULL;
1714 }
1715 }
1716
1717 static PyObject *
GMPy_MPZ_Attrib_GetNumer(MPZ_Object * self,void * closure)1718 GMPy_MPZ_Attrib_GetNumer(MPZ_Object *self, void *closure)
1719 {
1720 Py_INCREF((PyObject*)self);
1721 return (PyObject*)self;
1722 }
1723
1724 static PyObject *
GMPy_MPZ_Attrib_GetReal(MPZ_Object * self,void * closure)1725 GMPy_MPZ_Attrib_GetReal(MPZ_Object *self, void *closure)
1726 {
1727 Py_INCREF((PyObject*)self);
1728 return (PyObject*)self;
1729 }
1730
1731 static PyObject *
GMPy_MPZ_Attrib_GetDenom(MPZ_Object * self,void * closure)1732 GMPy_MPZ_Attrib_GetDenom(MPZ_Object *self, void *closure)
1733 {
1734 MPZ_Object *result;
1735
1736 if ((result = GMPy_MPZ_New(NULL))) {
1737 mpz_set_ui(result->z, 1);
1738 }
1739 return (PyObject*)result;
1740 }
1741
1742 static PyObject *
GMPy_MPZ_Attrib_GetImag(MPZ_Object * self,void * closure)1743 GMPy_MPZ_Attrib_GetImag(MPZ_Object *self, void *closure)
1744 {
1745 MPZ_Object *result;
1746
1747 if ((result = GMPy_MPZ_New(NULL))) {
1748 mpz_set_ui(result->z, 0);
1749 }
1750 return (PyObject*)result;
1751 }
1752
1753 PyDoc_STRVAR(GMPy_doc_mpz_method_sizeof,
1754 "x.__sizeof__()\n\n"
1755 "Returns the amount of memory consumed by x. Note: deleted mpz objects\n"
1756 "are reused and may or may not be resized when a new value is assigned.");
1757
1758 static PyObject *
GMPy_MPZ_Method_SizeOf(PyObject * self,PyObject * other)1759 GMPy_MPZ_Method_SizeOf(PyObject *self, PyObject *other)
1760 {
1761 return PyIntOrLong_FromSize_t(sizeof(MPZ_Object) + \
1762 (MPZ(self)->_mp_alloc * sizeof(mp_limb_t)));
1763 }
1764
1765 /* Note: this particular function is also used for xmpz, mpq, and mpfr. Only
1766 * mpc.conjugate() does more that just return another reference to the original
1767 * object.
1768 */
1769
1770 PyDoc_STRVAR(GMPy_doc_mp_method_conjugate,
1771 "x.conjugate() -> number\n\n"
1772 "Return the conjugate of x (which is just a new reference to x since x is\n"
1773 "not a complex number).");
1774
1775 static PyObject *
GMPy_MP_Method_Conjugate(PyObject * self,PyObject * args)1776 GMPy_MP_Method_Conjugate(PyObject *self, PyObject *args)
1777 {
1778 Py_INCREF((PyObject*)self);
1779 return (PyObject*)self;
1780 }
1781
1782
1783
1784