-
-
Notifications
You must be signed in to change notification settings - Fork 31.1k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add prod() function to the math module #79787
Comments
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 |
PR 11359 looks too complicated. I am not sure that a simple one-line function is worth it. |
@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 A naive implementation would also support user-defined types which would probably be a good thing IMO |
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).
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. |
[Raymond]
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
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. |
Computing the geometric mean of numbers require to compute the product of these numbers: 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:
"versus" Rémi Lapeyre:
Would it make sense to only implement product for an iterable of floats, as math.fsum()? |
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". |
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. |
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:
|
I'd like to divorce Not that floats should suffer benign neglect forever, but heroically complex - and expensive - float implementations should get their own function, like |
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)' ..................... ./python -m perf timeit -s "import functools;import operator;iterable=list(map(float,range(10000)))" 'functools.reduce(operator.mul, iterable, 1)' ./python -m perf timeit -s "import math;iterable=list(map(float,range(10000)))" 'math.prod(iterable)' ..................... ./python -m perf timeit -s "import functools;import decimal;import operator;iterable=list(map(decimal.Decimal,range(10000)))" 'functools.reduce(operator.mul, iterable, 1)' ./python -m perf timeit -s "import math;import decimal;iterable=list(map(decimal.Decimal,range(10000)))" 'math.prod(iterable)' Properties
------------- 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? |
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. |
@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. |
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. |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: