PyXR

c:\python24\lib \ test \ test_long.py



0001 from test.test_support import verify, verbose, TestFailed, fcmp
0002 from string import join
0003 from random import random, randint
0004 
0005 # SHIFT should match the value in longintrepr.h for best testing.
0006 SHIFT = 15
0007 BASE = 2 ** SHIFT
0008 MASK = BASE - 1
0009 KARATSUBA_CUTOFF = 70   # from longobject.c
0010 
0011 # Max number of base BASE digits to use in test cases.  Doubling
0012 # this will more than double the runtime.
0013 MAXDIGITS = 15
0014 
0015 # build some special values
0016 special = map(long, [0, 1, 2, BASE, BASE >> 1])
0017 special.append(0x5555555555555555L)
0018 special.append(0xaaaaaaaaaaaaaaaaL)
0019 #  some solid strings of one bits
0020 p2 = 4L  # 0 and 1 already added
0021 for i in range(2*SHIFT):
0022     special.append(p2 - 1)
0023     p2 = p2 << 1
0024 del p2
0025 # add complements & negations
0026 special = special + map(lambda x: ~x, special) + \
0027                     map(lambda x: -x, special)
0028 
0029 # ------------------------------------------------------------ utilities
0030 
0031 # Use check instead of assert so the test still does something
0032 # under -O.
0033 
0034 def check(ok, *args):
0035     if not ok:
0036         raise TestFailed, join(map(str, args), " ")
0037 
0038 # Get quasi-random long consisting of ndigits digits (in base BASE).
0039 # quasi == the most-significant digit will not be 0, and the number
0040 # is constructed to contain long strings of 0 and 1 bits.  These are
0041 # more likely than random bits to provoke digit-boundary errors.
0042 # The sign of the number is also random.
0043 
0044 def getran(ndigits):
0045     verify(ndigits > 0)
0046     nbits_hi = ndigits * SHIFT
0047     nbits_lo = nbits_hi - SHIFT + 1
0048     answer = 0L
0049     nbits = 0
0050     r = int(random() * (SHIFT * 2)) | 1  # force 1 bits to start
0051     while nbits < nbits_lo:
0052         bits = (r >> 1) + 1
0053         bits = min(bits, nbits_hi - nbits)
0054         verify(1 <= bits <= SHIFT)
0055         nbits = nbits + bits
0056         answer = answer << bits
0057         if r & 1:
0058             answer = answer | ((1 << bits) - 1)
0059         r = int(random() * (SHIFT * 2))
0060     verify(nbits_lo <= nbits <= nbits_hi)
0061     if random() < 0.5:
0062         answer = -answer
0063     return answer
0064 
0065 # Get random long consisting of ndigits random digits (relative to base
0066 # BASE).  The sign bit is also random.
0067 
0068 def getran2(ndigits):
0069     answer = 0L
0070     for i in range(ndigits):
0071         answer = (answer << SHIFT) | randint(0, MASK)
0072     if random() < 0.5:
0073         answer = -answer
0074     return answer
0075 
0076 # --------------------------------------------------------------- divmod
0077 
0078 def test_division_2(x, y):
0079     q, r = divmod(x, y)
0080     q2, r2 = x//y, x%y
0081     pab, pba = x*y, y*x
0082     check(pab == pba, "multiplication does not commute for", x, y)
0083     check(q == q2, "divmod returns different quotient than / for", x, y)
0084     check(r == r2, "divmod returns different mod than % for", x, y)
0085     check(x == q*y + r, "x != q*y + r after divmod on", x, y)
0086     if y > 0:
0087         check(0 <= r < y, "bad mod from divmod on", x, y)
0088     else:
0089         check(y < r <= 0, "bad mod from divmod on", x, y)
0090 
0091 def test_division(maxdigits=MAXDIGITS):
0092     if verbose:
0093         print "long / * % divmod"
0094     digits = range(1, maxdigits+1) + range(KARATSUBA_CUTOFF,
0095                                            KARATSUBA_CUTOFF + 14)
0096     digits.append(KARATSUBA_CUTOFF * 3)
0097     for lenx in digits:
0098         x = getran(lenx)
0099         for leny in digits:
0100             y = getran(leny) or 1L
0101             test_division_2(x, y)
0102 # ------------------------------------------------------------ karatsuba
0103 
0104 def test_karatsuba():
0105 
0106     if verbose:
0107         print "Karatsuba"
0108 
0109     digits = range(1, 5) + range(KARATSUBA_CUTOFF, KARATSUBA_CUTOFF + 10)
0110     digits.extend([KARATSUBA_CUTOFF * 10, KARATSUBA_CUTOFF * 100])
0111 
0112     bits = [digit * SHIFT for digit in digits]
0113 
0114     # Test products of long strings of 1 bits -- (2**x-1)*(2**y-1) ==
0115     # 2**(x+y) - 2**x - 2**y + 1, so the proper result is easy to check.
0116     for abits in bits:
0117         a = (1L << abits) - 1
0118         for bbits in bits:
0119             if bbits < abits:
0120                 continue
0121             b = (1L << bbits) - 1
0122             x = a * b
0123             y = ((1L << (abits + bbits)) -
0124                  (1L << abits) -
0125                  (1L << bbits) +
0126                  1)
0127             check(x == y, "bad result for", a, "*", b, x, y)
0128 # -------------------------------------------------------------- ~ & | ^
0129 
0130 def test_bitop_identities_1(x):
0131     check(x & 0 == 0, "x & 0 != 0 for", x)
0132     check(x | 0 == x, "x | 0 != x for", x)
0133     check(x ^ 0 == x, "x ^ 0 != x for", x)
0134     check(x & -1 == x, "x & -1 != x for", x)
0135     check(x | -1 == -1, "x | -1 != -1 for", x)
0136     check(x ^ -1 == ~x, "x ^ -1 != ~x for", x)
0137     check(x == ~~x, "x != ~~x for", x)
0138     check(x & x == x, "x & x != x for", x)
0139     check(x | x == x, "x | x != x for", x)
0140     check(x ^ x == 0, "x ^ x != 0 for", x)
0141     check(x & ~x == 0, "x & ~x != 0 for", x)
0142     check(x | ~x == -1, "x | ~x != -1 for", x)
0143     check(x ^ ~x == -1, "x ^ ~x != -1 for", x)
0144     check(-x == 1 + ~x == ~(x-1), "not -x == 1 + ~x == ~(x-1) for", x)
0145     for n in range(2*SHIFT):
0146         p2 = 2L ** n
0147         check(x << n >> n == x, "x << n >> n != x for", x, n)
0148         check(x // p2 == x >> n, "x // p2 != x >> n for x n p2", x, n, p2)
0149         check(x * p2 == x << n, "x * p2 != x << n for x n p2", x, n, p2)
0150         check(x & -p2 == x >> n << n == x & ~(p2 - 1),
0151             "not x & -p2 == x >> n << n == x & ~(p2 - 1) for x n p2",
0152             x, n, p2)
0153 
0154 def test_bitop_identities_2(x, y):
0155     check(x & y == y & x, "x & y != y & x for", x, y)
0156     check(x | y == y | x, "x | y != y | x for", x, y)
0157     check(x ^ y == y ^ x, "x ^ y != y ^ x for", x, y)
0158     check(x ^ y ^ x == y, "x ^ y ^ x != y for", x, y)
0159     check(x & y == ~(~x | ~y), "x & y != ~(~x | ~y) for", x, y)
0160     check(x | y == ~(~x & ~y), "x | y != ~(~x & ~y) for", x, y)
0161     check(x ^ y == (x | y) & ~(x & y),
0162          "x ^ y != (x | y) & ~(x & y) for", x, y)
0163     check(x ^ y == (x & ~y) | (~x & y),
0164          "x ^ y == (x & ~y) | (~x & y) for", x, y)
0165     check(x ^ y == (x | y) & (~x | ~y),
0166          "x ^ y == (x | y) & (~x | ~y) for", x, y)
0167 
0168 def test_bitop_identities_3(x, y, z):
0169     check((x & y) & z == x & (y & z),
0170          "(x & y) & z != x & (y & z) for", x, y, z)
0171     check((x | y) | z == x | (y | z),
0172          "(x | y) | z != x | (y | z) for", x, y, z)
0173     check((x ^ y) ^ z == x ^ (y ^ z),
0174          "(x ^ y) ^ z != x ^ (y ^ z) for", x, y, z)
0175     check(x & (y | z) == (x & y) | (x & z),
0176          "x & (y | z) != (x & y) | (x & z) for", x, y, z)
0177     check(x | (y & z) == (x | y) & (x | z),
0178          "x | (y & z) != (x | y) & (x | z) for", x, y, z)
0179 
0180 def test_bitop_identities(maxdigits=MAXDIGITS):
0181     if verbose:
0182         print "long bit-operation identities"
0183     for x in special:
0184         test_bitop_identities_1(x)
0185     digits = range(1, maxdigits+1)
0186     for lenx in digits:
0187         x = getran(lenx)
0188         test_bitop_identities_1(x)
0189         for leny in digits:
0190             y = getran(leny)
0191             test_bitop_identities_2(x, y)
0192             test_bitop_identities_3(x, y, getran((lenx + leny)//2))
0193 
0194 # ------------------------------------------------- hex oct repr str atol
0195 
0196 def slow_format(x, base):
0197     if (x, base) == (0, 8):
0198         # this is an oddball!
0199         return "0L"
0200     digits = []
0201     sign = 0
0202     if x < 0:
0203         sign, x = 1, -x
0204     while x:
0205         x, r = divmod(x, base)
0206         digits.append(int(r))
0207     digits.reverse()
0208     digits = digits or [0]
0209     return '-'[:sign] + \
0210            {8: '0', 10: '', 16: '0x'}[base] + \
0211            join(map(lambda i: "0123456789ABCDEF"[i], digits), '') + \
0212            "L"
0213 
0214 def test_format_1(x):
0215     from string import atol
0216     for base, mapper in (8, oct), (10, repr), (16, hex):
0217         got = mapper(x)
0218         expected = slow_format(x, base)
0219         check(got == expected, mapper.__name__, "returned",
0220               got, "but expected", expected, "for", x)
0221         check(atol(got, 0) == x, 'atol("%s", 0) !=' % got, x)
0222     # str() has to be checked a little differently since there's no
0223     # trailing "L"
0224     got = str(x)
0225     expected = slow_format(x, 10)[:-1]
0226     check(got == expected, mapper.__name__, "returned",
0227           got, "but expected", expected, "for", x)
0228 
0229 def test_format(maxdigits=MAXDIGITS):
0230     if verbose:
0231         print "long str/hex/oct/atol"
0232     for x in special:
0233         test_format_1(x)
0234     for i in range(10):
0235         for lenx in range(1, maxdigits+1):
0236             x = getran(lenx)
0237             test_format_1(x)
0238 
0239 # ----------------------------------------------------------------- misc
0240 
0241 def test_misc(maxdigits=MAXDIGITS):
0242     if verbose:
0243         print "long miscellaneous operations"
0244     import sys
0245 
0246     # check the extremes in int<->long conversion
0247     hugepos = sys.maxint
0248     hugeneg = -hugepos - 1
0249     hugepos_aslong = long(hugepos)
0250     hugeneg_aslong = long(hugeneg)
0251     check(hugepos == hugepos_aslong, "long(sys.maxint) != sys.maxint")
0252     check(hugeneg == hugeneg_aslong,
0253         "long(-sys.maxint-1) != -sys.maxint-1")
0254 
0255     # long -> int should not fail for hugepos_aslong or hugeneg_aslong
0256     try:
0257         check(int(hugepos_aslong) == hugepos,
0258               "converting sys.maxint to long and back to int fails")
0259     except OverflowError:
0260         raise TestFailed, "int(long(sys.maxint)) overflowed!"
0261     try:
0262         check(int(hugeneg_aslong) == hugeneg,
0263               "converting -sys.maxint-1 to long and back to int fails")
0264     except OverflowError:
0265         raise TestFailed, "int(long(-sys.maxint-1)) overflowed!"
0266 
0267     # but long -> int should overflow for hugepos+1 and hugeneg-1
0268     x = hugepos_aslong + 1
0269     try:
0270         y = int(x)
0271     except OverflowError:
0272         raise TestFailed, "int(long(sys.maxint) + 1) mustn't overflow"
0273     if not isinstance(y, long):
0274         raise TestFailed("int(long(sys.maxint) + 1) should have returned long")
0275 
0276     x = hugeneg_aslong - 1
0277     try:
0278         y = int(x)
0279     except OverflowError:
0280         raise TestFailed, "int(long(-sys.maxint-1) - 1) mustn't overflow"
0281     if not isinstance(y, long):
0282         raise TestFailed("int(long(-sys.maxint-1) - 1) should have returned long")
0283 
0284     class long2(long):
0285         pass
0286     x = long2(1L<<100)
0287     y = int(x)
0288     if type(y) is not long:
0289         raise TestFailed("overflowing int conversion must return long not long subtype")
0290 # ----------------------------------- tests of auto int->long conversion
0291 
0292 def test_auto_overflow():
0293     import math, sys
0294 
0295     if verbose:
0296         print "auto-convert int->long on overflow"
0297 
0298     special = [0, 1, 2, 3, sys.maxint-1, sys.maxint, sys.maxint+1]
0299     sqrt = int(math.sqrt(sys.maxint))
0300     special.extend([sqrt-1, sqrt, sqrt+1])
0301     special.extend([-i for i in special])
0302 
0303     def checkit(*args):
0304         # Heavy use of nested scopes here!
0305         verify(got == expected, "for %r expected %r got %r" %
0306                                 (args, expected, got))
0307 
0308     for x in special:
0309         longx = long(x)
0310 
0311         expected = -longx
0312         got = -x
0313         checkit('-', x)
0314 
0315         for y in special:
0316             longy = long(y)
0317 
0318             expected = longx + longy
0319             got = x + y
0320             checkit(x, '+', y)
0321 
0322             expected = longx - longy
0323             got = x - y
0324             checkit(x, '-', y)
0325 
0326             expected = longx * longy
0327             got = x * y
0328             checkit(x, '*', y)
0329 
0330             if y:
0331                 expected = longx / longy
0332                 got = x / y
0333                 checkit(x, '/', y)
0334 
0335                 expected = longx // longy
0336                 got = x // y
0337                 checkit(x, '//', y)
0338 
0339                 expected = divmod(longx, longy)
0340                 got = divmod(longx, longy)
0341                 checkit(x, 'divmod', y)
0342 
0343             if abs(y) < 5 and not (x == 0 and y < 0):
0344                 expected = longx ** longy
0345                 got = x ** y
0346                 checkit(x, '**', y)
0347 
0348                 for z in special:
0349                     if z != 0 :
0350                         if y >= 0:
0351                             expected = pow(longx, longy, long(z))
0352                             got = pow(x, y, z)
0353                             checkit('pow', x, y, '%', z)
0354                         else:
0355                             try:
0356                                 pow(longx, longy, long(z))
0357                             except TypeError:
0358                                 pass
0359                             else:
0360                                 raise TestFailed("pow%r should have raised "
0361                                 "TypeError" % ((longx, longy, long(z)),))
0362 
0363 # ---------------------------------------- tests of long->float overflow
0364 
0365 def test_float_overflow():
0366     import math
0367 
0368     if verbose:
0369         print "long->float overflow"
0370 
0371     for x in -2.0, -1.0, 0.0, 1.0, 2.0:
0372         verify(float(long(x)) == x)
0373 
0374     shuge = '12345' * 120
0375     huge = 1L << 30000
0376     mhuge = -huge
0377     namespace = {'huge': huge, 'mhuge': mhuge, 'shuge': shuge, 'math': math}
0378     for test in ["float(huge)", "float(mhuge)",
0379                  "complex(huge)", "complex(mhuge)",
0380                  "complex(huge, 1)", "complex(mhuge, 1)",
0381                  "complex(1, huge)", "complex(1, mhuge)",
0382                  "1. + huge", "huge + 1.", "1. + mhuge", "mhuge + 1.",
0383                  "1. - huge", "huge - 1.", "1. - mhuge", "mhuge - 1.",
0384                  "1. * huge", "huge * 1.", "1. * mhuge", "mhuge * 1.",
0385                  "1. // huge", "huge // 1.", "1. // mhuge", "mhuge // 1.",
0386                  "1. / huge", "huge / 1.", "1. / mhuge", "mhuge / 1.",
0387                  "1. ** huge", "huge ** 1.", "1. ** mhuge", "mhuge ** 1.",
0388                  "math.sin(huge)", "math.sin(mhuge)",
0389                  "math.sqrt(huge)", "math.sqrt(mhuge)", # should do better
0390                  "math.floor(huge)", "math.floor(mhuge)"]:
0391 
0392         try:
0393             eval(test, namespace)
0394         except OverflowError:
0395             pass
0396         else:
0397             raise TestFailed("expected OverflowError from %s" % test)
0398 
0399         # XXX Perhaps float(shuge) can raise OverflowError on some box?
0400         # The comparison should not.
0401         if float(shuge) == int(shuge):
0402             raise TestFailed("float(shuge) should not equal int(shuge)")
0403 
0404 # ---------------------------------------------- test huge log and log10
0405 
0406 def test_logs():
0407     import math
0408 
0409     if verbose:
0410         print "log and log10"
0411 
0412     LOG10E = math.log10(math.e)
0413 
0414     for exp in range(10) + [100, 1000, 10000]:
0415         value = 10 ** exp
0416         log10 = math.log10(value)
0417         verify(fcmp(log10, exp) == 0)
0418 
0419         # log10(value) == exp, so log(value) == log10(value)/log10(e) ==
0420         # exp/LOG10E
0421         expected = exp / LOG10E
0422         log = math.log(value)
0423         verify(fcmp(log, expected) == 0)
0424 
0425     for bad in -(1L << 10000), -2L, 0L:
0426         try:
0427             math.log(bad)
0428             raise TestFailed("expected ValueError from log(<= 0)")
0429         except ValueError:
0430             pass
0431 
0432         try:
0433             math.log10(bad)
0434             raise TestFailed("expected ValueError from log10(<= 0)")
0435         except ValueError:
0436             pass
0437 
0438 # ----------------------------------------------- test mixed comparisons
0439 
0440 def test_mixed_compares():
0441     import math
0442     import sys
0443 
0444     if verbose:
0445         print "mixed comparisons"
0446 
0447     # We're mostly concerned with that mixing floats and longs does the
0448     # right stuff, even when longs are too large to fit in a float.
0449     # The safest way to check the results is to use an entirely different
0450     # method, which we do here via a skeletal rational class (which
0451     # represents all Python ints, longs and floats exactly).
0452     class Rat:
0453         def __init__(self, value):
0454             if isinstance(value, (int, long)):
0455                 self.n = value
0456                 self.d = 1
0457 
0458             elif isinstance(value, float):
0459                 # Convert to exact rational equivalent.
0460                 f, e = math.frexp(abs(value))
0461                 assert f == 0 or 0.5 <= f < 1.0
0462                 # |value| = f * 2**e exactly
0463 
0464                 # Suck up CHUNK bits at a time; 28 is enough so that we suck
0465                 # up all bits in 2 iterations for all known binary double-
0466                 # precision formats, and small enough to fit in an int.
0467                 CHUNK = 28
0468                 top = 0
0469                 # invariant: |value| = (top + f) * 2**e exactly
0470                 while f:
0471                     f = math.ldexp(f, CHUNK)
0472                     digit = int(f)
0473                     assert digit >> CHUNK == 0
0474                     top = (top << CHUNK) | digit
0475                     f -= digit
0476                     assert 0.0 <= f < 1.0
0477                     e -= CHUNK
0478 
0479                 # Now |value| = top * 2**e exactly.
0480                 if e >= 0:
0481                     n = top << e
0482                     d = 1
0483                 else:
0484                     n = top
0485                     d = 1 << -e
0486                 if value < 0:
0487                     n = -n
0488                 self.n = n
0489                 self.d = d
0490                 assert float(n) / float(d) == value
0491 
0492             else:
0493                 raise TypeError("can't deal with %r" % val)
0494 
0495         def __cmp__(self, other):
0496             if not isinstance(other, Rat):
0497                 other = Rat(other)
0498             return cmp(self.n * other.d, self.d * other.n)
0499 
0500     cases = [0, 0.001, 0.99, 1.0, 1.5, 1e20, 1e200]
0501     # 2**48 is an important boundary in the internals.  2**53 is an
0502     # important boundary for IEEE double precision.
0503     for t in 2.0**48, 2.0**50, 2.0**53:
0504         cases.extend([t - 1.0, t - 0.3, t, t + 0.3, t + 1.0,
0505                       long(t-1), long(t), long(t+1)])
0506     cases.extend([0, 1, 2, sys.maxint, float(sys.maxint)])
0507     # 1L<<20000 should exceed all double formats.  long(1e200) is to
0508     # check that we get equality with 1e200 above.
0509     t = long(1e200)
0510     cases.extend([0L, 1L, 2L, 1L << 20000, t-1, t, t+1])
0511     cases.extend([-x for x in cases])
0512     for x in cases:
0513         Rx = Rat(x)
0514         for y in cases:
0515             Ry = Rat(y)
0516             Rcmp = cmp(Rx, Ry)
0517             xycmp = cmp(x, y)
0518             if Rcmp != xycmp:
0519                 raise TestFailed('%r %r %d %d' % (x, y, Rcmp, xycmp))
0520             if (x == y) != (Rcmp == 0):
0521                 raise TestFailed('%r == %r %d' % (x, y, Rcmp))
0522             if (x != y) != (Rcmp != 0):
0523                 raise TestFailed('%r != %r %d' % (x, y, Rcmp))
0524             if (x < y) != (Rcmp < 0):
0525                 raise TestFailed('%r < %r %d' % (x, y, Rcmp))
0526             if (x <= y) != (Rcmp <= 0):
0527                 raise TestFailed('%r <= %r %d' % (x, y, Rcmp))
0528             if (x > y) != (Rcmp > 0):
0529                 raise TestFailed('%r > %r %d' % (x, y, Rcmp))
0530             if (x >= y) != (Rcmp >= 0):
0531                 raise TestFailed('%r >= %r %d' % (x, y, Rcmp))
0532 
0533 # ---------------------------------------------------------------- do it
0534 
0535 test_division()
0536 test_karatsuba()
0537 test_bitop_identities()
0538 test_format()
0539 test_misc()
0540 test_auto_overflow()
0541 test_float_overflow()
0542 test_logs()
0543 test_mixed_compares()
0544 

Generated by PyXR 0.9.4
SourceForge.net Logo