search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 479 forks source link

Improve basic operations with fraction field elements #25318

Open mezzarobba opened 6 years ago

mezzarobba commented 6 years ago

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:

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".

Depends on #16268

CC: @roed314 @xcaruso @slel @nthiery @anneschilling

Component: algebra

Author: Marc Mezzarobba

Branch/Commit: u/mmezzarobba/fractions_trivial @ 51c4308

Reviewer: Julian Rüth

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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

d7ae439fewer temporaries in `_mul_`, `_richcmp_` of fractions
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 89e6e7f to d7ae439

mezzarobba commented 6 years ago

Dependencies: #16268

mezzarobba commented 6 years ago

Changed commit from d7ae439 to 8a92c36

mezzarobba commented 6 years ago

Changed branch from u/mmezzarobba/fractions_tmp to u/mmezzarobba/fractions_trivial

mezzarobba commented 6 years ago

New commits:

8a92c36better handle trivial cases of ==, * for fractions
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 8a92c36 to a08972e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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

a08972ebetter handle trivial cases of ==, * for fractions
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from a08972e to aede39f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from aede39f to da9f8d3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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

a8d994efractions: propagate the _is_reduced flag
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from da9f8d3 to a8d994e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from a8d994e to 345e73d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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

2b48678Merge branch 'develop' into fractions_trivial
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 345e73d to 2b48678

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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

15d9f06#25318 fix doctest after merging with develop
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 2b48678 to 15d9f06

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 15d9f06 to 81ac9ec

mezzarobba commented 6 years ago
comment:14

Replying to @sagetrac-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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 81ac9ec to 2f9621f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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
mezzarobba commented 6 years ago
comment:16

Rebased on 8.3.beta5 along with #16268.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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

964927fremove an (IMO) incorrect doctest
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 2f9621f to 964927f

saraedum commented 6 years ago
comment:18

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)
mezzarobba commented 6 years ago
comment:19

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...

saraedum commented 6 years ago
comment:21

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?

saraedum commented 6 years ago
comment:22

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

mezzarobba commented 6 years ago
comment:23

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.

xcaruso commented 6 years ago
comment:24

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?

mezzarobba commented 6 years ago
comment:25

Replying to @xcaruso:

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?

xcaruso commented 6 years ago
comment:26

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.

mezzarobba commented 6 years ago
comment:27

Replying to @xcaruso:

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()?

xcaruso commented 6 years ago
comment:28

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 964927f to 2293ce7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 2293ce7 to 18c3f55

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

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
videlec commented 6 years ago
comment:31

update milestone 8.3 -> 8.4

slel commented 5 years ago
comment:32

Could a few words be added to the ticket description?

mezzarobba commented 5 years ago
comment:33

Replying to @slel:

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?

embray commented 5 years ago
comment:34

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 18c3f55 to 91ad8e8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 91ad8e8 to 5856979

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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