Equivalence test

[Peter Chervenski]

I made this function to test for the equivalence of two expressions. It doesn't really prove anything, but if the tests are many, the probability of it being wrong becomes negligible. Do such utility functions have a place in SymPy?

def equiv(a, b, ntests=15):
    """ Test if expression a is equivalent to b
    by comparing the results of many random numeric tests """
   
    # get the symbols
    sb_a = filter(lambda x: x.is_Symbol, a.atoms())
    sb_b = filter(lambda x: x.is_Symbol, b.atoms())
   
    sb = list(set(sb_a + sb_b))
   
    eq = True
    for i in xrange(ntests):
        k = dict(zip(sb, np.random.randn(len(sb))))
       
        r_a = a.subs( k )
        r_b = b.subs( k )
       
        # prove there is a difference        
        if (r_a - r_b)**2 > 1e-30: # not the same? the expressions are different
            eq = False
            break

    return eq

[Tim Lahey]

Having seen expressions that are hard to simplify into the same form, I'd say that it has a place in SymPy (there's even a utilities directory). That said, I'd probably suggest a name like nequiv similar to nsolve.

Cheers,

Tim.

> --
> 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.
> 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/58700b18-624c-4723-935a-dd71bb30d738%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Ondřej Čertík]

Hi Peter,

Absolutely. I've also implemented a similar function in one PR:

https://github.com/sympy/sympy/pull/8036/files?diff=unified#diff-2c9ef1ef2c82f5d5781d0d12e1fe4910R33

It was pointed out to me that we have similar machinery here already:

https://github.com/sympy/sympy/blob/master/sympy/utilities/randtest.py#L43

This should be unified and put into sympy. We can call it
"zero_numerical" or something like that ("test_numerically", ...).
Mathematica calls this PossibleZeroQ (though I think it does both
symbolic an numerical tests).

Look at the implementation in my PR --- you should allow the user to
specify the range (I call it [a, b]) as well as the precision. I think
we can perhaps just test for 0, and then your "equiv" can just call
this zero testing function for a-b.

Ondrej

[Ondřej Čertík]

Actually, in my implementation I choose random integers from [-a, a]
and then test an interval
[-a/b, a/b]. That way you will get rational numbers, as opposed to
only integers (that could hide differences).

Ondrej

[Aaron Meurer]

Doesn't expr.equals also do something similar to this?

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.
> 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/CADDwiVDnybsk6Ke-ocGoPd%2BuB_S7v%3DDCeSgvGTR1JFTXiw5F_g%40mail.gmail.com.

[Ondřej Čertík]

On Mon, Feb 9, 2015 at 3:37 PM, Aaron Meurer <asme...@gmail.com> wrote:
> Doesn't expr.equals also do something similar to this?

No, that uses symbolics (thus it is not able to check complex
expressions or it will be slow).

Btw, you already asked this exact question here:

https://github.com/sympy/sympy/pull/8036#issuecomment-55969269

and my answer is right below it.

Ondrej

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6JV%3D_umM9hOnn446tz7Hz3bAL2g1%2B7TuqhYbdG1hmTCGg%40mail.gmail.com.

[Aaron Meurer]

On Mon, Feb 9, 2015 at 5:11 PM, Ondřej Čertík <ondrej...@gmail.com> wrote:
> On Mon, Feb 9, 2015 at 3:37 PM, Aaron Meurer <asme...@gmail.com> wrote:
>> Doesn't expr.equals also do something similar to this?
>
> No, that uses symbolics (thus it is not able to check complex
> expressions or it will be slow).
>
> Btw, you already asked this exact question here:
>
> https://github.com/sympy/sympy/pull/8036#issuecomment-55969269
>
> and my answer is right below it.

Heh.

But I seem to remember equals plugging in values. Maybe it used to do
it, but doesn't any more?

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CADDwiVBH3KHccMaR1dX4Uz4jAMzXqBXaaxGHz%3D6ZmZq0XtucTA%40mail.gmail.com.

[Ondřej Čertík]

On Mon, Feb 9, 2015 at 4:15 PM, Aaron Meurer <asme...@gmail.com> wrote:
> On Mon, Feb 9, 2015 at 5:11 PM, Ondřej Čertík <ondrej...@gmail.com> wrote:
>> On Mon, Feb 9, 2015 at 3:37 PM, Aaron Meurer <asme...@gmail.com> wrote:
>>> Doesn't expr.equals also do something similar to this?
>>
>> No, that uses symbolics (thus it is not able to check complex
>> expressions or it will be slow).
>>
>> Btw, you already asked this exact question here:
>>
>> https://github.com/sympy/sympy/pull/8036#issuecomment-55969269
>>
>> and my answer is right below it.
>
> Heh.
>
> But I seem to remember equals plugging in values. Maybe it used to do
> it, but doesn't any more?

The code is here:

https://github.com/sympy/sympy/blob/e015652bf34987128bca3176d1c939fbd0d486cf/sympy/core/expr.py#L563

Ondrej

[Aaron Meurer]

I'm unclear what this line is doing
https://github.com/sympy/sympy/blob/e015652bf34987128bca3176d1c939fbd0d486cf/sympy/core/expr.py#L613.
It looks like it evaluates it, at least in some cases.

Probably Chris Smith could give a more definite answer.

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.
> 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/CADDwiVCB2Ftb_bAQUNnh2F%3DeHZA_Oy1dOrTn7W5ApkfATfOpsQ%40mail.gmail.com.

[Chris Smith]

At that point in the routine we know the expression is constant so either it is zero or it is some other constant. So a set or random values for symbols is computed and if it is *not* zero we have an answer, otherwise we have to work harder to try *prove* that it's zero.

See also the discussion in https://github.com/sympy/sympy/issues/8516 and the routine I wrote there in response at

https://github.com/sympy/sympy/pull/8561

/c

[Joachim Durchholz]

Am 09.02.2015 um 20:40 schrieb Ondřej Čertík:
>We can call it
> "zero_numerical" or something like that ("test_numerically", ...).
> Mathematica calls this PossibleZeroQ

"stochastically_zero", maybe?
To highlight that it's a probabilistic test, not a
guaranteed-to-be-correct one.