classification
Title: Add prod() function to the math module
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.8
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: aleax, lschoe, mark.dickinson, pablogsal, pitrou, remi.lapeyre, rhettinger, serhiy.storchaka, tim.peters, vstinner, xtreak
Priority: normal Keywords: patch, patch, patch

Created on 2018-12-28 19:29 by rhettinger, last changed 2019-02-14 10:35 by lschoe. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 11359 merged pablogsal, 2018-12-29 22:06
Messages (15)
msg332676 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-12-28 19:29
Back in 2007, a user suggested a built-in prod() function with an API similar to the built-in sum() function.  The proposal was rejected because it wasn't needed often enough to justify a builtin function.  See https://bugs.python.org/issue1093

Though prod() doesn't meet the threshold for a builtin, it would be reasonable to add this to the math module (or an imath module).

Personally, I've wanted and written this function on several occasions (for applications such as multiplying probabilities).  On stack overflow, it has been a popular question with recurring interest.  See https://stackoverflow.com/questions/7948291/ and https://stackoverflow.com/questions/595374
msg332762 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-12-30 20:52
PR 11359 looks too complicated. I am not sure that a simple one-line function is worth it.
msg332763 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2018-12-30 21:10
@serhiy.storchaka, it should be possible to make it far simpler if we make math_prod_impl more naive by removing the hypothesis made on `iterable` and the many fast-paths like builtin_sum_impl() does when SLOW_SUM is defined, right?

A naive implementation would also support user-defined types which would probably be a good thing IMO
msg332777 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-12-31 00:48
> I am not sure that a simple one-line function is worth it.

FWIW, it is often the one liners that turn out to be the most useful building blocks.  In this case the one-liner is inconvenient (two imports), not as fast we would like, and a little opaque:  functools.reduce(operator.mul, iterable, 1).

> PR 11359 looks too complicated.

I would be happy with the simplest possible implementation.  That said, we do have a history of going gonzo in C internals to get better speed/space performance (look the code for math.factorial() for example), to have better accuracy and avoid overflow/underflow (math.hypot() for example), or to implement particular NaN/Inf handling not present in a naive implementation.
msg332824 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2018-12-31 17:02
[Raymond]

> or to implement particular NaN/Inf handling not present in a naive implementation

On this subject, some effort has been made in the past to make (almost) all the math module functions behave consistently with respect to things like exceptions, overflow, infinities, nans, signed zeros, etc. (There are unfortunately some exceptions to the general rule, like math.pow.) If possible, I'd like to see any implementation of math.prod do the same; I'd prefer us to get this right initially rather than tweak the definition to make subtle possibly-breaking changes to the implementation later.

That is, the ideal behaviour would include things like:

(a) a product of finite floating-point (or convertible-to-float) numbers should raise an exception on overflow. Probably OverflowError, though ValueError wouldn't be indefensible either.

(b) a product involving infinities but no NaNs or zeros should return an appropriately-signed infinity (where the sign is determined by an xor of all the signs of the inputs)

(c) a product involving both infinities and zeros (but not NaNs) should raise ValueError

(d) a product involving a NaN at any point should just return NaN

The combination of these can get a bit awkward: for example, if a list starts with `[1e300, 1e300, ...]`, then it's not necessarily correct to raise `OverflowError` after processing the first two inputs, because if there's a NaN somewhere later in the list then that NaN should dominate the result. However, IEEE 754 allows some leeway here for its "Reduction operations" (section 9.4 of the to-be-superseded-any-day-now 2008 version of the standard), stating:

> Numerical results and exceptional behavior, including the invalid operation exception, may differ among implementations due to the precision of intermediates and the order of evaluation.

BTW, if we wanted to go for IEEE 754 compliance, the operation to implement would be "scaledProd", which takes a vector of inputs and returns a float along with an exponent; this allows taking products of long lists of floats without needing to worry about underflow or overflow. That's probably not what we want here, but the spec of scaledProd might help guide us with the implementation of prod.
msg333005 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2019-01-04 22:03
Computing the geometric mean of numbers require to compute the product of these numbers:
https://en.wikipedia.org/wiki/Geometric_mean

The geometric mean can be used to summarize benchmark results using different units to get a single number.

--

When computing the product of floats, is there a smart implementation reducing the error? I'm asking because math.fsum() doesn't use a naive loop but a smart implementation to minimize the error.

--

Mark Dickinson:
> On this subject, some effort has been made in the past to make (almost) all the math module functions behave consistently with respect to things like exceptions, overflow, infinities, nans, signed zeros, etc.

"versus"

Rémi Lapeyre:
> A naive implementation would also support user-defined types which would probably be a good thing IMO

Would it make sense to only implement product for an iterable of floats, as math.fsum()?
msg333007 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2019-01-04 22:08
I agree with Mark that correctness, rather than performance, should be the main attraction of a stdlib implementation.

By the way "prod" is slightly obscure (though it's Numpy's chosen spelling), how about "product"?  After all, we went with the full "factorial".
msg333034 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-01-05 02:48
I don't like the name overlap with itertools.product().  Currently, math and itertools have no overlapping names.  Also, I expect that like sum(), the prod() function will be used with generator comprehensions and should best be kept short and not dominating the rest of the expression.

It's true that factorial is spelled-out, but that was probably a mistake -- it has been somewhat awkward in expressions that contain factorial terms.  Ideally, we would have comb, perm, fact, and prod.
msg333051 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2019-01-05 10:40
For the record, I would have to look up the documentation everytime I encounter "comb" and "perm", while the full names are intuitive to me.

"prod" and "fact" feel somewhat less obscure.

I suppose there are two possible audiences here:
- the expert math / itertools developer that values concise names when typing in complex expressions
- the occasional math / itertools user that would have to look up any non-intuitive name on every encounter
msg333090 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-01-06 06:26
I'd like to divorce `prod()` from floating-point complications.  The `sum()` builtin has proved extremely handy, even for floats, in large part because it's type-agnostic and straightforward.  While I'd usually use `prod()` on ints and Fractions, in almost all cases I have for multiplying floats a dirt simple implementation would work fine too (e.g., I don't multiply NaNs or infinities to begin with, overflow and underflow can't occur in context, and I usually couldn't care less about the accuracy of the trailing bits).

Not that floats should suffer benign neglect forever, but heroically complex - and expensive - float implementations should get their own function, like `fprod()` (like they got their own `fsum()` function).  Likewise if, e.g., someone wants an `iprod()` that makes heroic efforts to reorder partial products to speed multiplying sequences of giant integers, or `matprod()` to re-associate matrix multiplications in an optimal way, or ...
msg334995 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2019-02-07 01:16
PR 11359 has the following properties in its current state:

Performance vs naive implementation
-----------------------------------

./python -m perf timeit -s "import functools;import operator;iterable=list(range(10000))" 'functools.reduce(operator.mul, iterable, 1)'      .....................
Mean +- std dev: 654 us +- 15 us
./python -m perf timeit -s "import math;iterable=list(range(10000))" 'math.prod(iterable)'
.....................
Mean +- std dev: 72.3 us +- 1.1 us

./python -m perf timeit -s "import functools;import operator;iterable=list(map(float,range(10000)))" 'functools.reduce(operator.mul, iterable, 1)'
.....................
Mean +- std dev: 705 us +- 10 us

./python -m perf timeit -s "import math;iterable=list(map(float,range(10000)))" 'math.prod(iterable)'                                        .....................
Mean +- std dev: 52.9 us +- 2.0 us

./python -m perf timeit -s "import functools;import decimal;import operator;iterable=list(map(decimal.Decimal,range(10000)))" 'functools.reduce(operator.mul, iterable, 1)'
.....................
Mean +- std dev: 2.10 ms +- 0.03 ms

./python -m perf timeit -s "import math;import decimal;iterable=list(map(decimal.Decimal,range(10000)))" 'math.prod(iterable)'
Mean +- std dev: 1.12 ms +- 0.21 ms

Properties
----------

* It behaves with floats as numpy.prod:
   - A product of a finite floating-point (or convertible-to-float) numbers yields a float, nan or +-inf (no overflow checks).
   - A product involving infinities but no NaNs or zeros returns an appropriately-signed infinity.
   - A product involving both infinities and zeros (but not NaNs) returns 'NaN'.
   - A product involving a NaN at any point returns NaN.

* Is a implemented as general purpose function - like the built-in sum - as Tim is advising. It can multiply any Python type but has two fast-paths for floats and integers (or a mix of both).

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

In my humble opinion, any type-specialized implementation should exist in addition to this function (as fprod, iprod, scaledProd) while prod should remain as a general purpose function mirroring sum. Notice that people using numerical suites like numpy are used to the properties described in the previous paragraph and I think this is an advantage.

The main advantage of the function as it exists now in PR11359 is convenience and speed (almost 10x for fast paths and 2x for general types). I think this function will be very useful for scientific/statistical computing without the need for pulling in numpy and friends.

What do people think?
msg335007 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-02-07 07:04
New changeset bc098515864d0d1ffe8fb97ca1a0526c30fee45a by Raymond Hettinger (Pablo Galindo) in branch 'master':
bpo-35606: Implement math.prod (GH-11359)
https://github.com/python/cpython/commit/bc098515864d0d1ffe8fb97ca1a0526c30fee45a
msg335508 - (view) Author: Berry Schoenmakers (lschoe) Date: 2019-02-14 08:03
Nice to see the arrival of the prod() function.

Just as for the built-in pow(x, y[, z]) function it would be very useful to have an optional argument z for computing products modulo z. Typical use case in cryptography would be:

prod((pow(x, y, z) for x, y in zip(g, s)), z)

to compute the product of all (potentially many) g[i]**s[i]'s modulo z. 

And, just as with the use of pow(), the intermediate values for prod() may in general grow quickly, hence modular reduction is essential to limit time and space usage.
msg335510 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-02-14 08:26
@Berry: I'd suggest opening a separate issue for that discussion; this issue's already closed, so it's likely that few people will notice your message.
msg335515 - (view) Author: Berry Schoenmakers (lschoe) Date: 2019-02-14 10:35
Thanks for the suggestion, Mark.

I was not so sure, and the Nosy List for this issue is already quite extensive, so considered you guys as an appropriate audience for my first comment on this platform.

But I will also look into opening a separate issue later today.
History
Date User Action Args
2019-02-14 10:35:06lschoesetmessages: + msg335515
2019-02-14 08:26:29mark.dickinsonsetkeywords: patch, patch, patch

messages: + msg335510
2019-02-14 08:03:18lschoesetnosy: + lschoe
messages: + msg335508
2019-02-07 07:04:59rhettingersetkeywords: patch, patch, patch
status: open -> closed
resolution: fixed
stage: patch review -> resolved
2019-02-07 07:04:06rhettingersetmessages: + msg335007
2019-02-07 01:16:31pablogsalsetkeywords: patch, patch, patch
nosy: + pablogsal
messages: + msg334995

2019-01-06 06:26:58tim.peterssetkeywords: patch, patch, patch

messages: + msg333090
2019-01-05 10:40:19pitrousetkeywords: patch, patch, patch

messages: + msg333051
2019-01-05 02:48:13rhettingersetkeywords: patch, patch, patch

messages: + msg333034
2019-01-04 22:08:25pitrousetkeywords: patch, patch, patch
nosy: + pitrou
messages: + msg333007

2019-01-04 22:03:45vstinnersetkeywords: patch, patch, patch
nosy: + vstinner
messages: + msg333005

2018-12-31 17:02:30mark.dickinsonsetkeywords: patch, patch, patch

messages: + msg332824
2018-12-31 00:48:38rhettingersetkeywords: patch, patch, patch

messages: + msg332777
2018-12-30 21:10:43remi.lapeyresetnosy: + remi.lapeyre
messages: + msg332763
2018-12-30 20:52:38serhiy.storchakasetkeywords: patch, patch, patch
nosy: + serhiy.storchaka
messages: + msg332762

2018-12-29 22:09:02pablogsalsetpull_requests: - pull_request10677
2018-12-29 22:08:52pablogsalsetpull_requests: - pull_request10678
2018-12-29 22:07:12pablogsalsetkeywords: + patch
stage: patch review
pull_requests: + pull_request10678
2018-12-29 22:07:04pablogsalsetkeywords: + patch
stage: (no value)
pull_requests: + pull_request10677
2018-12-29 22:06:56pablogsalsetkeywords: + patch
stage: (no value)
pull_requests: + pull_request10676
2018-12-28 23:29:41xtreaksetnosy: + xtreak
2018-12-28 19:29:12rhettingercreate