

def dup_half_gcdex(f, g, K):
    '\n    Half extended Euclidean algorithm in `F[x]`.\n\n    Returns ``(s, h)`` such that ``h = gcd(f, g)`` and ``s*f = h (mod g)``.\n\n    Examples\n    ========\n\n    >>> from sympy.polys import ring, QQ\n    >>> R, x = ring("x", QQ)\n\n    >>> f = x**4 - 2*x**3 - 6*x**2 + 12*x + 15\n    >>> g = x**3 + x**2 - 4*x - 4\n\n    >>> R.dup_half_gcdex(f, g)\n    (-1/5*x + 3/5, x + 1)\n\n    '
    if (not K.has_Field):
        raise DomainError(("can't compute half extended GCD over %s" % K))
    (a, b) = ([K.one], [])
    while g:
        (q, r) = dup_div(f, g, K)
        (f, g) = (g, r)
        (a, b) = (b, dup_sub_mul(a, q, b, K))
    a = dup_quo_ground(a, dup_LC(f, K), K)
    f = dup_monic(f, K)
    return (a, f)

dataset/ETHPy150Open sympy/sympy/sympy/polys/euclidtools.py dup_half_gcdex/original