gcd and xgcd over fields, PID and UFD #17671

videlec · 2015-01-25T19:31:54Z

As reported on sage-support, gcd and xgcd disagree on fraction fields

sage: gcd(6/1,2/1)
2
sage: xgcd(6/1,2/1)
(1, 1/6, 0)

In this ticket we:

Ensure that gcd and xgcd are compatible over quotient fields by implementing the xgcd in the appropriate place. In particular, with that branch we have

sage: xgcd(6/1,2/1)
(2, 0, 1)
sage: xgcd(5/2, 3/4)
(1/4, -1/2, 2)

We fix the xgcd for trivial cases in rings.polynomial.polynomial_element_generic.Polynomial_generic_field in order that gcd and xgcd agree for them.
We introduce a generic test _test_gcd_vs_xgcd in the category PrincipalIdealDomains to ensure the compatibility of gcd and xgcd.
Modify the previous behavior for real numbers

sage: gcd(2.0, 4.0)
2
sage: gcd(2.0, 4.0).parent()
Integer Ring

The only difference is that now, Sage returns floating point with the same parent

sage: gcd(2.0, 4.0)
2.00000000000000
sage: gcd(2.0, 4.0).parent()
Real Field with 53 bits of precision

And the same kind of behavior will also hold for lcm and xgcd.

Note:

There is a method xgcd implemented for univariate polynomial over ZZ. ~~This is not a proper name since it has nothing to do with gcd~~ This might not be the best name since the first term is not the gcd in general (see this sage-devel thread and #17674)

Depends on #17675

Component: basic arithmetic

Author: Vincent Delecroix

Branch/Commit: 2e0d79e

Reviewer: Bruno Grenet

Issue created by migration from https://trac.sagemath.org/ticket/17671

The text was updated successfully, but these errors were encountered:

videlec · 2015-01-25T20:21:22Z

comment:1

I am annoyed with the current implementation... it is written in the generic gcd of categories.fields that

For fields of characteristic zero (i.e., containing the
integers as a sub-ring), evaluation in the integer ring is
attempted. This is for backwards compatibility.::
    sage: gcd(6.0,8); gcd(6.0,8).parent()
    2
    Integer Ring

This is completely crazy! And moreover different from what is in gcd!!

videlec · 2015-01-25T22:18:31Z

Dependencies: #17673

videlec · 2015-01-25T23:43:15Z

Commit: d8a03d7

videlec · 2015-01-25T23:43:15Z

New commits:

`7d2009c`	`trac #17673: __module__/__name__ for coerce_binop`
`16d942d`	`trac #17671: compatibility of gcd and xgcd`
`d8a03d7`	`trac #17671: fix doctests`

videlec · 2015-01-25T23:43:15Z

Branch: u/vdelecroix/17671

bgrenet · 2015-01-26T13:40:31Z

comment:6

In src/sage/categories/quotient_fields.py, lines 262-270:

            except (AttributeError, NotImplementedError, TypeError, ValueError):
                zero = self.parent.zero()
                one  = self.parent.one()
                if self == zero:
                    return (other, zero, one)
                elif other == zero:
                    return (self, one, zero)
                else:
                    return (zero, zero, zero)

I would have returned one as soon as one of self and other is nonzero, and zero only when none is nonzero. The current code is not consistent (if I am not mistaken) with the implementation of gcd (lines 125-128).

videlec · 2015-01-26T13:45:58Z

comment:7

Replying to @bgrenet:

In src/sage/categories/quotient_fields.py, lines 262-270:
...
I would have returned one as soon as one of self and other is nonzero, and zero only when none is nonzero.

You are totally right! Thanks!

Vincent

sagetrac-git · 2015-01-26T15:11:00Z

Changed commit from d8a03d7 to 401193c

sagetrac-git · 2015-01-26T15:11:00Z

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

`f22ac97`	`trac #17671: (review) fix gcd/xgcd in QuotientFields`
`401193c`	`trac #17671: fix xgcd of polynomial_field_generic`

bgrenet · 2015-01-26T15:21:33Z

comment:9

In src/sage/rings/arith.py, lines 1901-1910, the introducing sentence should to my mind be: Here is an example of a xgcd for two polynomials over the integers, where the linear combination is not the gcd but the gcd multiplied by the resultant::.

    Here is an example of a xgcd for two polynomials over the integers, where the linear
    combination is not the gcd but the resultant::

        sage: R.<x> = ZZ[]
        sage: gcd(2*x*(x-1), x^2)
        x
        sage: xgcd(2*x*(x-1), x^2)
        (2*x, -1, 2)
        sage: (2*(x-1)).resultant(x)
        2

I do not understand exactly what you want to do with your function _test_gcd_vs_xgcd(): As discussed, it is not clear that the results should always be the same.
To answer your questions:
1. As I've said on sage-devel, I am clearly in favor of gcd(RR(6), RR(3)).parent() to return Real Field with 53 bits of precision rather than Integer Ring.
2. I would keep the name xgcd though, with a clear documentation.

New commits:

`f22ac97`	`trac #17671: (review) fix gcd/xgcd in QuotientFields`
`401193c`	`trac #17671: fix xgcd of polynomial_field_generic`

videlec · 2015-01-26T15:33:38Z

comment:10

Replying to @bgrenet:

In src/sage/rings/arith.py, lines 1901-1910, the introducing sentence should to my mind be:

right

I do not understand exactly what you want to do with your function _test_gcd_vs_xgcd(): As discussed, it is not clear that the results should always be the same.

The test is only for principal ideal domains. Up to now I encountered two cases where the convention are a bit special:

quotient fields: the gcd/xgcd is compatible with the ring (managed by the category)
polynomial over fields: the gcd/xgcd always return monic polynomials (managed by the methods in rings.polynomial.polynomial_element_generic)
If there is an example of a PID where gcd and xgcd must be different I would be happy to remove my test.

Vincent

sagetrac-git · 2015-01-26T15:35:10Z

Changed commit from 401193c to 1d84c4a

sagetrac-git · 2015-01-26T15:35:10Z

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

`1d84c4a`	`trac #17671: (review) clearer doc in rings.arith.xgcd`

bgrenet · 2015-01-26T15:51:13Z

comment:13

Replying to @videlec:

I do not understand exactly what you want to do with your function _test_gcd_vs_xgcd(): As discussed, it is not clear that the results should always be the same.

The test is only for principal ideal domains.

Oh, right! Then I agree with your test.

Everything you've committed so far looks good to me (and passes the tests). There are two things left:

The parent of gcd(3.0,6.0): This ticket seems the right one to change this.
The name of xgcd for polynomials over UFD: There does not seem to be a consensus yet, so I would be in favor of letting this question to a later ticket so that this ticket can get a positive review soon.

videlec · 2015-01-26T15:56:21Z

comment:14

Nope. There seems to be a regression with respect to timings (at least I do not understand what is happening). If I run the doctest on the file coercion_and_categories.rst in $SAGE_ROOT/src/doc/en/thematic_tutorials/ then I end up with an incredibly long TestSuite(P).run(). If I instead replace it with TestSuite(P).run(skip='_test_gcd_vs_xgcd') everything looks fine.

Moreover, in sage.rings.function_field.function_field.py, line 62, the test

TestSuite(M).run(skip = '_test_gcd_vs_xgcd')  # long time (52s on sage.math, 2012)

is much longer for me. And if I remove the skip then it is even longer!

This is a critical issue.

videlec · 2015-01-27T01:45:29Z

comment:15

I finally find out the problem in the tests:

in function_field.py the timings are similar to what is here in sage-6.5.beta6. This is bad but at least not because of me
in coercions_and_categories.rst the problem comes from xgcd over ZZ['x'] (see xgcd(2,2) hangs forever in ZZ['x'] #17675)

I will add a small commit to fix some doctests.

videlec · 2015-01-27T01:45:29Z

Changed dependencies from #17673 to #17673, #17675

sagetrac-git · 2015-01-27T01:50:09Z

Changed commit from 1d84c4a to af1f7c6

sagetrac-git · 2015-01-27T01:50:09Z

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

`1f84c01`	`trac #17671: revert changes in function_field.py`
`af1f7c6`	`trac #17671: fix doctest in coercion_and_categories.rst`

sagetrac-git · 2015-01-28T12:41:51Z

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

`cc32b2b`	`trac #17671: gcd(2.0, 6.0) is now 1.0`
`d05ac70`	`trac #17675: fix xgcd of constant integer polynomials`
`f0d7ca3`	`trac #17675: doc typo`
`cf9d62b`	`17675: reviewer's patch: fix typo`
`089b629`	`merge #17675`
`91222b2`	`trac #16761: force the parent of gcd/lcm/xgcd`
`3275f3d`	`trac #16761: fix typo in doc`

sagetrac-git · 2015-01-28T12:41:51Z

Changed commit from af1f7c6 to 3275f3d

sagetrac-git · 2015-01-28T12:43:25Z

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

`02462bb`	`trac #17671: force the parent of gcd/lcm/xgcd`
`c6db5f8`	`trac #17671: fix typo in doc`

sagetrac-git · 2015-01-28T12:43:25Z

Changed commit from 3275f3d to c6db5f8

videlec · 2015-01-28T12:48:33Z

comment:19

Salut Bruno,

Sorry I had a typo in the two last commit messages so I had to do a forced push.

Now everything looks all right. Note that before setting this one to positive review, we need to wait for the trivial #17673 to be in positive review (!hint!). Thanks to Ralf #17675 is already in positive review.

In the last commits:

I changed the behavior for real numbers as you and I wanted (nobody answered on the sage-devel thread).
I made one change to _test_gcd_vs_xgcd in order to check whether the parent of gcd is really what we expect and not an element of another ring.

Vincent

bgrenet · 2015-01-28T13:15:54Z

comment:21

Salut Vincent,

I looked at #17673, but I am unable to review it since it goes beyond my knowledge in Sage... Or at least it will take some time for me to understand it and then review.

Concerning the real number, I would have thought of an implementation acting as follows:

sage: gcd(2.0,6.0)
2.00000000000000

I do not know if this makes sense.

videlec · 2015-01-28T14:32:29Z

comment:22

Replying to @bgrenet:

Salut Vincent,

I looked at #17673, but I am unable to review it since it goes beyond my knowledge in Sage... Or at least it will take some time for me to understand it and then review.

Concerning the real number, I would have thought of an implementation acting as follows:
sage: gcd(2.0,6.0)
2.00000000000000

Why? Would you like it to be nice only over ZZ and not over QQ? And this is where it becomes impossible. Within Sage any floating point can be converted to QQ...

sage: QQ(1.1231938951)
155072989/138064309

So the only way I would agree with your proposition is to have also

sage: gcd(RR(5/2), RR(3/2)) == RR(gcd(5/2, 3/2))

which is currently False as well.

Anyway mixing algebraic functions (like gcd) with floating point number is often a bad idea. So at least the proposed implementation tells you that something is wrong.

Vincent

bgrenet · 2015-01-28T15:50:01Z

comment:23

Replying to @videlec:

Why? Would you like it to be nice only over ZZ and not over QQ? And this is where it becomes impossible.

First of all, your current solution is mathematically perfectly correct and I am quite fine with it. This said, let me expose the reasons of my suggestion.

With my suggestion, "integral floating point numbers" are treated differently than other floating point numbers. Reasons:

The gcd function coincide with the mathematical GCD function for integers only;
Every floating point number can be seen as a rational, while not every floating point number can be seen as an integer.

Also, RR and QQ are treated differently. Reasons:

For inputs in QQ, we know that they are rational numbers, so we deviate from the mathematical definition to give a more meaningful answer and the definition we use "lives" in QQ;
For inputs in RR that are "integral", we make an assumption (the floating point numbers we have at hand represent integers) and then use the standard mathematical definition;
For inputs in RR that are not "integral", not returning 1.0000000 requires to make an assumption AND to deviate from the mathematical definition: that is, we would need to "move" from RR to QQ and then to use a non-standard definition.

Finally, if a user asks for the GCD of two "integral floating point numbers", I have no difficulty to understand what s/he means (since the GCD of the integers they represent is a well-defined mathematical function). It is much more difficult to me to interpret the will of a user that asks for the GCD of two "rational floating point numbers", and this (also) justifies to treat differently the two situations.

Anyway mixing algebraic functions (like gcd) with floating point number is often a bad idea. So at least the proposed implementation tells you that something is wrong.

I agree with that.

videlec · 2015-01-28T16:05:35Z

comment:24

All right. Let us do it your way.

(actually mine would be to not define floating point as a field ;-)

sagetrac-git · 2015-01-28T16:21:23Z

Changed commit from c6db5f8 to 0f536c9

sagetrac-git · 2015-01-28T16:21:23Z

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

`db90fdd`	`trac #17671: (review) fix gcd/xgcd in QuotientFields`
`673bca9`	`trac #17671: fix xgcd of polynomial_field_generic`
`dd86cb7`	`trac #17671: (review) clearer doc in rings.arith.xgcd`
`5bc4805`	`trac #17671: revert changes in function_field.py`
`994196f`	`trac #17671: fix doctest in coercion_and_categories.rst`
`c073eb9`	`trac #17671: gcd(2.0, 6.0) is now 1.0`
`9714f6a`	`trac #17671: force the parent of gcd/lcm/xgcd`
`9bbb25c`	`trac #17671: fix typo in doc`
`5d9f8d2`	`trac #17671: merge #17675`
`0f536c9`	`trac #17671: fix float definition of gcd/lcm/xgcd`

videlec · 2015-01-28T16:22:37Z

Changed dependencies from #17673, #17675 to #17675

videlec · 2015-01-28T16:22:37Z

comment:26

I removed #17673 from the dependencies... I had to do a forced push to remove the commit coming from that branch.

Vincent

bgrenet · 2015-01-28T17:20:26Z

comment:27

It seems that I get the same problem you had in #17673, thus the tests in src/sage/rings/polynomial/polynomial_quotient_ring.py don't pass. From line 281, there is a test that looks like the following (I removed irrelevant parts):

sage: P.<x> = QQ[]
sage: Q = P.quotient(x^2+2)
sage: Q in Fields()
True
sage: Q.an_element().gcd._module_
'sage.categories.fields'

but the test doesn't pass, and I get AttributeError: 'sage.structure.element.NamedBinopMethod' object has no attribute '__module__' instead of 'sage.categories.fields'.

videlec · 2015-01-28T17:35:43Z

comment:28

Yep. I forgot to change that. And the modification of gcd/lcm for floating point also causes some trouble for the symbolic ring. A commit is comming.

Vincent

sagetrac-git · 2015-01-28T17:36:01Z

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

`2e0d79e`	`trac #17671: fix two doctests`

sagetrac-git · 2015-01-28T17:36:01Z

Changed commit from 0f536c9 to 2e0d79e

bgrenet · 2015-01-29T12:55:13Z

comment:31

All tests pass! LGTM.

bgrenet · 2015-01-29T12:55:13Z

Reviewer: Bruno Grenet

videlec · 2015-01-29T14:54:58Z

comment:32

Cool! Thanks for the review.

vbraun · 2015-01-29T22:41:52Z

Changed branch from u/vdelecroix/17671 to 2e0d79e

…ss the TestSuite       The output of `xgcd` does not match the `gcd` output, but this is required by sagemath#17671. We change the computation to make these match. We also fix another bug as it should also take non-Laurent polynomial inputs to `xgcd`. We also implement the `euclidean_domain()` method. ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation accordingly. ### ⌛ Dependencies    URL: sagemath#37778 Reported by: Travis Scrimshaw Reviewer(s): Enrique Manuel Artal Bartolo, Travis Scrimshaw

videlec added this to the sage-6.5 milestone Jan 25, 2015

videlec added c: basic arithmetic labels Jan 25, 2015

videlec added the s: needs review label Jan 25, 2015

This comment has been minimized.

Sign in to view

videlec changed the title ~~Implement gcd for fraction fields~~ Implement xgcd for fraction fields Jan 25, 2015

This comment has been minimized.

Sign in to view

videlec changed the title ~~Implement xgcd for fraction fields~~ gcd and xgcd over fields, PID and UFD Jan 26, 2015

This comment has been minimized.

Sign in to view

bgrenet added s: positive review and removed s: needs review labels Jan 29, 2015

vbraun removed the s: positive review label Jan 29, 2015

vbraun closed this as completed in 0792516 Jan 29, 2015

videlec mentioned this issue Dec 29, 2022

xgcd is badly named on non PID domains #17674

Open

This was referenced Apr 10, 2024

Make univariate Laurent polynomials over a field pass the TestSuite #37778

Merged

Laurent polynomials, Fitting ideals and characteristic varieties #36368

Merged

gcd and xgcd over fields, PID and UFD #17671

gcd and xgcd over fields, PID and UFD #17671

Comments

videlec commented Jan 25, 2015

videlec commented Jan 25, 2015

videlec commented Jan 25, 2015

videlec commented Jan 25, 2015

videlec commented Jan 25, 2015

videlec commented Jan 25, 2015

This comment has been minimized.

bgrenet commented Jan 26, 2015

videlec commented Jan 26, 2015

sagetrac-git mannequin commented Jan 26, 2015

sagetrac-git mannequin commented Jan 26, 2015

bgrenet commented Jan 26, 2015

videlec commented Jan 26, 2015

sagetrac-git mannequin commented Jan 26, 2015

sagetrac-git mannequin commented Jan 26, 2015

This comment has been minimized.

bgrenet commented Jan 26, 2015

videlec commented Jan 26, 2015

videlec commented Jan 27, 2015

videlec commented Jan 27, 2015

sagetrac-git mannequin commented Jan 27, 2015

sagetrac-git mannequin commented Jan 27, 2015

sagetrac-git mannequin commented Jan 28, 2015

sagetrac-git mannequin commented Jan 28, 2015

sagetrac-git mannequin commented Jan 28, 2015

sagetrac-git mannequin commented Jan 28, 2015

videlec commented Jan 28, 2015

This comment has been minimized.

bgrenet commented Jan 28, 2015

videlec commented Jan 28, 2015

bgrenet commented Jan 28, 2015

videlec commented Jan 28, 2015

sagetrac-git mannequin commented Jan 28, 2015

sagetrac-git mannequin commented Jan 28, 2015

videlec commented Jan 28, 2015

videlec commented Jan 28, 2015

bgrenet commented Jan 28, 2015

videlec commented Jan 28, 2015

sagetrac-git mannequin commented Jan 28, 2015

sagetrac-git mannequin commented Jan 28, 2015

This comment has been minimized.

bgrenet commented Jan 29, 2015

bgrenet commented Jan 29, 2015

videlec commented Jan 29, 2015

vbraun commented Jan 29, 2015