Opened 5 years ago

Closed 5 years ago

#17675 closed defect (fixed)

xgcd(2,2) hangs forever in ZZ['x']

Reported by: vdelecroix Owned by:
Priority: critical Milestone: sage-6.5
Component: algebra Keywords:
Cc: wbhart Merged in:
Authors: Vincent Delecroix Reviewers: Ralf Stephan
Report Upstream: Reported upstream. Developers deny it's a bug. Work issues:
Branch: cf9d62b (Commits) Commit: cf9d62b6b0961ece59ae1e3cfdff6becc8da5b57
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

On sage-6.5.beta6 we have

sage: R.<x> = ZZ['x']
sage: R(2).xgcd(R(2))   # be prepared to wait

It is a problem in our way to use the FLINT function fmpz_poly_xgcd. As Bill reported on this sage-devel thread it does not work for input which are constant polynomials (note that it is already a bit more general that what is indicated in FLINT documentation: the function assumes that f and g are primitive (have Gaussian content equal to 1). The result is undefined otherwise.)

See also this FLINT bug report.

Change History (13)

comment:1 Changed 5 years ago by vdelecroix

  • Cc wbhart added

comment:2 follow-up: Changed 5 years ago by rws

  • Report Upstream changed from N/A to Reported upstream. No feedback yet.

comment:3 in reply to: ↑ 2 Changed 5 years ago by vdelecroix

  • Description modified (diff)

Replying to rws:

Reported at https://github.com/wbhart/flint2/issues/112

Thanks Ralf! I was not enough familiar to FLINT (and it was late after the bug tracking) to write the sample program.

Vincent

comment:4 Changed 5 years ago by rws

  • Report Upstream changed from Reported upstream. No feedback yet. to Reported upstream. Developers deny it's a bug.

comment:5 Changed 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/17675
  • Commit set to d05ac70434cafd7986e5e01671e1982e7fc8ffdc
  • Status changed from new to needs_review

As reported by Bill on sage-devel the only trouble was for constant input. In the commit I just treat this case first in the function xgcd... needs review!

Vincent


New commits:

d05ac70trac #17675: fix xgcd of constant integer polynomials

comment:6 Changed 5 years ago by rws

Typos found: sucht that, trivial casess.

comment:7 Changed 5 years ago by git

  • Commit changed from d05ac70434cafd7986e5e01671e1982e7fc8ffdc to a439152b4971501edd7e856d8e2c62681c6c9d08

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

a439152trac #17675: doc typo

comment:8 Changed 5 years ago by git

  • Commit changed from a439152b4971501edd7e856d8e2c62681c6c9d08 to f0d7ca3a02d79b66820aad2289ba5d0809ec9c3e

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f0d7ca3trac #17675: doc typo

comment:9 Changed 5 years ago by vdelecroix

  • Description modified (diff)

comment:10 Changed 5 years ago by rws

  • Branch changed from u/vdelecroix/17675 to u/rws/17675

comment:11 Changed 5 years ago by rws

  • Authors set to Vincent Delecroix
  • Commit changed from f0d7ca3a02d79b66820aad2289ba5d0809ec9c3e to cf9d62b6b0961ece59ae1e3cfdff6becc8da5b57
  • Reviewers set to Ralf Stephan
  • Status changed from needs_review to positive_review

I fixed a typo. Looks fine now and passes make ptestlong. I dare to fill the author field with your name.


New commits:

cf9d62b17675: reviewer's patch: fix typo

comment:12 Changed 5 years ago by vdelecroix

Great! Thanks for the quick review.

Vincent

comment:13 Changed 5 years ago by vbraun

  • Branch changed from u/rws/17675 to cf9d62b6b0961ece59ae1e3cfdff6becc8da5b57
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.