Opened 3 years ago

Last modified 3 weeks ago

#25318 needs_work enhancement

Improve basic operations with fraction field elements

Reported by: mmezzarobba Owned by:
Priority: major Milestone: sage-9.4
Component: algebra Keywords:
Cc: roed, caruso, slelievre, nthiery, aschilling Merged in:
Authors: Marc Mezzarobba Reviewers: Julian Rüth
Report Upstream: N/A Work issues:
Branch: u/mmezzarobba/fractions_trivial (Commits, GitHub, GitLab) Commit: 51c430873b0b8fe64865328afa73550241927866
Dependencies: #16268 Stopgaps:

Status badges

Description (last modified by slelievre)

As discussed in this 2018-06 sage-devel discussion, this is part of an effort to improve fraction field elements, and in particular rational fractions in several variables, spread across four tickets:

  • #25318: Improve basic operations with fraction field elements (the present ticket)
  • #25290: Don't use Karatsuba for multiplying polynomials over fraction fields
  • #23909; GCD for univariate polynomials over fraction fields
  • #16268: Better normalization for fraction field elements

At least for some applications, these tickets bring Sage fraction field elements from "so slow they are unusable" to "not really great yet but reasonable".

Change History (81)

comment:1 Changed 3 years ago by git

  • Commit changed from 89e6e7f254e5a6fc1f8a8a7cc4ec7e0967eda4fe to d7ae439978809de866b88411f0b0008838f756e9

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

d7ae439fewer temporaries in _mul_, _richcmp_ of fractions

comment:2 Changed 3 years ago by mmezzarobba

  • Dependencies set to #16268
  • Status changed from new to needs_review

comment:3 Changed 3 years ago by mmezzarobba

  • Branch changed from u/mmezzarobba/fractions_tmp to u/mmezzarobba/fractions_trivial
  • Commit changed from d7ae439978809de866b88411f0b0008838f756e9 to 8a92c3604437b755d1cf123dd1f2bbb66e32f85d
  • Priority changed from minor to major
  • Summary changed from Minor optimizations of arithmetic with fraction field elements to Improve basic operations with fraction field elements

New commits:

8a92c36better handle trivial cases of ==, * for fractions

comment:4 Changed 3 years ago by git

  • Commit changed from 8a92c3604437b755d1cf123dd1f2bbb66e32f85d to a08972e652a524849920a0d517225d390eedf9fe

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

a08972ebetter handle trivial cases of ==, * for fractions

comment:5 Changed 3 years ago by mmezzarobba

  • Status changed from needs_review to needs_work

comment:6 Changed 3 years ago by git

  • Commit changed from a08972e652a524849920a0d517225d390eedf9fe to aede39f806b75a559125d1ff008fff346eddbb74

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

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
c1f928f#16268 boring doctest updates
8cff798#16268 other doctest updates
544a8dffix normalization of leading coefficients
aede39fbetter handle trivial cases of ==, * for fractions

comment:7 Changed 3 years ago by git

  • Commit changed from aede39f806b75a559125d1ff008fff346eddbb74 to da9f8d3410249f27d6c95e4f4c4c6e884875ef32

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

75ddc0dfix normalization of leading coefficients
f22b223better handle trivial cases of ==, * for fractions
9b8e3f8simplify fraction field elements +, *, and reduction
da9f8d3fractions: propagate the _is_reduced flag

comment:8 Changed 3 years ago by git

  • Commit changed from da9f8d3410249f27d6c95e4f4c4c6e884875ef32 to a8d994e09356b9e0f00873f5eb9778c5ce1390cb

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

a8d994efractions: propagate the _is_reduced flag

comment:9 Changed 3 years ago by git

  • Commit changed from a8d994e09356b9e0f00873f5eb9778c5ce1390cb to 345e73dc7c76b46982a9735cb1f87bf7d45dae57

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

ccfe0efsimplify fraction field elements +, *, and reduction
345e73dfractions: propagate the _is_reduced flag

comment:10 Changed 3 years ago by mmezzarobba

  • Status changed from needs_work to needs_review

comment:11 Changed 3 years ago by git

  • Commit changed from 345e73dc7c76b46982a9735cb1f87bf7d45dae57 to 2b4867890bafb703bf47788e34666f52c2376ee2

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

2b48678Merge branch 'develop' into fractions_trivial

comment:12 follow-up: Changed 3 years ago by git

  • Commit changed from 2b4867890bafb703bf47788e34666f52c2376ee2 to 15d9f0654b5dc744cfe066372214025b06301ad1

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

15d9f06#25318 fix doctest after merging with develop

comment:13 Changed 3 years ago by git

  • Commit changed from 15d9f0654b5dc744cfe066372214025b06301ad1 to 81ac9ec89a31858955aa603672d518bcd0e11d51

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

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
e56e5a4better handle trivial cases of ==, * for fractions
e0430e4simplify fraction field elements +, *, and reduction
81ac9ecfractions: propagate the _is_reduced flag

comment:14 in reply to: ↑ 12 Changed 3 years ago by mmezzarobba

Replying to git:

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

15d9f06#25318 fix doctest after merging with develop

Oops, this fix should have gone to #16268. Moved it there and rebased on top of it.

comment:15 Changed 3 years ago by git

  • Commit changed from 81ac9ec89a31858955aa603672d518bcd0e11d51 to 2f9621f03a990aa181c4de868aa2d77b66e49dde

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

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
ed02ed1better handle trivial cases of ==, * for fractions
9af6633simplify fraction field elements +, *, and reduction
2f9621ffractions: propagate the _is_reduced flag

comment:16 Changed 3 years ago by mmezzarobba

Rebased on 8.3.beta5 along with #16268.

comment:17 Changed 3 years ago by git

  • Commit changed from 2f9621f03a990aa181c4de868aa2d77b66e49dde to 964927fe88a8b0c919eb796c51c5a18b49a5b30b

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

964927fremove an (IMO) incorrect doctest

comment:18 Changed 3 years ago by saraedum

  • Cc roed xcaruso added
  • Status changed from needs_review to needs_info

Could you explain why you need to remove the p-adic doctest? You mentioned this in #25440 but I could not immediately find a reason for this in this ticket:

-        Check that inexact elements are treated correctly::
-
-            sage: K=Qp(2,5)
-            sage: R.<x> = K[]
-            sage: L = R.fraction_field()
-            sage: S.<y> = L[]
-            sage: y(K(1,1)/x)
-            ((1 + O(2)))/((1 + O(2^5))*x)

comment:19 Changed 3 years ago by mmezzarobba

Because it breaks again after this ticket, due to new code that uses is_one() to test if a leading coefficient (or something like that, I don't remember exactly) is one. And while I have nothing against the workaround you added in #25440 to accommodate the behavior of is_one() for p-adics as long as it doesn't break anything else, I don't think we want to block other changes due to what I see as a bug of p-adics...

comment:20 Changed 3 years ago by mmezzarobba

  • Status changed from needs_info to needs_review

comment:21 follow-up: Changed 3 years ago by saraedum

I don't think it's a bug. p-adics make imho the less fortunate of two reasonable choices on how to implement ==. No matter how you implement it, lots of implementations that are not aware of inexact elements break.

If you take the above doctest out, doesn't this mean that you produce a wrong result again now? I am not sure that it's valid to just claim that p-adics are broken, so we should not care about them.

I also don't want to block progress on fraction fields which would be quite nice. But can't we have both?

comment:22 Changed 3 years ago by saraedum

Let's hear what some other people think about this…

comment:23 in reply to: ↑ 21 Changed 3 years ago by mmezzarobba

Replying to saraedum:

I don't think it's a bug. p-adics make imho the less fortunate of two reasonable choices on how to implement ==. No matter how you implement it, lots of implementations that are not aware of inexact elements break.

Ok, perhaps calling it a bug is a bit strong. But in the parts of Sage I'm familiar with, there are a number of generic algorithms that already use equality and (more importantly) is_zero(), is_one(), bool() in a way compatible with interval-like rings... but with the semantics of interval arithmetic, not those of p-adics.

If you take the above doctest out, doesn't this mean that you produce a wrong result again now?

Yes, I think so.

I am not sure that it's valid to just claim that p-adics are broken, so we should not care about them.

I also don't want to block progress on fraction fields which would be quite nice. But can't we have both?

In the present case, I don't really see how without changing the implementation of p-adics, but if you have an idea I'd love to hear it!

Do you think it would be break anything if we modified the p-adic is_zero() and is_one() without touching ==, though? While it can be argued that == is an “internal” operation on each parent (using it in combination with coercion is known to be dangerous anyway), whose semantics could vary from parent to parent, I really don't see anyone calling is_one() and expecting it to return True on anything but the exact unit element, even for p-adics... And I guess that change already would be enough to make most generic algorithms work on p-adics.

comment:24 follow-up: Changed 3 years ago by caruso

Currently, I think that the exact p-adic one does not exist in Sage (except for floating point arithmetics). So are you saying that is_one should always return False? Or that exact p-adic elements have to be implemented?

comment:25 in reply to: ↑ 24 Changed 3 years ago by mmezzarobba

Replying to caruso:

Currently, I think that the exact p-adic one does not exist in Sage (except for floating point arithmetics). So are you saying that is_one should always return False? Or that exact p-adic elements have to be implemented?

I don't know. Perhaps it should always return False, or perhaps it should return True when the element is one up to the maximum precision of the ring... I guess it depends how you want generic objects to behave. For example, what should be the degree of a polynomial whose leading term is O(pk)? When should multiplication by “zero”, resp. “one” yield R.zero(), resp. the other operand?

comment:26 follow-up: Changed 3 years ago by caruso

My personal philosophy is that a should be considered as equal to b as soon as they are indistinguishable (which is the current behavior), but I agree that this has disadvantages as well.

I'm not sure that it's a good idea to let a == 1 have a different meaning than a.is_one(). Personally, I consider the two constructions as equivalent.

comment:27 in reply to: ↑ 26 Changed 3 years ago by mmezzarobba

Replying to caruso:

My personal philosophy is that a should be considered as equal to b as soon as they are indistinguishable (which is the current behavior), but I agree that this has disadvantages as well.

And I'm fine with that. But it seems hard to me to make generic algorithms (that must work over other parents too) accommodate that, unless you also agree that operations involving p-adics can return results “equal” to the correct one in that sense (but possibly more precise).

I don't really like having x.is_one() differ from == 1 either, but that would solve the problem in many cases...

What do you think we should do in the case of the present ticket? Or, to take a similar but simpler example, what do you think c*pol should return when pol is a generic polynomial and c is a scalar with c.is_one()? And when c.is_zero()?

comment:28 Changed 3 years ago by caruso

Something I'm using times to times is to add a named argument (I usually use secure but it can also be exact, it's possibly better). If secure is true, then a == b returns false (or raises an error) if one cannot assert that they are equal for sure; otherwise, it behaves as it does currently.

I'm not very very enthusiastic with the solution, but I guess that it may solve the problem.

comment:29 Changed 3 years ago by git

  • Commit changed from 964927fe88a8b0c919eb796c51c5a18b49a5b30b to 2293ce75efff5c1e09f7334f999b5f024eb376ba

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

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
645e29cbetter handle trivial cases of ==, * for fractions
637061esimplify fraction field elements +, *, and reduction
94b5b19fractions: propagate the _is_reduced flag
2293ce7remove an (IMO) incorrect doctest

comment:30 Changed 3 years ago by git

  • Commit changed from 2293ce75efff5c1e09f7334f999b5f024eb376ba to 18c3f5546f39f965d34c8fab578f923d7e2699ce

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

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
1ffe62bbetter handle trivial cases of ==, * for fractions
213a63esimplify fraction field elements +, *, and reduction
d6ca21ffractions: propagate the _is_reduced flag
18c3f55remove an (IMO) incorrect doctest

comment:31 Changed 3 years ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

comment:32 follow-up: Changed 2 years ago by slelievre

  • Cc slelievre added
  • Milestone changed from sage-8.4 to sage-8.6

Could a few words be added to the ticket description?

comment:33 in reply to: ↑ 32 Changed 2 years ago by mmezzarobba

Replying to slelievre:

Could a few words be added to the ticket description?

I'm not sure what to add to what already is in the commit messages. (And I don't remember much about this ticket.) What information would you like to see?

comment:34 Changed 2 years ago by embray

  • Milestone changed from sage-8.6 to sage-8.7

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

comment:35 Changed 2 years ago by git

  • Commit changed from 18c3f5546f39f965d34c8fab578f923d7e2699ce to 91ad8e8c80ac03aa0642f02684ea667e4b0829fc

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

287ec3cbetter handle trivial cases of ==, * for fractions
d572aa3simplify fraction field elements +, *, and reduction
4d0dfd2fractions: propagate the _is_reduced flag
91ad8e8remove an (IMO) incorrect doctest

comment:36 Changed 2 years ago by git

  • Commit changed from 91ad8e8c80ac03aa0642f02684ea667e4b0829fc to 5856979df85452a692c4f70af5d7cf4f774da5d4

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

21b95d9better handle trivial cases of ==, * for fractions
1623be4simplify fraction field elements +, *, and reduction
1b03354fractions: propagate the _is_reduced flag
5856979remove an (IMO) incorrect doctest

comment:37 Changed 2 years ago by slelievre

  • Cc caruso added; xcaruso removed
  • Description modified (diff)

comment:38 Changed 2 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

comment:39 Changed 22 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

comment:40 follow-up: Changed 21 months ago by vdelecroix

Marc, I am likely to have a look next week (Sage days 100). If you have time to rebase, that would be appreciated).

comment:41 Changed 21 months ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:42 Changed 21 months ago by git

  • Commit changed from 5856979df85452a692c4f70af5d7cf4f774da5d4 to 4e72ae179dc70868a0bb2f3a8ae91484a1e6e46a

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

a969822better handle trivial cases of ==, * for fractions
8420f9dsimplify fraction field elements +, *, and reduction
767965dfractions: propagate the _is_reduced flag
4e72ae1remove an (IMO) incorrect doctest

comment:43 in reply to: ↑ 40 Changed 21 months ago by mmezzarobba

Replying to vdelecroix:

Marc, I am likely to have a look next week (Sage days 100). If you have time to rebase, that would be appreciated).

Done (but not tested at all: I'm on the train, on battery).

comment:44 Changed 21 months ago by mmezzarobba

  • Status changed from needs_work to needs_review

comment:45 Changed 17 months ago by git

  • Commit changed from 4e72ae179dc70868a0bb2f3a8ae91484a1e6e46a to 69cbbed57b6c8665333287a9951f4433b49b910c

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

29d4de5better handle trivial cases of ==, * for fractions
3d120desimplify fraction field elements +, *, and reduction
c46f2d7fractions: propagate the _is_reduced flag
69cbbedremove an (IMO) incorrect doctest

comment:46 Changed 17 months ago by mmezzarobba

rebased (result not tested)

comment:47 Changed 17 months ago by chapoton

Patchbot says

sage -t --long src/sage/combinat/root_system/non_symmetric_macdonald_polynomials.py  # 130 doctests failed
sage -t --long src/sage/combinat/root_system/root_lattice_realization_algebras.py  # 11 doctests failed
sage -t --long src/sage/combinat/root_system/hecke_algebra_representation.py  # 16 doctests failed
sage -t --long src/sage/categories/coxeter_group_algebras.py  # 1 doctest failed

comment:48 Changed 17 months ago by mmezzarobba

  • Status changed from needs_review to needs_work

comment:49 Changed 16 months ago by git

  • Commit changed from 69cbbed57b6c8665333287a9951f4433b49b910c to c81b9abba9685a12f68c017a05d7f3a515da3755

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

f22d085better handle trivial cases of ==, * for fractions
725cfd8simplify fraction field elements +, *, and reduction
64f4a8cfractions: propagate the _is_reduced flag
e624718remove an (IMO) incorrect doctest
c81b9ab#25318 fix / vs // issue revealed by changes to rational functions

comment:50 Changed 16 months ago by mmezzarobba

  • Status changed from needs_work to needs_review

Ok, I think the actual issue behind these failures was in the py3 port of hecke_algebra_representations, see my last commit. (Phew, this one wasn't easy to track down!)

comment:51 Changed 16 months ago by tscrim

  • Cc nthiery aschilling added

I think the last commit is correct, but perhaps Nicolas or Anne, could one of you verify?

comment:52 Changed 16 months ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:53 Changed 15 months ago by git

  • Commit changed from c81b9abba9685a12f68c017a05d7f3a515da3755 to 569267aeae87248a385b8984be051966cc876aa7

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

a8cb064Trac #28890: Pass --disable-static to autoconf packages by default.
f99562aTrac #28890: Don't install PARI's static library.
68de233Merge remote-tracking branch 'trac/u/embray/ticket-28890' into develop
806abc5better handle trivial cases of ==, * for fractions
8779b93simplify fraction field elements +, *, and reduction
0906ca7fractions: propagate the _is_reduced flag
6e86d9eremove an (IMO) incorrect doctest
569267a#25318 fix / vs // issue revealed by changes to rational functions

comment:54 Changed 15 months ago by git

  • Commit changed from 569267aeae87248a385b8984be051966cc876aa7 to 6f21d5cce812af9502949810b40715290e4daf4e

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

d69dfa6better handle trivial cases of ==, * for fractions
2bf7952simplify fraction field elements +, *, and reduction
27ec3c5fractions: propagate the _is_reduced flag
bc016abremove an (IMO) incorrect doctest
6f21d5c#25318 fix / vs // issue revealed by changes to rational functions

comment:55 Changed 15 months ago by chapoton

patchbot says that

++        Returns self raised to the `n^{th}` power.

should be

++        Return ``self`` raised to the `n^{th}` power.

comment:56 Changed 15 months ago by git

  • Commit changed from 6f21d5cce812af9502949810b40715290e4daf4e to 05b14bb40abf39a6280b8cb94765242953b93dd7

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

05b14bb#25318 minor fix in docstring

comment:57 Changed 15 months ago by mmezzarobba

Thank you.

comment:58 follow-up: Changed 14 months ago by saraedum

In gcd, why is self.__class__(self._parent, rnum*sden + rden*snum, rden*sden, coerce=False, reduce=False, is_reduced=True) necessarily reduced? You then divide by d but in the except: case, it won't be reduced, right?

comment:59 Changed 14 months ago by saraedum

Same a few lines below of course.

comment:60 Changed 14 months ago by saraedum

I believe that this is only correct over exact rings:

        if rnum.is_zero() or snum.is_zero():
            return self._parent.zero()
        elif self.is_one():
            return right
        elif _right.is_one():
            return self

comment:61 Changed 14 months ago by saraedum

Why is this here automatically reduced in the except case?

+            tnum = rnum * snum
+            tden = rden * sden
+            res = self.__class__(self._parent, tnum, tden, coerce=False,
+                   reduce=False)
+            try:
+                (<FractionFieldElement> res).normalize_unit_denominator()
+            except (AttributeError, NotImplementedError):
+                pass
+            (<FractionFieldElement> res)._is_reduced = True

comment:62 Changed 14 months ago by saraedum

This is not correct for inexact rings I think:

+        elif self.is_one():
+            return ~right

comment:63 Changed 14 months ago by saraedum

Maybe I am missing something in general here but why would that be automatically reduced if self isn't?

             return self.__class__(self.parent(),
-                snum**right, sden**right,
-                coerce=False, reduce=False)
+                snum**n, sden**n,
+                coerce=False, reduce=False, is_reduced=True)

comment:64 Changed 14 months ago by saraedum

Shouldn't that be protected by a try-except like in other places? This one is in pow.

+            (<FractionFieldElement> res).normalize_unit_denominator()
+            (<FractionFieldElement> res)._is_reduced = True

comment:65 Changed 14 months ago by saraedum

Again, here in neg. Can't it be that self is not reduced?

     return self.__class__(self._parent,
             -self.__numerator, self.__denominator,
-            coerce=False, reduce=False)
+            coerce=False, reduce=False, is_reduced=True)
Last edited 14 months ago by saraedum (previous) (diff)

comment:66 Changed 14 months ago by saraedum

In inv, should normalize_unit_denominator not be in try-except like in other places? Why is this reduced if normalize_unit_denominator failed silently? Why is this reduced if the original was not reduced?

+        (<FractionFieldElement> inv).normalize_unit_denominator()
+        (<FractionFieldElement> inv)._is_reduced = True
+        return inv

comment:67 Changed 14 months ago by saraedum

Why did you drop this test?

-
-        Check that inexact elements are treated correctly::
-
-            sage: K=Qp(2,5)
-            sage: R.<x> = K[]
-            sage: L = R.fraction_field()
-            sage: S.<y> = L[]
-            sage: y(K(1,1)/x)
-            (1 + O(2))/((1 + O(2))*x)

comment:68 Changed 14 months ago by saraedum

  • Reviewers set to Julian Rüth
  • Status changed from needs_review to needs_work

comment:69 Changed 14 months ago by saraedum

I like the idea of this ticket. Fraction fields are annoyingly slow and I am very much in favor of improving the situation. I might be misunderstanding a general pattern here, so looking forward to your comments.

comment:70 Changed 12 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

Moving tickets to milestone sage-9.2 based on a review of last modification date, branch status, and severity.

comment:71 Changed 8 months ago by mkoeppe

Needs rebase

comment:72 Changed 8 months ago by git

  • Commit changed from 05b14bb40abf39a6280b8cb94765242953b93dd7 to e82fd352272c4808ee7706b11a2461e72f98891d

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

3ce383f#25318 better handle trivial cases of ==, * for fractions
61c9a0b#25318 simplify fraction field elements +, *, and reduction
aafdf53#25318 fractions: propagate the _is_reduced flag
e32f2ca#25318 fix / vs // issue revealed by changes to rational functions
3194d4c#25318 minor fix in docstring
f6caa82#25318 Accommodate p-adic rings
e82fd35#25318 remove superfluous try/excepts

comment:73 in reply to: ↑ 58 Changed 8 months ago by mmezzarobba

  • Status changed from needs_work to needs_review

Thanks a lot for your comments--and sorry for taking so long to reply, you caught me at a bad time!

Replying to saraedum:

In gcd, why is self.__class__(self._parent, rnum*sden + rden*snum, rden*sden, coerce=False, reduce=False, is_reduced=True) necessarily reduced? You then divide by d but in the except: case, it won't be reduced, right?

I assume you mean in _add_? But even so I don't understand the question: this line is under if d.is_unit(), and I'm dividing by d (or trying to) when that's not the case.

Replying to saraedum:

Same a few lines below of course.

A few lines below, the whole fraction is zero.

Replying to saraedum:

I believe that this is only correct over exact rings:

        if rnum.is_zero() or snum.is_zero():
            return self._parent.zero()
        elif self.is_one():
            return right
        elif _right.is_one():
            return self

Replying to saraedum:

This is not correct for inexact rings I think:

+        elif self.is_one():
+            return ~right

Replying to saraedum:

Why did you drop this test?

-
-        Check that inexact elements are treated correctly::
-
-            sage: K=Qp(2,5)
-            sage: R.<x> = K[]
-            sage: L = R.fraction_field()
-            sage: S.<y> = L[]
-            sage: y(K(1,1)/x)
-            (1 + O(2))/((1 + O(2))*x)

See the discussion above: I think it is correct over most inexact rings (RR, RDF, RBF, RIF, CC, CDF, CBF, CIF, SR... and constructions over them), but apparently not over p-adic rings, unfortunately. For want of a proper solution, I'm now using this logic over exact rings only.

I dropped the test because I didn't realize this behavior of is_zero() and is_one() was something the p-adics people actually wanted. I have restored it in the rebased branch.

Replying to saraedum:

Why is this here automatically reduced in the except case?

+            tnum = rnum * snum
+            tden = rden * sden
+            res = self.__class__(self._parent, tnum, tden, coerce=False,
+                   reduce=False)
+            try:
+                (<FractionFieldElement> res).normalize_unit_denominator()
+            except (AttributeError, NotImplementedError):
+                pass
+            (<FractionFieldElement> res)._is_reduced = True

Strictly speaking it isn't, but that's because we're unable to reduce over that ring, hence there is no point in trying again later. (Cf. the comment in front of the initial definition of _is_reduced in __init__().)

Replying to saraedum:

Maybe I am missing something in general here but why would that be automatically reduced if self isn't?

             return self.__class__(self.parent(),
-                snum**right, sden**right,
-                coerce=False, reduce=False)
+                snum**n, sden**n,
+                coerce=False, reduce=False, is_reduced=True)

Replying to saraedum:

Again, here in neg. Can't it be that self is not reduced?

     return self.__class__(self._parent,
             -self.__numerator, self.__denominator,
-            coerce=False, reduce=False)
+            coerce=False, reduce=False, is_reduced=True)

I think you are right, is_reduced=self._is_reduced would be better in these cases.

Replying to saraedum:

Shouldn't that be protected by a try-except like in other places? This one is in pow.

+            (<FractionFieldElement> res).normalize_unit_denominator()
+            (<FractionFieldElement> res)._is_reduced = True

Replying to saraedum:

In inv, should normalize_unit_denominator not be in try-except like in other places? Why is this reduced if normalize_unit_denominator failed silently? Why is this reduced if the original was not reduced?

+        (<FractionFieldElement> inv).normalize_unit_denominator()
+        (<FractionFieldElement> inv)._is_reduced = True
+        return inv

AFAICT it is the other way around: the try-excepts that are present in some cases are leftovers from a previous version and are unnecessary.

See above for the other points.


New commits:

3ce383f#25318 better handle trivial cases of ==, * for fractions
61c9a0b#25318 simplify fraction field elements +, *, and reduction
aafdf53#25318 fractions: propagate the _is_reduced flag
e32f2ca#25318 fix / vs // issue revealed by changes to rational functions
3194d4c#25318 minor fix in docstring
f6caa82#25318 Accommodate p-adic rings
e82fd35#25318 remove superfluous try/excepts

comment:74 Changed 8 months ago by git

  • Commit changed from e82fd352272c4808ee7706b11a2461e72f98891d to f279b43ed55e465782bbaabeaf266b645e2722e2

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

fd39ad5#25318 minor fix in docstring to make the patchbot happy
eb63c06#25318 Accommodate p-adic rings
f279b43#25318 remove superfluous try/excepts

comment:75 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:76 Changed 4 months ago by git

  • Commit changed from f279b43ed55e465782bbaabeaf266b645e2722e2 to e5cdf79729f71f6cc4248620de9207c72d18552e

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

aee4200#25318 better handle trivial cases of ==, * for fractions
7d89343#25318 simplify fraction field elements +, *, and reduction
fc7cf8b#25318 fractions: propagate the _is_reduced flag
a64812c#25318 fix / vs // issue revealed by changes to rational functions
7b1e9f1#25318 minor fix in docstring to make the patchbot happy
8ed1d79#25318 Accommodate p-adic rings
e5cdf79#25318 remove superfluous try/excepts

comment:77 Changed 5 weeks ago by git

  • Commit changed from e5cdf79729f71f6cc4248620de9207c72d18552e to 51c430873b0b8fe64865328afa73550241927866

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

0e02180#25318 better handle trivial cases of ==, * for fractions
8714366#25318 simplify fraction field elements +, *, and reduction
9d89697#25318 fractions: propagate the _is_reduced flag
65d3edf#25318 fix / vs // issue revealed by changes to rational functions
4686b14#25318 minor fix in docstring to make the patchbot happy
b26fbf3#25318 Accommodate p-adic rings
51c4308#25318 remove superfluous try/excepts

comment:78 Changed 5 weeks ago by mmezzarobba

Rebased on 9.3.beta8.

comment:79 follow-up: Changed 5 weeks ago by tscrim

Do you have some timings?

comment:80 in reply to: ↑ 79 Changed 5 weeks ago by mmezzarobba

  • Status changed from needs_review to needs_work

Replying to tscrim:

Do you have some timings?

Good question. I am almost certain my version was faster when I first wrote it, but with the current Sage beta I no longer see any measurable improvement. For all I know the this ticket's branch may even be a bit slower. Thanks for asking! :-/

comment:81 Changed 3 weeks ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

Note: See TracTickets for help on using tickets.