#16268 closed defect (fixed)
Better normalization for fraction field elements
Reported by:  John Cremona  Owned by:  

Priority:  minor  Milestone:  sage8.4 
Component:  algebra  Keywords:  
Cc:  Travis Scrimshaw, Clemens Heuberger, Salvatore Stella, Jakob Kroeker, Ben Hutz, Samuel Lelièvre  Merged in:  sage8.4.beta2 
Authors:  Robert Bradshaw, Erik Massop, Marc Mezzarobba  Reviewers:  Julian Rüth 
Report Upstream:  N/A  Work issues:  
Branch:  af91bf5 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
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 blowup 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 nonfields 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*u81 sage: c = u^2 + 3*u + 9 sage: d = u3 sage: s = a/b sage: t = c/d sage: s==t True sage: len(Set([s,t])) 2
Change History (68)
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
Branch:  → u/robertwb/ticket/16268 

Created:  Apr 29, 2014, 3:00:38 PM → Apr 29, 2014, 3:00:38 PM 
Modified:  Apr 29, 2014, 4:29:25 PM → Apr 29, 2014, 4:29:25 PM 
comment:3 Changed 9 years ago by
Commit:  → 289d3aa124bd5a03349f14f0520e4b8d2845dd84 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
289d3aa  Fix hash for unreduced fraction field elements.

comment:4 Changed 9 years ago by
Commit:  289d3aa124bd5a03349f14f0520e4b8d2845dd84 → f7266ca383db2783ba0d485ac5c9ab5da6c6d614 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
f7266ca  Fix hash for unreduced fraction field elements.

comment:5 followup: 23 Changed 9 years ago by
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 9 years ago by
Authors:  → Robert Bradshaw 

Status:  new → needs_review 
comment:7 Changed 9 years ago by
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 notimplementedexception 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 9 years ago by
Branch:  u/robertwb/ticket/16268 → u/emassop/ticket/16268 

comment:9 Changed 9 years ago by
Commit:  f7266ca383db2783ba0d485ac5c9ab5da6c6d614 → 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:
cdf1163  Fix documentation of normalize

comment:10 Changed 9 years ago by
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 tracuser "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 9 years ago by
Commit:  cdf116327b93b5d29282c98d40042440d068ce44 → a4221ed3e1d16d38b271316b01b91344fb195746 

comment:12 Changed 9 years ago by
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)/(2x1) in Q(ZZ[x]) did not have the same normalisation. I doubt this can be fixed for general rings.  Removed call to reduce for nonexact 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 genericFractionFieldElement.__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 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:14 Changed 9 years ago by
Status:  needs_review → 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:16 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:18 Changed 8 years ago by
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 8 years ago by
Cc:  Travis Scrimshaw added 

comment:20 Changed 8 years ago by
Cc:  Clemens Heuberger added 

comment:21 Changed 7 years ago by
Cc:  Salvatore Stella added 

comment:23 Changed 5 years ago by
Authors:  Robert Bradshaw → Robert Bradshaw, Erik Massop, Marc Mezzarobba 

Branch:  u/emassop/ticket/16268 → u/mmezzarobba/16268normalize_fractions 
Commit:  a4221ed3e1d16d38b271316b01b91344fb195746 → 2d96533bde07fbbbce3a490dd786bbf7a9ffae53 
Status:  needs_work → 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 blowup 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 followup.)
New commits:
3d96f14  Fix hash for unreduced fraction field elements.

fb8a382  Fix documentation of normalize

2f7a320  Fix doctest

198c059  More careful hashing of FractionFieldElement

3e4fc0c  slightly simplify/robustify FractionFieldElement.reduce()

b418d40  FractionFieldElement: merge reduce() and normalize()

c45d34f  Tweak fraction field element hashing

aa73340  Small optimization in FracFieldElt richcmp()

e3a2da4  #16268 boring doctest updates

2d96533  #16268 other doctest updates

comment:24 Changed 5 years ago by
Commit:  2d96533bde07fbbbce3a490dd786bbf7a9ffae53 → 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 5 years ago by
Commit:  0830684d5a260960d215d52ed42ef932fa987e9e → b504f8e593367ae9c955b515965930d750674044 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
39b7ad3  FractionFieldElement: merge reduce() and normalize()

efd5979  Tweak fraction field element hashing

1db6427  Small optimization in FracFieldElt richcmp()

7adce21  #16268 boring doctest updates

b504f8e  #16268 other doctest updates

comment:26 followup: 27 Changed 5 years ago by
Commit:  b504f8e593367ae9c955b515965930d750674044 → fb113639b4c3e4ff7de67a8f8edcd67ffb3141c5 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
77dc9e1  FractionFieldElement: merge reduce() and normalize()

a25ab99  Tweak fraction field element hashing

0f310bc  Small optimization in FracFieldElt richcmp()

00104f5  #16268 boring doctest updates

fb11363  #16268 other doctest updates

comment:27 Changed 5 years ago by
comment:28 followup: 29 Changed 5 years ago by
Commit:  fb113639b4c3e4ff7de67a8f8edcd67ffb3141c5 → 3cf5014d43785fd384204981ead86702a3ea1662 

comment:29 Changed 5 years ago by
comment:30 Changed 5 years ago by
Commit:  3cf5014d43785fd384204981ead86702a3ea1662 → b031e3e49c50a31dbe298b58f4178fd5f96d08b2 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
259843a  Fix hash for unreduced fraction field elements.

3197980  Fix documentation of normalize

ff7be78  Fix doctest

9edad32  More careful hashing of FractionFieldElement

6a2fbd7  slightly simplify/robustify FractionFieldElement.reduce()

c16d55a  FractionFieldElement: merge reduce() and normalize()

7c8a45a  Tweak fraction field element hashing

5a78e11  Small optimization in FracFieldElt richcmp()

0f17da0  #16268 boring doctest updates

b031e3e  #16268 other doctest updates

comment:31 Changed 5 years ago by
Commit:  b031e3e49c50a31dbe298b58f4178fd5f96d08b2 → 8cff798aace0fe8d69b6fcdc3bf2054b6f71fcd0 

comment:32 Changed 5 years ago by
Status:  needs_review → needs_work 

comment:33 Changed 5 years ago by
Commit:  8cff798aace0fe8d69b6fcdc3bf2054b6f71fcd0 → 544a8dfb4bf1e385592d444062867ce2f4987232 

Branch pushed to git repo; I updated commit sha1. New commits:
544a8df  fix normalization of leading coefficients

comment:34 Changed 5 years ago by
Commit:  544a8dfb4bf1e385592d444062867ce2f4987232 → 75ddc0dee1104e6970d02352ea2aafc3262c0f49 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
75ddc0d  fix normalization of leading coefficients

comment:35 Changed 5 years ago by
Status:  needs_work → needs_review 

comment:36 Changed 5 years ago by
Cc:  Ben Hutz 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 doublecheck.
comment:38 followup: 40 Changed 5 years ago by
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/#sourcecode). Please put the double colons back.
In 7c8a45abecdf5224c9f0a324447ba69db22057b5 hashes are computed for inexact rings without reduction. This means that pythonequal 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 5 years ago by
Milestone:  sage6.4 → sage8.3 

comment:40 Changed 5 years ago by
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/#sourcecode). 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 pythonequal 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 roundoff 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 bugforbug 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 followup: 42 Changed 5 years ago by
Regarding EXAMPLES: Ah, I didn't notice that. Sorry.
Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bugforbug, 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 followup: 43 Changed 5 years ago by
Replying to emassop:
Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bugforbug, 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
implieshash(x) == hash(y)
", but if I recall correctly, it did strive to uphold this implication whenx
andy
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
intoreduce
means that there no longer is a method that guarantees a normal form. Insteadreduce
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 whenreduce
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 nonfields, I guess), and hence I agree that this would best be kept for another ticket.
comment:43 followup: 44 Changed 5 years ago by
Replying to mmezzarobba:
Regarding hashing: How about emitting a warning? (sage.misc.superseded.warning?) Then computations keep working bugforbug, 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
intoreduce
means that there no longer is a method that guarantees a normal form. Insteadreduce
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 whenreduce
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 nonfields, 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 Changed 5 years ago by
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 floatingpoint 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 keepingnormalize
around, as my initial preference would be towardsnormalize
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 5 years ago by
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( 156 156 sage: MeromorphicModularFormsRing()(1/x) == MeromorphicModularFormsRing()(1/(x)) 157 157 True 158 158 sage: MeromorphicModularFormsRing(base_ring=CC)(1/x) == MeromorphicModularFormsRing()(1/(x)) 159 True159 False 160 160 """ 161 161 if op not in [op_EQ, op_NE]: 162 162 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): 894 894 True 895 895 """ 896 896 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) 905 907 906 908 def valuation(self, v=None): 907 909 """ … … cdef class FractionFieldElement_1poly_field(FractionFieldElement): 1150 1152 if op == Py_EQ or op == Py_NE: 1151 1153 if self.__denominator == other.__denominator: 1152 1154 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()): 1154 1157 return op == Py_NE 1155 1158 return richcmp( 1156 1159 self.__numerator * other.__denominator,
comment:46 Changed 5 years ago by
Commit:  75ddc0dee1104e6970d02352ea2aafc3262c0f49 → 86b3b56b2bfd64a57f3a82dd022f5bd70b11b622 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
56b9292  Fix hash for unreduced fraction field elements.

7b1017d  Fix documentation of normalize

98b1301  Fix doctest

7281516  More careful hashing of FractionFieldElement

862604c  slightly simplify/robustify FractionFieldElement.reduce()

7f3c093  FractionFieldElement: merge reduce() and normalize()

b273531  Tweak fraction field element hashing

a21cb63  #16268 boring doctest updates

80c421d  #16268 other doctest updates

86b3b56  fix normalization of leading coefficients

comment:48 followup: 49 Changed 5 years ago by
Commit:  86b3b56b2bfd64a57f3a82dd022f5bd70b11b622 → 3a3d32fb60b4c5177c7ce0824076d78aeb90184c 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3ff950c  Fix hash for unreduced fraction field elements.

2bdd265  Fix documentation of normalize

bef8c4f  Fix doctest

305c98f  More careful hashing of FractionFieldElement

d524b75  slightly simplify/robustify FractionFieldElement.reduce()

9a9d4de  FractionFieldElement: merge reduce() and normalize()

59c558c  Tweak fraction field element hashing

afc6a05  #16268 boring doctest updates

7dfe3c3  #16268 other doctest updates

3a3d32f  fix normalization of leading coefficients

comment:49 Changed 5 years ago by
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 4 years ago by
Commit:  3a3d32fb60b4c5177c7ce0824076d78aeb90184c → 5d4a6890e27f84afb6aa8d713117dfcb0c5a702b 

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
40e22a0  Fix documentation of normalize

fc57a23  Fix doctest

21375ea  More careful hashing of FractionFieldElement

03d91ab  slightly simplify/robustify FractionFieldElement.reduce()

610e585  FractionFieldElement: merge reduce() and normalize()

8aa61d5  Tweak fraction field element hashing

e01d960  #16268 boring doctest updates

1bd6279  #16268 other doctest updates

1f6b0b6  fix normalization of leading coefficients

5d4a689  additional doctest update after #25440

comment:52 followup: 53 Changed 4 years ago by
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 followup: 54 Changed 4 years ago by
comment:54 Changed 4 years ago by
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 4 years ago by
Commit:  5d4a6890e27f84afb6aa8d713117dfcb0c5a702b → dcd92b72b863663c4306018735c8df9bd0213d73 

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

9d108cc  Fix doctest

47cf425  More careful hashing of FractionFieldElement

1d8546f  slightly simplify/robustify FractionFieldElement.reduce()

f220ba1  FractionFieldElement: merge reduce() and normalize()

d57e934  Tweak fraction field element hashing

db40831  #16268 boring doctest updates

2955aa9  #16268 other doctest updates

069cca8  fix normalization of leading coefficients

dcd92b7  additional doctest update after #25440

comment:56 Changed 4 years ago by
Commit:  dcd92b72b863663c4306018735c8df9bd0213d73 → db762fc4082cf6af913a7637b895f970a7492a74 

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

26c87d3  Fix doctest

78b5990  More careful hashing of FractionFieldElement

e768973  slightly simplify/robustify FractionFieldElement.reduce()

029346f  FractionFieldElement: merge reduce() and normalize()

80f18f0  Tweak fraction field element hashing

1153b5d  #16268 boring doctest updates

b71ab2d  #16268 other doctest updates

e663dbe  fix normalization of leading coefficients

db762fc  additional doctest update after #25440

comment:57 Changed 4 years ago by
Description:  modified (diff) 

Summary:  Better normalization for function field elements → Better normalization for fraction field elements 
comment:58 Changed 4 years ago by
Reviewers:  → 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:61 Changed 4 years ago by
Status:  needs_work → 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 4 years ago by
Commit:  db762fc4082cf6af913a7637b895f970a7492a74 → af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
fda2c7d  Adding documentation and fixing minor issues

dc2df56  Merge branch 't/21994/quo_rem_revision' into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields

e7a5b08  Reduce further after remove

e639fae  Add keyword reduce_relative in cremove

bbdbbdc  Merge 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

319f6d4  Remove the debugging method _unit

88f8bbf  Merge 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

109ded9  Merge branch 't/23218/ramified_extensions_of_general_p_adic_rings_and_fields' into t/24843/padic_prints

a736db8  Fixing doctests due to changes in polynomial printing

af91bf5  Merge '/u/roed/padic_prints' into fractions_normalize

comment:63 Changed 4 years ago by
Status:  needs_review → positive_review 

comment:64 Changed 4 years ago by
Branch:  u/mmezzarobba/16268normalize_fractions → af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:65 followup: 66 Changed 4 years ago by
Commit:  af91bf5f1dad1ab5bbb6fb376bb5c408bc85974e 

#16993 should probably be closed as a dup of this ticket.
Also, should there be a followup ticket for the desirable further improvements mentioned in the ticket description?
comment:66 Changed 4 years ago by
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 followup 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 followup ticket needs review.)
comment:68 Changed 4 years ago by
Cc:  Samuel Lelièvre added 

Description:  modified (diff) 
Merged in:  → sage8.4.beta2 
Milestone:  sage8.3 → sage8.4 
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 yieldgcd(27*u^2+81*u+243, 27*u81)==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.