cython

1
# mode: run
2

3
cdef extern from *:
4
    ctypedef long long int128_t "__int128_t"
5
    ctypedef unsigned long long uint128_t "__uint128_t"
6

7

8
def bigint(x):
9
    print(str(x).rstrip('L'))
10

11

12
def unsigned_conversion(x):
13
    """
14
    >>> bigint(unsigned_conversion(0))
15
    0
16
    >>> bigint(unsigned_conversion(2))
17
    2
18

19
    >>> unsigned_conversion(-2)  # doctest: +ELLIPSIS
20
    Traceback (most recent call last):
21
    OverflowError: can't convert negative value to ...uint128_t
22
    >>> unsigned_conversion(-2**120)  # doctest: +ELLIPSIS
23
    Traceback (most recent call last):
24
    OverflowError: can't convert negative value to ...uint128_t
25
    >>> unsigned_conversion(-2**127)  # doctest: +ELLIPSIS
26
    Traceback (most recent call last):
27
    OverflowError: can't convert negative value to ...uint128_t
28
    >>> unsigned_conversion(-2**128)  # doctest: +ELLIPSIS
29
    Traceback (most recent call last):
30
    OverflowError: can't convert negative value to ...uint128_t
31

32
    >>> bigint(unsigned_conversion(2**20))
33
    1048576
34
    >>> bigint(unsigned_conversion(2**30-1))
35
    1073741823
36
    >>> bigint(unsigned_conversion(2**30))
37
    1073741824
38
    >>> bigint(unsigned_conversion(2**30+1))
39
    1073741825
40

41
    >>> bigint(2**60)
42
    1152921504606846976
43
    >>> bigint(unsigned_conversion(2**60-1))
44
    1152921504606846975
45
    >>> bigint(unsigned_conversion(2**60))
46
    1152921504606846976
47
    >>> bigint(unsigned_conversion(2**60+1))
48
    1152921504606846977
49
    >>> bigint(2**64)
50
    18446744073709551616
51
    >>> bigint(unsigned_conversion(2**64))
52
    18446744073709551616
53

54
    >>> bigint(2**120)
55
    1329227995784915872903807060280344576
56
    >>> bigint(unsigned_conversion(2**120))
57
    1329227995784915872903807060280344576
58
    >>> bigint(2**128-1)
59
    340282366920938463463374607431768211455
60
    >>> bigint(unsigned_conversion(2**128-1))
61
    340282366920938463463374607431768211455
62
    >>> bigint(unsigned_conversion(2**128))  # doctest: +ELLIPSIS
63
    Traceback (most recent call last):
64
    OverflowError: ... to convert...
65
    >>> bigint(unsigned_conversion(2**128+1))  # doctest: +ELLIPSIS
66
    Traceback (most recent call last):
67
    OverflowError: ... to convert...
68
    >>> bigint(unsigned_conversion(2**129-1))  # doctest: +ELLIPSIS
69
    Traceback (most recent call last):
70
    OverflowError: ... to convert...
71
    >>> bigint(unsigned_conversion(2**129))  # doctest: +ELLIPSIS
72
    Traceback (most recent call last):
73
    OverflowError: ... to convert...
74
    """
75
    cdef uint128_t n = x
76
    return n
77

78

79
def signed_conversion(x):
80
    """
81
    >>> bigint(signed_conversion(0))
82
    0
83
    >>> bigint(signed_conversion(2))
84
    2
85
    >>> bigint(signed_conversion(-2))
86
    -2
87

88
    >>> bigint(signed_conversion(2**20))
89
    1048576
90
    >>> bigint(signed_conversion(2**32))
91
    4294967296
92
    >>> bigint(2**64)
93
    18446744073709551616
94
    >>> bigint(signed_conversion(2**64))
95
    18446744073709551616
96
    >>> bigint(signed_conversion(-2**64))
97
    -18446744073709551616
98

99
    >>> bigint(2**118)
100
    332306998946228968225951765070086144
101
    >>> bigint(signed_conversion(2**118))
102
    332306998946228968225951765070086144
103
    >>> bigint(signed_conversion(-2**118))
104
    -332306998946228968225951765070086144
105

106
    >>> bigint(2**120)
107
    1329227995784915872903807060280344576
108
    >>> bigint(signed_conversion(2**120))
109
    1329227995784915872903807060280344576
110
    >>> bigint(signed_conversion(-2**120))
111
    -1329227995784915872903807060280344576
112

113
    >>> bigint(2**127-1)
114
    170141183460469231731687303715884105727
115
    >>> bigint(signed_conversion(2**127-2))
116
    170141183460469231731687303715884105726
117
    >>> bigint(signed_conversion(2**127-1))
118
    170141183460469231731687303715884105727
119
    >>> bigint(signed_conversion(2**127))  # doctest: +ELLIPSIS
120
    Traceback (most recent call last):
121
    OverflowError: ... to convert...
122
    >>> bigint(signed_conversion(-2**127+1))
123
    -170141183460469231731687303715884105727
124
    >>> bigint(signed_conversion(-2**127))
125
    -170141183460469231731687303715884105728
126
    >>> bigint(signed_conversion(-2**127-1))  # doctest: +ELLIPSIS
127
    Traceback (most recent call last):
128
    OverflowError: ... to convert...
129
    >>> bigint(signed_conversion(-2**127-2))  # doctest: +ELLIPSIS
130
    Traceback (most recent call last):
131
    OverflowError: ... to convert...
132
    >>> bigint(signed_conversion(-2**128+1))  # doctest: +ELLIPSIS
133
    Traceback (most recent call last):
134
    OverflowError: ... to convert...
135
    >>> bigint(signed_conversion(-2**128))  # doctest: +ELLIPSIS
136
    Traceback (most recent call last):
137
    OverflowError: ... to convert...
138
    """
139
    cdef int128_t n = x
140
    return n
141

142

143
def get_int_distribution(shuffle=True):
144
    """
145
    >>> L = get_int_distribution()
146
    >>> bigint(L[0])
147
    682
148
    >>> bigint(L[ len(L) // 2 ])
149
    5617771410183435
150
    >>> bigint(L[-1])
151
    52818775009509558395695966805
152
    >>> len(L)
153
    66510
154
    """
155
    # Large integers that cover 1-4 (30 bits) or 1-7 (15 bits) PyLong digits.
156
    # Uses only integer calculations to avoid rounding issues.
157
    pow2 = [2**exp for exp in range(98)]
158
    ints = [
159
        n // 3
160
        for i in range(11, len(pow2) - 1)
161
        # Take a low but growing number of integers from each power-of-2 range.
162
        for n in range(pow2[i], pow2[i+1], pow2[i - 8] - 1)
163
    ]
164
    return ints * 3  # longer list, but keeps median in the middle
165

166

167
def intsum(L):
168
    """
169
    >>> L = get_int_distribution()
170
    >>> bigint(intsum(L))
171
    61084913298497804284622382871263
172
    >>> bigint(sum(L))
173
    61084913298497804284622382871263
174

175
    >>> from random import shuffle
176
    >>> shuffle(L)
177
    >>> bigint(intsum(L))
178
    61084913298497804284622382871263
179
    """
180
    cdef uint128_t i, x = 0
181
    for i in L:
182
        x += i
183
    return x
184

185

186
def intxor(L):
187
    """
188
    >>> L = get_int_distribution()
189
    >>> bigint(intxor(L))
190
    31773794341658093722410838161
191
    >>> bigint(intxor(L * 2))
192
    0
193
    >>> import operator
194
    >>> from functools import reduce
195
    >>> bigint(reduce(operator.xor, L))
196
    31773794341658093722410838161
197
    >>> bigint(reduce(operator.xor, L * 2))
198
    0
199

200
    >>> from random import shuffle
201
    >>> shuffle(L)
202
    >>> bigint(intxor(L))
203
    31773794341658093722410838161
204
    >>> bigint(intxor(L * 2))
205
    0
206
    """
207
    cdef uint128_t i, x = 0
208
    for i in L:
209
        x ^= i
210
    return x
211