1  Multiple-precision Integers
  2  ===========================
  3  
  4  The gmpy2 *mpz* type supports arbitrary precision integers. It should be a
  5  drop-in replacement for Python's *long* type. Depending on the platform and the
  6  specific operation, an *mpz* will be faster than Python's *long* once the
  7  precision exceeds 20 to 50 digits. All the special integer functions in GMP are
  8  supported.
  9  
 10  Examples
 11  --------
 12  
 13  ::
 14  
 15      >>> import gmpy2
 16      >>> from gmpy2 import mpz
 17      >>> mpz('123') + 1
 18      mpz(124)
 19      >>> 10 - mpz(1)
 20      mpz(9)
 21      >>> gmpy2.is_prime(17)
 22      True
 23  
 24  .. note::
 25      The use of ``from gmpy2 import *`` is not recommended. The names in gmpy2
 26      have been chosen to avoid conflict with Python's builtin names but gmpy2
 27      does use names that may conflict with other modules or variable names.
 28  
 29  mpz Methods
 30  -----------
 31  
 32  **bit_clear(...)**
 33      x.bit_clear(n) returns a copy of *x* with bit *n* set to 0.
 34  
 35  **bit_flip(...)**
 36      x.bit_flip(n) returns a copy of *x* with bit *n* inverted.
 37  
 38  **bit_length(...)**
 39      x.bit_length() returns the number of significant bits in the radix-2
 40      representation of *x*. For compatibility with Python, mpz(0).bit_length()
 41      returns 0.
 42  
 43  **bit_scan0(...)**
 44      x.bit_scan0(n) returns the index of the first 0-bit of *x* with
 45      index >= *n*. If there are no more 0-bits in *x* at or above index *n*
 46      (which can only happen for *x* < 0, assuming an infinitely long 2's
 47      complement format), then None is returned. *n* must be >= 0.
 48  
 49  **bit_scan1(...)**
 50      x.bit_scan1(n) returns the index of the first 1-bit of *x* with
 51      index >= *n*. If there are no more 1-bits in *x* at or above index *n*
 52      (which can only happen for *x* >= 0, assuming an infinitely long 2's
 53      complement format), then None is returned. *n* must be >= 0.
 54  
 55  **bit_set(...)**
 56      x.bit_set(n) returns a copy of *x* with bit *n* set to 1.
 57  
 58  **bit_test(...)**
 59      x.bit_test(n) returns True if bit *n* of *x* is set, and False if it
 60      is not set.
 61  
 62  **conjugtae(...)**
 63      Return the conjugate of x (which is just a new reference to x since x
 64      not a complex number).
 65  
 66  **denominator(...)**
 67      x.denominator() returns mpz(1).
 68  
 69  **digits(...)**
 70      x.digits([base=10]) returns a string representing *x* in radix *base*.
 71  
 72  **imag**
 73      Return the imaginary component of an *mpz*. Always *mpz(0)*.
 74  
 75  **is_congruent(...)**
 76      x.is_congruent(y, m) returns True if *x* is congruent to *y* modulo *m*,
 77      else returns False.
 78  
 79  **is_divisible(...)**
 80      x.is_divisible(d) returns True if *x* is divisible by *d*, else returns
 81      False.
 82  
 83  **is_even(...)**
 84      x.is_even() returns True if *x* is even, else returns False.
 85  
 86  **is_odd(...)**
 87      x.is_odd() returns True if *x* is even, else returns False.
 88  
 89  **is_power(...)**
 90      x.is_power() returns True if *x* is a perfect power (there exists integers
 91      *y* and *n* > 1, such that x=y**n), else returns False.
 92  
 93  **is_prime(...)**
 94      x.is_prime() returns True if *x* is _probably_ prime, else False if *x* is
 95      definitely composite.
 96  
 97      See the documentation for *gmpy2.is_prime* for details on the underlaying
 98      primality tests that are performed.
 99  
100  **is_square(...)**
101      x.is_square() returns True if *x* is a perfect square, else returns False.
102  
103  **num_digits(...)**
104      x.num_digits([base=10]) returns the length of the string representing
105      the absolute value of *x* in radix *base*. The result is correct if base is
106      a power of 2. For other bases, the result is usually correct but may
107      be 1 too large. *base* can range between 2 and 62, inclusive.
108  
109  **numerator(...)**
110      x.numerator() returns a copy of *x*.
111  
112  **real(...)**
113      x.real returns a copy of *x*.
114  
115  mpz Functions
116  -------------
117  
118  **add(...)**
119      add(x, y) returns *x* + *y*. The result type depends on the input
120      types.
121  
122  **bincoef(...)**
123      bincoef(x, n) returns the binomial coefficient. *n* must be >= 0.
124  
125  **bit_clear(...)**
126      bit_clear(x, n) returns a copy of *x* with bit *n* set to 0.
127  
128  **bit_flip(...)**
129      bit_flip(x, n) returns a copy of *x* with bit *n* inverted.
130  
131  **bit_length(...)**
132      bit_length(x) returns the number of significant bits in the radix-2
133      representation of *x*. For compatibility with Python, mpz(0).bit_length()
134      returns 0 while mpz(0).num_digits(2) returns 1.
135  
136  **bit_mask(...)**
137      bit_mask(n) returns an *mpz* object exactly *n* bits in length with all
138      bits set.
139  
140  **bit_scan0(...)**
141      bit_scan0(x, n) returns the index of the first 0-bit of *x* with
142      index >= *n*. If there are no more 0-bits in *x* at or above index *n*
143      (which can only happen for *x* < 0, assuming an infinitely long 2's
144      complement format), then None is returned. *n* must be >= 0.
145  
146  **bit_scan1(...)**
147      bit_scan1(x, n) returns the index of the first 1-bit of *x* with
148      index >= *n*. If there are no more 1-bits in *x* at or above index *n*
149      (which can only happen for *x* >= 0, assuming an infinitely long 2's
150      complement format), then None is returned. *n* must be >= 0.
151  
152  **bit_set(...)**
153      bit_set(x, n) returns a copy of *x* with bit *n* set to 1.
154  
155  **bit_test(...)**
156      bit_test(x, n) returns True if bit *n* of *x* is set, and False if it
157      is not set.
158  
159  **c_div(...)**
160      c_div(x, y) returns the quotient of *x* divided by *y*. The quotient is
161      rounded towards +Inf (ceiling rounding). *x* and *y* must be integers.
162  
163  **c_div_2exp(...)**
164      c_div_2exp(x, n) returns the quotient of *x* divided by 2**n. The
165      quotient is rounded towards +Inf (ceiling rounding). *x* must be an integer
166      and *n* must be > 0.
167  
168  **c_divmod(...)**
169      c_divmod(x, y) returns the quotient and remainder of *x* divided by
170      *y*. The quotient is rounded towards +Inf (ceiling rounding) and the
171      remainder will have the opposite sign of *y*. *x* and *y* must be integers.
172  
173  **c_divmod_2exp(...)**
174      c_divmod_2exp(x ,n) returns the quotient and remainder of *x* divided
175      by 2**n. The quotient is rounded towards +Inf (ceiling rounding) and the
176      remainder will be negative or zero. *x* must be an integer and *n* must
177      be > 0.
178  
179  **c_mod(...)**
180      c_mod(x, y) returns the remainder of *x* divided by *y*. The remainder
181      will have the opposite sign of *y*. *x* and *y* must be integers.
182  
183  **c_mod_2exp(...)**
184      c_mod_2exp(x, n) returns the remainder of *x* divided by 2**n. The
185      remainder will be negative. *x* must be an integer and *n* must be > 0.
186  
187  **comb(...)**
188      comb(x, n) returns the number of combinations of *x* things, taking *n*
189      at a time. *n* must be >= 0.
190  
191  **digits(...)**
192      digits(x[, base=10]) returns a string representing *x* in radix *base*.
193  
194  **div(...)**
195      div(x, y) returns *x* / *y*. The result type depends on the input
196      types.
197  
198  **divexact(...)**
199      divexact(x, y) returns the quotient of *x* divided by *y*. Faster than
200      standard division but requires the remainder is zero!
201  
202  **divm(...)**
203      divm(a, b, m) returns *x* such that *b* * *x* == *a* modulo *m*. Raises
204      a ZeroDivisionError exception if no such value *x* exists.
205  
206  **double_fac(...)**
207      double_fac(n) returns the exact double factorial of *n*.
208  
209  **f_div(...)**
210      f_div(x, y) returns the quotient of *x* divided by *y*. The quotient
211      is rounded towards -Inf (floor rounding). *x* and *y* must be integers.
212  
213  **f_div_2exp(...)**
214      f_div_2exp(x, n) returns the quotient of *x* divided by 2**n. The
215      quotient is rounded towards -Inf (floor rounding). *x* must be an integer
216      and *n* must be > 0.
217  
218  **f_divmod(...)**
219      f_divmod(x, y) returns the quotient and remainder of *x* divided by
220      *y*. The quotient is rounded towards -Inf (floor rounding) and the
221      remainder will have the same sign as *y*. *x* and *y* must be integers.
222  
223  **f_divmod_2exp(...)**
224      f_divmod_2exp(x, n) returns quotient and remainder after dividing *x*
225      by 2**n. The quotient is rounded towards -Inf (floor rounding) and the
226      remainder will be positive. *x* must be an integer and *n* must be > 0.
227  
228  **f_mod(...)**
229      f_mod(x, y) returns the remainder of *x* divided by *y*. The remainder
230      will have the same sign as *y*. *x* and *y* must be integers.
231  
232  **f_mod_2exp(...)**
233      f_mod_2exp(x, n) returns remainder of *x* divided by 2**n. The
234      remainder will be positive. *x* must be an integer and *n* must be > 0.
235  
236  **fac(...)**
237      fac(n) returns the exact factorial of *n*. Use factorial() to get the
238      floating-point approximation.
239  
240  **fib(...)**
241      fib(n) returns the *n*-th Fibonacci number.
242  
243  **fib2(...)**
244      fib2(n) returns a 2-tuple with the (*n*-1)-th and *n*-th Fibonacci
245      numbers.
246  
247  **gcd(...)**
248      gcd(a, b) returns the greatest common divisor of integers *a* and
249      *b*.
250  
251  **gcdext(...)**
252      gcdext(a, b) returns a 3-element tuple (*g*, *s*, *t*) such that
253  
254      *g* == gcd(*a*, *b*) and *g* == *a* * *s*  + *b* * *t*
255  
256  **hamdist(...)**
257      hamdist(x, y) returns the Hamming distance (number of bit-positions
258      where the bits differ) between integers *x* and *y*.
259  
260  **invert(...)**
261      invert(x, m) returns *y* such that *x* * *y* == 1 modulo *m*, or 0
262      if no such *y* exists.
263  
264  **iroot(...)**
265      iroot(x,n) returns a 2-element tuple (*y*, *b*) such that *y* is the integer
266      *n*-th root of *x* and *b* is True if the root is exact. *x* must be >= 0
267      and *n* must be > 0.
268  
269  **iroot_rem(...)**
270      iroot_rem(x,n) returns a 2-element tuple (*y*, *r*) such that *y* is
271      the integer *n*-th root of *x* and *x* = y**n + *r*. *x* must be >= 0 and
272      *n* must be > 0.
273  
274  **is_even(...)**
275      is_even(x) returns True if *x* is even, False otherwise.
276  
277  **is_odd(...)**
278      is_odd(x) returns True if *x* is odd, False otherwise.
279  
280  **is_power(...)**
281      is_power(x) returns True if *x* is a perfect power, False otherwise.
282  
283  **is_prime(...)**
284      is_prime(x[, n=25]) returns True if *x* is **probably** prime. False
285      is returned if *x* is definitely composite. *x* is checked for small
286      divisors and up to *n* Miller-Rabin tests are performed. The actual tests
287      performed may vary based on version of GMP or MPIR used.
288  
289  **is_square(...)**
290      is_square(x) returns True if *x* is a perfect square, False otherwise.
291  
292  **isqrt(...)**
293      isqrt(x) returns the integer square root of an integer *x*. *x* must be
294      >= 0.
295  
296  **isqrt_rem(...)**
297      isqrt_rem(x) returns a 2-tuple (*s*, *t*) such that *s* = isqrt(*x*)
298      and *t* = *x* - *s* * *s*. *x* must be >= 0.
299  
300  **jacobi(...)**
301      jacobi(x, y) returns the Jacobi symbol (*x* | *y*). *y* must be odd and
302      > 0.
303  
304  **kronecker(...)**
305      kronecker(x, y) returns the Kronecker-Jacobi symbol (*x* | *y*).
306  
307  **lcm(...)**
308      lcm(a, b) returns the lowest common multiple of integers *a* and *b*.
309  
310  **legendre(...)**
311      legendre(x, y) returns the Legendre symbol (*x* | *y*). *y* is assumed
312      to be an odd prime.
313  
314  **lucas(...)**
315      lucas(n) returns the *n*-th Lucas number.
316  
317  **lucas2(...)**
318      lucas2(n) returns a 2-tuple with the (*n*-1)-th and *n*-th Lucas
319      numbers.
320  
321  **mpz(...)**
322      mpz() returns a new *mpz* object set to 0.
323  
324      mpz(n) returns a new *mpz* object from a numeric value *n*. If *n* is
325      not an integer, it will be truncated to an integer.
326  
327      mpz(s[, base=0]) returns a new *mpz* object from a string *s* made of
328      digits in the given base. If base = 0, then binary, octal, or hex Python
329      strings are recognized by leading 0b, 0o, or 0x characters. Otherwise the
330      string is assumed to be decimal. Values for base can range between 2 and 62.
331  
332  **mpz_random(...)**
333      mpz_random(random_state, n) returns a uniformly distributed random
334      integer between 0 and *n*-1. The parameter *random_state* must be created
335      by random_state() first.
336  
337  **mpz_rrandomb(...)**
338      mpz_rrandomb(random_state, b) returns a random integer between 0 and
339      2**b - 1 with long sequences of zeros and one in its binary representation.
340      The parameter *random_state* must be created by random_state() first.
341  
342  **mpz_urandomb(...)**
343      mpz_urandomb(random_state, b) returns a uniformly distributed random
344      integer between 0 and 2**b - 1. The parameter *random_state* must be
345      created by random_state() first.
346  
347  **mul(...)**
348      mul(x, y) returns *x* \* *y*. The result type depends on the input
349      types.
350  
351  **multi_fac(...)**
352      multi_fac(n, m) returns the m-multi-factorial of *n* i.e n!^m.
353  
354  **next_prime(...)**
355      next_prime(x) returns the next **probable** prime number > *x*.
356  
357  **num_digits(...)**
358      num_digits(x[, base=10]) returns the length of the string representing
359      the absolute value of *x* in radix *base*. The result is correct if base is
360      a power of 2. For other bases, the result is usually correct but may
361      be 1 too large. *base* can range between 2 and 62, inclusive.
362  
363  **popcount(...)**
364      popcount(x) returns the number of bits with value 1 in *x*. If *x* < 0,
365      the number of bits with value 1 is infinite so -1 is returned in that case.
366  
367  **powmod(...)**
368      powmod(x, y, m) returns (*x* ** *y*) mod *m*. The exponent *y* can be
369      negative, and the correct result will be returned if the inverse of *x*
370      mod *m* exists. Otherwise, a ValueError is raised.
371  
372  **primorial(...)**
373      primorial(n) returns the exact primorial of *n*, i.e. the product of all
374      positive prime numbers <= *n*.
375  
376  **remove(...)**
377      remove(x, f) will remove the factor *f* from *x* as many times as possible
378      and return a 2-tuple (*y*, *m*) where *y* = *x* // (*f* ** *m*). *f* does
379      not divide *y*. *m* is the multiplicity of the factor *f* in *x*. *f* must
380      be > 1.
381  
382  **sub(...)**
383      sub(x, y) returns *x* - *y*. The result type depends on the input
384      types.
385  
386  **t_div(...)**
387      t_div(x, y) returns the quotient of *x* divided by *y*. The quotient
388      is rounded towards zero (truncation). *x* and *y* must be integers.
389  
390  **t_div_2exp(...)**
391      t_div_2exp(x, n) returns the quotient of *x* divided by 2**n. The
392      quotient is rounded towards zero (truncation). *n* must be > 0.
393  
394  **t_divmod(...)**
395      t_divmod(x, y) returns the quotient and remainder of *x* divided by
396      *y*. The quotient is rounded towards zero (truncation) and the remainder
397      will have the same sign as *x*. *x* and *y* must be integers.
398  
399  **t_divmod_2exp(...)**
400      t_divmod_2exp(x, n) returns the quotient and remainder of *x* divided
401      by 2**n. The quotient is rounded towards zero (truncation) and the
402      remainder will have the same sign as *x*. *x* must be an integer and *n*
403      must be > 0.
404  
405  **t_mod(...)**
406      t_mod(x, y) returns the remainder of *x* divided by *y*. The remainder
407      will have the same sign as *x*. *x* and *y* must be integers.
408  
409  **t_mod_2exp(...)**
410      t_mod_2exp(x, n) returns the remainder of *x* divided by 2**n. The
411      remainder will have the same sign as *x*. *x* must be an integer and *n*
412      must be > 0.
413  
414