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:  sage6.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/semiclosed 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 followup: ↓ 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 followup: ↓ 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 thirdparty 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 thirdparty 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 sage5.11 to sage5.12
comment:15 Changed 9 years ago by
 Milestone changed from sage6.1 to sage6.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/semiclosed 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 followup: ↓ 25 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to find OSXspecific cause of failure
comment:25 in reply to: ↑ 24 ; followup: ↓ 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 fallback comparison order).
comment:27 in reply to: ↑ 25 Changed 8 years ago by
 Status changed from needs_work to positive_review
 Work issues find OSXspecific 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. Semiinfinite 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 sage6.2 to sage6.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/sagedevel/_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 infinityrelated 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 fixinginfinity 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 sagedevel?
comment:52 Changed 8 years ago by
I've moved all infinityrelated 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 infinityrelated 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?