This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author rhettinger
Recipients mark.dickinson, pablogsal, rhettinger, tim.peters
Date 2020-08-02.20:03:18
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1596398598.74.0.852327933948.issue41458@roundup.psfhosted.org>
In-reply-to
Content
For float inputs, the math.prod() function could be made smarter about avoiding overflow() and underflow().  That would also improve commutativity as well.

Other tools like math.hypot() already take measures to avoid overflow/underflow and to improve commutativity.  This makes them nicer to use than näive implementations.

The recipe that I've been using for years is shown below.  It certainly isn't the best way, but it is O(n) and always avoids overflow and underflow when possible.  It has made for a nice primitive when implementing other functions that need to be as robust as possible.  For example, in the quadratic formula, the √(b²-4ac) factors to b√(1-4ac/b²) and the rightmost term gets implemented in Python as product([4.0, a, c, 1.0/b, 1.0/b]).

>>> from math import prod, fabs
>>> from collections import deque
>>> from itertools import permutations

>>> def product(seq):
    s = deque()
    for x in seq:
        s.appendleft(x) if fabs(x) < 1.0 else s.append(x)
    while len(s) > 1:
        x = s.popleft() * s.pop()
        s.appendleft(x) if fabs(x) < 1.0 else s.append(x)
    return s[0] if s else 1.0

>>> data = [2e300, 2e200, 0.5e-150, 0.5e-175]
>>> for factors in permutations(data):
	print(product(factors), prod(factors), sep='\t')

	
1e+175	inf
1.0000000000000001e+175	inf
1e+175	inf
1e+175	1e+175
1.0000000000000001e+175	inf
1.0000000000000001e+175	1.0000000000000001e+175
1.0000000000000001e+175	inf
1e+175	inf
1.0000000000000001e+175	inf
1.0000000000000001e+175	1.0000000000000001e+175
1e+175	inf
1e+175	1e+175
1e+175	inf
1e+175	1e+175
1.0000000000000001e+175	inf
1.0000000000000001e+175	1.0000000000000001e+175
1e+175	0.0
1.0000000000000001e+175	0.0
1.0000000000000001e+175	inf
1.0000000000000001e+175	1.0000000000000001e+175
1e+175	inf
1e+175	1e+175
1.0000000000000001e+175	0.0
1e+175	0.0

For math.prod(), I think a better implementation would be to run normally until an underflow or overflow is detected, then back up a step and switch-over to pairing low and high magnitude values.  Since this is fallback code, it would only affect speed to the extent that we test for overflow or underflow at every step.  Given how branch prediction works, the extra tests might even be free or at least very cheap.

The math module functions usually go the extra mile to be more robust (and often faster) than a näive implementation.  These are the primary reasons we teach people to prefer sqrt() over x**2, log1p(x) over log(1+x), prod(seq) over reduce(mul, seq, 1.0), log2(x) over log(x, 2), fsum(seq) over sum(seq), and hypot(x,y) over sqrt(x**2 + y**2).  In each case, the library function is some combination of more robust, more accurate, more commutative, and/or faster than a user can easily create for themselves.
History
Date User Action Args
2020-08-02 20:03:18rhettingersetrecipients: + rhettinger, tim.peters, mark.dickinson, pablogsal
2020-08-02 20:03:18rhettingersetmessageid: <1596398598.74.0.852327933948.issue41458@roundup.psfhosted.org>
2020-08-02 20:03:18rhettingerlinkissue41458 messages
2020-08-02 20:03:18rhettingercreate