msg332676 - (view) |
Author: Raymond Hettinger (rhettinger) *  |
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) *  |
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) *  |
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) *  |
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) *  |
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) *  |
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) *  |
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) *  |
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) *  |
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) *  |
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) *  |
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) *  |
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.
|
msg402772 - (view) |
Author: Pablo Galindo Salgado (pablogsal) *  |
Date: 2021-09-28 12:32 |
New changeset 84975146a7ce64f1d50dcec8311b7f7188a5c962 by Pablo Galindo Salgado in branch 'main':
bpo-35606: Fix math.prod tests using 'start' as keyword parameter (GH-28595)
https://github.com/python/cpython/commit/84975146a7ce64f1d50dcec8311b7f7188a5c962
|
msg402778 - (view) |
Author: miss-islington (miss-islington) |
Date: 2021-09-28 12:56 |
New changeset fd52afd1928643a715202147b1ce5b0d130ec252 by Miss Islington (bot) in branch '3.10':
bpo-35606: Fix math.prod tests using 'start' as keyword parameter (GH-28595)
https://github.com/python/cpython/commit/fd52afd1928643a715202147b1ce5b0d130ec252
|
msg402803 - (view) |
Author: Łukasz Langa (lukasz.langa) *  |
Date: 2021-09-28 20:19 |
New changeset cd00fee8dd63bc3a1360280f55640409cb579a05 by Miss Islington (bot) in branch '3.9':
bpo-35606: Fix math.prod tests using 'start' as keyword parameter (GH-28595) (GH-28604)
https://github.com/python/cpython/commit/cd00fee8dd63bc3a1360280f55640409cb579a05
|
|
Date |
User |
Action |
Args |
2022-04-11 14:59:09 | admin | set | github: 79787 |
2021-09-28 20:19:11 | lukasz.langa | set | nosy:
+ lukasz.langa messages:
+ msg402803
|
2021-09-28 12:56:59 | miss-islington | set | messages:
+ msg402778 |
2021-09-28 12:32:55 | miss-islington | set | pull_requests:
+ pull_request26979 |
2021-09-28 12:32:51 | pablogsal | set | messages:
+ msg402772 |
2021-09-28 12:32:50 | miss-islington | set | nosy:
+ miss-islington
pull_requests:
+ pull_request26978 |
2021-09-28 10:20:11 | pablogsal | set | pull_requests:
+ pull_request26975 |
2019-02-14 10:35:06 | lschoe | set | messages:
+ msg335515 |
2019-02-14 08:26:29 | mark.dickinson | set | keywords:
patch, patch, patch
messages:
+ msg335510 |
2019-02-14 08:03:18 | lschoe | set | nosy:
+ lschoe messages:
+ msg335508
|
2019-02-07 07:04:59 | rhettinger | set | keywords:
patch, patch, patch status: open -> closed resolution: fixed stage: patch review -> resolved |
2019-02-07 07:04:06 | rhettinger | set | messages:
+ msg335007 |
2019-02-07 01:16:31 | pablogsal | set | keywords:
patch, patch, patch nosy:
+ pablogsal messages:
+ msg334995
|
2019-01-06 06:26:58 | tim.peters | set | keywords:
patch, patch, patch
messages:
+ msg333090 |
2019-01-05 10:40:19 | pitrou | set | keywords:
patch, patch, patch
messages:
+ msg333051 |
2019-01-05 02:48:13 | rhettinger | set | keywords:
patch, patch, patch
messages:
+ msg333034 |
2019-01-04 22:08:25 | pitrou | set | keywords:
patch, patch, patch nosy:
+ pitrou messages:
+ msg333007
|
2019-01-04 22:03:45 | vstinner | set | keywords:
patch, patch, patch nosy:
+ vstinner messages:
+ msg333005
|
2018-12-31 17:02:30 | mark.dickinson | set | keywords:
patch, patch, patch
messages:
+ msg332824 |
2018-12-31 00:48:38 | rhettinger | set | keywords:
patch, patch, patch
messages:
+ msg332777 |
2018-12-30 21:10:43 | remi.lapeyre | set | nosy:
+ remi.lapeyre messages:
+ msg332763
|
2018-12-30 20:52:38 | serhiy.storchaka | set | keywords:
patch, patch, patch nosy:
+ serhiy.storchaka messages:
+ msg332762
|
2018-12-29 22:09:02 | pablogsal | set | pull_requests:
- pull_request10677 |
2018-12-29 22:08:52 | pablogsal | set | pull_requests:
- pull_request10678 |
2018-12-29 22:07:12 | pablogsal | set | keywords:
+ patch stage: patch review pull_requests:
+ pull_request10678 |
2018-12-29 22:07:04 | pablogsal | set | keywords:
+ patch stage: (no value) pull_requests:
+ pull_request10677 |
2018-12-29 22:06:56 | pablogsal | set | keywords:
+ patch stage: (no value) pull_requests:
+ pull_request10676 |
2018-12-28 23:29:41 | xtreak | set | nosy:
+ xtreak
|
2018-12-28 19:29:12 | rhettinger | create | |