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