#32033 closed defect (fixed)

lcm broken in corner cases on certain polynomial rings

Reported by: Alexander Galarraga Owned by:
Priority: major Milestone: sage-9.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:

Status badges

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

One fix would be to add a try except block to polynomial_element.pyx:

def lcm(self, other):
    try:
        f = self*other
        g = self.gcd(other)
        q = f//g
        return ~(q.leading_coefficient())*q
    except:
        return 0

comment:2 Changed 15 months ago by David Roe

Seems okay, but make sure to use except ZeroDivisionError: instead of except: (which should never be used since it catches KeyboardInterrupts).

comment:3 Changed 15 months ago by David Roe

Also note that there are special implementations elsewhere, such as sage.rings.polynomial.polynomial_integer_dense_flint.

comment:4 Changed 15 months ago by Alexander Galarraga

Branch: u/gh-EnderWannabe/lcm_fix

comment:5 in reply to:  3 Changed 15 months ago by Alexander Galarraga

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:

f3eb72d32033: added try except block
017b9da32033: added try catch blocks

comment:6 Changed 15 months ago by David Roe

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:7 Changed 15 months ago by David Roe

You should also point to this ticket using :trac:`32033`.

Last edited 15 months ago by Samuel Lelièvre (previous) (diff)

comment:8 Changed 15 months ago by git

Commit: 017b9da76bde540695857c8a6eeb5b102f1e9b621d3f01fc069960d1151316147095c967bf556d97

Branch pushed to git repo; I updated commit sha1. New commits:

43b7fcc32033: added tests
48334fd32033: fixed backticks
1d3f01f32033: fixed backticks

comment:9 Changed 15 months ago by Alexander Galarraga

Status: newneeds_review

comment:10 Changed 15 months ago by Dave Morris

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 in reply to:  10 Changed 15 months ago by Alexander Galarraga

Replying to gh-DaveWitteMorris:

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 git

Commit: 1d3f01fc069960d1151316147095c967bf556d9792b3d667573bc9f6575fb422938650b000d0fb4a

Branch pushed to git repo; I updated commit sha1. New commits:

92b3d6632033: fixed parent, fixed ZZ[] with NTL implementation

comment:13 Changed 15 months ago by Travis Scrimshaw

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 in reply to:  13 ; Changed 15 months ago by Alexander Galarraga

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 return 0 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 in reply to:  14 Changed 15 months ago by Travis Scrimshaw

Replying to gh-EnderWannabe:

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 return 0 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 try-except 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 Changed 15 months ago by David Roe

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 in reply to:  16 Changed 15 months ago by Alexander Galarraga

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 git

Commit: 92b3d667573bc9f6575fb422938650b000d0fb4a079b507b0e152a8403dfbdf8320a0c03548c328f

Branch pushed to git repo; I updated commit sha1. New commits:

079b50732033: switched to if statements

comment:19 Changed 15 months ago by Travis Scrimshaw

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

Authors: Alexander Galarraga

comment:21 Changed 15 months ago by Travis Scrimshaw

Status: needs_reviewpositive_review

LTGM. Thank you.

comment:22 Changed 15 months ago by Volker Braun

Branch: u/gh-EnderWannabe/lcm_fix079b507b0e152a8403dfbdf8320a0c03548c328f
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.