Simplification question

[Mike Witt]

Is it typical to have to "fiddle around" with different
forms of an expression to get it to simplify? For example:

In [7]: from sympy import sqrt

In [8]: foo=-sqrt(-2*sqrt(2)+3)+sqrt(2*sqrt(2)+3)

In [9]: print foo
-sqrt(-2*sqrt(2) + 3) + sqrt(2*sqrt(2) + 3)

In [10]: print foo.simplify()
-sqrt(-2*sqrt(2) + 3) + sqrt(2*sqrt(2) + 3)

In [11]: print (foo**2).expand()
-2*sqrt(-2*sqrt(2) + 3)*sqrt(2*sqrt(2) + 3) + 6

In [12]: print (foo**2).expand().simplify()
4

Or is there some kind of "general strategy" that will
always work (assuming there is clearly a simplification
possible, like an integer as above)?

-Mike

[Matthew Rocklin]

Short answer, "No."

In full generality what you're describing is actually a challenging search problem.  We've thought about attacking this problem more rigorously in SymPy but haven't gotten around to it except in a few small cases like trig simplification (see fu function).

-Mike

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/1400536494.2532.18%40Vector.
For more options, visit https://groups.google.com/d/optout.

[Aaron Meurer]

In this case, there is a simplification function that will do it, sqrtdenest:

In [3]: sqrtdenest(foo)
Out[3]: 2

In general, there is no single algorithm for simplification (indeed,
it's not even an easy concept to define), but simplify() tries to do
its best. The more you know about the steps that are required to do
the simplification you want, or the type of expression you have, the
better you can apply individual simplification functions to get what
you want.

In this case, though, I would consider it a bug that simplify() did
not try sqrtdenest.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to sympy+un...@googlegroups.com.

[Mike Witt]

On 05/19/2014 08:13:46 PM, Aaron Meurer wrote:
> In this case, there is a simplification function that will do it,
> sqrtdenest:
>
> In [3]: sqrtdenest(foo)
> Out[3]: 2

Thanks. I can use that in a number of places!

> https://groups.google.com/d/msgid/sympy/CAKgW%3D6LKVAZ5OT-z%2B_asPcLB97wU2GmtqNRxT1ws2Ga9779XuQ%40mail.gmail.com.

[Matthew Rocklin]

Just to increase awareness we do have a sexy search mechanism in SymPy living in sympy.strategies.tree (by my definition of sexiness). 

In [1]: from sympy.strategies.tree import greedy, brute

In [2]: funcs = [simplify, expand, fu, powsimp, sqrtdenest]

In [3]: objective = lambda x: len(str(x))  # minimize string length

In [4]: megasimp = greedy((funcs, funcs), objective)

megasimp tries each of simplify, expand, fu, powsimp, and sqrtdenest, then selects the result that minimizes the object (string length).  It then tries each of those functions again on the result (this is the result of including funcs twice in a tuple.)  We could swap out greedy for brute and it would try all 5 squared combinations.

In [5]: foo = -sqrt(-2*sqrt(2)+3)+sqrt(2*sqrt(2)+3)

In [6]: megasimp(foo)

Out[6]: 2

Of course, this is a fairly dumb example, because just using sqrtdenest once is the right answer.  In principle though we could have defined much more sophisticated function evaluation trees.  For anyone still reading, here is the docstring to greedy

Execute a strategic tree.  Select alternatives greedily

Trees

-----

Nodes in a tree can be either

function - a leaf

list     - a selection among operations

tuple    - a sequence of chained operations

Textual examples

----------------

Text: Run f, then run g, e.g. ``lambda x: g(f(x))``

Code: ``(f, g)``

Text: Run either f or g, whichever minimizes the objective

Code: ``[f, g]``

Textx: Run either f or g, whichever is better, then run h

Code: ``([f, g], h)``

Text: Either expand then simplify or try factor then foosimp. Finally print

Code: ``([(expand, simplify), (factor, foosimp)], print)``

Objective

---------

"Better" is determined by the objective keyword.  This function makes

choices to minimize the objective.  It defaults to the identity.

Example

-------

>>> from sympy.strategies.tree import greedy

>>> inc    = lambda x: x + 1

>>> dec    = lambda x: x - 1

>>> double = lambda x: 2*x

>>> tree = [inc, (dec, double)] # either inc or dec-then-double

>>> fn = greedy(tree)

>>> fn(4)  # lowest value comes from the inc

5

>>> fn(1)  # lowest value comes from dec then double

0

This funcion selects between options in a tuple.  The result is chosen that

minimizes the objective function.

>>> fn = greedy(tree, objective=lambda x: -x)  # maximize

>>> fn(4)  # highest value comes from the dec then double

6

>>> fn(1)  # highest value comes from the inc

2

Greediness

----------

This is a greedy algorithm.  In the example:

    ([a, b], c)  # do either a or b, then do c

the choice between running ``a`` or ``b`` is made without foresight to c

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6LKVAZ5OT-z%2B_asPcLB97wU2GmtqNRxT1ws2Ga9779XuQ%40mail.gmail.com.

[Mike Witt]

OK, very good to know.

On 05/19/2014 08:40:38 PM, Matthew Rocklin wrote:
> Just to increase awareness we *do* have a sexy search mechanism in

> https://groups.google.com/d/msgid/sympy/CAJ8oX-G-PDM%2BrPsq5MfRLX0zhkpEdLjCPgGdaQb80ii9v47e-g%40mail.gmail.com.