home *** CD-ROM | disk | FTP | other *** search
/ PC World 2005 June / PCWorld_2005-06_cd.bin / software / vyzkuste / firewally / firewally.exe / framework-2.3.exe / test_long.py < prev    next >
Text File  |  2003-12-30  |  15KB  |  444 lines
  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()
  444.