Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#25440 closed defect (fixed)

Recursive call in FractionFieldElement._evaluate_polynomial

Reported by: saraedum Owned by:
Priority: major Milestone: sage-8.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:

Status badges

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 saraedum

What happens here:

  • R.one() is coerced into the coefficient ring of y+1, i.e., R.fraction_field()
  • The _evaluate_polynomial for fraction field elements is called with self==R.fraction_field()(R.one()) and pol==y+1.
    inverse = ~self
    if inverse.denominator().is_one():
       num = inverse.numerator()
       return pol.reverse()(num)/num**pol.degree()
    
  • This sets num==R.one() and we're back to square one.

comment:2 Changed 3 years ago by saraedum

  • Branch set to u/saraedum/25440

comment:3 Changed 3 years ago by saraedum

  • 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:

26bf0c2Remove recursive call when evaluating polynomials in fractions
Last edited 3 years ago by saraedum (previous) (diff)

comment:4 Changed 3 years ago by saraedum

  • Authors set to Julian Rüth
  • Status changed from new to needs_review

I have not run full doctests yet. Let's see what the patchbots think.

comment:5 follow-ups: Changed 3 years ago by mmezzarobba

  • 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 chapoton

mistake here:

+            sage: (y+1)(R.one())
+            sage: 0

comment:7 Changed 3 years ago by git

  • Commit changed from 26bf0c2567501e9ecd7408e4b6b34b213aeefdd0 to b7736000464f55f59cd651387b2324bba68ff8c6

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

b773600Fix typo in doctest

comment:8 in reply to: ↑ 5 ; follow-up: Changed 3 years ago by saraedum

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 return True when foo 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 p-adics 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 ; follow-up: Changed 3 years ago by mmezzarobba

Replying to saraedum:

I think that's a dilemma of inexact objects and p-adics 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.

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 p-adics (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?) p-adic 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 ; follow-up: Changed 3 years ago by saraedum

  • Cc xcaruso swewers added

Replying to mmezzarobba:

Replying to saraedum:

I think that's a dilemma of inexact objects and p-adics 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.

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 p-adics (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 p-adics. 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 mmezzarobba

  • 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 vbraun

  • 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 mmezzarobba

  • 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 return True when foo 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 p-adics and with parents that use what I consider the correct semantics for is_one().

Note: See TracTickets for help on using tickets.