Opened 5 years ago

Closed 14 months ago

Last modified 10 months ago

#16268 closed defect (fixed)

Better normalization for fraction field elements

Reported by: cremona Owned by:
Priority: minor Milestone: sage-8.4
Component: algebra Keywords:
Cc: tscrim, cheuberg, etn40ff, jakobkroeker, bhutz, slelievre Merged in: sage-8.4.beta2
Authors: Robert Bradshaw, Erik Massop, Marc Mezzarobba Reviewers: Julian Rüth
Report Upstream: N/A Work issues:
Branch: af91bf5 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by slelievre)

Normalize the leading coefficient of the denominator to one when reducing elements of fraction fields of univariate polynomial rings over fields. Doing so

  • often leads to more readable results,
  • helps limiting coefficient blow-up during computations with fractions over complicated base fields (e.g., elements of ℚ(x,y)(t)), typically leading to much better performance,
  • makes hashing more (though not 100%) reliable, see the original description and the comments below.

The following further desirable improvements, out of the scope of this ticket, are dealt with at #26339:

  • clearing denominators in the numerator and denominator instead of making the leading coefficient of the denominator monic when that makes sense (i.e., for printing, and perhaps for computations in nested rational function fields, but making it fast enough requires some work),
  • also normalizing the leading coefficients over non-fields where that makes sense (see also discussion at #16993).

Original description:

If K is a field then K(u), the function field, has a reduce() method which cancels the gcd but does not put into a canonical form by (for example) dividing through by the leading coefficient of the denominator to make the denominator monic. This means that equal elements may have different hashes, and hence that putting function field elements into a set does not work as a mathematician would expect. For example:

sage: Ku.<u> = FractionField(PolynomialRing(QQ,'u'))
sage: a = 27*u^2+81*u+243
sage: b = 27*u-81
sage: c = u^2 + 3*u + 9
sage: d = u-3
sage: s = a/b
sage: t = c/d
sage: s==t
True
sage: len(Set([s,t]))
2

Change History (68)

comment:1 Changed 5 years ago by emassop

The normalization would already be much better if PolynomialRing(QQ, 'u') had a 'better' gcd, like the one implemented for QQ in #10771, which would yield gcd(27*u^2+81*u+243, 27*u-81)==27. However the gcd from flint in src/sage/rings/polynomial/polynomial_rational_flint.pyx is monic.

Ku could also figure out that it is also FractionField(PolynomialRing(ZZ, 'u')), which has a better reduce.

comment:2 Changed 5 years ago by robertwb

  • Branch set to u/robertwb/ticket/16268
  • Created changed from 04/29/14 15:00:38 to 04/29/14 15:00:38
  • Modified changed from 04/29/14 16:29:25 to 04/29/14 16:29:25

comment:3 Changed 5 years ago by git

  • Commit set to 289d3aa124bd5a03349f14f0520e4b8d2845dd84

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

289d3aaFix hash for unreduced fraction field elements.

comment:4 Changed 5 years ago by git

  • Commit changed from 289d3aa124bd5a03349f14f0520e4b8d2845dd84 to f7266ca383db2783ba0d485ac5c9ab5da6c6d614

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

f7266caFix hash for unreduced fraction field elements.

comment:5 follow-up: Changed 5 years ago by cremona

Thanks, Robert, I will review this. I had already started by patching the reduce function but had not yet discoivered where the automatic calling of reduction was actually happening. Your solution -- keeping reduce() and normalise() separate -- looks better.

comment:6 Changed 5 years ago by robertwb

  • Authors set to Robert Bradshaw
  • Status changed from new to needs_review

comment:7 Changed 5 years ago by emassop

As of yet the documentation at normalize is incorrect. It reads "Returns a normalized representation of self". However it does not return anything.

Also, shouldn't normalize in FractionFieldElement throw a not-implemented-exception or so? Or at least have a warning in its documentation that it might not actually normalize? For instance in FractionField(PolynomialRing(QQ, 'x,y')), calling reduce is still insufficient to do the normalization.

comment:8 Changed 5 years ago by emassop

  • Branch changed from u/robertwb/ticket/16268 to u/emassop/ticket/16268

comment:9 Changed 5 years ago by cremona

  • Commit changed from f7266ca383db2783ba0d485ac5c9ab5da6c6d614 to cdf116327b93b5d29282c98d40042440d068ce44

What is happening here? There are/were two commits by Robert Bradshaw but suddenly the branch name has changed to an emassop name. I assume that this means the emassop is doing something, so I will hold back.


New commits:

cdf1163Fix documentation of normalize

comment:10 Changed 5 years ago by emassop

I changed the documentation to not say "return". Then did git trac push, but apparently something went wrong, since it only changed the branch name without picking up on the new commithash (and hence the summary of my commit). I was hoping trac-user "git" would pick it up with some delay, but apparently not.

I'm not going to change more, as I'm unfamiliar with the conventions about what normalize in FractionFieldElement should do when its not actually guaranteeing that numerator and denominator are the same for a == b after calling normalize on both.

comment:11 Changed 5 years ago by git

  • Commit changed from cdf116327b93b5d29282c98d40042440d068ce44 to a4221ed3e1d16d38b271316b01b91344fb195746

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

9387fe2Fix doctest
a4221edMore careful hashing of FractionFieldElement

comment:12 Changed 5 years ago by emassop

I couldn't help myself and hacked a bit on this.

  • Removed normalize from generic FractionFieldElement, as I don't think it can live up to the behaviour in its documentation. For instance (2x)/(2x+1) and (-2x)/(-2x-1) in Q(ZZ[x]) did not have the same normalisation. I doubt this can be fixed for general rings.
  • Removed call to reduce for non-exact rings, as reduces' documentation says "Automatically called for exact rings, but because it may be numerically unstable for inexact rings it must be called manually in that case."
  • Raise NotImplementedError in generic FractionFieldElement.__hash__ except when the denominator is 1. In this exceptional case the hash necessarily agrees with the hash of the corresponding element of the integral domain and therefore can be computed without any trouble.

I (re)implemented hashing for elements of Q(R[X]) with R an integral domain, by passing from Q(R[X]) to Q(Q(R)[X]), reducing to the case of this bug. I haven't pushed this, as I don't like the architecture in my patch and that should probably be a separate bug anyway. There should probably be separate bug reports for many kinds of rings.

comment:13 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 5 years ago by rws

  • Status changed from needs_review to needs_work

patchbot:

sage -t --long src/sage/tests/book_schilling_zabrocki_kschur_primer.py  # 28 doctests failed
sage -t --long src/sage/combinat/sf/macdonald.py  # 8 doctests failed
sage -t --long src/sage/algebras/iwahori_hecke_algebra.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/sfa.py  # 8 doctests failed
sage -t --long src/sage/combinat/k_tableau.py  # 2 doctests failed
sage -t --long src/sage/schemes/projective/projective_morphism.py  # 1 doctest failed
sage -t --long src/sage/matrix/matrix2.pyx  # 6 doctests failed
sage -t --long src/sage/combinat/sf/k_dual.py  # 52 doctests failed
sage -t --long src/sage/rings/function_field/function_field.py  # 32 doctests failed
sage -t --long src/sage/combinat/sf/llt.py  # 49 doctests failed
sage -t --long src/sage/schemes/elliptic_curves/ell_point.py  # 8 doctests failed
sage -t --long src/sage/combinat/sf/new_kschur.py  # 10 doctests failed
sage -t --long src/sage/combinat/sf/jack.py  # 72 doctests failed
sage -t --long src/sage/rings/polynomial/multi_polynomial_ideal.py  # Killed due to terminate
sage -t --long src/sage/combinat/sf/sf.py  # 15 doctests failed
sage -t --long src/sage/combinat/sf/hall_littlewood.py  # 39 doctests failed
sage -t --long src/sage/modules/free_module_element.pyx  # 4 doctests failed
sage -t --long src/sage/modules/free_module.py  # 2 doctests failed
sage -t --long src/sage/combinat/cluster_algebra_quiver/cluster_seed.py  # 32 doctests failed
sage -t --long src/sage/schemes/toric/ideal.py  # 1 doctest failed
sage -t --long src/sage/categories/pushout.py  # 2 doctests failed
sage -t --long src/sage/categories/quotient_fields.py  # 3 doctests failed
sage -t --long src/sage/matrix/strassen.pyx  # 2 doctests failed
sage -t --long src/sage/calculus/wester.py  # 1 doctest failed
sage -t --long src/sage/algebras/quatalg/quaternion_algebra_element.pyx  # 6 doctests failed
sage -t --long src/sage/schemes/plane_conics/con_field.py  # 5 doctests failed
sage -t --long src/sage/combinat/free_module.py  # 2 doctests failed
sage -t --long src/sage/combinat/species/recursive_species.py  # 1 doctest failed
sage -t --long src/sage/rings/function_field/function_field_ideal.py  # 18 doctests failed
sage -t --long src/sage/combinat/sf/dual.py  # 4 doctests failed
sage -t --long src/sage/rings/function_field/function_field_order.py  # 6 doctests failed
sage -t --long src/sage/combinat/species/product_species.py  # 1 doctest failed
sage -t --long src/sage/combinat/species/species.py  # 2 doctests failed
sage -t --long src/sage/modules/matrix_morphism.py  # 1 doctest failed
sage -t --long src/sage/rings/function_field/function_field_element.pyx  # 10 doctests failed
sage -t --long src/sage/modules/free_quadratic_module.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/polynomial_element_generic.py  # 1 doctest failed
sage -t --long src/sage/rings/fraction_field_element.pyx  # 3 doctests failed
sage -t --long src/sage/matrix/tests.py  # 2 doctests failed
sage -t --long src/sage/categories/function_fields.py  # 1 doctest failed
sage -t --long src/sage/combinat/species/sum_species.py  # 1 doctest failed
sage -t --long src/sage/rings/function_field/constructor.py  # 2 doctests failed

comment:15 Changed 5 years ago by emassop

#15297 is related

comment:16 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:17 Changed 5 years ago by emassop

#16993 is related.

comment:18 Changed 5 years ago by emassop

Also, I sadly don't currently have time to work on this. In fact, I don't think I'll have time until spring.

comment:19 Changed 5 years ago by tscrim

  • Cc tscrim added

comment:20 Changed 5 years ago by cheuberg

  • Cc cheuberg added

comment:21 Changed 4 years ago by etn40ff

  • Cc etn40ff added

comment:22 Changed 3 years ago by jakobkroeker

  • Cc jakobkroeker added

ping

comment:23 in reply to: ↑ 5 Changed 18 months ago by mmezzarobba

  • Authors changed from Robert Bradshaw to Robert Bradshaw, Erik Massop, Marc Mezzarobba
  • Branch changed from u/emassop/ticket/16268 to u/mmezzarobba/16268-normalize_fractions
  • Commit changed from a4221ed3e1d16d38b271316b01b91344fb195746 to 2d96533bde07fbbbce3a490dd786bbf7a9ffae53
  • Status changed from needs_work to needs_review

Replying to cremona:

Thanks, Robert, I will review this. I had already started by patching the reduce function but had not yet discoivered where the automatic calling of reduction was actually happening. Your solution -- keeping reduce() and normalise() separate -- looks better.

IMO having reduce() normalize the leading coefficient is actually a better choice, because it helps limiting coefficient blow-up in computations with rational functions.

Here is another attempt that does that. See the commit messages for more information. (Addendum: this fixes #16993. Fixing #15297 in full generality requires more work, but could be done as a follow-up.)


New commits:

3d96f14Fix hash for unreduced fraction field elements.
fb8a382Fix documentation of normalize
2f7a320Fix doctest
198c059More careful hashing of FractionFieldElement
3e4fc0cslightly simplify/robustify FractionFieldElement.reduce()
b418d40FractionFieldElement: merge reduce() and normalize()
c45d34fTweak fraction field element hashing
aa73340Small optimization in FracFieldElt richcmp()
e3a2da4#16268 boring doctest updates
2d96533#16268 other doctest updates
Last edited 18 months ago by mmezzarobba (previous) (diff)

comment:24 Changed 18 months ago by git

  • Commit changed from 2d96533bde07fbbbce3a490dd786bbf7a9ffae53 to 0830684d5a260960d215d52ed42ef932fa987e9e

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

0830684#16268 other doctest updates

comment:25 Changed 18 months ago by git

  • Commit changed from 0830684d5a260960d215d52ed42ef932fa987e9e to b504f8e593367ae9c955b515965930d750674044

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

39b7ad3FractionFieldElement: merge reduce() and normalize()
efd5979Tweak fraction field element hashing
1db6427Small optimization in FracFieldElt richcmp()
7adce21#16268 boring doctest updates
b504f8e#16268 other doctest updates

comment:26 follow-up: Changed 18 months ago by git

  • Commit changed from b504f8e593367ae9c955b515965930d750674044 to fb113639b4c3e4ff7de67a8f8edcd67ffb3141c5

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

77dc9e1FractionFieldElement: merge reduce() and normalize()
a25ab99Tweak fraction field element hashing
0f310bcSmall optimization in FracFieldElt richcmp()
00104f5#16268 boring doctest updates
fb11363#16268 other doctest updates

comment:27 in reply to: ↑ 26 Changed 18 months ago by mmezzarobba

Replying to git:

77dc9e1FractionFieldElement: merge reduce() and normalize()

Replaced a nbsp by a plain ascii space; all tests passed before.

comment:28 follow-up: Changed 18 months ago by git

  • Commit changed from fb113639b4c3e4ff7de67a8f8edcd67ffb3141c5 to 3cf5014d43785fd384204981ead86702a3ea1662

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

daec622#16268 boring doctest updates
3cf5014#16268 other doctest updates

comment:29 in reply to: ↑ 28 Changed 18 months ago by mmezzarobba

Replying to git:

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

daec622#16268 boring doctest updates
3cf5014#16268 other doctest updates

Updated an optional test.

comment:30 Changed 18 months ago by git

  • Commit changed from 3cf5014d43785fd384204981ead86702a3ea1662 to b031e3e49c50a31dbe298b58f4178fd5f96d08b2

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

259843aFix hash for unreduced fraction field elements.
3197980Fix documentation of normalize
ff7be78Fix doctest
9edad32More careful hashing of FractionFieldElement
6a2fbd7slightly simplify/robustify FractionFieldElement.reduce()
c16d55aFractionFieldElement: merge reduce() and normalize()
7c8a45aTweak fraction field element hashing
5a78e11Small optimization in FracFieldElt richcmp()
0f17da0#16268 boring doctest updates
b031e3e#16268 other doctest updates

comment:31 Changed 18 months ago by git

  • Commit changed from b031e3e49c50a31dbe298b58f4178fd5f96d08b2 to 8cff798aace0fe8d69b6fcdc3bf2054b6f71fcd0

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

c1f928f#16268 boring doctest updates
8cff798#16268 other doctest updates

comment:32 Changed 18 months ago by mmezzarobba

  • Status changed from needs_review to needs_work

comment:33 Changed 18 months ago by git

  • Commit changed from 8cff798aace0fe8d69b6fcdc3bf2054b6f71fcd0 to 544a8dfb4bf1e385592d444062867ce2f4987232

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

544a8dffix normalization of leading coefficients

comment:34 Changed 18 months ago by git

  • Commit changed from 544a8dfb4bf1e385592d444062867ce2f4987232 to 75ddc0dee1104e6970d02352ea2aafc3262c0f49

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

75ddc0dfix normalization of leading coefficients

comment:35 Changed 18 months ago by mmezzarobba

  • Status changed from needs_work to needs_review

comment:36 Changed 18 months ago by mmezzarobba

  • Cc bhutz added

The only nontrivial doctest update in the last commit should be the one in endPN_automorphism_group.three_stable_points(); I think it is correct, but it would be nice if someone who actually understands what it is about could double-check.

comment:37 Changed 18 months ago by bhutz

Yes, the doc test change in three_stable_points is fine.

comment:38 follow-up: Changed 18 months ago by emassop

In c16d55a247b21d6c46d00f603ca21d7d6d64db19, "EXAMPLES::" became "EXAMPLES:". IIRC double colons are needed to use the examples in a doctest, or at least for formatting of the documentation (per https://devguide.python.org/documenting/#source-code). Please put the double colons back.

In 7c8a45abecdf5224c9f0a324447ba69db22057b5 hashes are computed for inexact rings without reduction. This means that python-equal fraction field elements can have distinct hashes, violating the preconditions of hashing in python. I would prefer to err on the side of caution and raise an exception rather than introducing a pathway for bugs that will be hard to find. If you decide to go the other way, please consider removing 198c0596630bb4ecc200e62c55715441e6f38d5c from the history as its intended effect is completely undone.

comment:39 Changed 18 months ago by vdelecroix

  • Milestone changed from sage-6.4 to sage-8.3

comment:40 in reply to: ↑ 38 Changed 17 months ago by mmezzarobba

Thanks for your comments!

Replying to emassop:

In c16d55a247b21d6c46d00f603ca21d7d6d64db19, "EXAMPLES::" became "EXAMPLES:". IIRC double colons are needed to use the examples in a doctest, or at least for formatting of the documentation (per https://devguide.python.org/documenting/#source-code). Please put the double colons back.

They are still there, after the introductory sentence instead of the "EXAMPLES:" heading.

In 7c8a45abecdf5224c9f0a324447ba69db22057b5 hashes are computed for inexact rings without reduction. This means that python-equal fraction field elements can have distinct hashes, violating the preconditions of hashing in python. I would prefer to err on the side of caution and raise an exception rather than introducing a pathway for bugs that will be hard to find. If you decide to go the other way, please consider removing 198c0596630bb4ecc200e62c55715441e6f38d5c from the history as its intended effect is completely undone.

I don't like that either. But over an inexact ring, the precondition of hashing would be violated anyway, because of the round-off errors during the computation of the reduction and the equality test. So what I'm suggesting in order to move forward is to keep the broken hash in this case, to be closer to bug-for-bug compatibility with the historic implementation...

This issue with equality appears almost everywhere in Sage, and unfortunately, I think we have to live with it. The only real fix IMO would be to drop the use of == for mathematical equality, define it to mean “syntactic” equality of the data structures (after normalization when relevant) instead, and introduce a separate method for mathematical equality. But that's not going to happen without a Sage fork at least, I guess...

comment:41 follow-up: Changed 17 months ago by emassop

Regarding EXAMPLES: Ah, I didn't notice that. Sorry.

Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bug-for-bug, but the user is at least made aware that something may be going wrong. I can't recall if there was a policy for or against this.

I am aware that in general sage does not guarantee "x == y implies hash(x) == hash(y)", but if I recall correctly, it did strive to uphold this implication when x and y have the same parent.

A point on API: Although I can believe that always making the denominator monic is a good thing, merging normalize into reduce means that there no longer is a method that guarantees a normal form. Instead reduce now maybe normalizes the numerator and denominator or maybe not, depending on the implementation. Would it perhaps make sense to have a bool _normalized (instead of or in addition to _reduced) that gets set when reduce has succeeded at normalization? This doesn't have to be done as part of this bug though.

comment:42 in reply to: ↑ 41 ; follow-up: Changed 17 months ago by mmezzarobba

Replying to emassop:

Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bug-for-bug, but the user is at least made aware that something may be going wrong. I can't recall if there was a policy for or against this.

I'll try that and look again at the test failures to see what makes sense.

I am aware that in general sage does not guarantee "x == y implies hash(x) == hash(y)", but if I recall correctly, it did strive to uphold this implication when x and y have the same parent.

Yes. But even that is not always possible, unfortunately.

A point on API: Although I can believe that always making the denominator monic is a good thing, merging normalize into reduce means that there no longer is a method that guarantees a normal form. Instead reduce now maybe normalizes the numerator and denominator or maybe not, depending on the implementation.

Depending whether we are working with univariate rational function over a field or not, actually, isn't it?

Would it perhaps make sense to have a bool _normalized (instead of or in addition to _reduced) that gets set when reduce has succeeded at normalization? This doesn't have to be done as part of this bug though.

I'm not sure. This is also related to the issue of provinding a normal form for more general fraction field elements (starting with rational functions over non-fields, I guess), and hence I agree that this would best be kept for another ticket.

comment:43 in reply to: ↑ 42 ; follow-up: Changed 17 months ago by emassop

Replying to mmezzarobba:

Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bug-for-bug, but the user is at least made aware that something may be going wrong. I can't recall if there was a policy for or against this.

I'll try that and look again at the test failures to see what makes sense.

Thanks, I'll wait for the result.

A point on API: Although I can believe that always making the denominator monic is a good thing, merging normalize into reduce means that there no longer is a method that guarantees a normal form. Instead reduce now maybe normalizes the numerator and denominator or maybe not, depending on the implementation.

Depending whether we are working with univariate rational function over a field or not, actually, isn't it?

Would it perhaps make sense to have a bool _normalized (instead of or in addition to _reduced) that gets set when reduce has succeeded at normalization? This doesn't have to be done as part of this bug though.

I'm not sure. This is also related to the issue of providing a normal form for more general fraction field elements (starting with rational functions over non-fields, I guess), and hence I agree that this would best be kept for another ticket.

With the current implementation "is this a univariate rational function over a field" is the criterion, yes. The point is that the criterion changes when the implementation changes, and no one will know except by looking at the code for their specific kind of base ring.

(For instance the present normalization easily generalizes to the multivariate case by looking at the leading coefficient for some monomial order.)

I was hoping for a convincing argument on why making reduce more powerful is better than keeping normalize around, as my initial preference would be towards normalize because I generally prefer explicit over implicit.

comment:44 in reply to: ↑ 43 Changed 17 months ago by mmezzarobba

Replying to emassop:

I'll try that and look again at the test failures to see what makes sense.

Thanks, I'll wait for the result.

Ok, the only failures I'm seeing are in src/sage/modular/modform_hecketriangle/ and apparently come from the fact that FormsRingElement inherits from UniqueRepresentation but is sometimes called on fractions with floating-point coefficients. I guess it would be possible to port it to UniqueFactory and somehow preprocess the arguments to avoid the warning.

However, I wonder if it wouldn't be better to keep __hash__() as it is now, and have == over inexact rings return True only when the fractions are equal without reduction. Then, hashing would be consistent with equality, the (arguably valid) use case of indexing a table by inexact fractions would work without warning, and hashing wouldn't break the promise that fractions over inexact ring are not automatically reduced. For ==, this would consistent with the semantics of equality in “difficult” cases like interval arithmetic and symbolic expressions, where a == b may return False in cases where a and b are actually equal but that could not be verified. (Not for !=, though, but I don't see what we could do about that.)

What do you think?

With the current implementation "is this a univariate rational function over a field" is the criterion, yes. The point is that the criterion changes when the implementation changes, and no one will know except by looking at the code for their specific kind of base ring.

(For instance the present normalization easily generalizes to the multivariate case by looking at the leading coefficient for some monomial order.)

I was hoping for a convincing argument on why making reduce more powerful is better than keeping normalize around, as my initial preference would be towards normalize because I generally prefer explicit over implicit.

Essentially, I agree with you. I'm just saying that I'd rather keep that question for later, and address it once we have a way of normalizing in more general situations, probably along the lines of what you suggested at #16993.

comment:45 Changed 17 months ago by mmezzarobba

FWIW, all tests pass with

  • src/sage/modular/modform_hecketriangle/graded_ring_element.py

    }}}diff --git a/src/sage/modular/modform_hecketriangle/graded_ring_element.py b/src/sage/modular/modform_hecketriangle/graded_ring_element.py
    index be3b1e614b..5b41348c07 100644
    a b class FormsRingElement(six.with_metaclass( 
    156156            sage: MeromorphicModularFormsRing()(-1/x) == MeromorphicModularFormsRing()(1/(-x))
    157157            True
    158158            sage: MeromorphicModularFormsRing(base_ring=CC)(-1/x) == MeromorphicModularFormsRing()(1/(-x))
    159             True
     159            False
    160160        """
    161161        if op not in [op_EQ, op_NE]:
    162162            return NotImplemented
  • src/sage/rings/fraction_field_element.pyx

    diff --git a/src/sage/rings/fraction_field_element.pyx b/src/sage/rings/fraction_field_element.pyx
    index 3013a7b3af..3b221ddf4b 100644
    a b cdef class FractionFieldElement(FieldElement): 
    894894            True
    895895        """
    896896        cdef FractionFieldElement other = other_
    897         if ((op == Py_EQ or op == Py_NE)
    898                 and self.__denominator == other.__denominator):
    899             return richcmp(self.__numerator, other.__numerator, op)
    900         else:
    901             return richcmp(
    902                     self.__numerator * other.__denominator,
    903                     self.__denominator * other.__numerator,
    904                     op)
     897        if (op == Py_EQ or op == Py_NE):
     898            if self.__denominator == other.__denominator:
     899                return richcmp(self.__numerator, other.__numerator, op)
     900            elif not self._parent.is_exact():
     901                # over inexact rings, compare unreduced representations
     902                return op == Py_NE
     903        return richcmp(
     904                self.__numerator * other.__denominator,
     905                self.__denominator * other.__numerator,
     906                op)
    905907
    906908    def valuation(self, v=None):
    907909        """
    cdef class FractionFieldElement_1poly_field(FractionFieldElement): 
    11501152        if op == Py_EQ or op == Py_NE:
    11511153            if self.__denominator == other.__denominator:
    11521154                return richcmp(self.__numerator, other.__numerator, op)
    1153             elif self._is_reduced and other._is_reduced:
     1155            elif (self._is_reduced and other._is_reduced
     1156                    or not self._parent.is_exact()):
    11541157                return op == Py_NE
    11551158        return richcmp(
    11561159                self.__numerator * other.__denominator,

comment:46 Changed 17 months ago by git

  • Commit changed from 75ddc0dee1104e6970d02352ea2aafc3262c0f49 to 86b3b56b2bfd64a57f3a82dd022f5bd70b11b622

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

56b9292Fix hash for unreduced fraction field elements.
7b1017dFix documentation of normalize
98b1301Fix doctest
7281516More careful hashing of FractionFieldElement
862604cslightly simplify/robustify FractionFieldElement.reduce()
7f3c093FractionFieldElement: merge reduce() and normalize()
b273531Tweak fraction field element hashing
a21cb63#16268 boring doctest updates
80c421d#16268 other doctest updates
86b3b56fix normalization of leading coefficients

comment:47 Changed 17 months ago by mmezzarobba

Rebased on the last beta due to a minor conflict.

comment:48 follow-up: Changed 17 months ago by git

  • Commit changed from 86b3b56b2bfd64a57f3a82dd022f5bd70b11b622 to 3a3d32fb60b4c5177c7ce0824076d78aeb90184c

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

3ff950cFix hash for unreduced fraction field elements.
2bdd265Fix documentation of normalize
bef8c4fFix doctest
305c98fMore careful hashing of FractionFieldElement
d524b75slightly simplify/robustify FractionFieldElement.reduce()
9a9d4deFractionFieldElement: merge reduce() and normalize()
59c558cTweak fraction field element hashing
afc6a05#16268 boring doctest updates
7dfe3c3#16268 other doctest updates
3a3d32ffix normalization of leading coefficients

comment:49 in reply to: ↑ 48 Changed 17 months ago by mmezzarobba

Replying to git:

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

Rebased and fixed minor test failure.

comment:50 Changed 17 months ago by git

  • Commit changed from 3a3d32fb60b4c5177c7ce0824076d78aeb90184c to 5d4a6890e27f84afb6aa8d713117dfcb0c5a702b

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

40e22a0Fix documentation of normalize
fc57a23Fix doctest
21375eaMore careful hashing of FractionFieldElement
03d91abslightly simplify/robustify FractionFieldElement.reduce()
610e585FractionFieldElement: merge reduce() and normalize()
8aa61d5Tweak fraction field element hashing
e01d960#16268 boring doctest updates
1bd6279#16268 other doctest updates
1f6b0b6fix normalization of leading coefficients
5d4a689additional doctest update after #25440

comment:51 Changed 17 months ago by mmezzarobba

Rebased on 8.3.beta5 to add a minor doctest update.

comment:52 follow-up: Changed 17 months ago by saraedum

This seems wrong:

-            ((1 + O(2)))/((1 + O(2^5))*x)
+            ((1 + O(2)))/((1 + O(2))*x)

But let's discuss this at #25318.

comment:53 in reply to: ↑ 52 ; follow-up: Changed 17 months ago by mmezzarobba

Replying to saraedum:

This seems wrong:

-            ((1 + O(2)))/((1 + O(2^5))*x)
+            ((1 + O(2)))/((1 + O(2))*x)

But let's discuss this at #25318.

Why? Isn't it the same result, just written in a different way?

comment:54 in reply to: ↑ 53 Changed 17 months ago by saraedum

Oops, sorry. I guess you're right.

Replying to mmezzarobba:

Replying to saraedum:

This seems wrong:

-            ((1 + O(2)))/((1 + O(2^5))*x)
+            ((1 + O(2)))/((1 + O(2))*x)

But let's discuss this at #25318.

Why? Isn't it the same result, just written in a different way?

comment:55 Changed 16 months ago by git

  • Commit changed from 5d4a6890e27f84afb6aa8d713117dfcb0c5a702b to dcd92b72b863663c4306018735c8df9bd0213d73

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

a1cd059Fix documentation of normalize
9d108ccFix doctest
47cf425More careful hashing of FractionFieldElement
1d8546fslightly simplify/robustify FractionFieldElement.reduce()
f220ba1FractionFieldElement: merge reduce() and normalize()
d57e934Tweak fraction field element hashing
db40831#16268 boring doctest updates
2955aa9#16268 other doctest updates
069cca8fix normalization of leading coefficients
dcd92b7additional doctest update after #25440

comment:56 Changed 16 months ago by git

  • Commit changed from dcd92b72b863663c4306018735c8df9bd0213d73 to db762fc4082cf6af913a7637b895f970a7492a74

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

2850652Fix documentation of normalize
26c87d3Fix doctest
78b5990More careful hashing of FractionFieldElement
e768973slightly simplify/robustify FractionFieldElement.reduce()
029346fFractionFieldElement: merge reduce() and normalize()
80f18f0Tweak fraction field element hashing
1153b5d#16268 boring doctest updates
b71ab2d#16268 other doctest updates
e663dbefix normalization of leading coefficients
db762fcadditional doctest update after #25440

comment:57 Changed 16 months ago by mmezzarobba

  • Description modified (diff)
  • Summary changed from Better normalization for function field elements to Better normalization for fraction field elements

comment:58 Changed 16 months ago by saraedum

  • Reviewers set to Julian Rüth

If you are confident that the output in the doctests is still correct (I did not check all of them) then feel free to set this to positive review.

comment:59 Changed 16 months ago by mmezzarobba

  • Status changed from needs_review to positive_review

Thank you!

comment:60 follow-up: Changed 15 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:61 in reply to: ↑ 60 Changed 14 months ago by mmezzarobba

  • Status changed from needs_work to needs_review

Replying to vbraun:

Merge conflict

Should be fixed. Back to needs_review mainly for the patchbot; there shouldn't be any nontrivial changes to review.

comment:62 Changed 14 months ago by git

  • Commit changed from db762fc4082cf6af913a7637b895f970a7492a74 to af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

fda2c7dAdding documentation and fixing minor issues
dc2df56Merge branch 't/21994/quo_rem_revision' into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields
e7a5b08Reduce further after remove
e639faeAdd keyword reduce_relative in cremove
bbdbbdcMerge branch 'u/caruso/ramified_extensions_of_general_p_adic_rings_and_fields' of git://trac.sagemath.org/sage into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields
319f6d4Remove the debugging method _unit
88f8bbfMerge branch 'u/caruso/ramified_extensions_of_general_p_adic_rings_and_fields' of git://trac.sagemath.org/sage into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields
109ded9Merge branch 't/23218/ramified_extensions_of_general_p_adic_rings_and_fields' into t/24843/padic_prints
a736db8Fixing doctests due to changes in polynomial printing
af91bf5Merge '/u/roed/padic_prints' into fractions_normalize

comment:63 Changed 14 months ago by mmezzarobba

  • Status changed from needs_review to positive_review

comment:64 Changed 14 months ago by vbraun

  • Branch changed from u/mmezzarobba/16268-normalize_fractions to af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:65 follow-up: Changed 13 months ago by mkoeppe

  • Commit af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e deleted

#16993 should probably be closed as a dup of this ticket.

Also, should there be a follow-up ticket for the desirable further improvements mentioned in the ticket description?

comment:66 in reply to: ↑ 65 Changed 13 months ago by mmezzarobba

  • Description modified (diff)

Replying to mkoeppe:

#16993 should probably be closed as a dup of this ticket.

Yes, thanks, I had forgotten to do that.

Also, should there be a follow-up ticket for the desirable further improvements mentioned in the ticket description?

Please go ahead if you want to open additional tickets and/or work on these improvements. (I have little time to work on them myself at the moment, unfortunately, but feel free to ping me if some follow-up ticket needs review.)

comment:67 Changed 13 months ago by mkoeppe

Follow-up ticket at #26339

comment:68 Changed 10 months ago by slelievre

  • Cc slelievre added
  • Description modified (diff)
  • Merged in set to sage-8.4.beta2
  • Milestone changed from sage-8.3 to sage-8.4
Note: See TracTickets for help on using tickets.