Multiple-precision Integers (Advanced topics)
The xmpz type
gmpy2 provides access to an experimental integer type called xmpz
. The
xmpz
type is a mutable integer type. In-place operations (+=, //=,
etc.) modify the original object and do not create a new object. Instances of
xmpz
cannot be used as dictionary keys.
>>> from gmpy2 import xmpz
>>> a = xmpz(123)
>>> b = a
>>> a += 1
>>> a
xmpz(124)
>>> b
xmpz(124)
The ability to change an xmpz
object in-place allows for efficient and
rapid bit manipulation.
Individual bits can be set or cleared:
>>> a[10]=1
>>> a
xmpz(1148)
Slice notation is supported. The bits referenced by a slice can be either ‘read from’ or ‘written to’. To clear a slice of bits, use a source value of 0. In 2s-complement format, 0 is represented by an arbitrary number of 0-bits. To set a slice of bits, use a source value of ~0. The tilde operator inverts, or complements the bits in an integer. (~0 is -1 so you can also use -1.) In 2s-complement format, -1 is represented by an arbitrary number of 1-bits.
If a value for stop is specified in a slice assignment and the actual
bit-length of the xmpz
is less than stop, then the destination
xmpz
is logically padded with 0-bits to length stop.
>>> a=xmpz(0)
>>> a[8:16] = ~0
>>> bin(a)
'0b1111111100000000'
>>> a[4:12] = ~a[4:12]
>>> bin(a)
'0b1111000011110000'
Bits can be reversed:
>>> a = xmpz(1148)
>>> bin(a)
'0b10001111100'
>>> a[::] = a[::-1]
>>> bin(a)
'0b111110001'
The iter_bits()
method returns a generator that returns True or
False for each bit position. The methods iter_clear()
, and
iter_set()
return generators that return the bit positions that are
1 or 0. The methods support arguments start and stop that define the
beginning and ending bit positions that are used. To mimic the behavior of
slices. the bit positions checked include start but the last position checked
is stop - 1.
>>> a=xmpz(117)
>>> bin(a)
'0b1110101'
>>> list(a.iter_bits())
[True, False, True, False, True, True, True]
>>> list(a.iter_clear())
[1, 3]
>>> list(a.iter_set())
[0, 2, 4, 5, 6]
>>> list(a.iter_bits(stop=12))
[True, False, True, False, True, True, True, False, False, False, False, False]
The following program uses the Sieve of Eratosthenes to generate a list of prime numbers.
import time
import gmpy2
def sieve(limit=1000000):
'''Returns a generator that yields the prime numbers up to limit.'''
# Increment by 1 to account for the fact that slices do not include
# the last index value but we do want to include the last value for
# calculating a list of primes.
sieve_limit = gmpy2.isqrt(limit) + 1
limit += 1
# Mark bit positions 0 and 1 as not prime.
bitmap = gmpy2.xmpz(3)
# Process 2 separately. This allows us to use p+p for the step size
# when sieving the remaining primes.
bitmap[4 : limit : 2] = -1
# Sieve the remaining primes.
for p in bitmap.iter_clear(3, sieve_limit):
bitmap[p*p : limit : p+p] = -1
return bitmap.iter_clear(2, limit)
if __name__ == "__main__":
start = time.time()
result = list(sieve())
print(time.time() - start)
print(len(result))
- class gmpy2.xmpz(n=0, /)
- class gmpy2.xmpz(s, /, base=0)
Return a mutable integer constructed from a numeric value n or a string s made of digits in the given base. Every input, that is accepted by the
mpz
type constructor is also accepted.Note: This type can be faster when used for augmented assignment (+=, -=, etc), but
xmpz
objects cannot be used as dictionary keys.- __format__(fmt) str
Return a Python string by formatting
mpz
‘x’ using the format string ‘fmt’. A valid format string consists of:optional alignment code:
‘<’ -> left shifted in field ‘>’ -> right shifted in field ‘^’ -> centered in field
optional leading sign code:
‘+’ -> always display leading sign ‘-’ -> only display minus sign ‘ ‘ -> minus for negative values, space for positive values
optional base indicator
‘#’ -> precede binary, octal, or hex with 0b, 0o or 0x
optional width
optional conversion code:
‘d’ -> decimal format ‘b’ -> binary format ‘o’ -> octal format ‘x’ -> hex format ‘X’ -> upper-case hex format
The default format is ‘d’.
- bit_length() int
Return the number of significant bits in the radix-2 representation of x. Note: mpz(0).bit_length() returns 0.
- bit_scan0(n=0, /) int | None
Return the index of the first 0-bit of x with index >= n. n >= 0. 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.
- bit_scan1(n=0, /) int | None
Return the index of the first 1-bit of x with index >= n. n >= 0. 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.
- conjugate() mpz
Return the conjugate of x (which is just a new reference to x since x is not a complex number).
- digits(base=10, /) str
Return Python string representing x in the given base. Values for base can range between 2 to 62. A leading ‘-’ is present if x<0 but no leading ‘+’ is present if x>=0.
- iter_bits(start=0, stop=-1) collections.abc.Iterator
Return
True
orFalse
for each bit position in x beginning at ‘start’. If a positive value is specified for ‘stop’, iteration is continued until ‘stop’ is reached. If a negative value is specified, iteration is continued until the last 1-bit. Note: the value of the underlyingxmpz
object can change during iteration.
- iter_clear(start=0, stop=-1) collections.abc.Iterator
Return every bit position that is clear in x, beginning at ‘start’. If a positive value is specified for ‘stop’, iteration is continued until ‘stop’ is reached. If a negative value is specified, iteration is continued until the last 1-bit. Note: the value of the underlying
xmpz
object can change during iteration.
- iter_set(start=0, stop=-1) collections.abc.Iterator
Return an iterator yielding the bit position for every bit that is set in x, beginning at ‘start’. If a positive value is specified for ‘stop’, iteration is continued until ‘stop’ is reached. To match the behavior of slicing, ‘stop’ is not included. If a negative value is specified, iteration is continued until the last 1-bit. Note: the value of the underlying
xmpz
object can change during iteration.
- limbs_finish(n, /) None
Must be called after writing to the address returned by x.limbs_write(n) or x.limbs_modify(n) to update the limbs of x.
- limbs_modify(n, /) int
Returns the address of a mutable buffer representing the limbs of x, resized so that it may hold at least n limbs. Must be followed by a call to x.limbs_finish(n) after writing to the returned address in order for the changes to take effect.
- limbs_write(n, /) int
Returns the address of a mutable buffer representing the limbs of x, resized so that it may hold at least n limbs. Must be followed by a call to x.limbs_finish(n) after writing to the returned address in order for the changes to take effect. WARNING: this operation is destructive and may destroy the old value of x.
- make_mpz() mpz
Return an
mpz
by converting x as quickly as possible.NOTE: Optimized for speed so the original
xmpz
value is set to 0!
- num_digits(base=10, /) int
Return length of string representing the absolute value of x in the given base. Values for base can range between 2 and 62. The value returned may be 1 too large.
- denominator
the denominator of a rational number in lowest terms
- numerator
the numerator of a rational number in lowest terms
- real
the real part of a complex number
Advanced Number Theory Functions
The following functions are based on mpz_lucas.c and mpz_prp.c by David Cleaver.
A good reference for probable prime testing is http://www.pseudoprime.com/pseudo.html
- gmpy2.is_bpsw_prp(n, /) bool
Return
True
if n is a Baillie-Pomerance-Selfridge-Wagstaff probable prime. A BPSW probable prime passes theis_strong_prp()
test with base 2 and theis_selfridge_prp()
test.
- gmpy2.is_euler_prp(n, a, /) bool
Return
True
if n is an Euler (also known as Solovay-Strassen) probable prime to the base a. Assuming:gcd(n,a) == 1 n is odd
Then an Euler probable prime requires:
a**((n-1)/2) == 1 (mod n)
- gmpy2.is_extra_strong_lucas_prp(n, p, /) bool
Return
True
if n is an extra strong Lucas probable prime with parameters (p,1). Assuming:n is odd D = p*p - 4, D != 0 gcd(n, 2*D) == 1 n = s*(2**r) + Jacobi(D,n), s odd
Then an extra strong Lucas probable prime requires:
lucasu(p,1,s) == 0 (mod n) or lucasv(p,1,s) == +/-2 (mod n) or lucasv(p,1,s*(2**t)) == 0 (mod n) for some t, 0 <= t < r
- gmpy2.is_fermat_prp(n, a, /) bool
Return
True
if n is a Fermat probable prime to the base a. Assuming:gcd(n,a) == 1
Then a Fermat probable prime requires:
a**(n-1) == 1 (mod n)
- gmpy2.is_fibonacci_prp(n, p, q, /) bool
Return
True
if n is a Fibonacci probable prime with parameters (p,q). Assuming:n is odd p > 0, q = +/-1 p*p - 4*q != 0
Then a Fibonacci probable prime requires:
lucasv(p,q,n) == p (mod n).
- gmpy2.is_lucas_prp(n, p, q, /) bool
Return
True
if n is a Lucas probable prime with parameters (p,q). Assuming:n is odd D = p*p - 4*q, D != 0 gcd(n, 2*q*D) == 1
Then a Lucas probable prime requires:
lucasu(p,q,n - Jacobi(D,n)) == 0 (mod n)
- gmpy2.is_selfridge_prp(n, /) bool
Return
True
if n is a Lucas probable prime with Selfidge parameters (p,q). The Selfridge parameters are chosen by finding the first element D in the sequence {5, -7, 9, -11, 13, …} such that Jacobi(D,n) == -1. Then let p=1 and q = (1-D)/4. Then perform a Lucas probable prime test.
- gmpy2.is_strong_bpsw_prp(n, /) bool
Return
True
if n is a strong Baillie-Pomerance-Selfridge-Wagstaff probable prime. A strong BPSW probable prime passes theis_strong_prp()
test with base and theis_strong_selfridge_prp()
test.
- gmpy2.is_strong_lucas_prp(n, p, q, /) bool
Return
True
if n is a strong Lucas probable prime with parameters (p,q). Assuming:n is odd D = p*p - 4*q, D != 0 gcd(n, 2*q*D) == 1 n = s*(2**r) + Jacobi(D,n), s odd
Then a strong Lucas probable prime requires:
lucasu(p,q,s) == 0 (mod n) or lucasv(p,q,s*(2**t)) == 0 (mod n) for some t, 0 <= t < r
- gmpy2.is_strong_prp(n, a, /) bool
Return
True
if n is a strong (also known as Miller-Rabin) probable prime to the base a. Assuming:gcd(n,a) == 1 n is odd n = s*(2**r) + 1, with s odd
Then a strong probable prime requires one of the following is true:
a**s == 1 (mod n) or a**(s*(2**t)) == -1 (mod n) for some t, 0 <= t < r.
- gmpy2.is_strong_selfridge_prp(n, /) bool
Return
True
if n is a strong Lucas probable prime with Selfidge parameters (p,q). The Selfridge parameters are chosen by finding the first element D in the sequence {5, -7, 9, -11, 13, …} such that Jacobi(D,n) == -1. Then let p=1 and q = (1-D)/4. Then perform a strong Lucas probable prime test.
- gmpy2.lucasu(p, q, k, /) mpz
Return the k-th element of the Lucas U sequence defined by p,q. p*p - 4*q must not equal 0; k must be greater than or equal to 0.
- gmpy2.lucasu_mod(p, q, k, n, /) mpz
Return the k-th element of the Lucas U sequence defined by p,q (mod n). p*p - 4*q must not equal 0; k must be greater than or equal to 0; n must be greater than 0.