Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I need to check an algebraic number for membership in a list of algebraic numbers. The numbers can be expressed in different forms (combinations of radicals, Root objects, trig functions), but the check should be exact. Now I use the following code:

ContainsAlgebraicQ[list_, a_] := 
  MatchQ[Intersection[ list, {a}, SameTest -> (MinimalPolynomial[#1 - #2] === (#&) &)], {_}]

but in some cases evaluation of MinimalPolynomial takes significant time, although I only want to check the difference for zero. Is there a better approach for my task?

share|improve this question
    
PossibleZeroQ might be of some help. –  Spawn1701D Jun 5 '13 at 19:46
    
Consider MemberQ[{Sqrt[2], Sqrt[3], Sin[\[Pi]/5], GoldenRatio, Root[#^3 - 2 &, 1]}, x_ /; RootReduce[x - 2^(1/3)] == 0]... –  J. M. Jun 5 '13 at 19:47
    
I'd do this with PossibleZeroQ[ # - a, "ExactAlgebraics"]@list, or just MemberQ[PossibleZeroQ[ #, Method -> "ExactAlgebraics"]& @ list, True]. This post is closely related: Most efficient way to determine conclusively whether an algebraic number is zero –  Artes Jun 5 '13 at 21:42
add comment

2 Answers 2

up vote 4 down vote accepted

PossibleZeroQ[ #, Method -> "ExactAlgebraics"] provides the most efficient and exact test whether two algebraics are equal, (see e.g. Most efficient way to determine conclusively whether an algebraic number is zero for some benchmarks). It is Listable so we can define the following function:

ContainsAlgebraicQ[list_, a_] := 
    MemberQ[PossibleZeroQ[list - a, Method -> "ExactAlgebraics"], True]

E.g. check if 1 + Sqrt[3] is an element of

list = { Root[4 + 2 #1^4 + #1^8 &, 8], 
         (Sqrt[2] + Sqrt[3] + Sqrt[6] + 3)/Sqrt[5 + 2 Sqrt[6]],
         ((7 - 2 I)/(1 + I Sqrt[2]) + (4 + 14 I)/(Sqrt[2] + 2 I) - 8 + 2 I)^(1/4) };

ContainsAlgebraicQ[ list, 1 + Sqrt[3]]
True

but

ContainsAlgebraicQ[ list, Root[4 + 2 #1^4 + #1^8 &, 7]]
False

and of course

ContainsAlgebraicQ[ list, Root[4 + 2 #1^4 + #1^8 &, 8]]
True
share|improve this answer
    
Thanks! Based on my observations of how this code works, I assume that trig functions of rational multiples of π are not considered explicit algebraics by Mathematica. So I added a step that invokes RootReduce on expressions containing any trig functions before passing them to PossibleZeroQ. Please let me know if you are aware of a better approach. –  Vladimir Reshetnikov Jun 6 '13 at 1:32
    
I think you need not to use RootReduce before PossibleZeroQ. Though Daniel Lichtblau has been surprised that PossibleZeroQ[ #, Method -> "ExactAlgebraics"]& worked for non-explicit algebraics. But for a more reliable approach it might be safer. –  Artes Jun 6 '13 at 9:54
add comment

If list has sufficiently many repeated subexpressions, it becomes efficient to convert the elements to explicit algebraic numbers in a common number field.

list=ToNumberField[list,All]

Performance testing suggests that ToNumberField memoizes evaluations of subexpressions. Evaluation is fast when the input is an algebraic combination of previously evaluated subexpressions.

(* all elements of list must be explicit algebraic numbers in a common number field *)
ContainsAlgebraicQ[{},a_,extension_]= False
ContainsAlgebraicQ[list_,a_,extension_]:=
  Quiet[MemberQ[list,ToNumberField[a,AlgebraicNumberPolynomial[list[[1]]]]]]

Here, Quiet suppresses a message that occurs when a is not in the number field generated by extension. I'm not sure what performance is like in this case; your application may allow better options for choice of extension.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.