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

Tim Peters added the comment: Or, like I did, they succumbed to an untested "seemingly plausible" illusion ;-) I generated 1,000 random vectors (in [0.0, 10.0)) of length 100, and for each generated 10,000 permutations. So that's 10 million 100-element products overall. The

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

Raymond Hettinger added the comment: IIRC, both Factor and Julia use pairwise multiplication. I'm guessing that the reason is that if you have an associative-reduce higher order function, you tend to use it everywhere even in cases where the benefits are negligible ;-) --

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

Tim Peters added the comment: More extensive testing convinces me that pairing multiplication is no real help at all - the error distributions appear statistically indistinguishable from left-to-right multiplication. I believe this has to do with the "condition numbers" of fp addition and

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

Raymond Hettinger added the comment: > But I see no obvious improvement in accuracy > over "left to right" for the uniformly random > test cases I've tried. Same here. -- ___ Python tracker

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

Tim Peters added the comment: Well, that can't work: the most likely result for a long input is 0.0 (try it!). frexp() forces the mantissa into range [0.5, 1.0). Multiply N of those, and the result _can_ be as small as 2**-N. So, as in Mark's code, every thousand times (2**-1000 is

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

Raymond Hettinger added the comment: Here's a pairwise variant: def prod(seq): stack = [] exp = 0 for i, x in enumerate(seq, start=1): m, e = frexp(x) exp += e stack += [m] while not i&1: i >>= 1

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

Tim Peters added the comment: "Denormal" and "subnormal" mean the same thing. The former is probably still in more common use, but all the relevant standards moved to "subnormal" some years ago. Long chains of floating mults can lose precision too, but hardly anyone bothers to do anything

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

Raymond Hettinger added the comment: I had not put any thought into subnormals (denormals?) because they didn't arise in my use cases. But it would be nice to handle them as well as possible. Accuracy improvements are welcome as well. And that goes hand in hand with better commutativity.

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

Tim Peters added the comment: I may well have misread the code, believing it can still allow spurious over/underflows. On second reading of the current file, I don't know - it's more complicated than I thought. If it does guarantee to prevent them, then I shift from -1 to (probably ) -0.

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

Tim Peters added the comment: Cool! So looks like you could also address an accuracy (not out-of-range) thing the frexp() method also does as well as possible: loosen the definition of "underflow" to include losing bits to subnormal products. For example, with the inputs >>> xs = [1e-200,

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

Raymond Hettinger added the comment: Variable name correction: - If "x" and "t" are on the opposite side + If "x" and "total" are on the opposite side Extreme points will successfully combine: >>> float_info.max * float_info.min 3.9996 --

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

Raymond Hettinger added the comment: The algorithm stops all spurious overflows and underflows. If favorable cancellations exist, it finds them. Algorithm in Words -- For every x in the sequence, multiply onto the total if possible. If x and "total" can't be combined

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

Tim Peters added the comment: See "wisdom" earlier ;-) It's ad hoc trickery that seemingly can't be explained without showing the precise implementation in use today. As already mentioned, frexp() trickery _can_ be explained: exactly what you'd get if left-to-right HW multiplication were

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

Raymond Hettinger added the comment: I attached a file with latest (and more tested) recipe. The underflow test was fixed: "not total and old_total and x". Also, the final call to math.prod() was in-lined so that I could time it with PyPy. --

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

Raymond Hettinger added the comment: FWIW, the occasions where this mattered all involved a mix of multiplications and divisions that mostly cancel out. The quadratic formula example is typical: product([4.0, a, c, 1.0/b, 1.0/b]. Or a floating point implementation of comb():

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

Raymond Hettinger added the comment: [Uncle Timmy] > I'm skeptical of the need for - and wisdom of - this. Granted, the need is not common. On the other hand, if we can do it cheaply, why wouldn't we? Unnecessary overflow or underflow is never a desirable outcome. Currently, users do not

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

Change by Raymond Hettinger : Added file: https://bugs.python.org/file49373/sum_and_prod.py ___ Python tracker ___ ___ Python-bugs-list

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

Tim Peters added the comment: I'm skeptical of the need for - and wisdom of - this. Where does it come up? I can't think of any context where this would have been useful, or of any other language or package that does something like this. Long chains of mults are unusual outside of integer

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

Mark Dickinson added the comment: Whoops. There's a missing `count += 1` in there, of course. -- ___ Python tracker ___ ___

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

Mark Dickinson added the comment: Here's code to illustrate the idea. It doesn't yet handle zeros, infinities or nans; that support would need to be added. import math def fprod(numbers): # Product of numbers, avoiding intermediate underflow and overflow. # Does not handle zeros,

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

Mark Dickinson added the comment: If we want to do this (and I'm still not convinced that we do), I think there's a simpler way: use `frexp` to decompose each float into a fraction and an exponent, multiply the fractions (which barring zeros will all be in [0.5, 1.0)), and keep track of the

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

Vedran Čačić added the comment: > s.append(x) if side == s_side else t.append(x) To me, (s if side == s_side else t).append(x) seems much better. Not only more is factored, but .append is viewed as a procedure (returning None, changing its object), and if-expression is really used for its

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

Raymond Hettinger added the comment: Two edits: - s.append(x) if side == s_side else t.append(y) + s.append(x) if side == s_side else t.append(x) - return prod(s, start=total) +for x in s: +total *= x +return total -- ___ Python

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

Raymond Hettinger 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

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

Change by Jeffrey Kintscher : -- nosy: +Jeffrey.Kintscher ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

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

Pablo Galindo Salgado added the comment: I think what Raymond proposes makes sense and it will certainly add value, especially given the mentioned expectations on what an implementation on the stdlib should have. The only think I would like to know is how much code/measured performance

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

Raymond Hettinger added the comment: The existing math.prod() already has a separate code path for floats. The proposal is to add an overflow/underflow check to that existing path so that we don't get nonsense like 0.0, 1e+175, or Inf depending on the data ordering. That doesn't warrant a

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

Vedran Čačić added the comment: Yes, fprod would be nice [though if you just want to avoid over/underflows, much easier solution is to first determine the sign, then sum the logarithms of absolute values, and exponentiate that]. But I agree with Tim that it should be a separate function. For

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

Mark Dickinson added the comment: This message from Tim, starting "I'd like to divorce `prod()` from floating-point complications", seems relevant here: https://bugs.python.org/issue35606#msg333090 -- ___ Python tracker

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

New submission from Raymond Hettinger : 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