Opened 7 years ago

Closed 5 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) Commit: c8187460bc0e90c0b58713a5c55bc6b86895a12b
Dependencies: Stopgaps:

Description (last modified by vbraun)

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)

trac_13125_real_set.patch (32.3 KB) - added by vbraun 6 years ago.
Initial patch
trac_13125_realsets.patch (26.2 KB) - added by ares 6 years ago.
Patch for realsets.py
trac_13125_misc.patch (21.2 KB) - added by vbraun 6 years ago.
Updated patch

Download all attachments as: .zip

Change History (63)

comment:1 Changed 7 years ago by ares

  • Description modified (diff)

comment:2 Changed 7 years ago by ares

  • Description modified (diff)

comment:3 follow-up: Changed 7 years ago by kcrisman

Patch?

comment:4 in reply to: ↑ 3 Changed 7 years ago by ares

Replying to kcrisman:

Patch?

uploaded

Changed 6 years ago by vbraun

Initial patch

comment:5 Changed 6 years ago by vbraun

  • Authors changed from Jordi Saludes and Ares Ribó to Volker Braun
  • 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 6 years ago by vbraun

  • 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 6 years ago by kcrisman

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 6 years ago by novoselt

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 6 years ago by kcrisman

Yes, I was being silly :)

Changed 6 years ago by ares

Patch for realsets.py

comment:10 Changed 6 years ago by ares

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 6 years ago by ares

  • Authors changed from Volker Braun to Volker Braun , Jordi Saludes , Ares Ribó
  • Description modified (diff)

Changed 6 years ago by vbraun

Updated patch

comment:12 follow-up: Changed 6 years ago by vbraun

  • 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 6 years ago by ares

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.

Last edited 6 years ago by ares (previous) (diff)

comment:14 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:15 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:16 Changed 5 years ago by rws

  • 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 5 years ago by rws

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

308d16bImplement RealSet - finite unions of open/closed/semi-closed subsets of the real line.
a861752Further improvements to RealSet
15ef91cTrac #13125: reviewer's patch: fix typos, add module to set refman

comment:18 Changed 5 years ago by vbraun

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 5 years ago by vbraun

In fact, only fails on OSX 10.9.2 but works on 10.6... weird.

comment:20 Changed 5 years ago by saludes

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 5 years ago by rws

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
Last edited 5 years ago by rws (previous) (diff)

comment:22 Changed 5 years ago by saludes

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))
[]
Last edited 5 years ago by saludes (previous) (diff)

comment:23 Changed 5 years ago by git

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

d7e2c53Merge branch 'develop' into ticket/13125

comment:24 follow-up: Changed 5 years ago by rws

  • 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: Changed 5 years ago by 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?

comment:26 Changed 5 years ago by vbraun

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 5 years ago by rws

  • 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 5 years ago by rws

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 5 years ago by rws

Anything missing for this ticket being accepted?

comment:30 Changed 5 years ago by vbraun

Sorry, I wanted to have a look at the changes but haven't had the time yet.

comment:31 Changed 5 years ago by vbraun

  • Branch changed from u/rws/ticket/13125 to u/vbraun/ticket/13125

comment:32 Changed 5 years ago by vbraun

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

142aa88add tests for comparison of infinity with other ring elements

comment:33 Changed 5 years ago by vbraun

See also #15004

comment:34 Changed 5 years ago by vbraun

  • Description modified (diff)

comment:35 Changed 5 years ago by vbraun

There was some work in #14045 to fix comparison with float('inf') but didn't go any further.

comment:36 Changed 5 years ago by git

  • Commit changed from 142aa888f8dd21c2546d9680481bfbd9b82285ef to fa497ee701f068e3980e458a519805b219b1b791
  • 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:

e4303eafix element constructor of the infinity ring
fa497eehandle conversion of RIF into InfinityRing

comment:37 Changed 5 years ago by vbraun

  • Cc tscrim robertwb added
  • Description modified (diff)

comment:38 Changed 5 years ago by tscrim

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 5 years ago by vbraun

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 5 years ago by git

  • Commit changed from fa497ee701f068e3980e458a519805b219b1b791 to 563a877c3d270be950aedb2e30c756f27f46051d

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

563a877also handle conversion of symbolic infinity

comment:41 Changed 5 years ago by vbraun

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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:43 Changed 5 years ago by rws

  • Status changed from needs_review to needs_work

Merge conflicts.

comment:44 Changed 5 years ago by git

  • Commit changed from 563a877c3d270be950aedb2e30c756f27f46051d to cef5700b656a2e7affcd5783040041108966d152

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

cef5700Merge branch 'develop' into t/13125/ticket/13125

comment:45 Changed 5 years ago by vbraun

  • Status changed from needs_work to needs_review

Fixed

comment:46 Changed 5 years ago by git

  • Commit changed from cef5700b656a2e7affcd5783040041108966d152 to f96c67ec2103455ab72783f4c4eb4484e588fdd5

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

f96c67estrip out grant acknowledgement

comment:47 Changed 5 years ago by vbraun

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 5 years ago by pbruin

  • 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 5 years ago by git

  • 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 5 years ago by vbraun

  • 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 5 years ago by tscrim

  • 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 5 years ago by vbraun

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 5 years ago by tscrim

  • Status changed from needs_info to needs_work

Okay, but the branch currently doesn't merge cleanly

comment:54 Changed 5 years ago by pbruin

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 5 years ago by git

  • Commit changed from d7e2c5387d76886ffd9ba509ba78b178447b2192 to 7b72a426674142e95b96ea1ba73aa85c108ff600

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

7b72a42Merge branch 'develop' into t/13125/real_sets

comment:56 Changed 5 years ago by vbraun

  • Status changed from needs_work to positive_review

comment:57 Changed 5 years ago by pbruin

OK, I didn't notice that the real sets code had already been reviewed.

comment:58 Changed 5 years ago by git

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

e620d38rm global is_HyperellipticCurve
1932b64rm global is_{Expect,Gap,Singular}Element
3841cc7rm global is_Finite_Field, is_Finite_FieldElement
ae72be9rm global is_Graphics
f0ac47drm global is_ProjectiveSpace
bd2b01arm global is_QuadraticForm
fa34d62rm global is_Scheme
8ad8402rm global is_Morphism
b948874global is_*: delete deprecation warning
c818746fix merge conflict with #14329

comment:59 Changed 5 years ago by pbruin

  • Status changed from needs_review to positive_review

comment:60 Changed 5 years ago by vbraun

  • Branch changed from u/vbraun/ticket/13125 to c8187460bc0e90c0b58713a5c55bc6b86895a12b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.