Re: [sage-devel] Re: is it intentional that prod does not stop when it hits 0?

[David Roe]

On Fri, Sep 23, 2022 at 4:39 AM 'Martin R' via sage-devel <
sage-devel@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



>
> Martin
> On Friday, 23 September 2022 at 10:28:57 UTC+2 john.c...@gmail.com wrote:
>
>> 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
>>  wrote:
>> >
>> > 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
>> >
>> > --
>> > 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.
>>
>>
> --
> 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+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sage-devel/de9719f7-1bbb-427a-8ab0-a8e12a5ea234n%40googlegroups.com
> 
> .
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/CAChs6_kvXQfnKJfGenFbrq6CHiNqbDSHn4tJdbBzqx0VkjO2nw%40mail.gmail.com.

Re: [sage-devel] Re: is it intentional that prod does not stop when it hits 0?

[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 :-)

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/09548ba8-4375-419c-a50c-b40ef5d9bfe9n%40googlegroups.com.

Re: [sage-devel] Re: is it intentional that prod does not stop when it hits 0?

['Martin R' via sage-devel]

@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
On Friday, 23 September 2022 at 10:28:57 UTC+2 john.c...@gmail.com wrote:

> 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
>  wrote:
> >
> > 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
> >
> > --
> > 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
> .
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/de9719f7-1bbb-427a-8ab0-a8e12a5ea234n%40googlegroups.com.

Re: [sage-devel] Re: is it intentional that prod does not stop when it hits 0?

[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
 wrote:
>
> 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
>
> --
> 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+unsubscr...@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.

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/CAD0p0K7%2BD8td1pxGLy08C8R5Q0sr1PJ1ZoK%3DtiTkB41gBo_CTw%40mail.gmail.com.

Re: [sage-devel] Re: is it intentional that prod does not stop when it hits 0?

[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

-- 
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+unsubscr...@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.

Re: [sage-devel] Re: is it intentional that prod does not stop when it hits 0?

['Martin R' via sage-devel]

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
On Friday, 23 September 2022 at 00:06:19 UTC+2 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
> 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...
>
> On Thu, Sep 22, 2022 at 2:54 PM kcrisman  wrote:
> >
> > 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??".
> >
> > On Thursday, September 22, 2022 at 10:39:03 AM UTC-4 axio...@yahoo.de 
> wrote:
> >>
> >> 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
> >
> > --
> > 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)
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/1cb8c213-59ef-4557-ae55-12314411c1c7n%40googlegroups.com.

Re: [sage-devel] Re: is it intentional that prod does not stop when it hits 0?

[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...

On Thu, Sep 22, 2022 at 2:54 PM kcrisman  wrote:
>
> 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??".
>
> On Thursday, September 22, 2022 at 10:39:03 AM UTC-4 axio...@yahoo.de wrote:
>>
>> 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
>
> --
> 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+unsubscr...@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)

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/CACLE5GA6XoVHbu10Pdk3y9D-wOd4k7ppCC3Z0Sd__TCsYad%2B_A%40mail.gmail.com.

[sage-devel] Re: is it intentional that prod does not stop when it hits 0?

[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.

On Thursday, 22 September 2022 at 07:39:03 UTC-7 axio...@yahoo.de wrote:

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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/f37b28a3-2622-43d9-8904-d06d599de477n%40googlegroups.com.

[sage-devel] Re: is it intentional that prod does not stop when it hits 0?

[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??".

On Thursday, September 22, 2022 at 10:39:03 AM UTC-4 axio...@yahoo.de wrote:

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

-- 
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+unsubscr...@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.