Opened 10 years ago
Closed 8 years ago
#13125 closed enhancement (fixed)
Reals sets consisting of intervals and isolated points
Reported by: | ares | Owned by: | Ares Ribó |
---|---|---|---|
Priority: | major | Milestone: | sage-6.3 |
Component: | calculus | Keywords: | |
Cc: | kcrisman, tscrim, robertwb | Merged in: | |
Authors: | Volker Braun , Jordi Saludes , Ares Ribó | Reviewers: | Ralf Stephan, Peter Bruin |
Report Upstream: | N/A | Work issues: | |
Branch: | c818746 (Commits, GitHub, GitLab) | Commit: | c8187460bc0e90c0b58713a5c55bc6b86895a12b |
Dependencies: | Stopgaps: |
Description (last modified by )
Finite unions of open/closed/semi-closed subsets of the real line, for example
sage: RealSet(0,2) + RealSet.unbounded_above_closed(10) (0, 2) + [10, +Infinity)
This ticket also encountered a number of bugs in the comparison of infinity with various field elements like
sage: RLF(0) < oo False
These are now also fixed and extensive doctests were added.
Attachments (3)
Change History (63)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 Changed 10 years ago by
- Description modified (diff)
comment:3 follow-up: ↓ 4 Changed 10 years ago by
comment:4 in reply to: ↑ 3 Changed 10 years ago by
comment:5 Changed 9 years ago by
- Cc kcrisman added
- Description modified (diff)
- Status changed from new to needs_review
I'm taking over this ticket since I need this for piecewise functions. I'm not sure what happened with the originally proposed patch, but what was attached here is not the actual code.
comment:6 Changed 9 years ago by
- Summary changed from Reals sets consisting of intervals and isolated points, supporting integration. to Reals sets consisting of intervals and isolated points
comment:7 Changed 9 years ago by
Is +
what we're looking for here? Maybe something like u
or U
? Just worried about the difference between this "sum" and the Minkowski sum (which is, in fact, already in Sage).
In fact, maybe these should inherit from something related to that... probably not, but just raising the possibility.
How do I get more exotic sets like the union of 1/n
for positive integer n? ;-)
comment:8 Changed 9 years ago by
It think it is better to stick to the category of finite unions of intervals and points, then with functions defined on such sets and their periodic extensions (like 1 on [0, 1], 0 on (1,2), then extend periodically in one or both directions to get square wave).
Things with infinite unions lead to accumulation points and cannot really be handled in a uniform way, I suspect.
comment:9 Changed 9 years ago by
Yes, I was being silly :)
comment:10 Changed 9 years ago by
I just attached the original patch. I did not notice before that the initial patch was not correctly uploaded, I am very sorry for that.
comment:11 Changed 9 years ago by
- Description modified (diff)
comment:12 follow-up: ↓ 13 Changed 9 years ago by
- Description modified (diff)
I've added the authors to my patch and incorporated any methods that made sense to me. Ares, since your patch would take a bit of work to make use of the Sage class hierarchy and since docstrings are not quite according to Sage specs I propose that we base the implementation on what I have currently posted. The imho only thing left is to decide what to do with the toGf
method. Which is some third-party code, I suppose. Maybe you can explain what it is for? If you think it should go into Sage we could turn it into a underscore method.
comment:13 in reply to: ↑ 12 Changed 9 years ago by
Replying to vbraun:
I've added the authors to my patch and incorporated any methods that made sense to me. Ares, since your patch would take a bit of work to make use of the Sage class hierarchy and since docstrings are not quite according to Sage specs I propose that we base the implementation on what I have currently posted. The imho only thing left is to decide what to do with the
toGf
method. Which is some third-party code, I suppose. Maybe you can explain what it is for? If you think it should go into Sage we could turn it into a underscore method.
We will move the toGf method into another paquet, since we use it to support our MOLTO project demo (D6.2.pdf) and it is not directly related to realsets.
comment:14 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:15 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:16 Changed 8 years ago by
- Branch set to u/rws/ticket/13125
- Created changed from 06/16/12 23:25:47 to 06/16/12 23:25:47
- Modified changed from 01/30/14 21:20:52 to 01/30/14 21:20:52
comment:17 Changed 8 years ago by
- Commit set to 15ef91ca207671f216731692edf5e10d0d863fe1
- Reviewers set to Ralf Stephan
- Status changed from needs_review to positive_review
Looks and tests fine. I've fixed some typos and added the module to the reference manual.
New commits:
308d16b | Implement RealSet - finite unions of open/closed/semi-closed subsets of the real line.
|
a861752 | Further improvements to RealSet
|
15ef91c | Trac #13125: reviewer's patch: fix typos, add module to set refman
|
comment:18 Changed 8 years ago by
Fails on OSX:
sage -t --long src/sage/sets/real_set.py ********************************************************************** File "src/sage/sets/real_set.py", line 1156, in sage.sets.real_set.RealSet.intersection Failed example: s1.intersection(s2) Expected: (1, 2) Got: (-oo, -10] + (1, 2) ********************************************************************** File "src/sage/sets/real_set.py", line 1158, in sage.sets.real_set.RealSet.intersection Failed example: s1 & s2 # syntactic sugar Expected: (1, 2) Got: (-oo, -10] + (1, 2) ********************************************************************** 1 item had failures: 2 of 11 in sage.sets.real_set.RealSet.intersection [191 tests, 2 failures, 0.14 s]
comment:19 Changed 8 years ago by
In fact, only fails on OSX 10.9.2 but works on 10.6... weird.
comment:20 Changed 8 years ago by
It fails in OSX 10.7.5 too.
The error seems to be in the comparation involving one sage.rings.real_lazy.LazyWrapper
instance:
sage: s1 = RealSet(0,2) + RealSet.unbounded_above_closed(10); s1 (0, 2) + [10, +oo) sage: s2 = RealSet(1,3) + RealSet.unbounded_below_closed(-10); s2 (-oo, -10] + (1, 3) sage: s1.intersection(s2) (-oo, -10] + (1, 2)
Not right. Look at the intersection of the first intervals:
sage: i1 = s1._intervals[0]; i1 (0, 2) sage: i2 = s2._intervals[0]; i2 (-oo, -10] sage: i1.intersection(i2) (-oo, -10]
Wrong. Compare the bounds:
sage: (i1._lower, i2._lower) (0, -Infinity) sage: cmp(i1._lower, i2._lower) -1 sage: i1._lower < i2._lower True
It doesn't fail for floats or integers:
sage: 0.0 < i2._lower False sage: type(i1._lower), type(i2._lower) (sage.rings.real_lazy.LazyWrapper, sage.rings.infinity.MinusInfinity)
comment:21 Changed 8 years ago by
Confirm different (correct) behaviour on Linux:
... sage: s1.intersection(s2) (1, 2) ... sage: i1.intersection(i2) (0, 0) ... sage: cmp(i1._lower, i2._lower) 1 sage: i1._lower < i2._lower False
comment:22 Changed 8 years ago by
More specifically, it seems to fail only when comparing to zero (OSX 10.7.5):
sage: filter(lambda x: RLF(x) < -oo, range(-10,10)) [0] sage: filter(lambda x: RLF(float(x)/3) < -oo, range(-10,10)) [0]
and +oo
is not affected:
sage: filter(lambda x: RLF(x) >= oo, range(-10,10)) []
comment:23 Changed 8 years ago by
- Commit changed from 15ef91ca207671f216731692edf5e10d0d863fe1 to d7e2c5387d76886ffd9ba509ba78b178447b2192
- Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
d7e2c53 | Merge branch 'develop' into ticket/13125
|
comment:24 follow-up: ↓ 25 Changed 8 years ago by
- Status changed from needs_review to needs_work
- Work issues set to find OSX-specific cause of failure
comment:25 in reply to: ↑ 24 ; follow-up: ↓ 27 Changed 8 years ago by
Replying to rws:
What to do now? Since the problem seems to be related with RLF
, should we open a new ticket and redirect this to the new one?
comment:26 Changed 8 years ago by
My guess is that the problem is comparisons with infinity, I noticed some wonky behavior when I wrote the patch. Its tricky to debug since it apparently depends on the position of objects in memory (the fall-back comparison order).
comment:27 in reply to: ↑ 25 Changed 8 years ago by
- Status changed from needs_work to positive_review
- Work issues find OSX-specific cause of failure deleted
Replying to saludes:
Replying to rws: What to do now? Since the problem seems to be related with
RLF
, should we open a new ticket and redirect this to the new one?
If it happens on OSX only then it cannot be in this patch, so I'll set to positive. Now it depends on if people on OSX can reproduce the problem without this patch or not; by the above reasoning it should be possible. If so, please open a ticket. If not you should wait until this one is in Sage.
comment:28 Changed 8 years ago by
Um, I just see that the problem code doesn't even need this patch, so I'll go ahead and open that ticket myself.
comment:29 Changed 8 years ago by
Anything missing for this ticket being accepted?
comment:30 Changed 8 years ago by
Sorry, I wanted to have a look at the changes but haven't had the time yet.
comment:31 Changed 8 years ago by
- Branch changed from u/rws/ticket/13125 to u/vbraun/ticket/13125
comment:32 Changed 8 years ago by
- Commit changed from d7e2c5387d76886ffd9ba509ba78b178447b2192 to 142aa888f8dd21c2546d9680481bfbd9b82285ef
I've added some tests for comparison with infinity; these need to be fixed before the ticket is usable. One of the gems on my machine is
sage: RLF(0) < oo False
New commits:
142aa88 | add tests for comparison of infinity with other ring elements
|
comment:33 Changed 8 years ago by
See also #15004
comment:34 Changed 8 years ago by
- Description modified (diff)
comment:35 Changed 8 years ago by
There was some work in #14045 to fix comparison with float('inf')
but didn't go any further.
comment:36 Changed 8 years ago by
- Commit changed from 142aa888f8dd21c2546d9680481bfbd9b82285ef to fa497ee701f068e3980e458a519805b219b1b791
- Status changed from positive_review to needs_review
comment:37 Changed 8 years ago by
- Cc tscrim robertwb added
- Description modified (diff)
comment:38 Changed 8 years ago by
I don't like this change:
+ elif isinstance(x, sage.rings.real_mpfi.RealIntervalFieldElement):
+ if x.upper().is_infinity() or x.lower().is_infinity():
return self.gen()
since RIF(0, oo)
gets turned into infinity (where is very likely to not be):
sage: UnsignedInfinityRing(RIF(2, oo)) Infinity
I think we should follow the usual paradigm for RIF:
sage: RIF(2, 4) == 4 False sage: RIF(2, 4) <= 4 True sage: RIF(2, 4) < 4 False sage: RIF(2) == 2 True
So I would say this is wrong:
sage: RIF(2, oo) == oo True
and I would raise an error anytime we're converting something which is not directly equal to a (signed) infinity. For example:
sage: UnsignedInfinityRing(RIF(2, oo)) Infinity
should raise an error, but this would be okay:
sage: UnsignedInfinityRing(RIF(oo, oo)) Infinity
comment:39 Changed 8 years ago by
The question is not whether or not you like a pony, but if and how RIF should coerce into the infinity ring. The way Sage works is that everything that should be comparable with infinity can be coerced into the infinity ring, so if you ever compare with infinity the comparison is done there. If you don't have a coercion (e.g. RIF before this ticket) then you will get undesirable answers from the fallback comparison (=memory location).
So if = yes, the only question is how. Semi-infinite intervals can either coerce into infinity, or "less than infinity", or zero (the only elements of the infinity ring). Its pretty clear that anything not infinite is undesirable.
comment:40 Changed 8 years ago by
- Commit changed from fa497ee701f068e3980e458a519805b219b1b791 to 563a877c3d270be950aedb2e30c756f27f46051d
Branch pushed to git repo; I updated commit sha1. New commits:
563a877 | also handle conversion of symbolic infinity
|
comment:41 Changed 8 years ago by
I forgot that SR can also represent infinity and conversion to the infinity ring should work. For SR there is no coercion to the infinity ring since SR wants to handle its own infinities (in fact: the infinity ring coerces into SR).
Arguably that should be changed and SR also coerce into the infinity ring instead of the other way round. But then SR wouldn't be able to react to things like oo * x
. Downside of the current way is
sage: bool(SR(-1000) > oo), bool(SR(-1000) < oo) (False, False)
i.e. SR doesn't know how to decide this rather simple inequality. In any case, thats for another ticket.
comment:42 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:44 Changed 8 years ago by
- Commit changed from 563a877c3d270be950aedb2e30c756f27f46051d to cef5700b656a2e7affcd5783040041108966d152
Branch pushed to git repo; I updated commit sha1. New commits:
cef5700 | Merge branch 'develop' into t/13125/ticket/13125
|
comment:46 Changed 8 years ago by
- Commit changed from cef5700b656a2e7affcd5783040041108966d152 to f96c67ec2103455ab72783f4c4eb4484e588fdd5
Branch pushed to git repo; I updated commit sha1. New commits:
f96c67e | strip out grant acknowledgement
|
comment:47 Changed 8 years ago by
I've removed the grant acknowledgement and will put it whereever we agree on in https://groups.google.com/d/msg/sage-devel/_NtS2b8W3uo/BsBz6IcLn4cJ
comment:48 Changed 8 years ago by
- Reviewers changed from Ralf Stephan to Ralf Stephan, Peter Bruin
I'm mostly happy with the fixes related to infinity, although we are nowhere close to fixing all the bugs in #11506. Of the examples listed there, the following one is changed by this ticket:
sage: InfinityRing(CC(oo)) A positive finite number
This used to return +Infinity
, which is not perfect either, but is at least consistent with InfinityRing(UnsignedInfinity(oo))
. (I'd argue that both of these should probably be undefined, since complex and unsigned infinity are in no way more positive than negative.)
Could you fix the above example to return +Infinity
again?
I leave it to someone else to review the new code for real sets. It would have been better if the infinity-related stuff had been done on a separate ticket.
comment:49 Changed 8 years ago by
- Commit changed from f96c67ec2103455ab72783f4c4eb4484e588fdd5 to d7e2c5387d76886ffd9ba509ba78b178447b2192
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:50 Changed 8 years ago by
- Status changed from needs_review to positive_review
Agree that it should be a separate ticket. It just wasn't clear to me in the beginning that things were this messed up. I've split off the fixing-infinity part into #11506
comment:51 Changed 8 years ago by
- Status changed from positive_review to needs_info
I let this slip off, sorry Volker. I think there should be no coercion because there is no way to deal with these (semi)infinite intervals. However if we are forced to make this a coercion, then it should be less than infinity since my (very anecdotal) evidence says that most computations won't escape to oo
, but instead just don't have a good upper bound.
That being said, I think this should not be positively reviewed as it stands.
Do you think Nils would be a good person to ask about this, someone else, or go directly to sage-devel?
comment:52 Changed 8 years ago by
I've moved all infinity-related commits to #11506, let's move the discussion there.
No coercion means: comparison by memory location.
comment:53 Changed 8 years ago by
- Status changed from needs_info to needs_work
Okay, but the branch currently doesn't merge cleanly
comment:54 Changed 8 years ago by
Just to be clear (since Volker set this to positive review after moving the infinity-related stuff to #11506): it wasn't my intention to give a positive review except for that example. I haven't looked at the real sets code at all.
comment:55 Changed 8 years ago by
- Commit changed from d7e2c5387d76886ffd9ba509ba78b178447b2192 to 7b72a426674142e95b96ea1ba73aa85c108ff600
Branch pushed to git repo; I updated commit sha1. New commits:
7b72a42 | Merge branch 'develop' into t/13125/real_sets
|
comment:56 Changed 8 years ago by
- Status changed from needs_work to positive_review
comment:57 Changed 8 years ago by
OK, I didn't notice that the real sets code had already been reviewed.
comment:58 Changed 8 years ago by
- Commit changed from 7b72a426674142e95b96ea1ba73aa85c108ff600 to c8187460bc0e90c0b58713a5c55bc6b86895a12b
- Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:
e620d38 | rm global is_HyperellipticCurve
|
1932b64 | rm global is_{Expect,Gap,Singular}Element
|
3841cc7 | rm global is_Finite_Field, is_Finite_FieldElement
|
ae72be9 | rm global is_Graphics
|
f0ac47d | rm global is_ProjectiveSpace
|
bd2b01a | rm global is_QuadraticForm
|
fa34d62 | rm global is_Scheme
|
8ad8402 | rm global is_Morphism
|
b948874 | global is_*: delete deprecation warning
|
c818746 | fix merge conflict with #14329
|
comment:59 Changed 8 years ago by
- Status changed from needs_review to positive_review
comment:60 Changed 8 years ago by
- Branch changed from u/vbraun/ticket/13125 to c8187460bc0e90c0b58713a5c55bc6b86895a12b
- Resolution set to fixed
- Status changed from positive_review to closed
Patch?