#25440 closed defect (fixed)
Recursive call in FractionFieldElement._evaluate_polynomial
Reported by:  saraedum  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  basic arithmetic  Keywords:  
Cc:  mmezzarobba, roed, xcaruso, swewers  Merged in:  
Authors:  Julian Rüth  Reviewers:  Marc Mezzarobba 
Report Upstream:  N/A  Work issues:  
Branch:  b773600 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description
Currently, the following fails:
sage: R.<x> = GF(2)[] sage: S.<y> = R.fraction_field()[] sage: (y+1)(R.one()) RuntimeError: maximum recursion depth exceeded while calling a Python object
Change History (13)
comment:1 Changed 3 years ago by
comment:2 Changed 3 years ago by
 Branch set to u/saraedum/25440
comment:3 Changed 3 years ago by
 Commit set to 26bf0c2567501e9ecd7408e4b6b34b213aeefdd0
I had run into a precision problem in the same spot several times before and had never bothered for long enough to track it down. I hope the reviewer doesn't mind that I also fix this while I am at it.
New commits:
26bf0c2  Remove recursive call when evaluating polynomials in fractions

comment:4 Changed 3 years ago by
 Status changed from new to needs_review
I have not run full doctests yet. Let's see what the patchbots think.
comment:5 followups: ↓ 8 ↓ 13 Changed 3 years ago by
 Cc roed added
The first part looks good to me. (Cc:ing the original author of the code just in case.)
Regarding the precision issue, while your fix doesn't hurt as far as I can see, I don't believe foo.is_one()
should ever return True
when foo
is not exactly one... so IMO the real bug is in elements for which that happens.
comment:6 Changed 3 years ago by
mistake here:
+ sage: (y+1)(R.one()) + sage: 0
comment:7 Changed 3 years ago by
 Commit changed from 26bf0c2567501e9ecd7408e4b6b34b213aeefdd0 to b7736000464f55f59cd651387b2324bba68ff8c6
Branch pushed to git repo; I updated commit sha1. New commits:
b773600  Fix typo in doctest

comment:8 in reply to: ↑ 5 ; followup: ↓ 9 Changed 3 years ago by
Replying to mmezzarobba:
The first part looks good to me. (Cc:ing the original author of the code just in case.)
Regarding the precision issue, while your fix doesn't hurt as far as I can see, I don't believe
foo.is_one()
should ever returnTrue
whenfoo
is not exactly one... so IMO the real bug is in elements for which that happens.
I think that's a dilemma of inexact objects and padics in particular. Currently, x == 1
and x.is_one()
are satisfied by inexact one elements. That comes with its drawbacks, as can be seen in this example. But changing this is probably going to break things in even more places. Also, it's unclear what the alternative would be. Should R(1) != 1
? Or should not R(1).is_one()
hold? Or just R(1)*p/p != 1
? Or should R(1) == 1
raise an exception?
I think there is no good answer here with the operators available in Sage/Python?. Whatever you choose, some algorithms are going to break because the assumptions made by the implementation are not met.
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 3 years ago by
Replying to saraedum:
I think that's a dilemma of inexact objects and padics in particular.Currently,
x == 1
andx.is_one()
are satisfied by inexact one elements. That comes with its drawbacks, as can be seen in this example. But changing this is probably going to break things in even more places.
I'm not so sure: intervals have exactly the same issue, but they only declare equal elements that are, and they work reasonably well with the rest of Sage... Really, for me, the way equality of padics (and series) appear to work is closer to a bug than an implementation choice.
Also, it's unclear what the alternative would be. Should
R(1) != 1
?
Ideally yes, but that's a lost battle.
Or should
not R(1).is_one()
hold?
Probably. Though, if I understand right, (some?) padic rings have a maximum precision, and there is an argument for declaring elements equal when they agree to the precision of the parent, or perhaps even to that of the more precise of the two elements.
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 3 years ago by
 Cc xcaruso swewers added
Replying to mmezzarobba:
Replying to saraedum:
I think that's a dilemma of inexact objects and padics in particular.Currently,
x == 1
andx.is_one()
are satisfied by inexact one elements. That comes with its drawbacks, as can be seen in this example. But changing this is probably going to break things in even more places.I'm not so sure: intervals have exactly the same issue, but they only declare equal elements that are, and they work reasonably well with the rest of Sage... Really, for me, the way equality of padics (and series) appear to work is closer to a bug than an implementation choice.
It's a valid alternative. Two elements are equal if they are indistinguishable. We have thought about this and it certainly has its merits. But you also have to keep this in mind when implementing generic algorithms. No matter what you do, some assumptions that exact implementations make are going to be violated, e.g., a + b  b == a
is not true in RIF.
I am not saying that we should not change the notion of equality in padics. I have discussed this with several people in the past and even had a ticket about this at some point. However, it's not clear what's the right notion of equality. The one we have is unfortunate but I am not convinced anymore that there is a better one.
Anyway, while things are the way they are, I'd like to fix this precision issue in Sage. If you are opposed to this, I don't mind at all to take this out of this changeset and propose it on a different ticket and continue the discussion there :)
comment:11 in reply to: ↑ 10 Changed 3 years ago by
 Reviewers set to Marc Mezzarobba
 Status changed from needs_review to positive_review
Replying to saraedum:
But you also have to keep this in mind when implementing generic algorithms. No matter what you do, some assumptions that exact implementations make are going to be violated, e.g.,
a + b  b == a
is not true in RIF.
Yes, of course. And I wholeheartedly agree that Sage is missing finer grained comparison operators. But I thought the (weak) consensus to deal with the situation—not only in the context of intervals, but also, e.g., for method that do their best to answer undecidable questions—was to stick as much as possible to the convention that positive boolean answers must be correct, while negative ones may mean “I don't know”. In any case, that's the convention I try to apply when writing or reviewing generic code where the issue might arise.
Anyway, while things are the way they are, I'd like to fix this precision issue in Sage. If you are opposed to this, I don't mind at all to take this out of this changeset and propose it on a different ticket and continue the discussion there :)
No, I don't really care about that particular change, and I'm happy to keep it in if it can help. I just don't think it will be a sustainable model in the long run.
comment:12 Changed 3 years ago by
 Branch changed from u/saraedum/25440 to b7736000464f55f59cd651387b2324bba68ff8c6
 Resolution set to fixed
 Status changed from positive_review to closed
comment:13 in reply to: ↑ 5 Changed 3 years ago by
 Commit b7736000464f55f59cd651387b2324bba68ff8c6 deleted
Replying to mmezzarobba:
Regarding the precision issue, while your fix doesn't hurt as far as I can see, I don't believe
foo.is_one()
should ever returnTrue
whenfoo
is not exactly one... so IMO the real bug is in elements for which that happens.
And, at #25318, I'm proposing to remove the doctest you added, because it breaks with the changes in that ticket, and I see no way of making things work both with padics and with parents that use what I consider the correct semantics for is_one()
.
What happens here:
R.one()
is coerced into the coefficient ring ofy+1
, i.e.,R.fraction_field()
_evaluate_polynomial
for fraction field elements is called withself==R.fraction_field()(R.one())
andpol==y+1
.num==R.one()
and we're back to square one.