Lib/test/test_long.py

   1 from test.test_support import verify, verbose, TestFailed, fcmp
   2 from string import join
   3 from random import random, randint
   4
   5 # SHIFT should match the value in longintrepr.h for best testing.
   6 SHIFT = 15
   7 BASE = 2 ** SHIFT
   8 MASK = BASE - 1
   9 KARATSUBA_CUTOFF = 35   # from longobject.c
  10
  11 # Max number of base BASE digits to use in test cases.  Doubling
  12 # this will more than double the runtime.
  13 MAXDIGITS = 15
  14
  15 # build some special values
  16 special = map(long, [0, 1, 2, BASE, BASE >> 1])
  17 special.append(0x5555555555555555L)
  18 special.append(0xaaaaaaaaaaaaaaaaL)
  19 #  some solid strings of one bits
  20 p2 = 4L  # 0 and 1 already added
  21 for i in range(2*SHIFT):
  22     special.append(p2 - 1)
  23     p2 = p2 << 1
  24 del p2
  25 # add complements & negations
  26 special = special + map(lambda x: ~x, special) + \
  27                     map(lambda x: -x, special)
  28
  29 # ------------------------------------------------------------ utilities
  30
  31 # Use check instead of assert so the test still does something
  32 # under -O.
  33
  34 def check(ok, *args):
  35     if not ok:
  36         raise TestFailed, join(map(str, args), " ")
  37
  38 # Get quasi-random long consisting of ndigits digits (in base BASE).
  39 # quasi == the most-significant digit will not be 0, and the number
  40 # is constructed to contain long strings of 0 and 1 bits.  These are
  41 # more likely than random bits to provoke digit-boundary errors.
  42 # The sign of the number is also random.
  43
  44 def getran(ndigits):
  45     verify(ndigits > 0)
  46     nbits_hi = ndigits * SHIFT
  47     nbits_lo = nbits_hi - SHIFT + 1
  48     answer = 0L
  49     nbits = 0
  50     r = int(random() * (SHIFT * 2)) | 1  # force 1 bits to start
  51     while nbits < nbits_lo:
  52         bits = (r >> 1) + 1
  53         bits = min(bits, nbits_hi - nbits)
  54         verify(1 <= bits <= SHIFT)
  55         nbits = nbits + bits
  56         answer = answer << bits
  57         if r & 1:
  58             answer = answer | ((1 << bits) - 1)
  59         r = int(random() * (SHIFT * 2))
  60     verify(nbits_lo <= nbits <= nbits_hi)
  61     if random() < 0.5:
  62         answer = -answer
  63     return answer
  64
  65 # Get random long consisting of ndigits random digits (relative to base
  66 # BASE).  The sign bit is also random.
  67
  68 def getran2(ndigits):
  69     answer = 0L
  70     for i in range(ndigits):
  71         answer = (answer << SHIFT) | randint(0, MASK)
  72     if random() < 0.5:
  73         answer = -answer
  74     return answer
  75
  76 # --------------------------------------------------------------- divmod
  77
  78 def test_division_2(x, y):
  79     q, r = divmod(x, y)
  80     q2, r2 = x//y, x%y
  81     pab, pba = x*y, y*x
  82     check(pab == pba, "multiplication does not commute for", x, y)
  83     check(q == q2, "divmod returns different quotient than / for", x, y)
  84     check(r == r2, "divmod returns different mod than % for", x, y)
  85     check(x == q*y + r, "x != q*y + r after divmod on", x, y)
  86     if y > 0:
  87         check(0 <= r < y, "bad mod from divmod on", x, y)
  88     else:
  89         check(y < r <= 0, "bad mod from divmod on", x, y)
  90
  91 def test_division(maxdigits=MAXDIGITS):
  92     if verbose:
  93         print "long / * % divmod"
  94     digits = range(1, maxdigits+1) + range(KARATSUBA_CUTOFF,
  95                                            KARATSUBA_CUTOFF + 14)
  96     digits.append(KARATSUBA_CUTOFF * 3)
  97     for lenx in digits:
  98         x = getran(lenx)
  99         for leny in digits:
 100             y = getran(leny) or 1L
 101             test_division_2(x, y)
 102 # ------------------------------------------------------------ karatsuba
 103
 104 def test_karatsuba():
 105
 106     if verbose:
 107         print "Karatsuba"
 108
 109     digits = range(1, 5) + range(KARATSUBA_CUTOFF, KARATSUBA_CUTOFF + 10)
 110     digits.extend([KARATSUBA_CUTOFF * 10, KARATSUBA_CUTOFF * 100])
 111
 112     bits = [digit * SHIFT for digit in digits]
 113
 114     # Test products of long strings of 1 bits -- (2**x-1)*(2**y-1) ==
 115     # 2**(x+y) - 2**x - 2**y + 1, so the proper result is easy to check.
 116     for abits in bits:
 117         a = (1L << abits) - 1
 118         for bbits in bits:
 119             if bbits < abits:
 120                 continue
 121             b = (1L << bbits) - 1
 122             x = a * b
 123             y = ((1L << (abits + bbits)) -
 124                  (1L << abits) -
 125                  (1L << bbits) +
 126                  1)
 127             check(x == y, "bad result for", a, "*", b, x, y)
 128 # -------------------------------------------------------------- ~ & | ^
 129
 130 def test_bitop_identities_1(x):
 131     check(x & 0 == 0, "x & 0 != 0 for", x)
 132     check(x | 0 == x, "x | 0 != x for", x)
 133     check(x ^ 0 == x, "x ^ 0 != x for", x)
 134     check(x & -1 == x, "x & -1 != x for", x)
 135     check(x | -1 == -1, "x | -1 != -1 for", x)
 136     check(x ^ -1 == ~x, "x ^ -1 != ~x for", x)
 137     check(x == ~~x, "x != ~~x for", x)
 138     check(x & x == x, "x & x != x for", x)
 139     check(x | x == x, "x | x != x for", x)
 140     check(x ^ x == 0, "x ^ x != 0 for", x)
 141     check(x & ~x == 0, "x & ~x != 0 for", x)
 142     check(x | ~x == -1, "x | ~x != -1 for", x)
 143     check(x ^ ~x == -1, "x ^ ~x != -1 for", x)
 144     check(-x == 1 + ~x == ~(x-1), "not -x == 1 + ~x == ~(x-1) for", x)
 145     for n in range(2*SHIFT):
 146         p2 = 2L ** n
 147         check(x << n >> n == x, "x << n >> n != x for", x, n)
 148         check(x // p2 == x >> n, "x // p2 != x >> n for x n p2", x, n, p2)
 149         check(x * p2 == x << n, "x * p2 != x << n for x n p2", x, n, p2)
 150         check(x & -p2 == x >> n << n == x & ~(p2 - 1),
 151             "not x & -p2 == x >> n << n == x & ~(p2 - 1) for x n p2",
 152             x, n, p2)
 153
 154 def test_bitop_identities_2(x, y):
 155     check(x & y == y & x, "x & y != y & x for", x, y)
 156     check(x | y == y | x, "x | y != y | x for", x, y)
 157     check(x ^ y == y ^ x, "x ^ y != y ^ x for", x, y)
 158     check(x ^ y ^ x == y, "x ^ y ^ x != y for", x, y)
 159     check(x & y == ~(~x | ~y), "x & y != ~(~x | ~y) for", x, y)
 160     check(x | y == ~(~x & ~y), "x | y != ~(~x & ~y) for", x, y)
 161     check(x ^ y == (x | y) & ~(x & y),
 162          "x ^ y != (x | y) & ~(x & y) for", x, y)
 163     check(x ^ y == (x & ~y) | (~x & y),
 164          "x ^ y == (x & ~y) | (~x & y) for", x, y)
 165     check(x ^ y == (x | y) & (~x | ~y),
 166          "x ^ y == (x | y) & (~x | ~y) for", x, y)
 167
 168 def test_bitop_identities_3(x, y, z):
 169     check((x & y) & z == x & (y & z),
 170          "(x & y) & z != x & (y & z) for", x, y, z)
 171     check((x | y) | z == x | (y | z),
 172          "(x | y) | z != x | (y | z) for", x, y, z)
 173     check((x ^ y) ^ z == x ^ (y ^ z),
 174          "(x ^ y) ^ z != x ^ (y ^ z) for", x, y, z)
 175     check(x & (y | z) == (x & y) | (x & z),
 176          "x & (y | z) != (x & y) | (x & z) for", x, y, z)
 177     check(x | (y & z) == (x | y) & (x | z),
 178          "x | (y & z) != (x | y) & (x | z) for", x, y, z)
 179
 180 def test_bitop_identities(maxdigits=MAXDIGITS):
 181     if verbose:
 182         print "long bit-operation identities"
 183     for x in special:
 184         test_bitop_identities_1(x)
 185     digits = range(1, maxdigits+1)
 186     for lenx in digits:
 187         x = getran(lenx)
 188         test_bitop_identities_1(x)
 189         for leny in digits:
 190             y = getran(leny)
 191             test_bitop_identities_2(x, y)
 192             test_bitop_identities_3(x, y, getran((lenx + leny)//2))
 193
 194 # ------------------------------------------------- hex oct repr str atol
 195
 196 def slow_format(x, base):
 197     if (x, base) == (0, 8):
 198         # this is an oddball!
 199         return "0L"
 200     digits = []
 201     sign = 0
 202     if x < 0:
 203         sign, x = 1, -x
 204     while x:
 205         x, r = divmod(x, base)
 206         digits.append(int(r))
 207     digits.reverse()
 208     digits = digits or [0]
 209     return '-'[:sign] + \
 210            {8: '0', 10: '', 16: '0x'}[base] + \
 211            join(map(lambda i: "0123456789ABCDEF"[i], digits), '') + \
 212            "L"
 213
 214 def test_format_1(x):
 215     from string import atol
 216     for base, mapper in (8, oct), (10, repr), (16, hex):
 217         got = mapper(x)
 218         expected = slow_format(x, base)
 219         check(got == expected, mapper.__name__, "returned",
 220               got, "but expected", expected, "for", x)
 221         check(atol(got, 0) == x, 'atol("%s", 0) !=' % got, x)
 222     # str() has to be checked a little differently since there's no
 223     # trailing "L"
 224     got = str(x)
 225     expected = slow_format(x, 10)[:-1]
 226     check(got == expected, mapper.__name__, "returned",
 227           got, "but expected", expected, "for", x)
 228
 229 def test_format(maxdigits=MAXDIGITS):
 230     if verbose:
 231         print "long str/hex/oct/atol"
 232     for x in special:
 233         test_format_1(x)
 234     for i in range(10):
 235         for lenx in range(1, maxdigits+1):
 236             x = getran(lenx)
 237             test_format_1(x)
 238
 239 # ----------------------------------------------------------------- misc
 240
 241 def test_misc(maxdigits=MAXDIGITS):
 242     if verbose:
 243         print "long miscellaneous operations"
 244     import sys
 245
 246     # check the extremes in int<->long conversion
 247     hugepos = sys.maxint
 248     hugeneg = -hugepos - 1
 249     hugepos_aslong = long(hugepos)
 250     hugeneg_aslong = long(hugeneg)
 251     check(hugepos == hugepos_aslong, "long(sys.maxint) != sys.maxint")
 252     check(hugeneg == hugeneg_aslong,
 253         "long(-sys.maxint-1) != -sys.maxint-1")
 254
 255     # long -> int should not fail for hugepos_aslong or hugeneg_aslong
 256     try:
 257         check(int(hugepos_aslong) == hugepos,
 258               "converting sys.maxint to long and back to int fails")
 259     except OverflowError:
 260         raise TestFailed, "int(long(sys.maxint)) overflowed!"
 261     try:
 262         check(int(hugeneg_aslong) == hugeneg,
 263               "converting -sys.maxint-1 to long and back to int fails")
 264     except OverflowError:
 265         raise TestFailed, "int(long(-sys.maxint-1)) overflowed!"
 266
 267     # but long -> int should overflow for hugepos+1 and hugeneg-1
 268     x = hugepos_aslong + 1
 269     try:
 270         y = int(x)
 271     except OverflowError:
 272         raise TestFailed, "int(long(sys.maxint) + 1) mustn't overflow"
 273     if not isinstance(y, long):
 274         raise TestFailed("int(long(sys.maxint) + 1) should have returned long")
 275
 276     x = hugeneg_aslong - 1
 277     try:
 278         y = int(x)
 279     except OverflowError:
 280         raise TestFailed, "int(long(-sys.maxint-1) - 1) mustn't overflow"
 281     if not isinstance(y, long):
 282         raise TestFailed("int(long(-sys.maxint-1) - 1) should have returned long")
 283
 284     class long2(long):
 285         pass
 286     x = long2(1L<<100)
 287     y = int(x)
 288     if type(y) is not long:
 289         raise TestFailed("overflowing int conversion must return long not long subtype")
 290 # ----------------------------------- tests of auto int->long conversion
 291
 292 def test_auto_overflow():
 293     import math, sys
 294
 295     if verbose:
 296         print "auto-convert int->long on overflow"
 297
 298     special = [0, 1, 2, 3, sys.maxint-1, sys.maxint, sys.maxint+1]
 299     sqrt = int(math.sqrt(sys.maxint))
 300     special.extend([sqrt-1, sqrt, sqrt+1])
 301     special.extend([-i for i in special])
 302
 303     def checkit(*args):
 304         # Heavy use of nested scopes here!
 305         verify(got == expected, "for %r expected %r got %r" %
 306                                 (args, expected, got))
 307
 308     for x in special:
 309         longx = long(x)
 310
 311         expected = -longx
 312         got = -x
 313         checkit('-', x)
 314
 315         for y in special:
 316             longy = long(y)
 317
 318             expected = longx + longy
 319             got = x + y
 320             checkit(x, '+', y)
 321
 322             expected = longx - longy
 323             got = x - y
 324             checkit(x, '-', y)
 325
 326             expected = longx * longy
 327             got = x * y
 328             checkit(x, '*', y)
 329
 330             if y:
 331                 expected = longx / longy
 332                 got = x / y
 333                 checkit(x, '/', y)
 334
 335                 expected = longx // longy
 336                 got = x // y
 337                 checkit(x, '//', y)
 338
 339                 expected = divmod(longx, longy)
 340                 got = divmod(longx, longy)
 341                 checkit(x, 'divmod', y)
 342
 343             if abs(y) < 5 and not (x == 0 and y < 0):
 344                 expected = longx ** longy
 345                 got = x ** y
 346                 checkit(x, '**', y)
 347
 348                 for z in special:
 349                     if z != 0 :
 350                         if y >= 0:
 351                             expected = pow(longx, longy, long(z))
 352                             got = pow(x, y, z)
 353                             checkit('pow', x, y, '%', z)
 354                         else:
 355                             try:
 356                                 pow(longx, longy, long(z))
 357                             except TypeError:
 358                                 pass
 359                             else:
 360                                 raise TestFailed("pow%r should have raised "
 361                                 "TypeError" % ((longx, longy, long(z)),))
 362
 363 # ---------------------------------------- tests of long->float overflow
 364
 365 def test_float_overflow():
 366     import math
 367
 368     if verbose:
 369         print "long->float overflow"
 370
 371     for x in -2.0, -1.0, 0.0, 1.0, 2.0:
 372         verify(float(long(x)) == x)
 373
 374     shuge = '12345' * 120
 375     huge = 1L << 30000
 376     mhuge = -huge
 377     namespace = {'huge': huge, 'mhuge': mhuge, 'shuge': shuge, 'math': math}
 378     for test in ["float(huge)", "float(mhuge)",
 379                  "complex(huge)", "complex(mhuge)",
 380                  "complex(huge, 1)", "complex(mhuge, 1)",
 381                  "complex(1, huge)", "complex(1, mhuge)",
 382                  "1. + huge", "huge + 1.", "1. + mhuge", "mhuge + 1.",
 383                  "1. - huge", "huge - 1.", "1. - mhuge", "mhuge - 1.",
 384                  "1. * huge", "huge * 1.", "1. * mhuge", "mhuge * 1.",
 385                  "1. // huge", "huge // 1.", "1. // mhuge", "mhuge // 1.",
 386                  "1. / huge", "huge / 1.", "1. / mhuge", "mhuge / 1.",
 387                  "1. ** huge", "huge ** 1.", "1. ** mhuge", "mhuge ** 1.",
 388                  "math.sin(huge)", "math.sin(mhuge)",
 389                  "math.sqrt(huge)", "math.sqrt(mhuge)", # should do better
 390                  "math.floor(huge)", "math.floor(mhuge)",
 391                  "float(shuge) == int(shuge)"]:
 392
 393         try:
 394             eval(test, namespace)
 395         except OverflowError:
 396             pass
 397         else:
 398             raise TestFailed("expected OverflowError from %s" % test)
 399
 400 # ---------------------------------------------- test huge log and log10
 401
 402 def test_logs():
 403     import math
 404
 405     if verbose:
 406         print "log and log10"
 407
 408     LOG10E = math.log10(math.e)
 409
 410     for exp in range(10) + [100, 1000, 10000]:
 411         value = 10 ** exp
 412         log10 = math.log10(value)
 413         verify(fcmp(log10, exp) == 0)
 414
 415         # log10(value) == exp, so log(value) == log10(value)/log10(e) ==
 416         # exp/LOG10E
 417         expected = exp / LOG10E
 418         log = math.log(value)
 419         verify(fcmp(log, expected) == 0)
 420
 421     for bad in -(1L << 10000), -2L, 0L:
 422         try:
 423             math.log(bad)
 424             raise TestFailed("expected ValueError from log(<= 0)")
 425         except ValueError:
 426             pass
 427
 428         try:
 429             math.log10(bad)
 430             raise TestFailed("expected ValueError from log10(<= 0)")
 431         except ValueError:
 432             pass
 433
 434 # ---------------------------------------------------------------- do it
 435
 436 test_division()
 437 test_karatsuba()
 438 test_bitop_identities()
 439 test_format()
 440 test_misc()
 441 test_auto_overflow()
 442 test_float_overflow()
 443 test_logs()