Opened 15 months ago
Closed 15 months ago
#32033 closed defect (fixed)
lcm broken in corner cases on certain polynomial rings
Reported by:  Alexander Galarraga  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  basic arithmetic  Keywords:  gsoc2021 
Cc:  Ben Hutz  Merged in:  
Authors:  Alexander Galarraga  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  079b507 (Commits, GitHub, GitLab)  Commit:  079b507b0e152a8403dfbdf8320a0c03548c328f 
Dependencies:  Stopgaps: 
Description
Currently, the following code fails, throwing a zero division error:
sage: K.<t> = GF(2)[] sage: lcm(K(0), K(0))
As does
sage: K.<t> = RR[] sage: lcm(K(0), K(0))
This ticket attempts to fix these errors.
Change History (22)
comment:1 Changed 15 months ago by
comment:2 Changed 15 months ago by
Seems okay, but make sure to use except ZeroDivisionError:
instead of except:
(which should never be used since it catches KeyboardInterrupts
).
comment:3 followup: 5 Changed 15 months ago by
Also note that there are special implementations elsewhere, such as sage.rings.polynomial.polynomial_integer_dense_flint
.
comment:4 Changed 15 months ago by
Branch:  → u/ghEnderWannabe/lcm_fix 

comment:5 Changed 15 months ago by
Commit:  → 017b9da76bde540695857c8a6eeb5b102f1e9b62 

Replying to roed:
Also note that there are special implementations elsewhere, such as
sage.rings.polynomial.polynomial_integer_dense_flint
.
Thanks, added a try except block there as well.
The fix doesn't seem to break anything  I ran all tests.
Should we add a test to test for the fix?
New commits:
f3eb72d  32033: added try except block

017b9da  32033: added try catch blocks

comment:6 Changed 15 months ago by
Yep, if you're fixing a bug you should always add a test to show that it has been fixed. In this case, just an lcm(R(0), R(0))
in each case will be sufficient.
comment:8 Changed 15 months ago by
Commit:  017b9da76bde540695857c8a6eeb5b102f1e9b62 → 1d3f01fc069960d1151316147095c967bf556d97 

comment:9 Changed 15 months ago by
Status:  new → needs_review 

comment:10 followup: 11 Changed 15 months ago by
I searched the sage source, and I think the other occurrences of this problem are:
def _lcm(self, other)
in src/sage/rings/polynomial/polynomial_element.pyx (line 4894)def lcm(self, ntl_ZZX other)
in /src/sage/libs/ntl/ntl_ZZX.pyx (line 680)def lcm(self, MPolynomial_libsingular g)
in src/sage/rings/polynomial/multi_polynomial_libsingular.pyx (line 4862)def lcm(self, right)
in src/sage/rings/polynomial/polynomial_integer_dense_ntl.pyx (line 595)
Can these all be fixed here, or do we need another ticket for some of them? (I think at least the first one should certainly be done here.)
comment:11 Changed 15 months ago by
Replying to ghDaveWitteMorris:
Can these all be fixed here, or do we need another ticket for some of them? (I think at least the first one should certainly be done here.)
The first one will definitely throw an error and we can fix that one here.
The one in ntl_ZZX also throws an error:
x1 = ntl.ZZX([0,0,0,0]) x1.lcm(x1)
But I am unsure how to fix it. If someone else would like to fix it here or create a ticket for it, that would be appreciated.
The multivariate polynomial works in some cases:
K.<t,z> = GF(3^4)[] lcm(K(0), K(0)) 0
But throws an error over CC for some reason:
K.<t,z> = CC[] lcm(K(0), K(0)) ValueError
Not sure what is going on there.
The last one throws an ArithmeticError?:
R.<x> = PolynomialRing(ZZ, implementation='NTL') R(0).lcm(R(0))
So I'll push a fix and test for that.
comment:12 Changed 15 months ago by
Commit:  1d3f01fc069960d1151316147095c967bf556d97 → 92b3d667573bc9f6575fb422938650b000d0fb4a 

Branch pushed to git repo; I updated commit sha1. New commits:
92b3d66  32033: fixed parent, fixed ZZ[] with NTL implementation

comment:13 followup: 14 Changed 15 months ago by
I feel like this is a very roundabout approach. If either one of the factors is 0
, which should be quick to check, then I would just return 0
immediately.
comment:14 followup: 15 Changed 15 months ago by
Replying to tscrim:
I feel like this is a very roundabout approach. If either one of the factors is
0
, which should be quick to check, then I would just return0
immediately.
The idea for a try except block is that lcm is almost never called on 0, so adding an if statement that runs in all cases would be slower overall. The try except block should be quicker in 99% of cases, but slower 1% when lcm is called on 0.
This is similar to the implementation for elements of QQ, where a calculation is attempted inside a try except block, and in the case where an error is thrown, they check to see if 0 or 1 should be returned.
comment:15 Changed 15 months ago by
Replying to ghEnderWannabe:
Replying to tscrim:
I feel like this is a very roundabout approach. If either one of the factors is
0
, which should be quick to check, then I would just return0
immediately.The idea for a try except block is that lcm is almost never called on 0, so adding an if statement that runs in all cases would be slower overall. The try except block should be quicker in 99% of cases, but slower 1% when lcm is called on 0.
The act of computing the lcm
should be significantly more than the is_zero()
check. So I feel any slowdown will be negligible and is not worth the extra code complexity. While it is not much, it does take a bit more time to parse and could accidentally catch some other error (especially the ArithmeticError
), making thing harder to debug.
This is similar to the implementation for elements of QQ, where a calculation is attempted inside a try except block, and in the case where an error is thrown, they check to see if 0 or 1 should be returned.
Actually, Rational._lcm
does a zero check first. Note, however, that the code in QuotientFields.ElementMethods.lcm
doesn't redirect there. That code works there because it redirects to the lcm
in ZZ
and does 0/1
. You can also look specifically that the tryexcept
block there does not catch an ArithmeticError
(or a ZeroDivisionError
).
From what I see, much of Sage does the zero check first rather than wrap via a try
except
block. At some point, we probably should deal with inconsistencies between the category level implementations and the stuff via subclasses of Element
. Yet, that is a separate ticket.
For the K.<t,z> = CC[]
case, you just don't have an lcm
method defined there. We probably should implement something for UFDs, which I believe has existence and uniqueness (up to a unit).
Now I am not strictly opposed to this way of fixing things, but I think these things should be weighed before committing to them. Perhaps someone else can comment on this?
comment:16 followup: 17 Changed 15 months ago by
I agree with Travis that an if
statement is better from a readability point of view, and that the speed difference will be negligible. I also don't feel strongly, so if the author of this ticket would prefer to use the try
block I think that getting this bug fixed is more important than the decision of which way to do it.
comment:17 Changed 15 months ago by
Replying to roed:
I agree with Travis that an
if
statement is better from a readability point of view, and that the speed difference will be negligible.
Makes sense to me, pushed a branch with an if statement instead of a try except block.
comment:18 Changed 15 months ago by
Commit:  92b3d667573bc9f6575fb422938650b000d0fb4a → 079b507b0e152a8403dfbdf8320a0c03548c328f 

Branch pushed to git repo; I updated commit sha1. New commits:
079b507  32033: switched to if statements

comment:19 Changed 15 months ago by
Reviewers:  → Travis Scrimshaw 

Thank you. Please add your name to the authors field and we will wait for the patchbot.
comment:20 Changed 15 months ago by
Authors:  → Alexander Galarraga 

comment:22 Changed 15 months ago by
Branch:  u/ghEnderWannabe/lcm_fix → 079b507b0e152a8403dfbdf8320a0c03548c328f 

Resolution:  → fixed 
Status:  positive_review → closed 
One fix would be to add a try except block to polynomial_element.pyx: