# Faster way to test if an expression equals zero

I want to test if expressions (mix of variables, functions and numbers) are zero valued, as fast as possible, and PossibleZeroQ is sometimes very slow. One solution I found was to substitute the variables for random reals and test if the value of the substituted expression is less than, say, $0.0001$.

It works good, but maybe there are other solutions out there.

I know it can cause some wrong answers, but what is most important is the speed, since I can check the false positive later with PossibleZeroQ.

Can you think of an algorithm that can perform fast zero value tests in detriment of some loss of accuracy?

Edit:

I'll post my algorithm here:

TestZeroValuedExpression[expression_,symbolslist_]:=Module[{numericvalue},
Quiet[TimeConstrained[If[Check[
numericvalue=N[Expand[expression/.Table[symbolslist[[i]]->RandomReal[{1,2}],{i,Length[symbolslist]}]]];
,False]=!=False,
If[Abs[numericvalue]>0.00001,False,PossibleZeroQ[expression]],
PossibleZeroQ[expression]
],3,False]]
];

-
It would be constructive if you demonstrated expressions making PossibleZeroQ work very slowly. Look e.g. here Most efficient way to determine conclusively whether an algebraic number is zero. PossibleZeroQ won all those tests. –  Artes Sep 11 '13 at 20:19
Maybe I was not very clear, but I want to test a lot of expressions per second, the more, the better. With the algorithm I suggested, I test about 300 expressions per second. With PossibleZeroQ, this drops to about 10 per second (using TimeConstrained for 0.5 seconds, otherwise this gets even worse, or just freezes). –  Giovanni Sep 11 '13 at 20:25
Perhaps you should try something like combinations of N and Chop[ N@expr_, delta] e.g. test[expr_, a_] := Chop[ N[expr /. x :> RandomReal[{-a, a}]], a] –  Artes Sep 11 '13 at 21:08
I'll test that suggestion. Thanks –  Giovanni Sep 11 '13 at 21:15
If you have say rational functions with sign changes and coefficients modestly large, and if your substituted numbers are machine doubles so precision tracking is not done, then cancellation error could give you false negatives. –  Daniel Lichtblau Sep 11 '13 at 23:45

Another improved version

TestConstantValuedExpression[expression_,zerovaluetest_]:=Module[{randomvaluestestresult,expressionrandomvalue,previousexpressionrandomvalue,symbolreplacementlist,extremesdifferencetestvalue},
randomvaluestestresult=True;
previousexpressionrandomvalue=False;
Quiet[
Do[
Block[{$MaxExtraPrecision=Infinity}, symbolreplacementlist={_->False}; TimeConstrained[ While[!FreeQ[$Assumptions/.symbolreplacementlist,False],symbolreplacementlist=Table[symbolslist[[dvi]]->RandomChoice[{-1,1}]*10^Round[RandomVariate[StudentTDistribution[2]]],{dvi,Length[symbolslist]}]]
,0.2,nskippedsymbolreplacementlists++;Continue[]];
TimeConstrained[
expressionrandomvalue=Check[N[expression/.symbolreplacementlist],Continue[]];
,0.2,nskippedexpressionrandomvalues++;Continue[]];
];
If[previousexpressionrandomvalue=!=False,
If[Chop[expressionrandomvalue-previousexpressionrandomvalue,10^-4]=!=0,randomvaluestestresult=False;Break[],previousexpressionrandomvalue=expressionrandomvalue];
,previousexpressionrandomvalue=expressionrandomvalue];
,{60}];
If[randomvaluestestresult,
extremesdifferencetestvalue=Chop[TimeConstrained[Minimize[{expression,$Assumptions},symbolslist][[1]],60,0]-TimeConstrained[Maximize[{expression,$Assumptions},symbolslist][[1]],60,0],10^-4];
If[extremesdifferencetestvalue===0||extremesdifferencetestvalue==={0,0},
If[zerovaluetest,TimeConstrained[PossibleZeroQ[FullSimplify[expression]],360,False],True]
,False]
,False]
]
];

-

Ok, posting my version here. It has 0.1 seconds to test, otherwise returns false. I am assuming that if it takes longer than that, then the expression being tested is too complex (for my problem) and is not useful.

TestZeroValuedExpression[expression_,symbolslist_]:=Module[{expressionrandomvalue},
Quiet[TimeConstrained[If[Check[
expressionrandomvalue=Chop[N[expression/.Table[symbolslist[[i]]->RandomInteger[{-3,3}],{i,Length[symbolslist]}]]];
,False]=!=False,
If[expressionrandomvalue!=0,False,PossibleZeroQ[expression]],
PossibleZeroQ[expression]
],0.1,False]]
];

-