Multiple-precision Integers
===========================

The gmpy2 *mpz* type supports arbitrary precision integers. It should be a
drop-in replacement for Python's *long* type. Depending on the platform and the
specific operation, an *mpz* will be faster than Python's *long* once the
precision exceeds 20 to 50 digits. All the special integer functions in GMP are
supported.

Examples
--------

::

    >>> import gmpy2
    >>> from gmpy2 import mpz
    >>> mpz('123') + 1
    mpz(124)
    >>> 10 - mpz(1)
    mpz(9)
    >>> gmpy2.is_prime(17)
    True

.. note::
    The use of ``from gmpy2 import *`` is not recommended. The names in gmpy2
    have been chosen to avoid conflict with Python's builtin names but gmpy2
    does use names that may conflict with other modules or variable names.

mpz Methods
-----------

**bit_clear(...)**
    x.bit_clear(n) returns a copy of *x* with bit *n* set to 0.

**bit_flip(...)**
    x.bit_flip(n) returns a copy of *x* with bit *n* inverted.

**bit_length(...)**
    x.bit_length() returns the number of significant bits in the radix-2
    representation of *x*. For compatibility with Python, mpz(0).bit_length()
    returns 0.

**bit_scan0(...)**
    x.bit_scan0(n) returns the index of the first 0-bit of *x* with
    index >= *n*. If there are no more 0-bits in *x* at or above index *n*
    (which can only happen for *x* < 0, assuming an infinitely long 2's
    complement format), then None is returned. *n* must be >= 0.

**bit_scan1(...)**
    x.bit_scan1(n) returns the index of the first 1-bit of *x* with
    index >= *n*. If there are no more 1-bits in *x* at or above index *n*
    (which can only happen for *x* >= 0, assuming an infinitely long 2's
    complement format), then None is returned. *n* must be >= 0.

**bit_set(...)**
    x.bit_set(n) returns a copy of *x* with bit *n* set to 0.

**bit_test(...)**
    x.bit_test(n) returns True if bit *n* of *x* is set, and False if it
    is not set.

**denominator(...)**
    x.denominator() returns mpz(1).

**digits(...)**
    x.digits([base=10]) returns a string representing *x* in radix *base*.

**numerator(...)**
    x.numerator() returns a copy of x.

**num_digits(...)**
    x.num_digits([base=10]) returns the length of the string representing
    the absolute value of *x* in radix *base*. The result is correct if base is
    a power of 2. For other other bases, the result is usually correct but may
    be 1 too large. *base* can range between 2 and 62, inclusive.

mpz Functions
-------------

**add(...)**
    add(x, y) returns *x* + *y*. The result type depends on the input
    types.

**bincoef(...)**
    bincoef(x, n) returns the binomial coefficient. *n* must be >= 0.

**bit_clear(...)**
    bit_clear(x, n) returns a copy of *x* with bit *n* set to 0.

**bit_flip(...)**
    bit_flip(x, n) returns a copy of *x* with bit *n* inverted.

**bit_length(...)**
    bit_length(x) returns the number of significant bits in the radix-2
    representation of *x*. For compatibility with Python, mpz(0).bit_length()
    returns 0 while mpz(0).num_digits(2) returns 1.

**bit_mask(...)**
    bit_mask(n) returns an *mpz* object exactly *n* bits in length with all
    bits set.

**bit_scan0(...)**
    bit_scan0(x, n) returns the index of the first 0-bit of *x* with
    index >= *n*. If there are no more 0-bits in *x* at or above index *n*
    (which can only happen for *x* < 0, assuming an infinitely long 2's
    complement format), then None is returned. *n* must be >= 0.

**bit_scan1(...)**
    bit_scan1(x, n) returns the index of the first 1-bit of *x* with
    index >= *n*. If there are no more 1-bits in *x* at or above index *n*
    (which can only happen for *x* >= 0, assuming an infinitely long 2's
    complement format), then None is returned. *n* must be >= 0.

**bit_set(...)**
    bit_set(x, n) returns a copy of *x* with bit *n* set to 0.

**bit_test(...)**
    bit_test(x, n) returns True if bit *n* of *x* is set, and False if it
    is not set.

**c_div(...)**
    c_div(x, y) returns the quotient of *x* divided by *y*. The quotient is
    rounded towards +Inf (ceiling rounding). *x* and *y* must be integers.

**c_div_2exp(...)**
    c_div_2exp(x, n) returns the quotient of *x* divided by 2**n. The
    quotient is rounded towards +Inf (ceiling rounding). *x* must be an integer
    and *n* must be > 0.

**c_divmod(...)**
    c_divmod(x, y) returns the quotient and remainder of *x* divided by
    *y*. The quotient is rounded towards +Inf (ceiling rounding) and the
    remainder will have the opposite sign of *y*. *x* and *y* must be integers.

**c_divmod_2exp(...)**
    c_divmod_2exp(x ,n) returns the quotient and remainder of *x* divided
    by 2**n. The quotient is rounded towards +Inf (ceiling rounding) and the
    remainder will be negative or zero. *x* must be an integer and *n* must
    be > 0.

**c_mod(...)**
    c_mod(x, y) returns the remainder of *x* divided by *y*. The remainder
    will have the opposite sign of *y*. *x* and *y* must be integers.

**c_mod_2exp(...)**
    c_mod_2exp(x, n) returns the remainder of *x* divided by 2**n. The
    remainder will be negative. *x* must be an integer and *n* must be > 0.

**comb(...)**
    comb(x, n) returns the number of combinations of *x* things, taking *n*
    at a time. *n* must be >= 0.

**digits(...)**
    digits(x[, base=10]) returns a string representing *x* in radix *base*.

**div(...)**
    div(x, y) returns *x* / *y*. The result type depends on the input
    types.

**divexact(...)**
    divexact(x, y) returns the quotient of *x* divided by *y*. Faster than
    standard division but requires the remainder is zero!

**divm(...)**
    divm(a, b, m) returns *x* such that *b* * *x* == *a* modulo *m*. Raises
    a ZeroDivisionError exception if no such value *x* exists.

**f_div(...)**
    f_div(x, y) returns the quotient of *x* divided by *y*. The quotient
    is rounded towards -Inf (floor rounding). *x* and *y* must be integers.

**f_div_2exp(...)**
    f_div_2exp(x, n) returns the quotient of *x* divided by 2**n. The
    quotient is rounded towards -Inf (floor rounding). *x* must be an integer
    and *n* must be > 0.

**f_divmod(...)**
    f_divmod(x, y) returns the quotient and remainder of *x* divided by
    *y*. The quotient is rounded towards -Inf (floor rounding) and the
    remainder will have the same sign as *y*. *x* and *y* must be integers.

**f_divmod_2exp(...)**
    f_divmod_2exp(x, n) returns quotient and remainder after dividing *x*
    by 2**n. The quotient is rounded towards -Inf (floor rounding) and the
    remainder will be positive. *x* must be an integer and *n* must be > 0.

**f_mod(...)**
    f_mod(x, y) returns the remainder of *x* divided by *y*. The remainder
    will have the same sign as *y*. *x* and *y* must be integers.

**f_mod_2exp(...)**
    f_mod_2exp(x, n) returns remainder of *x* divided by 2**n. The
    remainder will be positive. *x* must be an integer and *n* must be > 0.

**fac(...)**
    fac(n) returns the exact factorial of *n*. Use factorial() to get the
    floating-point approximation.

**fib(...)**
    fib(n) returns the *n*-th Fibonacci number.

**fib2(...)**
    fib2(n) returns a 2-tuple with the (*n*-1)-th and *n*-th Fibonacci
    numbers.

**gcd(...)**
    gcd(a, b) returns the greatest common denominator of integers *a* and
    *b*.

**gcdext(...)**
    gcdext(a, b) returns a 3-element tuple (*g*, *s*, *t*) such that

    *g* == gcd(*a*, *b*) and *g* == *a* * *s*  + *b* * *t*

**hamdist(...)**
    hamdist(x, y) returns the Hamming distance (number of bit-positions
    where the bits differ) between integers *x* and *y*.

**invert(...)**
    invert(x, m) returns *y* such that *x* * *y* == 1 modulo *m*, or 0
    if no such *y* exists.

**iroot(...)**
    iroot(x,n) returns a 2-element tuple (*y*, *b*) such that *y* is the integer
    *n*-th root of *x* and *b* is True if the root is exact. *x* must be >= 0
    and *n* must be > 0.

**iroot_rem(...)**
    iroot_rem(x,n) returns a 2-element tuple (*y*, *r*) such that *y* is
    the integer *n*-th root of *x* and *x* = y**n + *r*. *x* must be >= 0 and
    *n* must be > 0.

**is_even(...)**
    is_even(x) returns True if *x* is even, False otherwise.

**is_odd(...)**
    is_odd(x) returns True if *x* is odd, False otherwise.

**is_power(...)**
    is_power(x) returns True if *x* is a perfect power, False otherwise.

**is_prime(...)**
    is_prime(x[, n=25]) returns True if *x* is **probably** prime. False
    is returned if *x* is definately composite. *x* is checked for small
    divisors and up to *n* Miller-Rabin tests are performed. The actual tests
    performed may vary based on version of GMP or MPIR used.

**is_square(...)**
    is_square(x) returns True if *x* is a perfect square, False otherwise.

**isqrt(...)**
    isqrt(x) returns the integer square root of an integer *x*. *x* must be
    >= 0.

**isqrt_rem(...)**
    isqrt_rem(x) returns a 2-tuple (*s*, *t*) such that *s* = isqrt(*x*)
    and *t* = *x* - *s* * *s*. *x* must be >= 0.

**jacobi(...)**
    jacobi(x, y) returns the Jacobi symbol (*x* | *y*). *y* must be odd and
    > 0.

**kronecker(...)**
    kronecker(x, y) returns the Kronecker-Jacobi symbol (*x* | *y*).

**lcm(...)**
    lcm(a, b) returns the lowest common multiple of integers *a* and *b*.

**legendre(...)**
    legendre(x, y) returns the Legendre symbol (*x* | *y*). *y* is assumed
    to be an odd prime.

**lucas(...)**
    lucas(n) returns the *n*-th Lucas number.

**lucas2(...)**
    lucas2(n) returns a 2-tuple with the (*n*-1)-th and *n*-th Lucas
    numbers.

**mpz(...)**
    mpz() returns a new *mpz* object set to 0.

    mpz(n) returns a new *mpz* object from a numeric value *n*. If *n* is
    not an integer, it will be truncated to an integer.

    mpz(s[, base=0]) returns a new *mpz* object from a string *s* made of
    digits in the given base. If base = 0, thn binary, octal, or hex Python
    strings are recognized by leading 0b, 0o, or 0x characters. Otherwise the
    string is assumed to be decimal. Values for base can range between 2 and 62.

**mpz_random(...)**
    mpz_random(random_state, n) returns a uniformly distributed random
    integer between 0 and *n*-1. The parameter *random_state* must be created
    by random_state() first.

**mpz_rrandomb(...)**
    mpz_rrandomb(random_state, b) returns a random integer between 0 and
    2**b - 1 with long sequences of zeros and one in its binary representation.
    The parameter *random_state* must be created by random_state() first.

**mpz_urandomb(...)**
    mpz_urandomb(random_state, b) returns a uniformly distributed random
    integer between 0 and 2**b - 1. The parameter *random_state* must be
    created by random_state() first.

**mul(...)**
    mul(x, y) returns *x* \* *y*. The result type depends on the input
    types.

**next_prime(...)**
    next_prime(x) returns the next **probable** prime number > *x*.

**num_digits(...)**
    num_digits(x[, base=10]) returns the length of the string representing
    the absolute value of *x* in radix *base*. The result is correct if base is
    a power of 2. For other other bases, the result is usually correct but may
    be 1 too large. *base* can range between 2 and 62, inclusive.

**popcount(...)**
    popcount(x) returns the number of bits with value 1 in *x*. If *x* < 0,
    the number of bits with value 1 is infinite so -1 is returned in that case.

**powmod(...)**
    powmod(x, y, m) returns (*x* ** *y*) mod *m*. The exponenent *y* can be
    negative, and the correct result will be returned if the inverse of *x*
    mod *m* exists. Otherwise, a ValueError is raised.

**remove(...)**
    remove(x, f) will remove the factor *f* from *x* as many times as possible
    and return a 2-tuple (*y*, *m*) where *y* = *x* // (*f* ** *m*). *f* does
    not divide *y*. *m* is the multiplicity of the factor *f* in *x*. *f* must
    be > 1.

**sub(...)**
    sub(x, y) returns *x* - *y*. The result type depends on the input
    types.

**t_div(...)**
    t_div(x, y) returns the quotient of *x* divided by *y*. The quotient
    is rounded towards zero (truncation). *x* and *y* must be integers.

**t_div_2exp(...)**
    t_div_2exp(x, n) returns the quotient of *x* divided by 2**n. The
    quotient is rounded towards zero (truncation). *n* must be > 0.

**t_divmod(...)**
    t_divmod(x, y) returns the quotient and remainder of *x* divided by
    *y*. The quotient is rounded towards zero (truncation) and the remainder
    will have the same sign as *x*. *x* and *y* must be integers.

**t_divmod_2exp(...)**
    t_divmod_2exp(x, n) returns the quotient and remainder of *x* divided
    by 2**n. The quotient is rounded towards zero (truncation) and the
    remainder will have the same sign as *x*. *x* must be an integer and *n*
    must be > 0.

**t_mod(...)**
    t_mod(x, y) returns the remainder of *x* divided by *y*. The remainder
    will have the same sign as *x*. *x* and *y* must be integers.

**t_mod_2exp(...)**
    t_mod_2exp(x, n) returns the remainder of *x* divided by 2**n. The
    remainder will have the same sign as *x*. *x* must be an integer and *n*
    must be > 0.