(expr, G, *gens, **args)
return (c*r.q)/(d*r.p)
Simplifies a rational expression ``expr`` modulo the prime ideal
    generated by ``G``.  ``G`` should be a Groebner basis of the
    ideal.

    >>> from sympy.simplify.simplify import ratsimpmodprime
    >>> from sympy.abc import x, y
    >>> eq = (x + y**5 + y)/(x - y)
    >>> ratsimpmodprime(eq, [x*y**5 - x - y], x, y, order='lex')
    (x**2 + x*y + x + y)/(x**2 - x*y)

    If ``polynomial`` is False, the algorithm computes a rational
    simplification which minimizes the sum of the total degrees of
    the numerator and the denominator.

    If ``polynomial`` is True, this function just brings numerator and
    denominator into a canonical form. This is much faster, but has
    potentially worse results.

    References
    ==========

    M. Monagan, R. Pearce, Rational Simplification Modulo a Polynomial
    Ideal,
    http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.163.6984
    (specifically, the second algorithm)
Simplifies a rational expression ``expr`` modulo the prime ideal
    generated by ``G``.  ``G`` should be a Groebner basis of the
    ideal.
Simplifies a rational expression expr modulo the prime ideal generated by G . G should be a Groebner basis of the ideal .
def ratsimpmodprime(expr, G, *gens, **args):
    """
    Simplifies a rational expression ``expr`` modulo the prime ideal
    generated by ``G``.  ``G`` should be a Groebner basis of the
    ideal.

    >>> from sympy.simplify.simplify import ratsimpmodprime
    >>> from sympy.abc import x, y
    >>> eq = (x + y**5 + y)/(x - y)
    >>> ratsimpmodprime(eq, [x*y**5 - x - y], x, y, order='lex')
    (x**2 + x*y + x + y)/(x**2 - x*y)

    If ``polynomial`` is False, the algorithm computes a rational
    simplification which minimizes the sum of the total degrees of
    the numerator and the denominator.

    If ``polynomial`` is True, this function just brings numerator and
    denominator into a canonical form. This is much faster, but has
    potentially worse results.

    References
    ==========

    M. Monagan, R. Pearce, Rational Simplification Modulo a Polynomial
    Ideal,
    http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.163.6984
    (specifically, the second algorithm)
    """
    from sympy.polys import parallel_poly_from_expr
    from sympy.polys.polyerrors import PolificationFailed, DomainError
    from sympy import solve, Monomial
    from sympy.polys.monomials import monomial_div
    from sympy.core.compatibility import combinations_with_replacement
    from sympy.utilities.misc import debug

    quick = args.pop('quick', True)
    polynomial = args.pop('polynomial', False)
    debug('ratsimpmodprime', expr)

    # usual preparation of polynomials:

    num, denom = cancel(expr).as_numer_denom()

    try:
        polys, opt = parallel_poly_from_expr([num, denom] + G, *gens, **args)
    except PolificationFailed:
        return expr

    domain = opt.domain

    if domain.has_assoc_Field:
        opt.domain = domain.get_field()
    else:
        raise DomainError(
            "can't compute rational simplification over %s" % domain)

    # compute only once
    leading_monomials = [g.LM(opt.order) for g in polys[2:]]
    tested = set()

    def staircase(n):
        """
        Compute all monomials with degree less than ``n`` that are
        not divisible by any element of ``leading_monomials``.
        """
        if n == 0:
            return [1]
        S = []
        for mi in combinations_with_replacement(xrange(len(opt.gens)), n):
            m = [0]*len(opt.gens)
            for i in mi:
                m[i] += 1
            if all([monomial_div(m, lmg) is None for lmg in
                    leading_monomials]):
                S.append(m)

        return [Monomial(s).as_expr(*opt.gens) for s in S] + staircase(n - 1)

    def _ratsimpmodprime(a, b, allsol, N=0, D=0):
        """
        Computes a rational simplification of ``a/b`` which minimizes
        the sum of the total degrees of the numerator and the denominator.

        The algorithm proceeds by looking at ``a * d - b * c`` modulo
        the ideal generated by ``G`` for some ``c`` and ``d`` with degree
        less than ``a`` and ``b`` respectively.
        The coefficients of ``c`` and ``d`` are indeterminates and thus
        the coefficients of the normalform of ``a * d - b * c`` are
        linear polynomials in these indeterminates.
        If these linear polynomials, considered as system of
        equations, have a nontrivial solution, then `\frac{a}{b}
        \equiv \frac{c}{d}` modulo the ideal generated by ``G``. So,
        by construction, the degree of ``c`` and ``d`` is less than
        the degree of ``a`` and ``b``, so a simpler representation
        has been found.
        After a simpler representation has been found, the algorithm
        tries to reduce the degree of the numerator and denominator
        and returns the result afterwards.

        As an extension, if quick=False, we look at all possible degrees such
        that the total degree is less than *or equal to* the best current
        solution. We retain a list of all solutions of minimal degree, and try
        to find the best one at the end.
        """
        c, d = a, b
        steps = 0

        maxdeg = a.total_degree() + b.total_degree()
        if quick:
            bound = maxdeg - 1
        else:
            bound = maxdeg
        while N + D <= bound:
            if (N, D) in tested:
                break
            tested.add((N, D))

            M1 = staircase(N)
            M2 = staircase(D)
            debug('%s / %s: %s, %s' % (N, D, M1, M2))

            Cs = symbols("c:%d" % len(M1), cls=Dummy)
            Ds = symbols("d:%d" % len(M2), cls=Dummy)
            ng = Cs + Ds

            c_hat = Poly(
                sum([Cs[i] * M1[i] for i in xrange(len(M1))]), opt.gens + ng)
            d_hat = Poly(
                sum([Ds[i] * M2[i] for i in xrange(len(M2))]), opt.gens + ng)

            r = reduced(a * d_hat - b * c_hat, G, opt.gens + ng,
                        order=opt.order, polys=True)[1]

            S = Poly(r, gens=opt.gens).coeffs()
            sol = solve(S, Cs + Ds, particular=True, quick=True)

            if sol and not all([s == 0 for s in sol.values()]):
                c = c_hat.subs(sol)
                d = d_hat.subs(sol)

                # The "free" variables occuring before as parameters
                # might still be in the substituted c, d, so set them
                # to the value chosen before:
                c = c.subs(dict(list(zip(Cs + Ds, [1] * (len(Cs) + len(Ds))))))
                d = d.subs(dict(list(zip(Cs + Ds, [1] * (len(Cs) + len(Ds))))))

                c = Poly(c, opt.gens)
                d = Poly(d, opt.gens)
                if d == 0:
                    raise ValueError('Ideal not prime?')

                allsol.append((c_hat, d_hat, S, Cs + Ds))
                if N + D != maxdeg:
                    allsol = [allsol[-1]]

                break

            steps += 1
            N += 1
            D += 1

        if steps > 0:
            c, d, allsol = _ratsimpmodprime(c, d, allsol, N, D - steps)
            c, d, allsol = _ratsimpmodprime(c, d, allsol, N - steps, D)

        return c, d, allsol

    # preprocessing. this improves performance a bit when deg(num)
    # and deg(denom) are large:
    num = reduced(num, G, opt.gens, order=opt.order)[1]
    denom = reduced(denom, G, opt.gens, order=opt.order)[1]

    if polynomial:
        return (num/denom).cancel()

    c, d, allsol = _ratsimpmodprime(
        Poly(num, opt.gens), Poly(denom, opt.gens), [])
    if not quick and allsol:
        debug('Looking for best minimal solution. Got: %s' % len(allsol))
        newsol = []
        for c_hat, d_hat, S, ng in allsol:
            sol = solve(S, ng, particular=True, quick=False)
            newsol.append((c_hat.subs(sol), d_hat.subs(sol)))
        c, d = min(newsol, key=lambda x: len(x[0].terms()) + len(x[1].terms()))

    if not domain.has_Field:
        cn, c = c.clear_denoms(convert=True)
        dn, d = d.clear_denoms(convert=True)
    r = Rational(cn, dn)

    return (c*r.q)/(d*r.p)
def ratsimpmodprime ( expr , G , * gens , * * args ) : from sympy . polys import parallel_poly_from_expr from sympy . polys . polyerrors import PolificationFailed , DomainError from sympy import solve , Monomial from sympy . polys . monomials import monomial_div from sympy . core . compatibility import combinations_with_replacement from sympy . utilities . misc import debug quick = args . pop ( 'quick' , True ) polynomial = args . pop ( 'polynomial' , False ) debug ( 'ratsimpmodprime' , expr ) # usual preparation of polynomials: num , denom = cancel ( expr ) . as_numer_denom ( ) try : polys , opt = parallel_poly_from_expr ( [ num , denom ] + G , * gens , * * args ) except PolificationFailed : return expr domain = opt . domain if domain . has_assoc_Field : opt . domain = domain . get_field ( ) else : raise DomainError ( "can't compute rational simplification over %s" % domain ) # compute only once leading_monomials = [ g . LM ( opt . order ) for g in polys [ 2 : ] ] tested = set ( ) def staircase ( n ) : """
        Compute all monomials with degree less than ``n`` that are
        not divisible by any element of ``leading_monomials``.
        """ if n == 0 : return [ 1 ] S = [ ] for mi in combinations_with_replacement ( xrange ( len ( opt . gens ) ) , n ) : m = [ 0 ] * len ( opt . gens ) for i in mi : m [ i ] += 1 if all ( [ monomial_div ( m , lmg ) is None for lmg in leading_monomials ] ) : S . append ( m ) return [ Monomial ( s ) . as_expr ( * opt . gens ) for s in S ] + staircase ( n - 1 ) def _ratsimpmodprime ( a , b , allsol , N = 0 , D = 0 ) : """
        Computes a rational simplification of ``a/b`` which minimizes
        the sum of the total degrees of the numerator and the denominator.

        The algorithm proceeds by looking at ``a * d - b * c`` modulo
        the ideal generated by ``G`` for some ``c`` and ``d`` with degree
        less than ``a`` and ``b`` respectively.
        The coefficients of ``c`` and ``d`` are indeterminates and thus
        the coefficients of the normalform of ``a * d - b * c`` are
        linear polynomials in these indeterminates.
        If these linear polynomials, considered as system of
        equations, have a nontrivial solution, then `\frac{a}{b}
        \equiv \frac{c}{d}` modulo the ideal generated by ``G``. So,
        by construction, the degree of ``c`` and ``d`` is less than
        the degree of ``a`` and ``b``, so a simpler representation
        has been found.
        After a simpler representation has been found, the algorithm
        tries to reduce the degree of the numerator and denominator
        and returns the result afterwards.

        As an extension, if quick=False, we look at all possible degrees such
        that the total degree is less than *or equal to* the best current
        solution. We retain a list of all solutions of minimal degree, and try
        to find the best one at the end.
        """ c , d = a , b steps = 0 maxdeg = a . total_degree ( ) + b . total_degree ( ) if quick : bound = maxdeg - 1 else : bound = maxdeg while N + D <= bound : if ( N , D ) in tested : break tested . add ( ( N , D ) ) M1 = staircase ( N ) M2 = staircase ( D ) debug ( '%s / %s: %s, %s' % ( N , D , M1 , M2 ) ) Cs = symbols ( "c:%d" % len ( M1 ) , cls = Dummy ) Ds = symbols ( "d:%d" % len ( M2 ) , cls = Dummy ) ng = Cs + Ds c_hat = Poly ( sum ( [ Cs [ i ] * M1 [ i ] for i in xrange ( len ( M1 ) ) ] ) , opt . gens + ng ) d_hat = Poly ( sum ( [ Ds [ i ] * M2 [ i ] for i in xrange ( len ( M2 ) ) ] ) , opt . gens + ng ) r = reduced ( a * d_hat - b * c_hat , G , opt . gens + ng , order = opt . order , polys = True ) [ 1 ] S = Poly ( r , gens = opt . gens ) . coeffs ( ) sol = solve ( S , Cs + Ds , particular = True , quick = True ) if sol and not all ( [ s == 0 for s in sol . values ( ) ] ) : c = c_hat . subs ( sol ) d = d_hat . subs ( sol ) # The "free" variables occuring before as parameters # might still be in the substituted c, d, so set them # to the value chosen before: c = c . subs ( dict ( list ( zip ( Cs + Ds , [ 1 ] * ( len ( Cs ) + len ( Ds ) ) ) ) ) ) d = d . subs ( dict ( list ( zip ( Cs + Ds , [ 1 ] * ( len ( Cs ) + len ( Ds ) ) ) ) ) ) c = Poly ( c , opt . gens ) d = Poly ( d , opt . gens ) if d == 0 : raise ValueError ( 'Ideal not prime?' ) allsol . append ( ( c_hat , d_hat , S , Cs + Ds ) ) if N + D != maxdeg : allsol = [ allsol [ - 1 ] ] break steps += 1 N += 1 D += 1 if steps > 0 : c , d , allsol = _ratsimpmodprime ( c , d , allsol , N , D - steps ) c , d , allsol = _ratsimpmodprime ( c , d , allsol , N - steps , D ) return c , d , allsol # preprocessing. this improves performance a bit when deg(num) # and deg(denom) are large: num = reduced ( num , G , opt . gens , order = opt . order ) [ 1 ] denom = reduced ( denom , G , opt . gens , order = opt . order ) [ 1 ] if polynomial : return ( num / denom ) . cancel ( ) c , d , allsol = _ratsimpmodprime ( Poly ( num , opt . gens ) , Poly ( denom , opt . gens ) , [ ] ) if not quick and allsol : debug ( 'Looking for best minimal solution. Got: %s' % len ( allsol ) ) newsol = [ ] for c_hat , d_hat , S , ng in allsol : sol = solve ( S , ng , particular = True , quick = False ) newsol . append ( ( c_hat . subs ( sol ) , d_hat . subs ( sol ) ) ) c , d = min ( newsol , key = lambda x : len ( x [ 0 ] . terms ( ) ) + len ( x [ 1 ] . terms ( ) ) ) if not domain . has_Field : cn , c = c . clear_denoms ( convert = True ) dn , d = d . clear_denoms ( convert = True ) r = Rational ( cn , dn ) return ( c * r . q ) / ( d * r . p )