fix(sets): remove intersect fallback in is_subset #26872
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
✅ Hi, I am the SymPy bot. I'm here to help you write a release notes entry. Please read the guide on how to write release notes. Your release notes are in good order. Here is what the release notes will look like:
This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.14. Click here to see the pull request description that was parsed. |
|
This is ready for review. |
|
Benchmark results from GitHub Actions Lower numbers are good, higher numbers are bad. A ratio less than 1 Significantly changed benchmark results (PR vs master) Significantly changed benchmark results (master vs previous release) Full benchmark results can be found as artifacts in GitHub Actions |
|
This one is also still ready for review. |
The Set.is_subset method would fallback on computing the intersection of two sets. This is backwards though because a query like is_subset should be resolved without creating new sets and it should be possible for the intersection code to check whether one set is a subset of another rather than the other way round. This commit removes the intersect fallback and adds enough direct handlers for is_subset to pass the existing test suite.
Using != is error-prone because in SymPy == and != are for structural equality rather than mathematical equality. It is safe to assume that A == B means that A and B are mathematically equivalent but the converse that A != B implies that A and B are not mathematically equivalent does not hold.
The imageset intersection handler was overly complex and made faulty
assumptions about the expression to be inverted. This commit simplifies
the intersect handler so that it is limited to inverting linear
transformations e.g.:
{a*x + b: x in S} n [c, d]
is now transformed to:
{a*x + b: x in (S n [(c - b)/a, (d - b)/a])}
So if the base set S can compute an intersection with an interval, then
the imageset intersection can be expressed in terms of that.
oscarbenjamin
force-pushed
the
pr_is_subset_intersect_fallback
branch
from
cd7bbff to
3d94ebd
Compare
oscarbenjamin
commented
Nov 8, 2024
Comment on lines
-755
to
+761
| assert dumeq(solveset(Eq(sin(Abs(x)), 1), x, domain=S.Reals), Union( | ||
| Intersection(Interval(0, oo), Union( | ||
| Intersection(ImageSet(Lambda(n, 2*n*pi + 3*pi/2), S.Integers), | ||
| Interval(-oo, 0)), | ||
| Intersection(ImageSet(Lambda(n, 2*n*pi + pi/2), S.Integers), | ||
| Interval(0, oo)))))) | ||
|
|
||
| eq = Eq(sin(Abs(x)), 1) | ||
| sol = Union( | ||
| ImageSet(Lambda(n, -2*n*pi - pi/2), Range(0, oo, 1)), | ||
| ImageSet(Lambda(n, 2*n*pi + pi/2), Range(0, oo, 1)) | ||
| ) | ||
| assert dumeq(solveset(eq, x, domain=S.Reals), sol) |
There was a problem hiding this comment.
The previous answer here evaluates to:
In [1]: Union(
...: Intersection(Interval(0, oo), Union(
...: Intersection(ImageSet(Lambda(n, 2*n*pi + 3*pi/2), S.Integers),
...: Interval(-oo, 0)),
...: Intersection(ImageSet(Lambda(n, 2*n*pi + pi/2), S.Integers),
...: Interval(0, oo)))))
Out[1]:
⎧ π │ ⎫
[0, ∞) ∩ ⎨2⋅π⋅n + ─ │ n ∊ ℤ⎬
⎩ 2 │ ⎭This is incorrect because there also negative solutions for x. This is due to a bug in the intersection handler for imageset and interval that is fixed here so that the answer is:
In [2]: solveset(Eq(sin(Abs(x)), 1), x, domain=S.Reals)
Out[2]:
⎧ π │ ⎫ ⎧ π │ ⎫
⎨-2⋅n⋅π - ─ │ n ∊ {0, 1, …}⎬ ∪ ⎨2⋅n⋅π + ─ │ n ∊ {0, 1, …}⎬
⎩ 2 │ ⎭ ⎩ 2 │ ⎭
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
The Set.is_subset method would fallback on computing the intersection of two sets. This is backwards though because a query like is_subset should be resolved without creating new sets and it should be possible for the intersection code to check whether one set is a subset of another rather than the other way round. This commit removes the intersect fallback and adds enough direct handlers for is_subset to pass the existing test suite.
References to other Issues or PRs
Brief description of what is fixed or changed
Other comments
Release Notes
Set.is_subsethandling routine no longer callsSet.intersect. Additional direct handlers have been added foris_subsetto make this not necessary any more.