#NEWLINE# def _minpoly_groebner( ex , x , cls ) : #NEWLINE# #INDENT# '\n    Computes the minimal polynomial of an algebraic number\n    using Groebner bases\n\n    Examples\n    ========\n\n    >>> from sympy import minimal_polynomial, sqrt, Rational\n    >>> from sympy.abc import x\n    >>> minimal_polynomial(sqrt(2) + 3*Rational(1, 3), x, compose=False)\n    x**2 - 2*x - 1\n\n    ' #NEWLINE# from sympy.polys.polytools import degree #NEWLINE# from sympy.core.function import expand_multinomial #NEWLINE# generator = numbered_symbols ( 'a' , cls = Dummy ) #NEWLINE# ( mapping , symbols , replace ) = ( { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } , [ ] ) #NEWLINE# def update_mapping( ex , exp , base = None ) : #NEWLINE# #INDENT# a = next ( generator ) #NEWLINE# symbols [ ex ] = a #NEWLINE# if ( base is not None ) : #NEWLINE# #INDENT# mapping [ ex ] = ( ( a ** exp ) + base ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# mapping [ ex ] = exp . as_expr ( a ) #NEWLINE# #UNINDENT# return a #NEWLINE# #UNINDENT# def bottom_up_scan( ex ) : #NEWLINE# #INDENT# if ex . is_Atom : #NEWLINE# #INDENT# if ( ex is S . ImaginaryUnit ) : #NEWLINE# #INDENT# if ( ex not in mapping ) : #NEWLINE# #INDENT# return update_mapping ( ex , 2 , 1 ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# return symbols [ ex ] #NEWLINE# #UNINDENT# #UNINDENT# else : #NEWLINE# #INDENT# if ex . is_Rational : #NEWLINE# #INDENT# return ex #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# else : #NEWLINE# #INDENT# if ex . is_Add : #NEWLINE# #INDENT# return Add ( * [ bottom_up_scan ( g ) for g in ex . args ] ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ex . is_Mul : #NEWLINE# #INDENT# return Mul ( * [ bottom_up_scan ( g ) for g in ex . args ] ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ex . is_Pow : #NEWLINE# #INDENT# if ex . exp . is_Rational : #NEWLINE# #INDENT# if ( ( ex . exp < 0 ) and ex . base . is_Add ) : #NEWLINE# #INDENT# ( coeff , terms ) = ex . base . as_coeff_add ( ) #NEWLINE# ( elt , _ ) = primitive_element ( terms , polys = True ) #NEWLINE# alg = ( ex . base - coeff ) #NEWLINE# inverse = invert ( ( elt . gen + coeff ) , elt ) . as_expr ( ) #NEWLINE# base = inverse . subs ( elt . gen , alg ) . expand ( ) #NEWLINE# if ( ex . exp == ( - 1 ) ) : #NEWLINE# #INDENT# return bottom_up_scan ( base ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# ex = ( base ** ( - ex . exp ) ) #NEWLINE# #UNINDENT# #UNINDENT# if ( not ex . exp . is_Integer ) : #NEWLINE# #INDENT# ( base , exp ) = ( ( ex . base ** ex . exp . p ) . expand ( ) , Rational ( 1 , ex . exp . q ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# ( base , exp ) = ( ex . base , ex . exp ) #NEWLINE# #UNINDENT# base = bottom_up_scan ( base ) #NEWLINE# expr = ( base ** exp ) #NEWLINE# if ( expr not in mapping ) : #NEWLINE# #INDENT# return update_mapping ( expr , ( 1 / exp ) , ( - base ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# return symbols [ expr ] #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# else : #NEWLINE# #INDENT# if ex . is_AlgebraicNumber : #NEWLINE# #INDENT# if ( ex . root not in mapping ) : #NEWLINE# #INDENT# return update_mapping ( ex . root , ex . minpoly ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# return symbols [ ex . root ] #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# raise NotAlgebraic ( ( "%s doesn't seem to be an algebraic number" % ex ) ) #NEWLINE# #UNINDENT# def simpler_inverse( ex ) : #NEWLINE# #INDENT# '\n        Returns True if it is more likely that the minimal polynomial\n        algorithm works better with the inverse\n        ' #NEWLINE# if ex . is_Pow : #NEWLINE# #INDENT# if ( ( 1 / ex . exp ) . is_integer and ( ex . exp < 0 ) ) : #NEWLINE# #INDENT# if ex . base . is_Add : #NEWLINE# #INDENT# return True #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# if ex . is_Mul : #NEWLINE# #INDENT# hit = True #NEWLINE# a = [ ] #NEWLINE# for p in ex . args : #NEWLINE# #INDENT# if p . is_Add : #NEWLINE# #INDENT# return False #NEWLINE# #UNINDENT# if p . is_Pow : #NEWLINE# #INDENT# if ( p . base . is_Add and ( p . exp > 0 ) ) : #NEWLINE# #INDENT# return False #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# if hit : #NEWLINE# #INDENT# return True #NEWLINE# #UNINDENT# #UNINDENT# return False #NEWLINE# #UNINDENT# inverted = False #NEWLINE# ex = expand_multinomial ( ex ) #NEWLINE# if ex . is_AlgebraicNumber : #NEWLINE# #INDENT# return ex . minpoly . as_expr ( x ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ex . is_Rational : #NEWLINE# #INDENT# result = ( ( ex . q * x ) - ex . p ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# inverted = simpler_inverse ( ex ) #NEWLINE# if inverted : #NEWLINE# #INDENT# ex = ( ex ** ( - 1 ) ) #NEWLINE# #UNINDENT# res = None #NEWLINE# if ( ex . is_Pow and ( 1 / ex . exp ) . is_Integer ) : #NEWLINE# #INDENT# n = ( 1 / ex . exp ) #NEWLINE# res = _minimal_polynomial_sq ( ex . base , n , x ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if _is_sum_surds ( ex ) : #NEWLINE# #INDENT# res = _minimal_polynomial_sq ( ex , S . One , x ) #NEWLINE# #UNINDENT# #UNINDENT# if ( res is not None ) : #NEWLINE# #INDENT# result = res #NEWLINE# #UNINDENT# if ( res is None ) : #NEWLINE# #INDENT# bus = bottom_up_scan ( ex ) #NEWLINE# F = ( [ ( x - bus ) ] + list ( mapping . values ( ) ) ) #NEWLINE# G = groebner ( F , ( list ( symbols . values ( ) ) + [ x ] ) , order = 'lex' ) #NEWLINE# ( _ , factors ) = factor_list ( G [ ( - 1 ) ] ) #NEWLINE# result = _choose_factor ( factors , x , ex ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# if inverted : #NEWLINE# #INDENT# result = _invertx ( result , x ) #NEWLINE# if ( result . coeff ( ( x ** degree ( result , x ) ) ) < 0 ) : #NEWLINE# #INDENT# result = expand_mul ( ( - result ) ) #NEWLINE# #UNINDENT# #UNINDENT# return result