Merged revisions 65258,65292,65299,65308-65309,65315,65326 via svnmerge from
svn+ssh://pythondev@svn.python.org/python/trunk
........
r65258 | mark.dickinson | 2008-07-27 08:15:29 +0100 (Sun, 27 Jul 2008) | 4 lines
Remove math.sum tests related to overflow, special values, and behaviour
near the extremes of the floating-point range. (The behaviour of math.sum
should be regarded as undefined in these cases.)
........
r65292 | mark.dickinson | 2008-07-29 19:45:38 +0100 (Tue, 29 Jul 2008) | 4 lines
More modifications to tests for math.sum: replace the Python
version of msum by a version using a different algorithm, and
use the new float.fromhex method to specify test results exactly.
........
r65299 | mark.dickinson | 2008-07-30 13:01:41 +0100 (Wed, 30 Jul 2008) | 5 lines
Fix special-value handling for math.sum.
Also minor cleanups to the code: fix tabbing, remove
trailing whitespace, and reformat to fit into 80
columns.
........
r65308 | mark.dickinson | 2008-07-30 17:20:10 +0100 (Wed, 30 Jul 2008) | 2 lines
Rename math.sum to math.fsum
........
r65309 | mark.dickinson | 2008-07-30 17:25:16 +0100 (Wed, 30 Jul 2008) | 3 lines
Replace math.sum with math.fsum in a couple of comments
that were missed by r65308
........
r65315 | mark.dickinson | 2008-07-30 21:23:15 +0100 (Wed, 30 Jul 2008) | 2 lines
Add note about problems with math.fsum on x86 hardware.
........
r65326 | mark.dickinson | 2008-07-31 15:48:32 +0100 (Thu, 31 Jul 2008) | 2 lines
Rename testSum to testFsum and move it to proper place in test_math.py
........
diff --git a/Lib/test/test_math.py b/Lib/test/test_math.py
index 1eafeba..9e646ac 100644
--- a/Lib/test/test_math.py
+++ b/Lib/test/test_math.py
@@ -359,6 +359,102 @@
self.assertEquals(math.frexp(NINF)[0], NINF)
self.assert_(math.isnan(math.frexp(NAN)[0]))
+ def testFsum(self):
+ # math.fsum relies on exact rounding for correct operation.
+ # There's a known problem with IA32 floating-point that causes
+ # inexact rounding in some situations, and will cause the
+ # math.fsum tests below to fail; see issue #2937. On non IEEE
+ # 754 platforms, and on IEEE 754 platforms that exhibit the
+ # problem described in issue #2937, we simply skip the whole
+ # test.
+
+ if not float.__getformat__("double").startswith("IEEE"):
+ return
+
+ # on IEEE 754 compliant machines, both of the expressions
+ # below should round to 10000000000000002.0.
+ if 1e16+2.0 != 1e16+2.9999:
+ return
+
+ # Python version of math.fsum, for comparison. Uses a
+ # different algorithm based on frexp, ldexp and integer
+ # arithmetic.
+ from sys import float_info
+ mant_dig = float_info.mant_dig
+ etiny = float_info.min_exp - mant_dig
+
+ def msum(iterable):
+ """Full precision summation. Compute sum(iterable) without any
+ intermediate accumulation of error. Based on the 'lsum' function
+ at http://code.activestate.com/recipes/393090/
+
+ """
+ tmant, texp = 0, 0
+ for x in iterable:
+ mant, exp = math.frexp(x)
+ mant, exp = int(math.ldexp(mant, mant_dig)), exp - mant_dig
+ if texp > exp:
+ tmant <<= texp-exp
+ texp = exp
+ else:
+ mant <<= exp-texp
+ tmant += mant
+ # Round tmant * 2**texp to a float. The original recipe
+ # used float(str(tmant)) * 2.0**texp for this, but that's
+ # a little unsafe because str -> float conversion can't be
+ # relied upon to do correct rounding on all platforms.
+ tail = max(len(bin(abs(tmant)))-2 - mant_dig, etiny - texp)
+ if tail > 0:
+ h = 1 << (tail-1)
+ tmant = tmant // (2*h) + bool(tmant & h and tmant & 3*h-1)
+ texp += tail
+ return math.ldexp(tmant, texp)
+
+ test_values = [
+ ([], 0.0),
+ ([0.0], 0.0),
+ ([1e100, 1.0, -1e100, 1e-100, 1e50, -1.0, -1e50], 1e-100),
+ ([2.0**53, -0.5, -2.0**-54], 2.0**53-1.0),
+ ([2.0**53, 1.0, 2.0**-100], 2.0**53+2.0),
+ ([2.0**53+10.0, 1.0, 2.0**-100], 2.0**53+12.0),
+ ([2.0**53-4.0, 0.5, 2.0**-54], 2.0**53-3.0),
+ ([1./n for n in range(1, 1001)],
+ float.fromhex('0x1.df11f45f4e61ap+2')),
+ ([(-1.)**n/n for n in range(1, 1001)],
+ float.fromhex('-0x1.62a2af1bd3624p-1')),
+ ([1.7**(i+1)-1.7**i for i in range(1000)] + [-1.7**1000], -1.0),
+ ([1e16, 1., 1e-16], 10000000000000002.0),
+ ([1e16-2., 1.-2.**-53, -(1e16-2.), -(1.-2.**-53)], 0.0),
+ # exercise code for resizing partials array
+ ([2.**n - 2.**(n+50) + 2.**(n+52) for n in range(-1074, 972, 2)] +
+ [-2.**1022],
+ float.fromhex('0x1.5555555555555p+970')),
+ ]
+
+ for i, (vals, expected) in enumerate(test_values):
+ try:
+ actual = math.fsum(vals)
+ except OverflowError:
+ self.fail("test %d failed: got OverflowError, expected %r "
+ "for math.fsum(%.100r)" % (i, expected, vals))
+ except ValueError:
+ self.fail("test %d failed: got ValueError, expected %r "
+ "for math.fsum(%.100r)" % (i, expected, vals))
+ self.assertEqual(actual, expected)
+
+ from random import random, gauss, shuffle
+ for j in range(1000):
+ vals = [7, 1e100, -7, -1e100, -9e-20, 8e-20] * 10
+ s = 0
+ for i in range(200):
+ v = gauss(0, random()) ** 7 - s
+ s += v
+ vals.append(v)
+ shuffle(vals)
+
+ s = msum(vals)
+ self.assertEqual(msum(vals), math.fsum(vals))
+
def testHypot(self):
self.assertRaises(TypeError, math.hypot)
self.ftest('hypot(0,0)', math.hypot(0,0), 0)
@@ -641,158 +737,6 @@
self.assertRaises(ValueError, math.sqrt, NINF)
self.assert_(math.isnan(math.sqrt(NAN)))
- def testSum(self):
- # math.sum relies on exact rounding for correct operation.
- # There's a known problem with IA32 floating-point that causes
- # inexact rounding in some situations, and will cause the
- # math.sum tests below to fail; see issue #2937. On non IEEE
- # 754 platforms, and on IEEE 754 platforms that exhibit the
- # problem described in issue #2937, we simply skip the whole
- # test.
-
- if not float.__getformat__("double").startswith("IEEE"):
- return
-
- # on IEEE 754 compliant machines, both of the expressions
- # below should round to 10000000000000002.0.
- if 1e16+2.999 != 1e16+2.9999:
- return
-
- # Python version of math.sum algorithm, for comparison
- def msum(iterable):
- """Full precision sum of values in iterable. Returns the value of
- the sum, rounded to the nearest representable floating-point number
- using the round-half-to-even rule.
-
- """
- # Stage 1: accumulate partials
- partials = []
- for x in iterable:
- i = 0
- for y in partials:
- if abs(x) < abs(y):
- x, y = y, x
- hi = x + y
- lo = y - (hi - x)
- if lo:
- partials[i] = lo
- i += 1
- x = hi
- partials[i:] = [x] if x else []
-
- # Stage 2: sum partials
- if not partials:
- return 0.0
-
- # sum from the top, stopping as soon as the sum is inexact.
- total = partials.pop()
- while partials:
- x = partials.pop()
- old_total, total = total, total + x
- error = x - (total - old_total)
- if error != 0.0:
- # adjust for correct rounding if necessary
- if partials and (partials[-1] > 0.0) == (error > 0.0) and \
- total + 2*error - total == 2*error:
- total += 2*error
- break
- return total
-
- from sys import float_info
- maxfloat = float_info.max
- twopow = 2.**(float_info.max_exp - 1)
-
- test_values = [
- ([], 0.0),
- ([0.0], 0.0),
- ([1e100, 1.0, -1e100, 1e-100, 1e50, -1.0, -1e50], 1e-100),
- ([1e308, 1e308, -1e308], OverflowError),
- ([-1e308, 1e308, 1e308], 1e308),
- ([1e308, -1e308, 1e308], 1e308),
- ([2.0**1023, 2.0**1023, -2.0**1000], OverflowError),
- ([twopow, twopow, twopow, twopow, -twopow, -twopow, -twopow],
- OverflowError),
- ([2.0**53, -0.5, -2.0**-54], 2.0**53-1.0),
- ([2.0**53, 1.0, 2.0**-100], 2.0**53+2.0),
- ([2.0**53+10.0, 1.0, 2.0**-100], 2.0**53+12.0),
-
- ([2.0**53-4.0, 0.5, 2.0**-54], 2.0**53-3.0),
- ([2.0**1023-2.0**970, -1.0, 2.0**1023], OverflowError),
- ([maxfloat, maxfloat*2.**-54], maxfloat),
- ([maxfloat, maxfloat*2.**-53], OverflowError),
- ([1./n for n in range(1, 1001)], 7.4854708605503451),
- ([(-1.)**n/n for n in range(1, 1001)], -0.69264743055982025),
- ([1.7**(i+1)-1.7**i for i in range(1000)] + [-1.7**1000], -1.0),
- ([INF, -INF, NAN], ValueError),
- ([NAN, INF, -INF], ValueError),
- ([INF, NAN, INF], ValueError),
-
- ([INF, INF], OverflowError),
- ([INF, -INF], ValueError),
- ([-INF, 1e308, 1e308, -INF], OverflowError),
- ([2.0**1023-2.0**970, 0.0, 2.0**1023], OverflowError),
- ([2.0**1023-2.0**970, 1.0, 2.0**1023], OverflowError),
- ([2.0**1023, 2.0**1023], OverflowError),
- ([2.0**1023, 2.0**1023, -1.0], OverflowError),
- ([twopow, twopow, twopow, twopow, -twopow, -twopow],
- OverflowError),
- ([twopow, twopow, twopow, twopow, -twopow, twopow], OverflowError),
- ([-twopow, -twopow, -twopow, -twopow], OverflowError),
-
- ([2.**1023, 2.**1023, -2.**971], OverflowError),
- ([2.**1023, 2.**1023, -2.**970], OverflowError),
- ([-2.**970, 2.**1023, 2.**1023, -2.**-1074], OverflowError),
- ([ 2.**1023, 2.**1023, -2.**970, 2.**-1074], OverflowError),
- ([-2.**1023, 2.**971, -2.**1023], -maxfloat),
- ([-2.**1023, -2.**1023, 2.**970], OverflowError),
- ([-2.**1023, -2.**1023, 2.**970, 2.**-1074], OverflowError),
- ([-2.**-1074, -2.**1023, -2.**1023, 2.**970], OverflowError),
- ([2.**930, -2.**980, 2.**1023, 2.**1023, twopow, -twopow],
- OverflowError),
- ([2.**1023, 2.**1023, -1e307], OverflowError),
- ([1e16, 1., 1e-16], 10000000000000002.0),
- ([1e16-2., 1.-2.**-53, -(1e16-2.), -(1.-2.**-53)], 0.0),
- ]
-
- for i, (vals, s) in enumerate(test_values):
- if isinstance(s, type) and issubclass(s, Exception):
- try:
- m = math.sum(vals)
- except s:
- pass
- else:
- self.fail("test %d failed: got %r, expected %r "
- "for math.sum(%.100r)" %
- (i, m, s.__name__, vals))
- else:
- try:
- self.assertEqual(math.sum(vals), s)
- except OverflowError:
- self.fail("test %d failed: got OverflowError, expected %r "
- "for math.sum(%.100r)" % (i, s, vals))
- except ValueError:
- self.fail("test %d failed: got ValueError, expected %r "
- "for math.sum(%.100r)" % (i, s, vals))
-
- # compare with output of msum above, but only when
- # result isn't an IEEE special or an exception
- if not math.isinf(s) and not math.isnan(s):
- self.assertEqual(msum(vals), s)
-
- from random import random, gauss, shuffle
- for j in range(1000):
- vals = [7, 1e100, -7, -1e100, -9e-20, 8e-20] * 10
- s = 0
- for i in range(200):
- v = gauss(0, random()) ** 7 - s
- s += v
- vals.append(v)
- shuffle(vals)
-
- s = msum(vals)
- self.assertEqual(msum(vals), math.sum(vals))
-
-
def testTan(self):
self.assertRaises(TypeError, math.tan)
self.ftest('tan(0)', math.tan(0), 0)
diff --git a/Lib/test/test_random.py b/Lib/test/test_random.py
index da62a4f..14e9fca 100644
--- a/Lib/test/test_random.py
+++ b/Lib/test/test_random.py
@@ -5,7 +5,7 @@
import time
import pickle
import warnings
-from math import log, exp, sqrt, pi, sum as msum
+from math import log, exp, sqrt, pi, fsum as msum
from test import support
class TestBasicOps(unittest.TestCase):