[issue41458] Avoid overflow/underflow in math.prod()

[Raymond Hettinger]

Raymond Hettinger <raymond.hettinger at gmail.com> added the comment:

Here's variant (minimally tested) that has a fast path for the common case (no overflow or underflow), that uses a list instead of a deque, that keeps memory use small (only storing pending values that can't be combined without triggering an overflow or underflow).

----------------------------

from math import fabs, prod, isfinite

def product(seq, start=1.0):
    total = start
    s = []                 # values that would overflow the total
    s_side = False         # true if s_i increase the magnitude of the product
    for x in seq:
        old_total = total
        total *= x
        underflow = not total and old_total and not x
        if isfinite(total) and not underflow:
            continue       # fast-path for multiplies that doesn't overflow/underflow
        total = old_total

        side = fabs(x) > 1.0
        if not s or side == s_side:
            s.append(x)
            s_side = side
            continue

        t = [x, total]
        while s and t:      # opposite sides:  matter and antimatter
            x = s.pop() * t.pop()
            side = fabs(x) > 1.0
            s.append(x) if side == s_side else t.append(y)
        if t:
            s = t
            s_side = not s_side
        total = s.pop()
    return prod(s, start=total)

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue41458>
_______________________________________