def dup_invert(f, g, K):
    """
    Compute multiplicative inverse of ``f`` modulo ``g`` in ``F[x]``.

    **Examples**

    >>> from sympy.polys.domains import QQ
    >>> from sympy.polys.euclidtools import dup_invert

    >>> f = QQ.map([1, 0, -1])
    >>> g = QQ.map([2, -1])
    >>> h = QQ.map([1, -1])

    >>> dup_invert(f, g, QQ)
    [-4/3]

    >>> dup_invert(f, h, QQ)
    Traceback (most recent call last):
    ...
    NotInvertible: zero divisor

    """
    s, h = dup_half_gcdex(f, g, K)

    if h == [K.one]:
        return dup_rem(s, g, K)
    else:
        raise NotInvertible("zero divisor")

def dup_revert(f, n, K):
    """
    Compute ``f**(-1)`` mod ``x**n`` using Newton iteration.

    This function computes first ``2**n`` terms of a polynomial that
    is a result of inversion of a polynomial modulo ``x**n``. This is
    useful to efficiently compute series expansion of ``1/f``.

    Examples
    ========

    >>> from sympy.polys import ring, QQ
    >>> R, x = ring("x", QQ)

    >>> f = -QQ(1,720)*x**6 + QQ(1,24)*x**4 - QQ(1,2)*x**2 + 1

    >>> R.dup_revert(f, 8)
    61/720*x**6 + 5/24*x**4 + 1/2*x**2 + 1

    """
    g = [K.revert(dup_TC(f, K))]
    h = [K.one, K.zero, K.zero]

    N = int(_ceil(_log(n, 2)))

    for i in range(1, N + 1):
        a = dup_mul_ground(g, K(2), K)
        b = dup_mul(f, dup_sqr(g, K), K)
        g = dup_rem(dup_sub(a, b, K), h, K)
        h = dup_lshift(h, dup_degree(h), K)

    return g

def dup_revert(f, n, K):
    """
    Compute ``f**(-1)`` mod ``x**n`` using Newton iteration.

    This function computes first ``2**n`` terms of a polynomial that
    is a result of inversion of a polynomial modulo ``x**n``. This is
    useful to efficiently compute series expansion of ``1/f``.

    Examples
    ========

    >>> from sympy.polys.domains import QQ
    >>> from sympy.polys.densetools import dup_revert

    >>> f = [-QQ(1,720), QQ(0), QQ(1,24), QQ(0), -QQ(1,2), QQ(0), QQ(1)]

    >>> dup_revert(f, 8, QQ)
    [61/720, 0/1, 5/24, 0/1, 1/2, 0/1, 1/1]

    """
    g = [K.revert(dup_TC(f, K))]
    h = [K.one, K.zero, K.zero]

    N = int(_ceil(_log(n, 2)))

    for i in xrange(1, N + 1):
        a = dup_mul_ground(g, K(2), K)
        b = dup_mul(f, dup_sqr(g, K), K)
        g = dup_rem(dup_sub(a, b, K), h, K)
        h = dup_lshift(h, dup_degree(h), K)

    return g

def test_dup_div():
    f, g, q, r = [5,4,3,2,1], [1,2,3], [5,-6,0], [20,1]

    assert dup_div(f, g, ZZ) == (q, r)
    assert dup_quo(f, g, ZZ) == q
    assert dup_rem(f, g, ZZ) == r

    raises(ExactQuotientFailed, lambda: dup_exquo(f, g, ZZ))

    f, g, q, r = [5,4,3,2,1,0], [1,2,0,0,9], [5,-6], [15,2,-44,54]

    assert dup_div(f, g, ZZ) == (q, r)
    assert dup_quo(f, g, ZZ) == q
    assert dup_rem(f, g, ZZ) == r

    raises(ExactQuotientFailed, lambda: dup_exquo(f, g, ZZ))

def dup_invert(f, g, K):
    """
    Compute multiplicative inverse of `f` modulo `g` in `F[x]`.

    Examples
    ========

    >>> from sympy.polys import ring, QQ
    >>> R, x = ring("x", QQ)

    >>> f = x**2 - 1
    >>> g = 2*x - 1
    >>> h = x - 1

    >>> R.dup_invert(f, g)
    -4/3

    >>> R.dup_invert(f, h)
    Traceback (most recent call last):
    ...
    NotInvertible: zero divisor

    """
    s, h = dup_half_gcdex(f, g, K)

    if h == [K.one]:
        return dup_rem(s, g, K)
    else:
        raise NotInvertible("zero divisor")

    def pow(f, n):
        """Raise `f` to a non-negative power `n`. """
        if isinstance(n, int):
            if n < 0:
                F, n = dup_invert(f.rep, f.mod, f.dom), -n
            else:
                F = f.rep

            return f.per(dup_rem(dup_pow(F, n, f.dom), f.mod, f.dom))
        else:
            raise TypeError("`int` expected, got %s" % type(n))

def dup_euclidean_prs(f, g, K):
    """
    Euclidean polynomial remainder sequence (PRS) in `K[x]`.

    Examples
    ========

    >>> from sympy.polys import ring, QQ
    >>> R, x = ring("x", QQ)

    >>> f = x**8 + x**6 - 3*x**4 - 3*x**3 + 8*x**2 + 2*x - 5
    >>> g = 3*x**6 + 5*x**4 - 4*x**2 - 9*x + 21

    >>> prs = R.dup_euclidean_prs(f, g)

    >>> prs[0]
    x**8 + x**6 - 3*x**4 - 3*x**3 + 8*x**2 + 2*x - 5
    >>> prs[1]
    3*x**6 + 5*x**4 - 4*x**2 - 9*x + 21
    >>> prs[2]
    -5/9*x**4 + 1/9*x**2 - 1/3
    >>> prs[3]
    -117/25*x**2 - 9*x + 441/25
    >>> prs[4]
    233150/19773*x - 102500/6591
    >>> prs[5]
    -1288744821/543589225

    """
    prs = [f, g]
    h = dup_rem(f, g, K)

    while h:
        prs.append(h)
        f, g = g, h
        h = dup_rem(f, g, K)

    return prs

def dup_euclidean_prs(f, g, K):
    """
    Euclidean polynomial remainder sequence (PRS) in `K[x]`.

    Examples
    ========

    >>> from sympy.polys.domains import QQ
    >>> from sympy.polys.euclidtools import dup_euclidean_prs

    >>> f = QQ.map([1, 0, 1, 0, -3, -3, 8, 2, -5])
    >>> g = QQ.map([3, 0, 5, 0, -4, -9, 21])

    >>> prs = dup_euclidean_prs(f, g, QQ)

    >>> prs[0]
    [1/1, 0/1, 1/1, 0/1, -3/1, -3/1, 8/1, 2/1, -5/1]
    >>> prs[1]
    [3/1, 0/1, 5/1, 0/1, -4/1, -9/1, 21/1]
    >>> prs[2]
    [-5/9, 0/1, 1/9, 0/1, -1/3]
    >>> prs[3]
    [-117/25, -9/1, 441/25]
    >>> prs[4]
    [233150/19773, -102500/6591]
    >>> prs[5]
    [-1288744821/543589225]

    """
    prs = [f, g]
    h = dup_rem(f, g, K)

    while h:
        prs.append(h)
        f, g = g, h
        h = dup_rem(f, g, K)

    return prs

 def quo(f, g):
     dom, per, F, G, mod = f.unify(g)
     return per(dup_rem(dup_mul(F, dup_invert(G, mod, dom), dom), mod, dom))

 def div(f, g):
     dom, per, F, G, mod = f.unify(g)
     return (per(dup_rem(dup_mul(F, dup_invert(G, mod, dom), dom), mod, dom)), self.zero(mod, dom))

 def mul(f, g):
     dom, per, F, G, mod = f.unify(g)
     return per(dup_rem(dup_mul(F, G, dom), mod, dom))