1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
Integers (Advanced topics)
==========================
.. currentmodule:: gmpy2
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.
.. doctest::
>>> 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:
.. doctest::
>>> 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*.
.. doctest::
>>> a=xmpz(0)
>>> a[8:16] = ~0
>>> bin(a)
'0b1111111100000000'
>>> a[4:12] = ~a[4:12]
>>> bin(a)
'0b1111000011110000'
Bits can be reversed:
.. doctest::
>>> a = xmpz(1148)
>>> bin(a)
'0b10001111100'
>>> a[::] = a[::-1]
>>> bin(a)
'0b111110001'
The `~xmpz.iter_bits()` method returns a generator that returns True or
False for each bit position. The methods `~xmpz.iter_clear()`, and
`~xmpz.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.
.. doctest::
>>> 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.
.. code-block:: python
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))
The xmpz type
-------------
.. autoclass:: xmpz
:special-members: __format__
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
.. autofunction:: is_bpsw_prp
.. autofunction:: is_euler_prp
.. autofunction:: is_extra_strong_lucas_prp
.. autofunction:: is_fermat_prp
.. autofunction:: is_fibonacci_prp
.. autofunction:: is_lucas_prp
.. autofunction:: is_selfridge_prp
.. autofunction:: is_strong_bpsw_prp
.. autofunction:: is_strong_lucas_prp
.. autofunction:: is_strong_prp
.. autofunction:: is_strong_selfridge_prp
.. autofunction:: lucasu
.. autofunction:: lucasu_mod
.. autofunction:: lucasv
.. autofunction:: lucasv_mod
|
