Repository URL to install this package:
import unittest
from test import support
import sys
import random
import math
import array
# SHIFT should match the value in longintrepr.h for best testing.
SHIFT = sys.int_info.bits_per_digit
BASE = 2 ** SHIFT
MASK = BASE - 1
KARATSUBA_CUTOFF = 70 # from longobject.c
# Max number of base BASE digits to use in test cases. Doubling
# this will more than double the runtime.
MAXDIGITS = 15
# build some special values
special = [0, 1, 2, BASE, BASE >> 1, 0x5555555555555555, 0xaaaaaaaaaaaaaaaa]
# some solid strings of one bits
p2 = 4 # 0 and 1 already added
for i in range(2*SHIFT):
special.append(p2 - 1)
p2 = p2 << 1
del p2
# add complements & negations
special += [~x for x in special] + [-x for x in special]
DBL_MAX = sys.float_info.max
DBL_MAX_EXP = sys.float_info.max_exp
DBL_MIN_EXP = sys.float_info.min_exp
DBL_MANT_DIG = sys.float_info.mant_dig
DBL_MIN_OVERFLOW = 2**DBL_MAX_EXP - 2**(DBL_MAX_EXP - DBL_MANT_DIG - 1)
# Pure Python version of correctly-rounded integer-to-float conversion.
def int_to_float(n):
"""
Correctly-rounded integer-to-float conversion.
"""
# Constants, depending only on the floating-point format in use.
# We use an extra 2 bits of precision for rounding purposes.
PRECISION = sys.float_info.mant_dig + 2
SHIFT_MAX = sys.float_info.max_exp - PRECISION
Q_MAX = 1 << PRECISION
ROUND_HALF_TO_EVEN_CORRECTION = [0, -1, -2, 1, 0, -1, 2, 1]
# Reduce to the case where n is positive.
if n == 0:
return 0.0
elif n < 0:
return -int_to_float(-n)
# Convert n to a 'floating-point' number q * 2**shift, where q is an
# integer with 'PRECISION' significant bits. When shifting n to create q,
# the least significant bit of q is treated as 'sticky'. That is, the
# least significant bit of q is set if either the corresponding bit of n
# was already set, or any one of the bits of n lost in the shift was set.
shift = n.bit_length() - PRECISION
q = n << -shift if shift < 0 else (n >> shift) | bool(n & ~(-1 << shift))
# Round half to even (actually rounds to the nearest multiple of 4,
# rounding ties to a multiple of 8).
q += ROUND_HALF_TO_EVEN_CORRECTION[q & 7]
# Detect overflow.
if shift + (q == Q_MAX) > SHIFT_MAX:
raise OverflowError("integer too large to convert to float")
# Checks: q is exactly representable, and q**2**shift doesn't overflow.
assert q % 4 == 0 and q // 4 <= 2**(sys.float_info.mant_dig)
assert q * 2**shift <= sys.float_info.max
# Some circularity here, since float(q) is doing an int-to-float
# conversion. But here q is of bounded size, and is exactly representable
# as a float. In a low-level C-like language, this operation would be a
# simple cast (e.g., from unsigned long long to double).
return math.ldexp(float(q), shift)
# pure Python version of correctly-rounded true division
def truediv(a, b):
"""Correctly-rounded true division for integers."""
negative = a^b < 0
a, b = abs(a), abs(b)
# exceptions: division by zero, overflow
if not b:
raise ZeroDivisionError("division by zero")
if a >= DBL_MIN_OVERFLOW * b:
raise OverflowError("int/int too large to represent as a float")
# find integer d satisfying 2**(d - 1) <= a/b < 2**d
d = a.bit_length() - b.bit_length()
if d >= 0 and a >= 2**d * b or d < 0 and a * 2**-d >= b:
d += 1
# compute 2**-exp * a / b for suitable exp
exp = max(d, DBL_MIN_EXP) - DBL_MANT_DIG
a, b = a << max(-exp, 0), b << max(exp, 0)
q, r = divmod(a, b)
# round-half-to-even: fractional part is r/b, which is > 0.5 iff
# 2*r > b, and == 0.5 iff 2*r == b.
if 2*r > b or 2*r == b and q % 2 == 1:
q += 1
result = math.ldexp(q, exp)
return -result if negative else result
class LongTest(unittest.TestCase):
# Get quasi-random long consisting of ndigits digits (in base BASE).
# quasi == the most-significant digit will not be 0, and the number
# is constructed to contain long strings of 0 and 1 bits. These are
# more likely than random bits to provoke digit-boundary errors.
# The sign of the number is also random.
def getran(self, ndigits):
self.assertGreater(ndigits, 0)
nbits_hi = ndigits * SHIFT
nbits_lo = nbits_hi - SHIFT + 1
answer = 0
nbits = 0
r = int(random.random() * (SHIFT * 2)) | 1 # force 1 bits to start
while nbits < nbits_lo:
bits = (r >> 1) + 1
bits = min(bits, nbits_hi - nbits)
self.assertTrue(1 <= bits <= SHIFT)
nbits = nbits + bits
answer = answer << bits
if r & 1:
answer = answer | ((1 << bits) - 1)
r = int(random.random() * (SHIFT * 2))
self.assertTrue(nbits_lo <= nbits <= nbits_hi)
if random.random() < 0.5:
answer = -answer
return answer
# Get random long consisting of ndigits random digits (relative to base
# BASE). The sign bit is also random.
def getran2(ndigits):
answer = 0
for i in range(ndigits):
answer = (answer << SHIFT) | random.randint(0, MASK)
if random.random() < 0.5:
answer = -answer
return answer
def check_division(self, x, y):
eq = self.assertEqual
with self.subTest(x=x, y=y):
q, r = divmod(x, y)
q2, r2 = x//y, x%y
pab, pba = x*y, y*x
eq(pab, pba, "multiplication does not commute")
eq(q, q2, "divmod returns different quotient than /")
eq(r, r2, "divmod returns different mod than %")
eq(x, q*y + r, "x != q*y + r after divmod")
if y > 0:
self.assertTrue(0 <= r < y, "bad mod from divmod")
else:
self.assertTrue(y < r <= 0, "bad mod from divmod")
def test_division(self):
digits = list(range(1, MAXDIGITS+1)) + list(range(KARATSUBA_CUTOFF,
KARATSUBA_CUTOFF + 14))
digits.append(KARATSUBA_CUTOFF * 3)
for lenx in digits:
x = self.getran(lenx)
for leny in digits:
y = self.getran(leny) or 1
self.check_division(x, y)
# specific numbers chosen to exercise corner cases of the
# current long division implementation
# 30-bit cases involving a quotient digit estimate of BASE+1
self.check_division(1231948412290879395966702881,
1147341367131428698)
self.check_division(815427756481275430342312021515587883,
707270836069027745)
self.check_division(627976073697012820849443363563599041,
643588798496057020)
self.check_division(1115141373653752303710932756325578065,
1038556335171453937726882627)
# 30-bit cases that require the post-subtraction correction step
self.check_division(922498905405436751940989320930368494,
949985870686786135626943396)
self.check_division(768235853328091167204009652174031844,
1091555541180371554426545266)
# 15-bit cases involving a quotient digit estimate of BASE+1
self.check_division(20172188947443, 615611397)
self.check_division(1020908530270155025, 950795710)
self.check_division(128589565723112408, 736393718)
self.check_division(609919780285761575, 18613274546784)
# 15-bit cases that require the post-subtraction correction step
self.check_division(710031681576388032, 26769404391308)
self.check_division(1933622614268221, 30212853348836)
def test_karatsuba(self):
digits = list(range(1, 5)) + list(range(KARATSUBA_CUTOFF,
KARATSUBA_CUTOFF + 10))
digits.extend([KARATSUBA_CUTOFF * 10, KARATSUBA_CUTOFF * 100])
bits = [digit * SHIFT for digit in digits]
# Test products of long strings of 1 bits -- (2**x-1)*(2**y-1) ==
# 2**(x+y) - 2**x - 2**y + 1, so the proper result is easy to check.
for abits in bits:
a = (1 << abits) - 1
for bbits in bits:
if bbits < abits:
continue
with self.subTest(abits=abits, bbits=bbits):
b = (1 << bbits) - 1
x = a * b
y = ((1 << (abits + bbits)) -
(1 << abits) -
(1 << bbits) +
1)
self.assertEqual(x, y)
def check_bitop_identities_1(self, x):
eq = self.assertEqual
with self.subTest(x=x):
eq(x & 0, 0)
eq(x | 0, x)
eq(x ^ 0, x)
eq(x & -1, x)
eq(x | -1, -1)
eq(x ^ -1, ~x)
eq(x, ~~x)
eq(x & x, x)
eq(x | x, x)
eq(x ^ x, 0)
eq(x & ~x, 0)
eq(x | ~x, -1)
eq(x ^ ~x, -1)
eq(-x, 1 + ~x)
eq(-x, ~(x-1))
for n in range(2*SHIFT):
p2 = 2 ** n
with self.subTest(x=x, n=n, p2=p2):
eq(x << n >> n, x)
eq(x // p2, x >> n)
eq(x * p2, x << n)
eq(x & -p2, x >> n << n)
eq(x & -p2, x & ~(p2 - 1))
def check_bitop_identities_2(self, x, y):
eq = self.assertEqual
with self.subTest(x=x, y=y):
eq(x & y, y & x)
eq(x | y, y | x)
eq(x ^ y, y ^ x)
eq(x ^ y ^ x, y)
eq(x & y, ~(~x | ~y))
eq(x | y, ~(~x & ~y))
eq(x ^ y, (x | y) & ~(x & y))
eq(x ^ y, (x & ~y) | (~x & y))
eq(x ^ y, (x | y) & (~x | ~y))
def check_bitop_identities_3(self, x, y, z):
eq = self.assertEqual
with self.subTest(x=x, y=y, z=z):
eq((x & y) & z, x & (y & z))
eq((x | y) | z, x | (y | z))
eq((x ^ y) ^ z, x ^ (y ^ z))
eq(x & (y | z), (x & y) | (x & z))
eq(x | (y & z), (x | y) & (x | z))
def test_bitop_identities(self):
for x in special:
self.check_bitop_identities_1(x)
digits = range(1, MAXDIGITS+1)
for lenx in digits:
x = self.getran(lenx)
self.check_bitop_identities_1(x)
for leny in digits:
y = self.getran(leny)
self.check_bitop_identities_2(x, y)
self.check_bitop_identities_3(x, y, self.getran((lenx + leny)//2))
def slow_format(self, x, base):
digits = []
sign = 0
if x < 0:
sign, x = 1, -x
while x:
x, r = divmod(x, base)
digits.append(int(r))
digits.reverse()
digits = digits or [0]
return '-'[:sign] + \
{2: '0b', 8: '0o', 10: '', 16: '0x'}[base] + \
"".join("0123456789abcdef"[i] for i in digits)
def check_format_1(self, x):
for base, mapper in (2, bin), (8, oct), (10, str), (10, repr), (16, hex):
got = mapper(x)
with self.subTest(x=x, mapper=mapper.__name__):
expected = self.slow_format(x, base)
self.assertEqual(got, expected)
with self.subTest(got=got):
self.assertEqual(int(got, 0), x)
def test_format(self):
for x in special:
self.check_format_1(x)
for i in range(10):
for lenx in range(1, MAXDIGITS+1):
x = self.getran(lenx)
self.check_format_1(x)
def test_long(self):
# Check conversions from string
LL = [
('1' + '0'*20, 10**20),
('1' + '0'*100, 10**100)
]
for s, v in LL:
for sign in "", "+", "-":
for prefix in "", " ", "\t", " \t\t ":
ss = prefix + sign + s
vv = v
if sign == "-" and v is not ValueError:
vv = -v
try:
self.assertEqual(int(ss), vv)
except ValueError:
pass
# trailing L should no longer be accepted...
self.assertRaises(ValueError, int, '123L')
self.assertRaises(ValueError, int, '123l')
self.assertRaises(ValueError, int, '0L')
Loading ...