RecursionError _solve _tsolve _vsolve in expression involving Mod and floor #24368
Comments
|
I have a few more repros from different models but on inspection of the stack I'm guessing they're all the same deal. |
|
A check is made to see if the |
|
It's really just the big mod factor that produces the recursion error. The other factor isn't implemented (which doesn't leave much hope that the other one would actually produce an answer): >>> sympy.solve(floor(s2/2 - S(1)/2) + 1, s2)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Users/aaronmeurer/Documents/Python/sympy/sympy/./sympy/solvers/solvers.py", line 1144, in solve
solution = _solve(f[0], *symbols, **flags)
File "/Users/aaronmeurer/Documents/Python/sympy/sympy/./sympy/solvers/solvers.py", line 1690, in _solve
raise NotImplementedError('\n'.join([msg, not_impl_msg % f]))
NotImplementedError:
No algorithms are implemented to solve equation floor(s2/2 - 1/2) + 1Solving >>> reduce_inequalities(((s2 - 1)/2 < 2) & ((s2 - 1)/2 >= 1))
False |
|
I found a very simple mod that induces the infinite loop: |
Solving >>> reduce_inequalities([(s-1)/2>=-1, (s2-1)/2<1])
(-1 <= x) & (x < 2) |
|
Ah, I didn't realize So it seems the following steps are needed to make this work:
What's the best way to achieve the last item? A set of reduced inequalities might not represent a finite set, of course, so maybe this is a better fit for It seems this is possible with >>> reduce_inequalities([(s-1)/2>=-1, (s-1)/2<1]).as_set().intersection(Integers)
Range(-1, 3, 1)Actually this is wrong (it should be The result being a Regarding the actual recursion error. _tsolve is stuck in an infinite loop recursively passing the same expression to itself. It looks like the problem is that it tries to recursively rewrite the expression as If we can fix that, then comes the hard part, which is making things like >>> simplify(S("Mod(floor(s2/2 - 1/2)**2/(floor(s2/2 - 1/2) + 1) + 2*floor(s2/2 - 1/2)/(floor(s2/2 - 1/2) + 1) + 1/(floor(s2/2 - 1/2) + 1), 1)"))
Mod(floor(s2/2 - 1/2), 1)However, This really ought to simplify away completely to just 0, since floor() is always an integer. So in fact, the solution set to this particular equation is all real numbers (you can verify this by substituting random values). @ezyang is this is intended. Is being able to solve the other factor ( |
|
I don't think we care too much about getting solutions here, we would like sympy to try some easy solving and if it fails no biggy, we will keep going. |
|
Cc @Chillee |
It's ok: Range, like range, does not include the end point:
|
Setting it to False (it is True by default) disables rewriting cases that create unevaluated Pow/exp objects. This is used in solve to avoid a recursion error (fixes sympy#24368) which is caused by the call to rewrite(exp) in solve, which then gets rewritten back to a Pow by Poly. There doesn't appear to be any benefit to solving to rewrite powers with nonsymbolic exponents to exp.
|
Fix for the recursion error is at #24549. Let's open new issues for the other things identified above, like getting the actual solutions to work. |
Oh my bad. I was misled by your comment that said the endpoint should be 2 but |
Setting it to False (it is True by default) disables rewriting cases that create unevaluated Pow/exp objects. This is used in solve to avoid a recursion error (fixes sympy#24368) which is caused by the call to rewrite(exp) in solve, which then gets rewritten back to a Pow by Poly. There doesn't appear to be any benefit to solving to rewrite powers with nonsymbolic exponents to exp.
|
The problem is that this code is flakey: sympy/sympy/solvers/solvers.py Lines 2750 to 2752 in f4176c7 I have seen this cause recursion error in other examples as well, not necessarily involving evaluate=False. This runs the risk of infinite recursion because it presumes that just because rewrite changed the expression in some way we can recurse again. The new expression should be equivalent to the one we started with though so there is a high chance that we will get back to the same place with the same expression because of any code that tries to canonicalise the form of the expression.
If possible we should just remove these lines: diff --git a/sympy/solvers/solvers.py b/sympy/solvers/solvers.py
index 5c0f3ea..2ebbaa7 100644
--- a/sympy/solvers/solvers.py
+++ b/sympy/solvers/solvers.py
@@ -2747,9 +2747,6 @@ def equal(expr1, expr2):
elif lhs.func == LambertW:
return _vsolve(lhs.args[0] - rhs*exp(rhs), sym, **flags)
- rewrite = lhs.rewrite(exp)
- if rewrite != lhs:
- return _vsolve(rewrite - rhs, sym, **flags)
except NotImplementedError:
pass
That change passes all except two of the not slow tests in solvers. The failing examples are: assert solve(5**(x/2) - 2**(3/x)) == [-b, b]
assert solve(sin(x) + tan(x)) == [0, -pi, pi, 2*pi]Both give For one thing it is possible to be specific about what types you want to rewrite: In [11]: (1/x + cos(x)).rewrite(exp)
Out[11]:
ⅈ⋅x -ⅈ⋅x
ℯ ℯ -log(x)
──── + ───── + ℯ
2 2
In [12]: (1/x + cos(x)).rewrite([cos, sin], exp)
Out[12]:
ⅈ⋅x -ⅈ⋅x
ℯ ℯ 1
──── + ───── + ─
2 2 xAlternatively other rewrites can be used e.g.: For the case of two exponentials: In [19]: (5**(x/2) - 2**(3/x)).rewrite(exp)
Out[19]:
3⋅log(2) x⋅log(5)
──────── ────────
x 2
- ℯ + ℯ Here we can just check if we have In [30]: solve(log(5)*(x/2) - log(2)*3/x)
Out[30]:
⎡ ________ ________⎤
⎢-√6⋅╲╱ log(2) √6⋅╲╱ log(2) ⎥
⎢───────────────, ─────────────⎥
⎢ ________ ________ ⎥
⎣ ╲╱ log(5) ╲╱ log(5) ⎦Of course the full solution set here is infinite and corresponds to solutions of |
|
My thinking is that we do want to keep the exponential rewriting for trig solving, since implementing a trig solver that works without rewriting will likely just be a lot of work that would ultimately be duplicated. We could limit the rewrite to only rewrite trig functions, although that could be a regression if we miss a function, or if there is some custom user function that relied on being able to work with solve with an For the non-base e exponentials, I think we just need to fix the code that does the inversion so that it works the same way. It looks like there is a branch here that produces a different result for sympy/sympy/solvers/solvers.py Lines 3162 to 3171 in f4176c7 |
This can lead to recursion errors (e.g., sympy#24368) because it is too easy for the expression to get rewritten back to the way it was again in a recursive call. This still has some test failures. We need to handle trigonometric equations in some other way (e.g., by doing a more targeted rewrite of them).
I think that a better way to do this is by rewriting to a system of polynomial equations: In [24]: eq = sin(x) + cos(x)
In [25]: solve(eq, x)
Out[25]:
⎡-π ⎤
⎢───⎥
⎣ 4 ⎦
In [26]: s, c = symbols('s, c')
In [27]: sols = solve([s + c, s**2 + c**2 - 1], [s, c], dict=True)
In [28]: sols
Out[28]:
⎡⎧ -√2 √2⎫ ⎧ √2 -√2 ⎫⎤
⎢⎨c: ────, s: ──⎬, ⎨c: ──, s: ────⎬⎥
⎣⎩ 2 2 ⎭ ⎩ 2 2 ⎭⎦
In [29]: [{x: atan2(sol[s], sol[c])} for sol in sols]
Out[29]:
⎡⎧ 3⋅π⎫ ⎧ -π ⎫⎤
⎢⎨x: ───⎬, ⎨x: ───⎬⎥
⎣⎩ 4 ⎭ ⎩ 4 ⎭⎦
In [30]: [checksol(eq, sol) for sol in _]
Out[30]: [True, True] |
|
I implemented the rewrite in terms of just trig functions for now. I'll need to look into how hard it is to implement your idea with the existing solve helpers. |
This makes some tests still work similar to how they did before, but still leaves sympy#24368 fixed. However, it does change the behavior of some of the slow Lambert W tests, so this approach may still require some thought.
This can lead to infinite recursion. Fixes sympy#24368
|
OK, third attempt here. This is the simplest possible fix for this issue #24999, namely, just rebuild the expression after rewriting to filter out any evaluate=False rewrites (I've only applied it in this one place in the solve code; a more general way to do this is to add evaluate=True to |
This expression was extracted from some PyTorch model shape expressions involving SymPy. We have discovered the expression in question is zero, and we would like to know if s2 is now statically known. We don't mind if solving says not implemented, or if there are no solutions (there are probably no solutions). However, the equation instead stack overflows.
Fragment of the backtrace:
Reproduces on 1fbd995 (master at time of writing)
The text was updated successfully, but these errors were encountered: