is it intentional that prod does not stop when it hits 0?

[Martin R]

sage: def test(n):
....:     print("n:", n)
....:     return n
....:
sage: l = [2,3,5,0,7,11,17,19]
sage: prod(map(test, l))
n: 2
n: 3
n: 5
n: 0
n: 7
n: 11
n: 17
n: 19

0

I expected that it would return 0 once we multiply with 0.

Martin

[kcrisman]

I'm not sure what you were expecting.  It does return 0, but it does so after all the print statements are done.  Remember, your "test" function just returns the input, so the map function just returns a list (well, a map object, but ...) and then we prod everything in the list.  But that happens AFTER you have done the map on test, and that requires printing out all of them.  The prod can't finish up until the entire list has been processed via map and the function "test".  I could imagine an alternate implementation of prod which checked each time whether zero had been produced in an intermediate step, but that doesn't appear to be in the code in "prod??".

[Nils Bruin]

as kcrisman mentions, prod first gathers all the factors before it multiplies them together. It does so for a reason: it takes the product in a balanced fasion; not just going through the factors iteratively. I don't know if it does an early exit if any zeros are encountered, but the strategy of multiplying together in a tree-like configuration is a significant optimisation for many common cases.

[William Stein]

Note also that prod(range(1,n)) does *NOT* just multiple 1 times 2
times 3 in order. Instead, it uses a tree approach so that the
multiplications involve objects with more balanced sizes, which is
much faster, e.g., for large integers multiplyling n*m with n and m
having similar sizes can overall be massively better than n * m with n
large and m tiny...

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/9c864eb6-b8fd-42c4-b1e7-b7eef89deae0n%40googlegroups.com.



--
William (http://wstein.org)

[Martin R]

Dear all!

Thank you for all the interesting answers!

I expected that prod would stop once it hits a zero value, assuming that multiplication would be more expensive.  In the special case I posted, the map object is actually *not* expanded first, it is handed to iterator_prod, which processes its input one by one.  In terms of code, I expeced something like

diff --git a/src/sage/misc/misc_c.pyx b/src/sage/misc/misc_c.pyx
index 20a0fe0016c..c98857122ec 100644
--- a/src/sage/misc/misc_c.pyx
+++ b/src/sage/misc/misc_c.pyx
@@ -219,6 +219,8 @@ cpdef iterator_prod(L, z=None):
    cdef Py_ssize_t tip = 0
 
    for x in L:
+        if not x:
+            return x
        i += 1
        if i & 1:
            # for odd i we extend the stack

I did a quick (non-comprehensive) check: iterator_prod is called often in the library, and it does seem that all tests pass (I only checked (part of?) sage/rings, because of a slow computer).

Of course, prod and iterator_prod are much faster than anything naive that checks for 0, which is why I actually guessed that prod would stop on zero.

I think I could do something like

class ZeroError(Exception):
    pass

def check0(x):
    if not x:
        raise ZeroError
    return x

def myprod(l):
    try:
        return prod(map(check0, l))
    except ZeroError:
        return 0   

but I don't really see a reason not to do the easy thing in prod.  Would you support such a change?  Or is there a simpler (efficient) solution I am overlooking?  If I remember correctly, in python it may be slow to construct a list using append.

I admit, however, that I have not checked whether or not the majority of the library code is such that arguments to prod will not contain 0 anyway.

(In my case -- lazy plethysm -- , this may happen, and it makes a huge difference)

Martin

[chris wuthrich]

Handling with try and check would be bad, but even in general this is an idea that may not be what we want. For instance there are cases where the product is interesting even if it "is zero".

sage: x = Qp(5,10)(0)
sage: y = x.add_bigoh(5)
sage: not x, not y
(True, True)
sage: x * 5, y * 5
(0, O(5^6))

Chris

[John Cremona]

If you really have a list and not just a generator, might it be worth
a first pass to see if there's a 0 in the list before forming the
product? With the tree structure for efficiently computing the
product, you might be doing a lot of multiplication before hitting the
zero item. I think that all(L) will be True if and only if L contains
a zero.

John

On Fri, 23 Sept 2022 at 09:11, chris wuthrich

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/28fee9ed-e94e-4f04-8e80-c02b585cafd3n%40googlegroups.com.

[Martin R]

@chris: that's a great point.  Although I thought that the convention for "_bool_" is to return False only if it provably False, and otherwise True?

@john: yes, in my very particular case I can pre-allocate the list, compute an element and store it in the list if it is non-zero, otherwise stop.  But that feels very clumsy.  I.e.;

lf = [None]*len(X)

for i, x in enumerate(X):

    f = compute_factor(x)

    if f:

        lf[i] = f

    else:

        p = f

        break

else:

    p = prod(lf)

Since in this very particular case, compute_factor likely dominates everything else, I can use append, too.  However, I certainly do not want to call compute_factor anymore once I have found a zero.

Martin

[kcrisman]

On Thursday, September 22, 2022 at 6:06:19 PM UTC-4 wst...@gmail.com wrote:

Note also that prod(range(1,n)) does *NOT* just multiple 1 times 2
times 3 in order. Instead, it uses a tree approach so that the
multiplications involve objects with more balanced sizes, which is

Thanks for that clarification - I was too lazy to look at the balanced_list_prod code :-)

[David Roe]

On Fri, Sep 23, 2022 at 4:39 AM 'Martin R' via sage-devel <sage-...@googlegroups.com> wrote:

@chris: that's a great point.  Although I thought that the convention for "_bool_" is to return False only if it provably False, and otherwise True?

That's not the convention for p-adics:

sage: bool(O(5^2))

False

 

@john: yes, in my very particular case I can pre-allocate the list, compute an element and store it in the list if it is non-zero, otherwise stop.  But that feels very clumsy.  I.e.;

lf = [None]*len(X)

for i, x in enumerate(X):

    f = compute_factor(x)

    if f:

        lf[i] = f

    else:

        p = f

        break

else:

    p = prod(lf)

Since in this very particular case, compute_factor likely dominates everything else, I can use append, too.  However, I certainly do not want to call compute_factor anymore once I have found a zero.

If you don't care about the balanced product, you can do

def short_circuit_mul(total, n):

    if total == 0:

        return total

    return total * n

p = itertools.accumulate(X, short_circuit_mul)

Since prod is supposed to be able to multiply a very general set of objects in sage, I don't think it's a good idea to add short-circuiting code to it in general.

David

 

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/de9719f7-1bbb-427a-8ab0-a8e12a5ea234n%40googlegroups.com.

[Martin R]

OK, this is off topic, but: shouldn't it be this convention?  At least: shouldn't there be some convention?  Maybe it would be good to discuss this in a separate thread.  Thus, I repeat the question:

Is there, or should there be a convention about x._bool_ returning False only when x is provably False?

(I don't object to keeping prod as it is, I was only curious, and I suspect that there are further places in the codebase where it matters.)

Martin

[Nils Bruin]

On Friday, 23 September 2022 at 10:37:01 UTC-7 axio...@yahoo.de wrote:

OK, this is off topic, but: shouldn't it be this convention?  At least: shouldn't there be some convention?  Maybe it would be good to discuss this in a separate thread.  Thus, I repeat the question:

Is there, or should there be a convention about x._bool_ returning False only when x is provably False?

No, quite the opposite. Certainly in SR, equalities that can't be proven correct (for "proof" used in the loose sense of what the various symbolic engines are willing to confirm), will return "False" when converted to "bool" value. The key is: _bool_ cannot really error out (that would break too much in python) and does not allow for "unknown" outcomes, so some choice must be made.

(I don't object to keeping prod as it is, I was only curious, and I suspect that there are further places in the codebase where it matters.)

If you're in a situation where generating the list of elements is expensive, so terminating on encountering a 0, you could do that yourself. Once you've constructed the list of elements without a 0, you can pass it to "prod". If you're doing this on objects that are prone to coefficient swell, the balanced product is worth it and the result will need about the same number of bits as the factors, so there is no significant memory benefit to not storing all the factors.

It would be perfectly possible to build a stream-based balanced product that only needs to store log(n) intermediate products. Whether that should terminate on encountering a 0 depends on whether the representation of 0 could be affected by mults (as it does for p-adics and series).

I suspect that "prod" being built this way is because Python 2 was much more list-based that iterator-based. In Python 3 it would make sense to rewrite it iterator-based. For products where these is a heuristic "size" you could of course do better than just balancing on factors: you could combine pairs of minimal height for your multiplications. In an iterator-based version, you'd probably want to do that while adding fresh pairs of factors to the mix while they are available.

[Martin R]

On Friday, 23 September 2022 at 20:09:55 UTC+2 Nils Bruin wrote:

On Friday, 23 September 2022 at 10:37:01 UTC-7 axio...@yahoo.de wrote:

OK, this is off topic, but: shouldn't it be this convention?  At least: shouldn't there be some convention?  Maybe it would be good to discuss this in a separate thread.  Thus, I repeat the question:

Is there, or should there be a convention about x._bool_ returning False only when x is provably False?

No, quite the opposite. Certainly in SR, equalities that can't be proven correct (for "proof" used in the loose sense of what the various symbolic engines are willing to confirm), will return "False" when converted to "bool" value. The key is: _bool_ cannot really error out (that would break too much in python) and does not allow for "unknown" outcomes, so some choice must be made.

The doc of Expression.__bool__ says:

        Return True unless this symbolic expression can be shown by Sage
        to be zero.  Note that deciding if an expression is zero is
        undecidable in general.

which seems to be in agreement with what I thought.  Or am I missing something?

It seems really strange to me that "not O(x^7)" should be True.

Martin

[Vincent Delecroix]

On Tue, 27 Sept 2022 at 11:58, 'Martin R' via sage-devel

According to this symbolic specification,O(x^7) is not provably an
exact zero so it is reasonable to evaluate it to False. Which means
that "not O(x^7)" ought to be True.

[Martin R]

I am reading this differently, but that may be my lack of knowledge of English.

I thought "Return True, unless provably zero" would give true, if something cannot be shown to be zero.

Martin

[Vincent Delecroix]

You are right of course (my bad): bool(expr) could be considered as
being True according to these specifications (and anyway "True" is
always a good answer). Though these are specifications for SR and does
not apply to the entire library. It is not clear to me what global
specification we could have for bool(algebraic expression).

On Tue, 27 Sept 2022 at 12:49, 'Martin R' via sage-devel

<sage-...@googlegroups.com> wrote:
>
> I am reading this differently, but that may be my lack of knowledge of English.
>
> I thought "Return True, unless provably zero" would give true, if something cannot be shown to be zero.
>
> Martin
>
> On Tuesday, 27 September 2022 at 12:21:12 UTC+2 vdelecroix wrote:
>>
>> On Tue, 27 Sept 2022 at 11:58, 'Martin R' via sage-devel
>> <sage-...@googlegroups.com> wrote:
>> >
>> >
>> >
>> > On Friday, 23 September 2022 at 20:09:55 UTC+2 Nils Bruin wrote:
>> >>
>> >> On Friday, 23 September 2022 at 10:37:01 UTC-7 axio...@yahoo.de wrote:
>> >>>
>> >>> OK, this is off topic, but: shouldn't it be this convention? At least: shouldn't there be some convention? Maybe it would be good to discuss this in a separate thread. Thus, I repeat the question:
>> >>>
>> >>> Is there, or should there be a convention about x._bool_ returning False only when x is provably False?
>> >>>
>> >> No, quite the opposite. Certainly in SR, equalities that can't be proven correct (for "proof" used in the loose sense of what the various symbolic engines are willing to confirm), will return "False" when converted to "bool" value. The key is: _bool_ cannot really error out (that would break too much in python) and does not allow for "unknown" outcomes, so some choice must be made.
>> >
>> >
>> > The doc of Expression.__bool__ says:
>> >
>> > Return True unless this symbolic expression can be shown by Sage
>> > to be zero. Note that deciding if an expression is zero is
>> > undecidable in general.
>> >
>> > which seems to be in agreement with what I thought. Or am I missing something?
>> >
>> > It seems really strange to me that "not O(x^7)" should be True.
>>
>> According to this symbolic specification,O(x^7) is not provably an
>> exact zero so it is reasonable to evaluate it to False. Which means
>> that "not O(x^7)" ought to be True.
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/a4a00641-0b8d-4fd4-8690-7e75bb860c74n%40googlegroups.com.

[Marc Mezzarobba]

Vincent Delecroix wrote:
> Though these are specifications for SR and does
> not apply to the entire library. It is not clear to me what global
> specification we could have for bool(algebraic expression).

Something like "bool(x) iff x is not trivially zero" would make sense to
me, where "not trivially zero" means "not exactly identical to the most
simple representation of zero of the given type". Something that can be
used to decide whether a coefficient of a polynomial should be
displayed, for instance. (And that is cheap to test.)

--
Marc