Debian Codegraph @

Lib/test/test_long.py

raw
1 import unittest
2 from test import support
3
4 import sys
5
6 import random
7 import math
8 import array
9
10 # SHIFT should match the value in longintrepr.h for best testing.
11 SHIFT = sys.int_info.bits_per_digit
12 BASE = 2 ** SHIFT
13 MASK = BASE - 1
14 KARATSUBA_CUTOFF = 70 # from longobject.c
15
16 # Max number of base BASE digits to use in test cases. Doubling
17 # this will more than double the runtime.
18 MAXDIGITS = 15
19
20 # build some special values
21 special = [0, 1, 2, BASE, BASE >> 1, 0x5555555555555555, 0xaaaaaaaaaaaaaaaa]
22 # some solid strings of one bits
23 p2 = 4 # 0 and 1 already added
24 for i in range(2*SHIFT):
25 special.append(p2 - 1)
26 p2 = p2 << 1
27 del p2
28 # add complements & negations
29 special += [~x for x in special] + [-x for x in special]
30
31 DBL_MAX = sys.float_info.max
32 DBL_MAX_EXP = sys.float_info.max_exp
33 DBL_MIN_EXP = sys.float_info.min_exp
34 DBL_MANT_DIG = sys.float_info.mant_dig
35 DBL_MIN_OVERFLOW = 2**DBL_MAX_EXP - 2**(DBL_MAX_EXP - DBL_MANT_DIG - 1)
36
37
38 # Pure Python version of correctly-rounded integer-to-float conversion.
39 def int_to_float(n):
40 """
41 Correctly-rounded integer-to-float conversion.
42
43 """
44 # Constants, depending only on the floating-point format in use.
45 # We use an extra 2 bits of precision for rounding purposes.
46 PRECISION = sys.float_info.mant_dig + 2
47 SHIFT_MAX = sys.float_info.max_exp - PRECISION
48 Q_MAX = 1 << PRECISION
49 ROUND_HALF_TO_EVEN_CORRECTION = [0, -1, -2, 1, 0, -1, 2, 1]
50
51 # Reduce to the case where n is positive.
52 if n == 0:
53 return 0.0
54 elif n < 0:
55 return -int_to_float(-n)
56
57 # Convert n to a 'floating-point' number q * 2**shift, where q is an
58 # integer with 'PRECISION' significant bits. When shifting n to create q,
59 # the least significant bit of q is treated as 'sticky'. That is, the
60 # least significant bit of q is set if either the corresponding bit of n
61 # was already set, or any one of the bits of n lost in the shift was set.
62 shift = n.bit_length() - PRECISION
63 q = n << -shift if shift < 0 else (n >> shift) | bool(n & ~(-1 << shift))
64
65 # Round half to even (actually rounds to the nearest multiple of 4,
66 # rounding ties to a multiple of 8).
67 q += ROUND_HALF_TO_EVEN_CORRECTION[q & 7]
68
69 # Detect overflow.
70 if shift + (q == Q_MAX) > SHIFT_MAX:
71 raise OverflowError("integer too large to convert to float")
72
73 # Checks: q is exactly representable, and q**2**shift doesn't overflow.
74 assert q % 4 == 0 and q // 4 <= 2**(sys.float_info.mant_dig)
75 assert q * 2**shift <= sys.float_info.max
76
77 # Some circularity here, since float(q) is doing an int-to-float
78 # conversion. But here q is of bounded size, and is exactly representable
79 # as a float. In a low-level C-like language, this operation would be a
80 # simple cast (e.g., from unsigned long long to double).
81 return math.ldexp(float(q), shift)
82
83
84 # pure Python version of correctly-rounded true division
85 def truediv(a, b):
86 """Correctly-rounded true division for integers."""
87 negative = a^b < 0
88 a, b = abs(a), abs(b)
89
90 # exceptions: division by zero, overflow
91 if not b:
92 raise ZeroDivisionError("division by zero")
93 if a >= DBL_MIN_OVERFLOW * b:
94 raise OverflowError("int/int too large to represent as a float")
95
96 # find integer d satisfying 2**(d - 1) <= a/b < 2**d
97 d = a.bit_length() - b.bit_length()
98 if d >= 0 and a >= 2**d * b or d < 0 and a * 2**-d >= b:
99 d += 1
100
101 # compute 2**-exp * a / b for suitable exp
102 exp = max(d, DBL_MIN_EXP) - DBL_MANT_DIG
103 a, b = a << max(-exp, 0), b << max(exp, 0)
104 q, r = divmod(a, b)
105
106 # round-half-to-even: fractional part is r/b, which is > 0.5 iff
107 # 2*r > b, and == 0.5 iff 2*r == b.
108 if 2*r > b or 2*r == b and q % 2 == 1:
109 q += 1
110
111 result = math.ldexp(q, exp)
112 return -result if negative else result
113
114
115 class LongTest(unittest.TestCase):
116
117 # Get quasi-random long consisting of ndigits digits (in base BASE).
118 # quasi == the most-significant digit will not be 0, and the number
119 # is constructed to contain long strings of 0 and 1 bits. These are
120 # more likely than random bits to provoke digit-boundary errors.
121 # The sign of the number is also random.
122
123 def getran(self, ndigits):
124 self.assertGreater(ndigits, 0)
125 nbits_hi = ndigits * SHIFT
126 nbits_lo = nbits_hi - SHIFT + 1
127 answer = 0
128 nbits = 0
129 r = int(random.random() * (SHIFT * 2)) | 1 # force 1 bits to start
130 while nbits < nbits_lo:
131 bits = (r >> 1) + 1
132 bits = min(bits, nbits_hi - nbits)
133 self.assertTrue(1 <= bits <= SHIFT)
134 nbits = nbits + bits
135 answer = answer << bits
136 if r & 1:
137 answer = answer | ((1 << bits) - 1)
138 r = int(random.random() * (SHIFT * 2))
139 self.assertTrue(nbits_lo <= nbits <= nbits_hi)
140 if random.random() < 0.5:
141 answer = -answer
142 return answer
143
144 # Get random long consisting of ndigits random digits (relative to base
145 # BASE). The sign bit is also random.
146
147 def getran2(ndigits):
148 answer = 0
149 for i in range(ndigits):
150 answer = (answer << SHIFT) | random.randint(0, MASK)
151 if random.random() < 0.5:
152 answer = -answer
153 return answer
154
155 def check_division(self, x, y):
156 eq = self.assertEqual
157 with self.subTest(x=x, y=y):
158 q, r = divmod(x, y)
159 q2, r2 = x//y, x%y
160 pab, pba = x*y, y*x
161 eq(pab, pba, "multiplication does not commute")
162 eq(q, q2, "divmod returns different quotient than /")
163 eq(r, r2, "divmod returns different mod than %")
164 eq(x, q*y + r, "x != q*y + r after divmod")
165 if y > 0:
166 self.assertTrue(0 <= r < y, "bad mod from divmod")
167 else:
168 self.assertTrue(y < r <= 0, "bad mod from divmod")
169
170 def test_division(self):
171 digits = list(range(1, MAXDIGITS+1)) + list(range(KARATSUBA_CUTOFF,
172 KARATSUBA_CUTOFF + 14))
173 digits.append(KARATSUBA_CUTOFF * 3)
174 for lenx in digits:
175 x = self.getran(lenx)
176 for leny in digits:
177 y = self.getran(leny) or 1
178 self.check_division(x, y)
179
180 # specific numbers chosen to exercise corner cases of the
181 # current long division implementation
182
183 # 30-bit cases involving a quotient digit estimate of BASE+1
184 self.check_division(1231948412290879395966702881,
185 1147341367131428698)
186 self.check_division(815427756481275430342312021515587883,
187 707270836069027745)
188 self.check_division(627976073697012820849443363563599041,
189 643588798496057020)
190 self.check_division(1115141373653752303710932756325578065,
191 1038556335171453937726882627)
192 # 30-bit cases that require the post-subtraction correction step
193 self.check_division(922498905405436751940989320930368494,
194 949985870686786135626943396)
195 self.check_division(768235853328091167204009652174031844,
196 1091555541180371554426545266)
197
198 # 15-bit cases involving a quotient digit estimate of BASE+1
199 self.check_division(20172188947443, 615611397)
200 self.check_division(1020908530270155025, 950795710)
201 self.check_division(128589565723112408, 736393718)
202 self.check_division(609919780285761575, 18613274546784)
203 # 15-bit cases that require the post-subtraction correction step
204 self.check_division(710031681576388032, 26769404391308)
205 self.check_division(1933622614268221, 30212853348836)
206
207
208
209 def test_karatsuba(self):
210 digits = list(range(1, 5)) + list(range(KARATSUBA_CUTOFF,
211 KARATSUBA_CUTOFF + 10))
212 digits.extend([KARATSUBA_CUTOFF * 10, KARATSUBA_CUTOFF * 100])
213
214 bits = [digit * SHIFT for digit in digits]
215
216 # Test products of long strings of 1 bits -- (2**x-1)*(2**y-1) ==
217 # 2**(x+y) - 2**x - 2**y + 1, so the proper result is easy to check.
218 for abits in bits:
219 a = (1 << abits) - 1
220 for bbits in bits:
221 if bbits < abits:
222 continue
223 with self.subTest(abits=abits, bbits=bbits):
224 b = (1 << bbits) - 1
225 x = a * b
226 y = ((1 << (abits + bbits)) -
227 (1 << abits) -
228 (1 << bbits) +
229 1)
230 self.assertEqual(x, y)
231
232 def check_bitop_identities_1(self, x):
233 eq = self.assertEqual
234 with self.subTest(x=x):
235 eq(x & 0, 0)
236 eq(x | 0, x)
237 eq(x ^ 0, x)
238 eq(x & -1, x)
239 eq(x | -1, -1)
240 eq(x ^ -1, ~x)
241 eq(x, ~~x)
242 eq(x & x, x)
243 eq(x | x, x)
244 eq(x ^ x, 0)
245 eq(x & ~x, 0)
246 eq(x | ~x, -1)
247 eq(x ^ ~x, -1)
248 eq(-x, 1 + ~x)
249 eq(-x, ~(x-1))
250 for n in range(2*SHIFT):
251 p2 = 2 ** n
252 with self.subTest(x=x, n=n, p2=p2):
253 eq(x << n >> n, x)
254 eq(x // p2, x >> n)
255 eq(x * p2, x << n)
256 eq(x & -p2, x >> n << n)
257 eq(x & -p2, x & ~(p2 - 1))
258
259 def check_bitop_identities_2(self, x, y):
260 eq = self.assertEqual
261 with self.subTest(x=x, y=y):
262 eq(x & y, y & x)
263 eq(x | y, y | x)
264 eq(x ^ y, y ^ x)
265 eq(x ^ y ^ x, y)
266 eq(x & y, ~(~x | ~y))
267 eq(x | y, ~(~x & ~y))
268 eq(x ^ y, (x | y) & ~(x & y))
269 eq(x ^ y, (x & ~y) | (~x & y))
270 eq(x ^ y, (x | y) & (~x | ~y))
271
272 def check_bitop_identities_3(self, x, y, z):
273 eq = self.assertEqual
274 with self.subTest(x=x, y=y, z=z):
275 eq((x & y) & z, x & (y & z))
276 eq((x | y) | z, x | (y | z))
277 eq((x ^ y) ^ z, x ^ (y ^ z))
278 eq(x & (y | z), (x & y) | (x & z))
279 eq(x | (y & z), (x | y) & (x | z))
280
281 def test_bitop_identities(self):
282 for x in special:
283 self.check_bitop_identities_1(x)
284 digits = range(1, MAXDIGITS+1)
285 for lenx in digits:
286 x = self.getran(lenx)
287 self.check_bitop_identities_1(x)
288 for leny in digits:
289 y = self.getran(leny)
290 self.check_bitop_identities_2(x, y)
291 self.check_bitop_identities_3(x, y, self.getran((lenx + leny)//2))
292
293 def slow_format(self, x, base):
294 digits = []
295 sign = 0
296 if x < 0:
297 sign, x = 1, -x
298 while x:
299 x, r = divmod(x, base)
300 digits.append(int(r))
301 digits.reverse()
302 digits = digits or [0]
303 return '-'[:sign] + \
304 {2: '0b', 8: '0o', 10: '', 16: '0x'}[base] + \
305 "".join("0123456789abcdef"[i] for i in digits)
306
307 def check_format_1(self, x):
308 for base, mapper in (2, bin), (8, oct), (10, str), (10, repr), (16, hex):
309 got = mapper(x)
310 with self.subTest(x=x, mapper=mapper.__name__):
311 expected = self.slow_format(x, base)
312 self.assertEqual(got, expected)
313 with self.subTest(got=got):
314 self.assertEqual(int(got, 0), x)
315
316 def test_format(self):
317 for x in special:
318 self.check_format_1(x)
319 for i in range(10):
320 for lenx in range(1, MAXDIGITS+1):
321 x = self.getran(lenx)
322 self.check_format_1(x)
323
324 def test_long(self):
325 # Check conversions from string
326 LL = [
327 ('1' + '0'*20, 10**20),
328 ('1' + '0'*100, 10**100)
329 ]
330 for s, v in LL:
331 for sign in "", "+", "-":
332 for prefix in "", " ", "\t", " \t\t ":
333 ss = prefix + sign + s
334 vv = v
335 if sign == "-" and v is not ValueError:
336 vv = -v
337 try:
338 self.assertEqual(int(ss), vv)
339 except ValueError:
340 pass
341
342 # trailing L should no longer be accepted...
343 self.assertRaises(ValueError, int, '123L')
344 self.assertRaises(ValueError, int, '123l')
345 self.assertRaises(ValueError, int, '0L')
346 self.assertRaises(ValueError, int, '-37L')
347 self.assertRaises(ValueError, int, '0x32L', 16)
348 self.assertRaises(ValueError, int, '1L', 21)
349 # ... but it's just a normal digit if base >= 22
350 self.assertEqual(int('1L', 22), 43)
351
352 # tests with base 0
353 self.assertEqual(int('000', 0), 0)
354 self.assertEqual(int('0o123', 0), 83)
355 self.assertEqual(int('0x123', 0), 291)
356 self.assertEqual(int('0b100', 0), 4)
357 self.assertEqual(int(' 0O123 ', 0), 83)
358 self.assertEqual(int(' 0X123 ', 0), 291)
359 self.assertEqual(int(' 0B100 ', 0), 4)
360 self.assertEqual(int('0', 0), 0)
361 self.assertEqual(int('+0', 0), 0)
362 self.assertEqual(int('-0', 0), 0)
363 self.assertEqual(int('00', 0), 0)
364 self.assertRaises(ValueError, int, '08', 0)
365 self.assertRaises(ValueError, int, '-012395', 0)
366
367 # invalid bases
368 invalid_bases = [-909,
369 2**31-1, 2**31, -2**31, -2**31-1,
370 2**63-1, 2**63, -2**63, -2**63-1,
371 2**100, -2**100,
372 ]
373 for base in invalid_bases:
374 self.assertRaises(ValueError, int, '42', base)
375
376 # Invalid unicode string
377 # See bpo-34087
378 self.assertRaises(ValueError, int, '\u3053\u3093\u306b\u3061\u306f')
379
380
381 def test_conversion(self):
382
383 class JustLong:
384 # test that __long__ no longer used in 3.x
385 def __long__(self):
386 return 42
387 self.assertRaises(TypeError, int, JustLong())
388
389 def check_float_conversion(self, n):
390 # Check that int -> float conversion behaviour matches
391 # that of the pure Python version above.
392 try:
393 actual = float(n)
394 except OverflowError:
395 actual = 'overflow'
396
397 try:
398 expected = int_to_float(n)
399 except OverflowError:
400 expected = 'overflow'
401
402 msg = ("Error in conversion of integer {} to float. "
403 "Got {}, expected {}.".format(n, actual, expected))
404 self.assertEqual(actual, expected, msg)
405
406 @support.requires_IEEE_754
407 def test_float_conversion(self):
408
409 exact_values = [0, 1, 2,
410 2**53-3,
411 2**53-2,
412 2**53-1,
413 2**53,
414 2**53+2,
415 2**54-4,
416 2**54-2,
417 2**54,
418 2**54+4]
419 for x in exact_values:
420 self.assertEqual(float(x), x)
421 self.assertEqual(float(-x), -x)
422
423 # test round-half-even
424 for x, y in [(1, 0), (2, 2), (3, 4), (4, 4), (5, 4), (6, 6), (7, 8)]:
425 for p in range(15):
426 self.assertEqual(int(float(2**p*(2**53+x))), 2**p*(2**53+y))
427
428 for x, y in [(0, 0), (1, 0), (2, 0), (3, 4), (4, 4), (5, 4), (6, 8),
429 (7, 8), (8, 8), (9, 8), (10, 8), (11, 12), (12, 12),
430 (13, 12), (14, 16), (15, 16)]:
431 for p in range(15):
432 self.assertEqual(int(float(2**p*(2**54+x))), 2**p*(2**54+y))
433
434 # behaviour near extremes of floating-point range
435 int_dbl_max = int(DBL_MAX)
436 top_power = 2**DBL_MAX_EXP
437 halfway = (int_dbl_max + top_power)//2
438 self.assertEqual(float(int_dbl_max), DBL_MAX)
439 self.assertEqual(float(int_dbl_max+1), DBL_MAX)
440 self.assertEqual(float(halfway-1), DBL_MAX)
441 self.assertRaises(OverflowError, float, halfway)
442 self.assertEqual(float(1-halfway), -DBL_MAX)
443 self.assertRaises(OverflowError, float, -halfway)
444 self.assertRaises(OverflowError, float, top_power-1)
445 self.assertRaises(OverflowError, float, top_power)
446 self.assertRaises(OverflowError, float, top_power+1)
447 self.assertRaises(OverflowError, float, 2*top_power-1)
448 self.assertRaises(OverflowError, float, 2*top_power)
449 self.assertRaises(OverflowError, float, top_power*top_power)
450
451 for p in range(100):
452 x = 2**p * (2**53 + 1) + 1
453 y = 2**p * (2**53 + 2)
454 self.assertEqual(int(float(x)), y)
455
456 x = 2**p * (2**53 + 1)
457 y = 2**p * 2**53
458 self.assertEqual(int(float(x)), y)
459
460 # Compare builtin float conversion with pure Python int_to_float
461 # function above.
462 test_values = [
463 int_dbl_max-1, int_dbl_max, int_dbl_max+1,
464 halfway-1, halfway, halfway + 1,
465 top_power-1, top_power, top_power+1,
466 2*top_power-1, 2*top_power, top_power*top_power,
467 ]
468 test_values.extend(exact_values)
469 for p in range(-4, 8):
470 for x in range(-128, 128):
471 test_values.append(2**(p+53) + x)
472 for value in test_values:
473 self.check_float_conversion(value)
474 self.check_float_conversion(-value)
475
476 @support.requires_IEEE_754
477 @support.bigmemtest(2**32, memuse=0.2)
478 def test_float_conversion_huge_integer(self, size):
479 v = 1 << size
480 self.assertRaises(OverflowError, float, v)
481
482 def test_float_overflow(self):
483 for x in -2.0, -1.0, 0.0, 1.0, 2.0:
484 self.assertEqual(float(int(x)), x)
485
486 shuge = '12345' * 120
487 huge = 1 << 30000
488 mhuge = -huge
489 namespace = {'huge': huge, 'mhuge': mhuge, 'shuge': shuge, 'math': math}
490 for test in ["float(huge)", "float(mhuge)",
491 "complex(huge)", "complex(mhuge)",
492 "complex(huge, 1)", "complex(mhuge, 1)",
493 "complex(1, huge)", "complex(1, mhuge)",
494 "1. + huge", "huge + 1.", "1. + mhuge", "mhuge + 1.",
495 "1. - huge", "huge - 1.", "1. - mhuge", "mhuge - 1.",
496 "1. * huge", "huge * 1.", "1. * mhuge", "mhuge * 1.",
497 "1. // huge", "huge // 1.", "1. // mhuge", "mhuge // 1.",
498 "1. / huge", "huge / 1.", "1. / mhuge", "mhuge / 1.",
499 "1. ** huge", "huge ** 1.", "1. ** mhuge", "mhuge ** 1.",
500 "math.sin(huge)", "math.sin(mhuge)",
501 "math.sqrt(huge)", "math.sqrt(mhuge)", # should do better
502 # math.floor() of an int returns an int now
503 ##"math.floor(huge)", "math.floor(mhuge)",
504 ]:
505
506 self.assertRaises(OverflowError, eval, test, namespace)
507
508 # XXX Perhaps float(shuge) can raise OverflowError on some box?
509 # The comparison should not.
510 self.assertNotEqual(float(shuge), int(shuge),
511 "float(shuge) should not equal int(shuge)")
512
513 def test_logs(self):
514 LOG10E = math.log10(math.e)
515
516 for exp in list(range(10)) + [100, 1000, 10000]:
517 value = 10 ** exp
518 log10 = math.log10(value)
519 self.assertAlmostEqual(log10, exp)
520
521 # log10(value) == exp, so log(value) == log10(value)/log10(e) ==
522 # exp/LOG10E
523 expected = exp / LOG10E
524 log = math.log(value)
525 self.assertAlmostEqual(log, expected)
526
527 for bad in -(1 << 10000), -2, 0:
528 self.assertRaises(ValueError, math.log, bad)
529 self.assertRaises(ValueError, math.log10, bad)
530
531 def test_mixed_compares(self):
532 eq = self.assertEqual
533
534 # We're mostly concerned with that mixing floats and ints does the
535 # right stuff, even when ints are too large to fit in a float.
536 # The safest way to check the results is to use an entirely different
537 # method, which we do here via a skeletal rational class (which
538 # represents all Python ints and floats exactly).
539 class Rat:
540 def __init__(self, value):
541 if isinstance(value, int):
542 self.n = value
543 self.d = 1
544 elif isinstance(value, float):
545 # Convert to exact rational equivalent.
546 f, e = math.frexp(abs(value))
547 assert f == 0 or 0.5 <= f < 1.0
548 # |value| = f * 2**e exactly
549
550 # Suck up CHUNK bits at a time; 28 is enough so that we suck
551 # up all bits in 2 iterations for all known binary double-
552 # precision formats, and small enough to fit in an int.
553 CHUNK = 28
554 top = 0
555 # invariant: |value| = (top + f) * 2**e exactly
556 while f:
557 f = math.ldexp(f, CHUNK)
558 digit = int(f)
559 assert digit >> CHUNK == 0
560 top = (top << CHUNK) | digit
561 f -= digit
562 assert 0.0 <= f < 1.0
563 e -= CHUNK
564
565 # Now |value| = top * 2**e exactly.
566 if e >= 0:
567 n = top << e
568 d = 1
569 else:
570 n = top
571 d = 1 << -e
572 if value < 0:
573 n = -n
574 self.n = n
575 self.d = d
576 assert float(n) / float(d) == value
577 else:
578 raise TypeError("can't deal with %r" % value)
579
580 def _cmp__(self, other):
581 if not isinstance(other, Rat):
582 other = Rat(other)
583 x, y = self.n * other.d, self.d * other.n
584 return (x > y) - (x < y)
585 def __eq__(self, other):
586 return self._cmp__(other) == 0
587 def __ge__(self, other):
588 return self._cmp__(other) >= 0
589 def __gt__(self, other):
590 return self._cmp__(other) > 0
591 def __le__(self, other):
592 return self._cmp__(other) <= 0
593 def __lt__(self, other):
594 return self._cmp__(other) < 0
595
596 cases = [0, 0.001, 0.99, 1.0, 1.5, 1e20, 1e200]
597 # 2**48 is an important boundary in the internals. 2**53 is an
598 # important boundary for IEEE double precision.
599 for t in 2.0**48, 2.0**50, 2.0**53:
600 cases.extend([t - 1.0, t - 0.3, t, t + 0.3, t + 1.0,
601 int(t-1), int(t), int(t+1)])
602 cases.extend([0, 1, 2, sys.maxsize, float(sys.maxsize)])
603 # 1 << 20000 should exceed all double formats. int(1e200) is to
604 # check that we get equality with 1e200 above.
605 t = int(1e200)
606 cases.extend([0, 1, 2, 1 << 20000, t-1, t, t+1])
607 cases.extend([-x for x in cases])
608 for x in cases:
609 Rx = Rat(x)
610 for y in cases:
611 Ry = Rat(y)
612 Rcmp = (Rx > Ry) - (Rx < Ry)
613 with self.subTest(x=x, y=y, Rcmp=Rcmp):
614 xycmp = (x > y) - (x < y)
615 eq(Rcmp, xycmp)
616 eq(x == y, Rcmp == 0)
617 eq(x != y, Rcmp != 0)
618 eq(x < y, Rcmp < 0)
619 eq(x <= y, Rcmp <= 0)
620 eq(x > y, Rcmp > 0)
621 eq(x >= y, Rcmp >= 0)
622
623 @support.requires_IEEE_754
624 @support.bigmemtest(2**32, memuse=0.2)
625 def test_mixed_compares_huge_integer(self, size):
626 v = 1 << size
627 f = sys.float_info.max
628 self.assertIs(f == v, False)
629 self.assertIs(f != v, True)
630 self.assertIs(f < v, True)
631 self.assertIs(f <= v, True)
632 self.assertIs(f > v, False)
633 self.assertIs(f >= v, False)
634 f = float('inf')
635 self.assertIs(f == v, False)
636 self.assertIs(f != v, True)
637 self.assertIs(f < v, False)
638 self.assertIs(f <= v, False)
639 self.assertIs(f > v, True)
640 self.assertIs(f >= v, True)
641 f = float('nan')
642 self.assertIs(f == v, False)
643 self.assertIs(f != v, True)
644 self.assertIs(f < v, False)
645 self.assertIs(f <= v, False)
646 self.assertIs(f > v, False)
647 self.assertIs(f >= v, False)
648
649 del v
650 v = (-1) << size
651 f = -sys.float_info.max
652 self.assertIs(f == v, False)
653 self.assertIs(f != v, True)
654 self.assertIs(f < v, False)
655 self.assertIs(f <= v, False)
656 self.assertIs(f > v, True)
657 self.assertIs(f >= v, True)
658 f = float('-inf')
659 self.assertIs(f == v, False)
660 self.assertIs(f != v, True)
661 self.assertIs(f < v, True)
662 self.assertIs(f <= v, True)
663 self.assertIs(f > v, False)
664 self.assertIs(f >= v, False)
665 f = float('nan')
666 self.assertIs(f == v, False)
667 self.assertIs(f != v, True)
668 self.assertIs(f < v, False)
669 self.assertIs(f <= v, False)
670 self.assertIs(f > v, False)
671 self.assertIs(f >= v, False)
672
673 def test__format__(self):
674 self.assertEqual(format(123456789, 'd'), '123456789')
675 self.assertEqual(format(123456789, 'd'), '123456789')
676 self.assertEqual(format(123456789, ','), '123,456,789')
677 self.assertEqual(format(123456789, '_'), '123_456_789')
678
679 # sign and aligning are interdependent
680 self.assertEqual(format(1, "-"), '1')
681 self.assertEqual(format(-1, "-"), '-1')
682 self.assertEqual(format(1, "-3"), ' 1')
683 self.assertEqual(format(-1, "-3"), ' -1')
684 self.assertEqual(format(1, "+3"), ' +1')
685 self.assertEqual(format(-1, "+3"), ' -1')
686 self.assertEqual(format(1, " 3"), ' 1')
687 self.assertEqual(format(-1, " 3"), ' -1')
688 self.assertEqual(format(1, " "), ' 1')
689 self.assertEqual(format(-1, " "), '-1')
690
691 # hex
692 self.assertEqual(format(3, "x"), "3")
693 self.assertEqual(format(3, "X"), "3")
694 self.assertEqual(format(1234, "x"), "4d2")
695 self.assertEqual(format(-1234, "x"), "-4d2")
696 self.assertEqual(format(1234, "8x"), " 4d2")
697 self.assertEqual(format(-1234, "8x"), " -4d2")
698 self.assertEqual(format(1234, "x"), "4d2")
699 self.assertEqual(format(-1234, "x"), "-4d2")
700 self.assertEqual(format(-3, "x"), "-3")
701 self.assertEqual(format(-3, "X"), "-3")
702 self.assertEqual(format(int('be', 16), "x"), "be")
703 self.assertEqual(format(int('be', 16), "X"), "BE")
704 self.assertEqual(format(-int('be', 16), "x"), "-be")
705 self.assertEqual(format(-int('be', 16), "X"), "-BE")
706 self.assertRaises(ValueError, format, 1234567890, ',x')
707 self.assertEqual(format(1234567890, '_x'), '4996_02d2')
708 self.assertEqual(format(1234567890, '_X'), '4996_02D2')
709
710 # octal
711 self.assertEqual(format(3, "o"), "3")
712 self.assertEqual(format(-3, "o"), "-3")
713 self.assertEqual(format(1234, "o"), "2322")
714 self.assertEqual(format(-1234, "o"), "-2322")
715 self.assertEqual(format(1234, "-o"), "2322")
716 self.assertEqual(format(-1234, "-o"), "-2322")
717 self.assertEqual(format(1234, " o"), " 2322")
718 self.assertEqual(format(-1234, " o"), "-2322")
719 self.assertEqual(format(1234, "+o"), "+2322")
720 self.assertEqual(format(-1234, "+o"), "-2322")
721 self.assertRaises(ValueError, format, 1234567890, ',o')
722 self.assertEqual(format(1234567890, '_o'), '111_4540_1322')
723
724 # binary
725 self.assertEqual(format(3, "b"), "11")
726 self.assertEqual(format(-3, "b"), "-11")
727 self.assertEqual(format(1234, "b"), "10011010010")
728 self.assertEqual(format(-1234, "b"), "-10011010010")
729 self.assertEqual(format(1234, "-b"), "10011010010")
730 self.assertEqual(format(-1234, "-b"), "-10011010010")
731 self.assertEqual(format(1234, " b"), " 10011010010")
732 self.assertEqual(format(-1234, " b"), "-10011010010")
733 self.assertEqual(format(1234, "+b"), "+10011010010")
734 self.assertEqual(format(-1234, "+b"), "-10011010010")
735 self.assertRaises(ValueError, format, 1234567890, ',b')
736 self.assertEqual(format(12345, '_b'), '11_0000_0011_1001')
737
738 # make sure these are errors
739 self.assertRaises(ValueError, format, 3, "1.3") # precision disallowed
740 self.assertRaises(ValueError, format, 3, "_c") # underscore,
741 self.assertRaises(ValueError, format, 3, ",c") # comma, and
742 self.assertRaises(ValueError, format, 3, "+c") # sign not allowed
743 # with 'c'
744
745 self.assertRaisesRegex(ValueError, 'Cannot specify both', format, 3, '_,')
746 self.assertRaisesRegex(ValueError, 'Cannot specify both', format, 3, ',_')
747 self.assertRaisesRegex(ValueError, 'Cannot specify both', format, 3, '_,d')
748 self.assertRaisesRegex(ValueError, 'Cannot specify both', format, 3, ',_d')
749
750 self.assertRaisesRegex(ValueError, "Cannot specify ',' with 's'", format, 3, ',s')
751 self.assertRaisesRegex(ValueError, "Cannot specify '_' with 's'", format, 3, '_s')
752
753 # ensure that only int and float type specifiers work
754 for format_spec in ([chr(x) for x in range(ord('a'), ord('z')+1)] +
755 [chr(x) for x in range(ord('A'), ord('Z')+1)]):
756 if not format_spec in 'bcdoxXeEfFgGn%':
757 self.assertRaises(ValueError, format, 0, format_spec)
758 self.assertRaises(ValueError, format, 1, format_spec)
759 self.assertRaises(ValueError, format, -1, format_spec)
760 self.assertRaises(ValueError, format, 2**100, format_spec)
761 self.assertRaises(ValueError, format, -(2**100), format_spec)
762
763 # ensure that float type specifiers work; format converts
764 # the int to a float
765 for format_spec in 'eEfFgG%':
766 for value in [0, 1, -1, 100, -100, 1234567890, -1234567890]:
767 self.assertEqual(format(value, format_spec),
768 format(float(value), format_spec))
769
770 def test_nan_inf(self):
771 self.assertRaises(OverflowError, int, float('inf'))
772 self.assertRaises(OverflowError, int, float('-inf'))
773 self.assertRaises(ValueError, int, float('nan'))
774
775 def test_mod_division(self):
776 with self.assertRaises(ZeroDivisionError):
777 _ = 1 % 0
778
779 self.assertEqual(13 % 10, 3)
780 self.assertEqual(-13 % 10, 7)
781 self.assertEqual(13 % -10, -7)
782 self.assertEqual(-13 % -10, -3)
783
784 self.assertEqual(12 % 4, 0)
785 self.assertEqual(-12 % 4, 0)
786 self.assertEqual(12 % -4, 0)
787 self.assertEqual(-12 % -4, 0)
788
789 def test_true_division(self):
790 huge = 1 << 40000
791 mhuge = -huge
792 self.assertEqual(huge / huge, 1.0)
793 self.assertEqual(mhuge / mhuge, 1.0)
794 self.assertEqual(huge / mhuge, -1.0)
795 self.assertEqual(mhuge / huge, -1.0)
796 self.assertEqual(1 / huge, 0.0)
797 self.assertEqual(1 / huge, 0.0)
798 self.assertEqual(1 / mhuge, 0.0)
799 self.assertEqual(1 / mhuge, 0.0)
800 self.assertEqual((666 * huge + (huge >> 1)) / huge, 666.5)
801 self.assertEqual((666 * mhuge + (mhuge >> 1)) / mhuge, 666.5)
802 self.assertEqual((666 * huge + (huge >> 1)) / mhuge, -666.5)
803 self.assertEqual((666 * mhuge + (mhuge >> 1)) / huge, -666.5)
804 self.assertEqual(huge / (huge << 1), 0.5)
805 self.assertEqual((1000000 * huge) / huge, 1000000)
806
807 namespace = {'huge': huge, 'mhuge': mhuge}
808
809 for overflow in ["float(huge)", "float(mhuge)",
810 "huge / 1", "huge / 2", "huge / -1", "huge / -2",
811 "mhuge / 100", "mhuge / 200"]:
812 self.assertRaises(OverflowError, eval, overflow, namespace)
813
814 for underflow in ["1 / huge", "2 / huge", "-1 / huge", "-2 / huge",
815 "100 / mhuge", "200 / mhuge"]:
816 result = eval(underflow, namespace)
817 self.assertEqual(result, 0.0,
818 "expected underflow to 0 from %r" % underflow)
819
820 for zero in ["huge / 0", "mhuge / 0"]:
821 self.assertRaises(ZeroDivisionError, eval, zero, namespace)
822
823 def test_floordiv(self):
824 with self.assertRaises(ZeroDivisionError):
825 _ = 1 // 0
826
827 self.assertEqual(2 // 3, 0)
828 self.assertEqual(2 // -3, -1)
829 self.assertEqual(-2 // 3, -1)
830 self.assertEqual(-2 // -3, 0)
831
832 self.assertEqual(-11 // -3, 3)
833 self.assertEqual(-11 // 3, -4)
834 self.assertEqual(11 // -3, -4)
835 self.assertEqual(11 // 3, 3)
836
837 self.assertEqual(-12 // -3, 4)
838 self.assertEqual(-12 // 3, -4)
839 self.assertEqual(12 // -3, -4)
840 self.assertEqual(12 // 3, 4)
841
842 def check_truediv(self, a, b, skip_small=True):
843 """Verify that the result of a/b is correctly rounded, by
844 comparing it with a pure Python implementation of correctly
845 rounded division. b should be nonzero."""
846
847 # skip check for small a and b: in this case, the current
848 # implementation converts the arguments to float directly and
849 # then applies a float division. This can give doubly-rounded
850 # results on x87-using machines (particularly 32-bit Linux).
851 if skip_small and max(abs(a), abs(b)) < 2**DBL_MANT_DIG:
852 return
853
854 try:
855 # use repr so that we can distinguish between -0.0 and 0.0
856 expected = repr(truediv(a, b))
857 except OverflowError:
858 expected = 'overflow'
859 except ZeroDivisionError:
860 expected = 'zerodivision'
861
862 try:
863 got = repr(a / b)
864 except OverflowError:
865 got = 'overflow'
866 except ZeroDivisionError:
867 got = 'zerodivision'
868
869 self.assertEqual(expected, got, "Incorrectly rounded division {}/{}: "
870 "expected {}, got {}".format(a, b, expected, got))
871
872 @support.requires_IEEE_754
873 def test_correctly_rounded_true_division(self):
874 # more stringent tests than those above, checking that the
875 # result of true division of ints is always correctly rounded.
876 # This test should probably be considered CPython-specific.
877
878 # Exercise all the code paths not involving Gb-sized ints.
879 # ... divisions involving zero
880 self.check_truediv(123, 0)
881 self.check_truediv(-456, 0)
882 self.check_truediv(0, 3)
883 self.check_truediv(0, -3)
884 self.check_truediv(0, 0)
885 # ... overflow or underflow by large margin
886 self.check_truediv(671 * 12345 * 2**DBL_MAX_EXP, 12345)
887 self.check_truediv(12345, 345678 * 2**(DBL_MANT_DIG - DBL_MIN_EXP))
888 # ... a much larger or smaller than b
889 self.check_truediv(12345*2**100, 98765)
890 self.check_truediv(12345*2**30, 98765*7**81)
891 # ... a / b near a boundary: one of 1, 2**DBL_MANT_DIG, 2**DBL_MIN_EXP,
892 # 2**DBL_MAX_EXP, 2**(DBL_MIN_EXP-DBL_MANT_DIG)
893 bases = (0, DBL_MANT_DIG, DBL_MIN_EXP,
894 DBL_MAX_EXP, DBL_MIN_EXP - DBL_MANT_DIG)
895 for base in bases:
896 for exp in range(base - 15, base + 15):
897 self.check_truediv(75312*2**max(exp, 0), 69187*2**max(-exp, 0))
898 self.check_truediv(69187*2**max(exp, 0), 75312*2**max(-exp, 0))
899
900 # overflow corner case
901 for m in [1, 2, 7, 17, 12345, 7**100,
902 -1, -2, -5, -23, -67891, -41**50]:
903 for n in range(-10, 10):
904 self.check_truediv(m*DBL_MIN_OVERFLOW + n, m)
905 self.check_truediv(m*DBL_MIN_OVERFLOW + n, -m)
906
907 # check detection of inexactness in shifting stage
908 for n in range(250):
909 # (2**DBL_MANT_DIG+1)/(2**DBL_MANT_DIG) lies halfway
910 # between two representable floats, and would usually be
911 # rounded down under round-half-to-even. The tiniest of
912 # additions to the numerator should cause it to be rounded
913 # up instead.
914 self.check_truediv((2**DBL_MANT_DIG + 1)*12345*2**200 + 2**n,
915 2**DBL_MANT_DIG*12345)
916
917 # 1/2731 is one of the smallest division cases that's subject
918 # to double rounding on IEEE 754 machines working internally with
919 # 64-bit precision. On such machines, the next check would fail,
920 # were it not explicitly skipped in check_truediv.
921 self.check_truediv(1, 2731)
922
923 # a particularly bad case for the old algorithm: gives an
924 # error of close to 3.5 ulps.
925 self.check_truediv(295147931372582273023, 295147932265116303360)
926 for i in range(1000):
927 self.check_truediv(10**(i+1), 10**i)
928 self.check_truediv(10**i, 10**(i+1))
929
930 # test round-half-to-even behaviour, normal result
931 for m in [1, 2, 4, 7, 8, 16, 17, 32, 12345, 7**100,
932 -1, -2, -5, -23, -67891, -41**50]:
933 for n in range(-10, 10):
934 self.check_truediv(2**DBL_MANT_DIG*m + n, m)
935
936 # test round-half-to-even, subnormal result
937 for n in range(-20, 20):
938 self.check_truediv(n, 2**1076)
939
940 # largeish random divisions: a/b where |a| <= |b| <=
941 # 2*|a|; |ans| is between 0.5 and 1.0, so error should
942 # always be bounded by 2**-54 with equality possible only
943 # if the least significant bit of q=ans*2**53 is zero.
944 for M in [10**10, 10**100, 10**1000]:
945 for i in range(1000):
946 a = random.randrange(1, M)
947 b = random.randrange(a, 2*a+1)
948 self.check_truediv(a, b)
949 self.check_truediv(-a, b)
950 self.check_truediv(a, -b)
951 self.check_truediv(-a, -b)
952
953 # and some (genuinely) random tests
954 for _ in range(10000):
955 a_bits = random.randrange(1000)
956 b_bits = random.randrange(1, 1000)
957 x = random.randrange(2**a_bits)
958 y = random.randrange(1, 2**b_bits)
959 self.check_truediv(x, y)
960 self.check_truediv(x, -y)
961 self.check_truediv(-x, y)
962 self.check_truediv(-x, -y)
963
964 def test_negative_shift_count(self):
965 with self.assertRaises(ValueError):
966 42 << -3
967 with self.assertRaises(ValueError):
968 42 << -(1 << 1000)
969 with self.assertRaises(ValueError):
970 42 >> -3
971 with self.assertRaises(ValueError):
972 42 >> -(1 << 1000)
973
974 def test_lshift_of_zero(self):
975 self.assertEqual(0 << 0, 0)
976 self.assertEqual(0 << 10, 0)
977 with self.assertRaises(ValueError):
978 0 << -1
979 self.assertEqual(0 << (1 << 1000), 0)
980 with self.assertRaises(ValueError):
981 0 << -(1 << 1000)
982
983 @support.cpython_only
984 def test_huge_lshift_of_zero(self):
985 # Shouldn't try to allocate memory for a huge shift. See issue #27870.
986 # Other implementations may have a different boundary for overflow,
987 # or not raise at all.
988 self.assertEqual(0 << sys.maxsize, 0)
989 self.assertEqual(0 << (sys.maxsize + 1), 0)
990
991 @support.cpython_only
992 @support.bigmemtest(2**32, memuse=0.2)
993 def test_huge_lshift(self, size):
994 v = 5 << size
995 self.assertEqual(v.bit_length(), size + 3)
996 self.assertEqual(v.bit_count(), 2)
997 self.assertEqual(v >> size, 5)
998
999 def test_huge_rshift(self):
1000 huge_shift = 1 << 1000
1001 self.assertEqual(42 >> huge_shift, 0)
1002 self.assertEqual((-42) >> huge_shift, -1)
1003 self.assertEqual(1123 >> huge_shift, 0)
1004 self.assertEqual((-1123) >> huge_shift, -1)
1005 self.assertEqual(2**128 >> huge_shift, 0)
1006 self.assertEqual(-2**128 >> huge_shift, -1)
1007
1008 @support.cpython_only
1009 @support.bigmemtest(2**32, memuse=0.2)
1010 def test_huge_rshift_of_huge(self, size):
1011 huge = ((1 << 500) + 11) << size
1012 self.assertEqual(huge.bit_length(), size + 501)
1013 self.assertEqual(huge.bit_count(), 4)
1014 self.assertEqual(huge >> (size + 1), (1 << 499) + 5)
1015 self.assertEqual(huge >> (size + 1000), 0)
1016
1017 def test_small_rshift(self):
1018 self.assertEqual(42 >> 1, 21)
1019 self.assertEqual((-42) >> 1, -21)
1020 self.assertEqual(43 >> 1, 21)
1021 self.assertEqual((-43) >> 1, -22)
1022
1023 self.assertEqual(1122 >> 1, 561)
1024 self.assertEqual((-1122) >> 1, -561)
1025 self.assertEqual(1123 >> 1, 561)
1026 self.assertEqual((-1123) >> 1, -562)
1027
1028 self.assertEqual(2**128 >> 1, 2**127)
1029 self.assertEqual(-2**128 >> 1, -2**127)
1030 self.assertEqual((2**128 + 1) >> 1, 2**127)
1031 self.assertEqual(-(2**128 + 1) >> 1, -2**127 - 1)
1032
1033 def test_medium_rshift(self):
1034 self.assertEqual(42 >> 9, 0)
1035 self.assertEqual((-42) >> 9, -1)
1036 self.assertEqual(1122 >> 9, 2)
1037 self.assertEqual((-1122) >> 9, -3)
1038 self.assertEqual(2**128 >> 9, 2**119)
1039 self.assertEqual(-2**128 >> 9, -2**119)
1040 # Exercise corner case of the current algorithm, where the result of
1041 # shifting a two-limb int by the limb size still has two limbs.
1042 self.assertEqual((1 - BASE*BASE) >> SHIFT, -BASE)
1043 self.assertEqual((BASE - 1 - BASE*BASE) >> SHIFT, -BASE)
1044
1045 def test_big_rshift(self):
1046 self.assertEqual(42 >> 32, 0)
1047 self.assertEqual((-42) >> 32, -1)
1048 self.assertEqual(1122 >> 32, 0)
1049 self.assertEqual((-1122) >> 32, -1)
1050 self.assertEqual(2**128 >> 32, 2**96)
1051 self.assertEqual(-2**128 >> 32, -2**96)
1052
1053 def test_small_lshift(self):
1054 self.assertEqual(42 << 1, 84)
1055 self.assertEqual((-42) << 1, -84)
1056 self.assertEqual(561 << 1, 1122)
1057 self.assertEqual((-561) << 1, -1122)
1058 self.assertEqual(2**127 << 1, 2**128)
1059 self.assertEqual(-2**127 << 1, -2**128)
1060
1061 def test_medium_lshift(self):
1062 self.assertEqual(42 << 9, 21504)
1063 self.assertEqual((-42) << 9, -21504)
1064 self.assertEqual(1122 << 9, 574464)
1065 self.assertEqual((-1122) << 9, -574464)
1066
1067 def test_big_lshift(self):
1068 self.assertEqual(42 << 32, 42 * 2**32)
1069 self.assertEqual((-42) << 32, -42 * 2**32)
1070 self.assertEqual(1122 << 32, 1122 * 2**32)
1071 self.assertEqual((-1122) << 32, -1122 * 2**32)
1072 self.assertEqual(2**128 << 32, 2**160)
1073 self.assertEqual(-2**128 << 32, -2**160)
1074
1075 @support.cpython_only
1076 def test_small_ints_in_huge_calculation(self):
1077 a = 2 ** 100
1078 b = -a + 1
1079 c = a + 1
1080 self.assertIs(a + b, 1)
1081 self.assertIs(c - a, 1)
1082
1083 @support.cpython_only
1084 def test_pow_uses_cached_small_ints(self):
1085 self.assertIs(pow(10, 3, 998), 2)
1086 self.assertIs(10 ** 3 % 998, 2)
1087 a, p, m = 10, 3, 998
1088 self.assertIs(a ** p % m, 2)
1089
1090 self.assertIs(pow(2, 31, 2 ** 31 - 1), 1)
1091 self.assertIs(2 ** 31 % (2 ** 31 - 1), 1)
1092 a, p, m = 2, 31, 2 ** 31 - 1
1093 self.assertIs(a ** p % m, 1)
1094
1095 self.assertIs(pow(2, 100, 2**100 - 3), 3)
1096 self.assertIs(2 ** 100 % (2 ** 100 - 3), 3)
1097 a, p, m = 2, 100, 2**100 - 3
1098 self.assertIs(a ** p % m, 3)
1099
1100 @support.cpython_only
1101 def test_divmod_uses_cached_small_ints(self):
1102 big = 10 ** 100
1103
1104 self.assertIs((big + 1) % big, 1)
1105 self.assertIs((big + 1) // big, 1)
1106 self.assertIs(big // (big // 2), 2)
1107 self.assertIs(big // (big // -4), -4)
1108
1109 q, r = divmod(2 * big + 3, big)
1110 self.assertIs(q, 2)
1111 self.assertIs(r, 3)
1112
1113 q, r = divmod(-4 * big + 100, big)
1114 self.assertIs(q, -4)
1115 self.assertIs(r, 100)
1116
1117 q, r = divmod(3 * (-big) - 1, -big)
1118 self.assertIs(q, 3)
1119 self.assertIs(r, -1)
1120
1121 q, r = divmod(3 * big - 1, -big)
1122 self.assertIs(q, -3)
1123 self.assertIs(r, -1)
1124
1125 def test_small_ints(self):
1126 for i in range(-5, 257):
1127 self.assertIs(i, i + 0)
1128 self.assertIs(i, i * 1)
1129 self.assertIs(i, i - 0)
1130 self.assertIs(i, i // 1)
1131 self.assertIs(i, i & -1)
1132 self.assertIs(i, i | 0)
1133 self.assertIs(i, i ^ 0)
1134 self.assertIs(i, ~~i)
1135 self.assertIs(i, i**1)
1136 self.assertIs(i, int(str(i)))
1137 self.assertIs(i, i<<2>>2, str(i))
1138 # corner cases
1139 i = 1 << 70
1140 self.assertIs(i - i, 0)
1141 self.assertIs(0 * i, 0)
1142
1143 def test_bit_length(self):
1144 tiny = 1e-10
1145 for x in range(-65000, 65000):
1146 k = x.bit_length()
1147 # Check equivalence with Python version
1148 self.assertEqual(k, len(bin(x).lstrip('-0b')))
1149 # Behaviour as specified in the docs
1150 if x != 0:
1151 self.assertTrue(2**(k-1) <= abs(x) < 2**k)
1152 else:
1153 self.assertEqual(k, 0)
1154 # Alternative definition: x.bit_length() == 1 + floor(log_2(x))
1155 if x != 0:
1156 # When x is an exact power of 2, numeric errors can
1157 # cause floor(log(x)/log(2)) to be one too small; for
1158 # small x this can be fixed by adding a small quantity
1159 # to the quotient before taking the floor.
1160 self.assertEqual(k, 1 + math.floor(
1161 math.log(abs(x))/math.log(2) + tiny))
1162
1163 self.assertEqual((0).bit_length(), 0)
1164 self.assertEqual((1).bit_length(), 1)
1165 self.assertEqual((-1).bit_length(), 1)
1166 self.assertEqual((2).bit_length(), 2)
1167 self.assertEqual((-2).bit_length(), 2)
1168 for i in [2, 3, 15, 16, 17, 31, 32, 33, 63, 64, 234]:
1169 a = 2**i
1170 self.assertEqual((a-1).bit_length(), i)
1171 self.assertEqual((1-a).bit_length(), i)
1172 self.assertEqual((a).bit_length(), i+1)
1173 self.assertEqual((-a).bit_length(), i+1)
1174 self.assertEqual((a+1).bit_length(), i+1)
1175 self.assertEqual((-a-1).bit_length(), i+1)
1176
1177 def test_bit_count(self):
1178 for a in range(-1000, 1000):
1179 self.assertEqual(a.bit_count(), bin(a).count("1"))
1180
1181 for exp in [10, 17, 63, 64, 65, 1009, 70234, 1234567]:
1182 a = 2**exp
1183 self.assertEqual(a.bit_count(), 1)
1184 self.assertEqual((a - 1).bit_count(), exp)
1185 self.assertEqual((a ^ 63).bit_count(), 7)
1186 self.assertEqual(((a - 1) ^ 510).bit_count(), exp - 8)
1187
1188 def test_round(self):
1189 # check round-half-even algorithm. For round to nearest ten;
1190 # rounding map is invariant under adding multiples of 20
1191 test_dict = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0,
1192 6:10, 7:10, 8:10, 9:10, 10:10, 11:10, 12:10, 13:10, 14:10,
1193 15:20, 16:20, 17:20, 18:20, 19:20}
1194 for offset in range(-520, 520, 20):
1195 for k, v in test_dict.items():
1196 got = round(k+offset, -1)
1197 expected = v+offset
1198 self.assertEqual(got, expected)
1199 self.assertIs(type(got), int)
1200
1201 # larger second argument
1202 self.assertEqual(round(-150, -2), -200)
1203 self.assertEqual(round(-149, -2), -100)
1204 self.assertEqual(round(-51, -2), -100)
1205 self.assertEqual(round(-50, -2), 0)
1206 self.assertEqual(round(-49, -2), 0)
1207 self.assertEqual(round(-1, -2), 0)
1208 self.assertEqual(round(0, -2), 0)
1209 self.assertEqual(round(1, -2), 0)
1210 self.assertEqual(round(49, -2), 0)
1211 self.assertEqual(round(50, -2), 0)
1212 self.assertEqual(round(51, -2), 100)
1213 self.assertEqual(round(149, -2), 100)
1214 self.assertEqual(round(150, -2), 200)
1215 self.assertEqual(round(250, -2), 200)
1216 self.assertEqual(round(251, -2), 300)
1217 self.assertEqual(round(172500, -3), 172000)
1218 self.assertEqual(round(173500, -3), 174000)
1219 self.assertEqual(round(31415926535, -1), 31415926540)
1220 self.assertEqual(round(31415926535, -2), 31415926500)
1221 self.assertEqual(round(31415926535, -3), 31415927000)
1222 self.assertEqual(round(31415926535, -4), 31415930000)
1223 self.assertEqual(round(31415926535, -5), 31415900000)
1224 self.assertEqual(round(31415926535, -6), 31416000000)
1225 self.assertEqual(round(31415926535, -7), 31420000000)
1226 self.assertEqual(round(31415926535, -8), 31400000000)
1227 self.assertEqual(round(31415926535, -9), 31000000000)
1228 self.assertEqual(round(31415926535, -10), 30000000000)
1229 self.assertEqual(round(31415926535, -11), 0)
1230 self.assertEqual(round(31415926535, -12), 0)
1231 self.assertEqual(round(31415926535, -999), 0)
1232
1233 # should get correct results even for huge inputs
1234 for k in range(10, 100):
1235 got = round(10**k + 324678, -3)
1236 expect = 10**k + 325000
1237 self.assertEqual(got, expect)
1238 self.assertIs(type(got), int)
1239
1240 # nonnegative second argument: round(x, n) should just return x
1241 for n in range(5):
1242 for i in range(100):
1243 x = random.randrange(-10000, 10000)
1244 got = round(x, n)
1245 self.assertEqual(got, x)
1246 self.assertIs(type(got), int)
1247 for huge_n in 2**31-1, 2**31, 2**63-1, 2**63, 2**100, 10**100:
1248 self.assertEqual(round(8979323, huge_n), 8979323)
1249
1250 # omitted second argument
1251 for i in range(100):
1252 x = random.randrange(-10000, 10000)
1253 got = round(x)
1254 self.assertEqual(got, x)
1255 self.assertIs(type(got), int)
1256
1257 # bad second argument
1258 bad_exponents = ('brian', 2.0, 0j)
1259 for e in bad_exponents:
1260 self.assertRaises(TypeError, round, 3, e)
1261
1262 def test_to_bytes(self):
1263 def check(tests, byteorder, signed=False):
1264 def equivalent_python(n, length, byteorder, signed=False):
1265 if byteorder == 'little':
1266 order = range(length)
1267 elif byteorder == 'big':
1268 order = reversed(range(length))
1269 return bytes((n >> i*8) & 0xff for i in order)
1270
1271 for test, expected in tests.items():
1272 try:
1273 self.assertEqual(
1274 test.to_bytes(len(expected), byteorder, signed=signed),
1275 expected)
1276 except Exception as err:
1277 raise AssertionError(
1278 "failed to convert {} with byteorder={} and signed={}"
1279 .format(test, byteorder, signed)) from err
1280
1281 # Test for all default arguments.
1282 if len(expected) == 1 and byteorder == 'big' and not signed:
1283 try:
1284 self.assertEqual(test.to_bytes(), expected)
1285 except Exception as err:
1286 raise AssertionError(
1287 "failed to convert {} with default arguments"
1288 .format(test)) from err
1289
1290 try:
1291 self.assertEqual(
1292 equivalent_python(
1293 test, len(expected), byteorder, signed=signed),
1294 expected
1295 )
1296 except Exception as err:
1297 raise AssertionError(
1298 "Code equivalent from docs is not equivalent for "
1299 "conversion of {0} with byteorder byteorder={1} and "
1300 "signed={2}".format(test, byteorder, signed)) from err
1301
1302 # Convert integers to signed big-endian byte arrays.
1303 tests1 = {
1304 0: b'\x00',
1305 1: b'\x01',
1306 -1: b'\xff',
1307 -127: b'\x81',
1308 -128: b'\x80',
1309 -129: b'\xff\x7f',
1310 127: b'\x7f',
1311 129: b'\x00\x81',
1312 -255: b'\xff\x01',
1313 -256: b'\xff\x00',
1314 255: b'\x00\xff',
1315 256: b'\x01\x00',
1316 32767: b'\x7f\xff',
1317 -32768: b'\xff\x80\x00',
1318 65535: b'\x00\xff\xff',
1319 -65536: b'\xff\x00\x00',
1320 -8388608: b'\x80\x00\x00'
1321 }
1322 check(tests1, 'big', signed=True)
1323
1324 # Convert integers to signed little-endian byte arrays.
1325 tests2 = {
1326 0: b'\x00',
1327 1: b'\x01',
1328 -1: b'\xff',
1329 -127: b'\x81',
1330 -128: b'\x80',
1331 -129: b'\x7f\xff',
1332 127: b'\x7f',
1333 129: b'\x81\x00',
1334 -255: b'\x01\xff',
1335 -256: b'\x00\xff',
1336 255: b'\xff\x00',
1337 256: b'\x00\x01',
1338 32767: b'\xff\x7f',
1339 -32768: b'\x00\x80',
1340 65535: b'\xff\xff\x00',
1341 -65536: b'\x00\x00\xff',
1342 -8388608: b'\x00\x00\x80'
1343 }
1344 check(tests2, 'little', signed=True)
1345
1346 # Convert integers to unsigned big-endian byte arrays.
1347 tests3 = {
1348 0: b'\x00',
1349 1: b'\x01',
1350 127: b'\x7f',
1351 128: b'\x80',
1352 255: b'\xff',
1353 256: b'\x01\x00',
1354 32767: b'\x7f\xff',
1355 32768: b'\x80\x00',
1356 65535: b'\xff\xff',
1357 65536: b'\x01\x00\x00'
1358 }
1359 check(tests3, 'big', signed=False)
1360
1361 # Convert integers to unsigned little-endian byte arrays.
1362 tests4 = {
1363 0: b'\x00',
1364 1: b'\x01',
1365 127: b'\x7f',
1366 128: b'\x80',
1367 255: b'\xff',
1368 256: b'\x00\x01',
1369 32767: b'\xff\x7f',
1370 32768: b'\x00\x80',
1371 65535: b'\xff\xff',
1372 65536: b'\x00\x00\x01'
1373 }
1374 check(tests4, 'little', signed=False)
1375
1376 self.assertRaises(OverflowError, (256).to_bytes, 1, 'big', signed=False)
1377 self.assertRaises(OverflowError, (256).to_bytes, 1, 'little', signed=False)
1378 self.assertRaises(OverflowError, (128).to_bytes, 1, 'big', signed=True)
1379 self.assertRaises(OverflowError, (128).to_bytes, 1, 'little', signed=True)
1380 self.assertRaises(OverflowError, (-129).to_bytes, 1, 'big', signed=True)
1381 self.assertRaises(OverflowError, (-129).to_bytes, 1, 'little', signed=True)
1382 self.assertRaises(OverflowError, (-1).to_bytes, 2, 'big', signed=False)
1383 self.assertRaises(OverflowError, (-1).to_bytes, 2, 'little', signed=False)
1384 self.assertEqual((0).to_bytes(0, 'big'), b'')
1385 self.assertEqual((0).to_bytes(0, 'big', signed=True), b'')
1386 self.assertEqual((1).to_bytes(5, 'big'), b'\x00\x00\x00\x00\x01')
1387 self.assertEqual((0).to_bytes(5, 'big'), b'\x00\x00\x00\x00\x00')
1388 self.assertEqual((-1).to_bytes(5, 'big', signed=True),
1389 b'\xff\xff\xff\xff\xff')
1390 self.assertRaises(OverflowError, (1).to_bytes, 0, 'big')
1391 self.assertRaises(OverflowError, (-1).to_bytes, 0, 'big', signed=True)
1392 self.assertRaises(OverflowError, (-1).to_bytes, 0, 'little', signed=True)
1393
1394 # gh-98783
1395 class SubStr(str):
1396 pass
1397 self.assertEqual((0).to_bytes(1, SubStr('big')), b'\x00')
1398 self.assertEqual((0).to_bytes(0, SubStr('little')), b'')
1399
1400 def test_from_bytes(self):
1401 def check(tests, byteorder, signed=False):
1402 def equivalent_python(byte_array, byteorder, signed=False):
1403 if byteorder == 'little':
1404 little_ordered = list(byte_array)
1405 elif byteorder == 'big':
1406 little_ordered = list(reversed(byte_array))
1407
1408 n = sum(b << i*8 for i, b in enumerate(little_ordered))
1409 if signed and little_ordered and (little_ordered[-1] & 0x80):
1410 n -= 1 << 8*len(little_ordered)
1411
1412 return n
1413
1414 for test, expected in tests.items():
1415 try:
1416 self.assertEqual(
1417 int.from_bytes(test, byteorder, signed=signed),
1418 expected)
1419 except Exception as err:
1420 raise AssertionError(
1421 "failed to convert {} with byteorder={!r} and signed={}"
1422 .format(test, byteorder, signed)) from err
1423
1424 # Test for all default arguments.
1425 if byteorder == 'big' and not signed:
1426 try:
1427 self.assertEqual(
1428 int.from_bytes(test),
1429 expected)
1430 except Exception as err:
1431 raise AssertionError(
1432 "failed to convert {} with default arguments"
1433 .format(test)) from err
1434
1435 try:
1436 self.assertEqual(
1437 equivalent_python(test, byteorder, signed=signed),
1438 expected
1439 )
1440 except Exception as err:
1441 raise AssertionError(
1442 "Code equivalent from docs is not equivalent for "
1443 "conversion of {0} with byteorder={1!r} and signed={2}"
1444 .format(test, byteorder, signed)) from err
1445
1446 # Convert signed big-endian byte arrays to integers.
1447 tests1 = {
1448 b'': 0,
1449 b'\x00': 0,
1450 b'\x00\x00': 0,
1451 b'\x01': 1,
1452 b'\x00\x01': 1,
1453 b'\xff': -1,
1454 b'\xff\xff': -1,
1455 b'\x81': -127,
1456 b'\x80': -128,
1457 b'\xff\x7f': -129,
1458 b'\x7f': 127,
1459 b'\x00\x81': 129,
1460 b'\xff\x01': -255,
1461 b'\xff\x00': -256,
1462 b'\x00\xff': 255,
1463 b'\x01\x00': 256,
1464 b'\x7f\xff': 32767,
1465 b'\x80\x00': -32768,
1466 b'\x00\xff\xff': 65535,
1467 b'\xff\x00\x00': -65536,
1468 b'\x80\x00\x00': -8388608
1469 }
1470 check(tests1, 'big', signed=True)
1471
1472 # Convert signed little-endian byte arrays to integers.
1473 tests2 = {
1474 b'': 0,
1475 b'\x00': 0,
1476 b'\x00\x00': 0,
1477 b'\x01': 1,
1478 b'\xff': -1,
1479 b'\xff\xff': -1,
1480 b'\x81': -127,
1481 b'\x80': -128,
1482 b'\x7f\xff': -129,
1483 b'\x7f': 127,
1484 b'\x81\x00': 129,
1485 b'\x01\xff': -255,
1486 b'\x00\xff': -256,
1487 b'\xff\x00': 255,
1488 b'\x00\x01': 256,
1489 b'\xff\x7f': 32767,
1490 b'\x00\x80': -32768,
1491 b'\xff\xff\x00': 65535,
1492 b'\x00\x00\xff': -65536,
1493 b'\x00\x00\x80': -8388608
1494 }
1495 check(tests2, 'little', signed=True)
1496
1497 # Convert unsigned big-endian byte arrays to integers.
1498 tests3 = {
1499 b'': 0,
1500 b'\x00': 0,
1501 b'\x01': 1,
1502 b'\x7f': 127,
1503 b'\x80': 128,
1504 b'\xff': 255,
1505 b'\x01\x00': 256,
1506 b'\x7f\xff': 32767,
1507 b'\x80\x00': 32768,
1508 b'\xff\xff': 65535,
1509 b'\x01\x00\x00': 65536,
1510 }
1511 check(tests3, 'big', signed=False)
1512
1513 # Convert integers to unsigned little-endian byte arrays.
1514 tests4 = {
1515 b'': 0,
1516 b'\x00': 0,
1517 b'\x01': 1,
1518 b'\x7f': 127,
1519 b'\x80': 128,
1520 b'\xff': 255,
1521 b'\x00\x01': 256,
1522 b'\xff\x7f': 32767,
1523 b'\x00\x80': 32768,
1524 b'\xff\xff': 65535,
1525 b'\x00\x00\x01': 65536,
1526 }
1527 check(tests4, 'little', signed=False)
1528
1529 class myint(int):
1530 pass
1531
1532 self.assertIs(type(myint.from_bytes(b'\x00', 'big')), myint)
1533 self.assertEqual(myint.from_bytes(b'\x01', 'big'), 1)
1534 self.assertIs(
1535 type(myint.from_bytes(b'\x00', 'big', signed=False)), myint)
1536 self.assertEqual(myint.from_bytes(b'\x01', 'big', signed=False), 1)
1537 self.assertIs(type(myint.from_bytes(b'\x00', 'little')), myint)
1538 self.assertEqual(myint.from_bytes(b'\x01', 'little'), 1)
1539 self.assertIs(type(myint.from_bytes(
1540 b'\x00', 'little', signed=False)), myint)
1541 self.assertEqual(myint.from_bytes(b'\x01', 'little', signed=False), 1)
1542 self.assertEqual(
1543 int.from_bytes([255, 0, 0], 'big', signed=True), -65536)
1544 self.assertEqual(
1545 int.from_bytes((255, 0, 0), 'big', signed=True), -65536)
1546 self.assertEqual(int.from_bytes(
1547 bytearray(b'\xff\x00\x00'), 'big', signed=True), -65536)
1548 self.assertEqual(int.from_bytes(
1549 bytearray(b'\xff\x00\x00'), 'big', signed=True), -65536)
1550 self.assertEqual(int.from_bytes(
1551 array.array('B', b'\xff\x00\x00'), 'big', signed=True), -65536)
1552 self.assertEqual(int.from_bytes(
1553 memoryview(b'\xff\x00\x00'), 'big', signed=True), -65536)
1554 self.assertRaises(ValueError, int.from_bytes, [256], 'big')
1555 self.assertRaises(ValueError, int.from_bytes, [0], 'big\x00')
1556 self.assertRaises(ValueError, int.from_bytes, [0], 'little\x00')
1557 self.assertRaises(TypeError, int.from_bytes, "", 'big')
1558 self.assertRaises(TypeError, int.from_bytes, "\x00", 'big')
1559 self.assertRaises(TypeError, int.from_bytes, 0, 'big')
1560 self.assertRaises(TypeError, int.from_bytes, 0, 'big', True)
1561 self.assertRaises(TypeError, myint.from_bytes, "", 'big')
1562 self.assertRaises(TypeError, myint.from_bytes, "\x00", 'big')
1563 self.assertRaises(TypeError, myint.from_bytes, 0, 'big')
1564 self.assertRaises(TypeError, int.from_bytes, 0, 'big', True)
1565
1566 class myint2(int):
1567 def __new__(cls, value):
1568 return int.__new__(cls, value + 1)
1569
1570 i = myint2.from_bytes(b'\x01', 'big')
1571 self.assertIs(type(i), myint2)
1572 self.assertEqual(i, 2)
1573
1574 class myint3(int):
1575 def __init__(self, value):
1576 self.foo = 'bar'
1577
1578 i = myint3.from_bytes(b'\x01', 'big')
1579 self.assertIs(type(i), myint3)
1580 self.assertEqual(i, 1)
1581 self.assertEqual(getattr(i, 'foo', 'none'), 'bar')
1582
1583 class ValidBytes:
1584 def __bytes__(self):
1585 return b'\x01'
1586 class InvalidBytes:
1587 def __bytes__(self):
1588 return 'abc'
1589 class MissingBytes: ...
1590 class RaisingBytes:
1591 def __bytes__(self):
1592 1 / 0
1593
1594 self.assertEqual(int.from_bytes(ValidBytes()), 1)
1595 self.assertRaises(TypeError, int.from_bytes, InvalidBytes())
1596 self.assertRaises(TypeError, int.from_bytes, MissingBytes())
1597 self.assertRaises(ZeroDivisionError, int.from_bytes, RaisingBytes())
1598
1599 # gh-98783
1600 class SubStr(str):
1601 pass
1602 self.assertEqual(int.from_bytes(b'', SubStr('big')), 0)
1603 self.assertEqual(int.from_bytes(b'\x00', SubStr('little')), 0)
1604
1605 @support.cpython_only
1606 def test_from_bytes_small(self):
1607 # bpo-46361
1608 for i in range(-5, 257):
1609 b = i.to_bytes(2, signed=True)
1610 self.assertIs(int.from_bytes(b, signed=True), i)
1611
1612 def test_is_integer(self):
1613 self.assertTrue((-1).is_integer())
1614 self.assertTrue((0).is_integer())
1615 self.assertTrue((1).is_integer())
1616
1617 def test_access_to_nonexistent_digit_0(self):
1618 # http://bugs.python.org/issue14630: A bug in _PyLong_Copy meant that
1619 # ob_digit[0] was being incorrectly accessed for instances of a
1620 # subclass of int, with value 0.
1621 class Integer(int):
1622 def __new__(cls, value=0):
1623 self = int.__new__(cls, value)
1624 self.foo = 'foo'
1625 return self
1626
1627 integers = [Integer(0) for i in range(1000)]
1628 for n in map(int, integers):
1629 self.assertEqual(n, 0)
1630
1631 def test_shift_bool(self):
1632 # Issue #21422: ensure that bool << int and bool >> int return int
1633 for value in (True, False):
1634 for shift in (0, 2):
1635 self.assertEqual(type(value << shift), int)
1636 self.assertEqual(type(value >> shift), int)
1637
1638 def test_as_integer_ratio(self):
1639 class myint(int):
1640 pass
1641 tests = [10, 0, -10, 1, sys.maxsize + 1, True, False, myint(42)]
1642 for value in tests:
1643 numerator, denominator = value.as_integer_ratio()
1644 self.assertEqual((numerator, denominator), (int(value), 1))
1645 self.assertEqual(type(numerator), int)
1646 self.assertEqual(type(denominator), int)
1647
1648 def test_square(self):
1649 # Multiplication makes a special case of multiplying an int with
1650 # itself, using a special, faster algorithm. This test is mostly
1651 # to ensure that no asserts in the implementation trigger, in
1652 # cases with a maximal amount of carries.
1653 for bitlen in range(1, 400):
1654 n = (1 << bitlen) - 1 # solid string of 1 bits
1655 with self.subTest(bitlen=bitlen, n=n):
1656 # (2**i - 1)**2 = 2**(2*i) - 2*2**i + 1
1657 self.assertEqual(n**2,
1658 (1 << (2 * bitlen)) - (1 << (bitlen + 1)) + 1)
1659
1660 def test___sizeof__(self):
1661 self.assertEqual(int.__itemsize__, sys.int_info.sizeof_digit)
1662
1663 # Pairs (test_value, number of allocated digits)
1664 test_values = [
1665 # We always allocate space for at least one digit, even for
1666 # a value of zero; sys.getsizeof should reflect that.
1667 (0, 1),
1668 (1, 1),
1669 (-1, 1),
1670 (BASE-1, 1),
1671 (1-BASE, 1),
1672 (BASE, 2),
1673 (-BASE, 2),
1674 (BASE*BASE - 1, 2),
1675 (BASE*BASE, 3),
1676 ]
1677
1678 for value, ndigits in test_values:
1679 with self.subTest(value):
1680 self.assertEqual(
1681 value.__sizeof__(),
1682 int.__basicsize__ + int.__itemsize__ * ndigits
1683 )
1684
1685 # Same test for a subclass of int.
1686 class MyInt(int):
1687 pass
1688
1689 self.assertEqual(MyInt.__itemsize__, sys.int_info.sizeof_digit)
1690
1691 for value, ndigits in test_values:
1692 with self.subTest(value):
1693 self.assertEqual(
1694 MyInt(value).__sizeof__(),
1695 MyInt.__basicsize__ + MyInt.__itemsize__ * ndigits
1696 )
1697
1698 # GH-117195 -- This shouldn't crash
1699 object.__sizeof__(1)
1700
1701 def test_hash(self):
1702 # gh-136599
1703 self.assertEqual(hash(-1), -2)
1704 self.assertEqual(hash(0), 0)
1705 self.assertEqual(hash(10), 10)
1706
1707 self.assertEqual(hash(sys.hash_info.modulus - 2), sys.hash_info.modulus - 2)
1708 self.assertEqual(hash(sys.hash_info.modulus - 1), sys.hash_info.modulus - 1)
1709 self.assertEqual(hash(sys.hash_info.modulus), 0)
1710 self.assertEqual(hash(sys.hash_info.modulus + 1), 1)
1711
1712 self.assertEqual(hash(-sys.hash_info.modulus - 2), -2)
1713 self.assertEqual(hash(-sys.hash_info.modulus - 1), -2)
1714 self.assertEqual(hash(-sys.hash_info.modulus), 0)
1715 self.assertEqual(hash(-sys.hash_info.modulus + 1), -sys.hash_info.modulus + 1)
1716
1717 if __name__ == "__main__":
1718 unittest.main()