<commit_before>"""Real and complex root isolation and refinement algorithms. """

from __future__ import print_function, division

from sympy.polys.densebasic import (
    dup_LC, dup_TC, dup_degree,
    dup_strip, dup_reverse,
    dup_convert,
    dup_terms_gcd)

from sympy.polys.densearith import (
    dup_neg, dup_rshift, dup_rem)

from sympy.polys.densetools import (
    dup_clear_denoms,
    dup_mirror, dup_scale, dup_shift,
    dup_transform,
    dup_diff,
    dup_eval, dmp_eval_in,
    dup_sign_variations,
    dup_real_imag)

from sympy.polys.sqfreetools import (
    dup_sqf_part, dup_sqf_list)

from sympy.polys.factortools import (
    dup_factor_list)

from sympy.polys.polyerrors import (
    RefinementFailed,
    DomainError)

from sympy.core.compatibility import xrange

def dup_sturm(f, K):
    """
    Computes the Sturm sequence of ``f`` in ``F[x]``.

    Given a univariate, square-free polynomial ``f(x)`` returns the
    associated Sturm sequence ``f_0(x), ..., f_n(x)`` defined by::

       f_0(x), f_1(x) = f(x), f'(x)
       f_n = -rem(f_{n-2}(x), f_{n-1}(x))

    Examples
    ========

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

    >>> R.dup_sturm(x**3 - 2*x**2 + x - 3)
    [x**3 - 2*x**2 + x - 3, 3*x**2 - 4*x + 1, 2/9*x + 25/9, -2079/4]

    References
    ==========

    1. [Davenport88]_

    """
    if not K.has_Field:
        raise DomainError("can't compute Sturm sequence over %s" % K)

    f = dup_sqf_part(f, K)

    sturm = [f, dup_diff(f, 1, K)]

    while sturm[-1]:
        s = dup_rem(sturm[-2], sturm[-1], K)
        sturm.append(dup_neg(s, K))

    return sturm[:-1]

def dup_root_upper_bound(f, K):
    """Compute LMQ upper bound for `f`'s positive roots. 
       
       Reference:<NAME>: "Linear and Quadratic Complexity Bounds on the      
           Values of the Positive Roots of Polynomials"  
           Journal of Universal Computer Science, Vol. 15, No. 3, 523-537, 2009. 
    """
    n, t, P = len(f), K.one, []

    if dup_LC(f, K) < 0:
        f = dup_neg(f, K)

    f = list(reversed(f))

    for i in xrange(0, n):
        if f[i] >= 0:
            continue

        a, Q = K.log(-f[i], 2), []

        for j in xrange(i + 1, n):

            if f[j] <= 0:
                continue

            q = t + a - K.log(f[j], 2)
            Q.append(q // (j - i))

            t += 1

        if not Q:
            continue

        P.append(min(Q))

    if not P:
        return None
    else:
        return 2.0**(max(P) + 1)

def dup_root_lower_bound(f, K):
    """Compute LMQ lower bound for `f`'s positive roots. 
       
       Reference:<NAME>: "Linear and Quadratic Complexity Bounds on the      
           Values of the Positive Roots of Polynomials"  
           Journal of Universal Computer Science, Vol. 15, No. 3, 523-537, 2009. 
    """
    bound = dup_root_upper_bound(dup_reverse(f), K)

    if bound is not None:
        return 1.0 / bound
    else:
        return None

def _mobius_from_interval(I, field):
    """Convert an open interval to a Mobius transform. """
    s, t = I

    a, c = field.numer(s), field.denom(s)
    b, d = field.numer(t), field.denom(t)

    return a, b, c, d

def _mobius_to_interval(M, field):
    """Convert a Mobius transform to an open interval. """
    a, b, c, d = M

    s, t = field(a, c), field(b, d)

    if s <= t:
        return (s, t)
    else:
        return (t, s)

def dup_step_refine_real_root(f, M, K, fast=False):
    """One step of positive real root refinement algorithm. """
    a, b, c, d = M

    if a == b and c == d:
        return f, (a, b, c, d)

    A = dup_root_lower_bound(f, K)

    if A is not None:
        A = K(int(A))
    else:
        A = K.zero

    if fast and A > 16:
        f = dup_scale(f, A, K)
        a, c, A = A*a, A*c, K.one

    if A >= K.one:
        f = dup_shift(f, A, K)
        b, d = A*a + b, A*c + d

        if not dup_eval(f, K.zero, K):
            return f, (b, b, d, d)

    f, g = dup_shift(f, K.one, K), f

    a1, b1, c1, d1 = a, a + b, c, c + d

    if not dup_eval(f, K.zero, K):
        return f, (b1, b1, d1, d1)

    k = dup_sign_variations(f, K)

    if k == 1:
        a, b, c, d = a1, b1, c1, d1
    else:
        f = dup_shift(dup_reverse(g), K.one, K)

        if not dup_eval(f, K.zero, K):
            f = dup_rshift(f, 1, K)

        a, b, c, d = b, a + b, d, c + d

    return f, (a, b, c, d)

def dup_inner_refine_real_root(f, M, K, eps=None, steps=None, disjoint=None, fast=False, mobius=False):
    """Refine a positive root of `f` given a Mobius transform or an interval. """
    F = K.get_field()

    if len(M) == 2:
        a, b, c, d = _mobius_from_interval(M, F)
    else:
        a, b, c, d = M

    while not c:
        f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c,
            d), K, fast=fast)

    if eps is not None and steps is not None:
        for i in xrange(0, steps):
            if abs(F(a, c) - F(b, d)) >= eps:
                f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c, d), K, fast=fast)
            else:
                break
    else:
        if eps is not None:
            while abs(F(a, c) - F(b, d)) >= eps:
                f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c, d), K, fast=fast)

        if steps is not None:
            for i in xrange(0, steps):
                f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c, d), K, fast=fast)

    if disjoint is not None:
        while True:
            u, v = _mobius_to_interval((a, b, c, d), F)

            if v <= disjoint or disjoint <= u:
                break
            else:
                f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c, d), K, fast=fast)

    if not mobius:
        return _mobius_to_interval((a, b, c, d), F)
    else:
        return f, (a, b, c, d)

def dup_outer_refine_real_root(f, s, t, K, eps=None, steps=None, disjoint=None, fast=False):
    """Refine a positive root of `f` given an interval `(s, t)`. """
    a, b, c, d = _mobius_from_interval((s, t), K.get_field())

    f = dup_transform(f, dup_strip([a, b]),
                         dup_strip([c, d]), K)

    if dup_sign_variations(f, K) != 1:
        raise RefinementFailed("there should be exactly one root in (%s, %s) interval" % (s, t))

    return dup_inner_refine_real_root(f, (a, b, c, d), K, eps=eps, steps=steps, disjoint=disjoint, fast=fast)

def dup_refine_real_root(f, s, t, K, eps=None, steps=None, disjoint=None, fast=False):
    """Refine real root's approximating interval to the given precision. """
    if K.is_QQ:
        (_, f), K = dup_clear_denoms(f, K, convert=True), K.get_ring()
    elif not K.is_ZZ:
        raise DomainError("real root refinement not supported over %s" % K)

    if s == t:
        return (s, t)

    if s > t:
        s, t = t, s

    negative = False

    if s < 0:
        if t <= 0:
            f, s, t, negative = dup_mirror(f, K), -t, -s, True
        else:
            raise ValueError("can't refine a real root in (%s, %s)" % (s, t))

    if negative and disjoint is not None:
        if disjoint < 0:
            disjoint = -disjoint
        else:
            disjoint = None

    s, t = dup_outer_refine_real_root(
        f, s, t, K, eps=eps, steps=steps, disjoint=disjoint, fast=fast)

    if negative:
        return (-t, -s)
    else:
        return ( s, t)

def dup_inner_isolate_real_roots(f, K, eps=None, fast=False):
    """Internal function for isolation positive roots up to given precision. 
       
       References:
           1. <NAME> and <NAME>: A Comparative Study of Two Real Root         
           Isolation Methods . Nonlinear Analysis: Modelling and Control, Vol. 10, No. 4, 297-304,    
           2005.
           2. <NAME>, <NAME> and <NAME>: Improving the  
           Performance of the Continued Fractions Method Using new Bounds of Positive Roots. Nonlinear  
           Analysis: Modelling and Control, Vol. 13, No. 3, 265-279, 2008.
    """
    a, b, c, d = K.one, K.zero, K.zero, K.one

    k = dup_sign_variations(f, K)

    if k == 0:
        return []
    if k == 1:
        roots = [dup_inner_refine_real_root(
            f, (a, b, c, d), K, eps=eps, fast=fast, mobius=True)]
    else:
        roots, stack = [], [(a, b, c, d, f, k)]

        while stack:
            a, b, c, d, f, k = stack.pop()

            A = dup_root_lower_bound(f, K)

            if A is not None:
                A = K(int(A))
            else:
                A = K.zero

            if fast and A > 16:
                f = dup_scale(f, A, K)
                a, c, A = A*a, A*c, K.one

            if A >= K.one:
                f = dup_shift(f, A, K)
                b, d = A*a + b, A*c + d

                if not dup_TC(f, K):
                    roots.append((f, (b, b, d, d)))
                    f = dup_rshift(f, 1, K)

                k = dup_sign_variations(f, K)

                if k == 0:
                    continue
                if k == 1:
                    roots.append(dup_inner_refine_real_root(
                        f, (a, b, c, d), K, eps=eps, fast=fast, mobius=True))
                    continue

            f1 = dup_shift(f, K.one, K)

            a1, b1, c1, d1, r = a, a + b, c, c + d, 0

            if not dup_TC(f1, K):
                roots.append((f1, (b1, b1, d1, d1)))
                f1, r = dup_rshift(f1, 1, K), 1

            k1 = dup_sign_variations(f1, K)
            k2 = k - k1 - r

            a2, b2, c2, d2 = b, a + b, d, c + d

            if k2 > 1:
                f2 = dup_shift(dup_reverse(f), K.one, K)

                if not dup_TC(f2, K):
                    f2 = dup_rshift(f2, 1, K)

                k2 = dup_sign_variations(f2, K)
            else:
                f2 = None

            if k1 < k2:
                a1, a2, b1, b2 = a2, a1, b2, b1
                c1, c2, d1, d2 = c2, c1, d2, d1
                f1, f2, k1, k2 = f2, f1, k2, k1

            if not k1:
                continue

            if f1 is None:
                f1 = dup_shift(dup_reverse(f), K.one, K)

                if not dup_TC(f1, K):
                    f1 = dup_rshift(f1, 1, K)

            if k1 == 1:
                roots.append(dup_inner_refine_real_root(
                    f1, (a1, b1, c1, d1), K, eps=eps, fast=fast, mobius=True))
            else:
                stack.append((a1, b1, c1, d1, f1, k1))

            if not k2:
                continue

            if f2 is None:
                f2 = dup_shift(dup_reverse(f), K.one, K)

                if not dup_TC(f2, K):
                    f2 = dup_rshift(f2, 1, K)

            if k2 == 1:
                roots.append(dup_inner_refine_real_root(
                    f2, (a2, b2, c2, d2), K, eps=eps, fast=fast, mobius=True))
            else:
                stack.append((a2, b2, c2, d2, f2, k2))

    return roots

def _discard_if_outside_interval(f, M, inf, sup, K, negative, fast, mobius):
    """Discard an isolating interval if outside ``(inf, sup)``. """
    F = K.get_field()

    while True:
        u, v = _mobius_to_interval(M, F)

        if negative:
            u, v = -v, -u

        if (inf is None or u >= inf) and (sup is None or v <= sup):
            if not mobius:
                return u, v
            else:
                return f, M
        elif (sup is not None and u > sup) or (inf is not None and v < inf):
            return None
        else:
            f, M = dup_step_refine_real_root(f, M, K, fast=fast)

def dup_inner_isolate_positive_roots(f, K, eps=None, inf=None, sup=None, fast=False, mobius=False):
    """Iteratively compute disjoint positive root isolation intervals. """
    if sup is not None and sup < 0:
        return []

    roots = dup_inner_isolate_real_roots(f, K, eps=eps, fast=fast)

    F, results = K.get_field(), []

    if inf is not None or sup is not None:
        for f, M in roots:
            result = _discard_if_outside_interval(f, M, inf, sup, K, False, fast, mobius)

            if result is not None:
                results.append(result)
    elif not mobius:
        for f, M in roots:
            u, v = _mobius_to_interval(M, F)
            results.append((u, v))
    else:
        results = roots

    return results

def dup_inner_isolate_negative_roots(f, K, inf=None, sup=None, eps=None, fast=False, mobius=False):
    """Iteratively compute disjoint negative root isolation intervals. """
    if inf is not None and inf >= 0:
        return []

    roots = dup_inner_isolate_real_roots(dup_mirror(f, K), K, eps=eps, fast=fast)

    F, results = K.get_field(), []

    if inf is not None or sup is not None:
        for f, M in roots:
            result = _discard_if_outside_interval(f, M, inf, sup, K, True, fast, mobius)

            if result is not None:
                results.append(result)
    elif not mobius:
        for f, M in roots:
            u, v = _mobius_to_interval(M, F)
            results.append((-v, -u))
    else:
        results = roots

    return results

def _isolate_zero(f, K, inf, sup, basis=False, sqf=False):
    """Handle special case of CF algorithm when ``f`` is homogeneous. """
    j, f = dup_terms_gcd(f, K)

    if j > 0:
        F = K.get_field()

        if (inf is None or inf <= 0) and (sup is None or 0 <= sup):
            if not sqf:
                if not basis:
                    return [((F.zero, F.zero), j)], f
                else:
                    return [((F.zero, F.zero), j, [K.one, K.zero])], f
            else:
                return [(F.zero, F.zero)], f

    return [], f

def dup_isolate_real_roots_sqf(f, K, eps=None, inf=None, sup=None, fast=False, blackbox=False):
    """Isolate real roots of a square-free polynomial using CF approach. """
    if K.is_QQ:
        (_, f), K = dup_clear_denoms(f, K, convert=True), K.get_ring()
    elif not K.is_ZZ:
        raise DomainError("isolation of real roots not supported over %s" % K)

    if dup_degree(f) <= 0:
        return []

    I_zero, f = _isolate_zero(f, K, inf, sup, basis=False, sqf=True)

    I_neg = dup_inner_isolate_negative_roots(f, K, eps=eps, inf=inf, sup=sup, fast=fast)
    I_pos = dup_inner_isolate_positive_roots(f, K, eps=eps, inf=inf, sup=sup, fast=fast)<commit_msg>Added refs to one more place and removed whitespaces<commit_after>"""Real and complex root isolation and refinement algorithms. """

from __future__ import print_function, division

from sympy.polys.densebasic import (
    dup_LC, dup_TC, dup_degree,
    dup_strip, dup_reverse,
    dup_convert,
    dup_terms_gcd)

from sympy.polys.densearith import (
    dup_neg, dup_rshift, dup_rem)

from sympy.polys.densetools import (
    dup_clear_denoms,
    dup_mirror, dup_scale, dup_shift,
    dup_transform,
    dup_diff,
    dup_eval, dmp_eval_in,
    dup_sign_variations,
    dup_real_imag)

from sympy.polys.sqfreetools import (
    dup_sqf_part, dup_sqf_list)

from sympy.polys.factortools import (
    dup_factor_list)

from sympy.polys.polyerrors import (
    RefinementFailed,
    DomainError)

from sympy.core.compatibility import xrange

def dup_sturm(f, K):
    """
    Computes the Sturm sequence of ``f`` in ``F[x]``.

    Given a univariate, square-free polynomial ``f(x)`` returns the
    associated Sturm sequence ``f_0(x), ..., f_n(x)`` defined by::

       f_0(x), f_1(x) = f(x), f'(x)
       f_n = -rem(f_{n-2}(x), f_{n-1}(x))

    Examples
    ========

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

    >>> R.dup_sturm(x**3 - 2*x**2 + x - 3)
    [x**3 - 2*x**2 + x - 3, 3*x**2 - 4*x + 1, 2/9*x + 25/9, -2079/4]

    References
    ==========

    1. [Davenport88]_

    """
    if not K.has_Field:
        raise DomainError("can't compute Sturm sequence over %s" % K)

    f = dup_sqf_part(f, K)

    sturm = [f, dup_diff(f, 1, K)]

    while sturm[-1]:
        s = dup_rem(sturm[-2], sturm[-1], K)
        sturm.append(dup_neg(s, K))

    return sturm[:-1]

def dup_root_upper_bound(f, K):
    """Compute the LMQ upper bound for `f`'s positive roots, 
       which was developed by Akritas-Strzebonski-Vigklas.
       
       Reference:
       ==========
       <NAME>: "Linear and Quadratic Complexity Bounds on the      
           Values of the Positive Roots of Polynomials"  
           Journal of Universal Computer Science, Vol. 15, No. 3, 523-537, 2009. 
    """
    n, t, P = len(f), K.one, []

    if dup_LC(f, K) < 0:
        f = dup_neg(f, K)

    f = list(reversed(f))

    for i in xrange(0, n):
        if f[i] >= 0:
            continue

        a, Q = K.log(-f[i], 2), []

        for j in xrange(i + 1, n):

            if f[j] <= 0:
                continue

            q = t + a - K.log(f[j], 2)
            Q.append(q // (j - i))

            t += 1

        if not Q:
            continue

        P.append(min(Q))

    if not P:
        return None
    else:
        return 2.0**(max(P) + 1)

def dup_root_lower_bound(f, K):
    """Compute LMQ lower bound for `f`'s positive roots. 
       
       Reference:
       ==========
       <NAME>: "Linear and Quadratic Complexity Bounds on the      
           Values of the Positive Roots of Polynomials"  
           Journal of Universal Computer Science, Vol. 15, No. 3, 523-537, 2009. 
    """
    bound = dup_root_upper_bound(dup_reverse(f), K)

    if bound is not None:
        return 1.0 / bound
    else:
        return None

def _mobius_from_interval(I, field):
    """Convert an open interval to a Mobius transform. """
    s, t = I

    a, c = field.numer(s), field.denom(s)
    b, d = field.numer(t), field.denom(t)

    return a, b, c, d

def _mobius_to_interval(M, field):
    """Convert a Mobius transform to an open interval. """
    a, b, c, d = M

    s, t = field(a, c), field(b, d)

    if s <= t:
        return (s, t)
    else:
        return (t, s)

def dup_step_refine_real_root(f, M, K, fast=False):
    """One step of positive real root refinement algorithm. """
    a, b, c, d = M

    if a == b and c == d:
        return f, (a, b, c, d)

    A = dup_root_lower_bound(f, K)

    if A is not None:
        A = K(int(A))
    else:
        A = K.zero

    if fast and A > 16:
        f = dup_scale(f, A, K)
        a, c, A = A*a, A*c, K.one

    if A >= K.one:
        f = dup_shift(f, A, K)
        b, d = A*a + b, A*c + d

        if not dup_eval(f, K.zero, K):
            return f, (b, b, d, d)

    f, g = dup_shift(f, K.one, K), f

    a1, b1, c1, d1 = a, a + b, c, c + d

    if not dup_eval(f, K.zero, K):
        return f, (b1, b1, d1, d1)

    k = dup_sign_variations(f, K)

    if k == 1:
        a, b, c, d = a1, b1, c1, d1
    else:
        f = dup_shift(dup_reverse(g), K.one, K)

        if not dup_eval(f, K.zero, K):
            f = dup_rshift(f, 1, K)

        a, b, c, d = b, a + b, d, c + d

    return f, (a, b, c, d)

def dup_inner_refine_real_root(f, M, K, eps=None, steps=None, disjoint=None, fast=False, mobius=False):
    """Refine a positive root of `f` given a Mobius transform or an interval. """
    F = K.get_field()

    if len(M) == 2:
        a, b, c, d = _mobius_from_interval(M, F)
    else:
        a, b, c, d = M

    while not c:
        f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c,
            d), K, fast=fast)

    if eps is not None and steps is not None:
        for i in xrange(0, steps):
            if abs(F(a, c) - F(b, d)) >= eps:
                f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c, d), K, fast=fast)
            else:
                break
    else:
        if eps is not None:
            while abs(F(a, c) - F(b, d)) >= eps:
                f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c, d), K, fast=fast)

        if steps is not None:
            for i in xrange(0, steps):
                f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c, d), K, fast=fast)

    if disjoint is not None:
        while True:
            u, v = _mobius_to_interval((a, b, c, d), F)

            if v <= disjoint or disjoint <= u:
                break
            else:
                f, (a, b, c, d) = dup_step_refine_real_root(f, (a, b, c, d), K, fast=fast)

    if not mobius:
        return _mobius_to_interval((a, b, c, d), F)
    else:
        return f, (a, b, c, d)

def dup_outer_refine_real_root(f, s, t, K, eps=None, steps=None, disjoint=None, fast=False):
    """Refine a positive root of `f` given an interval `(s, t)`. """
    a, b, c, d = _mobius_from_interval((s, t), K.get_field())

    f = dup_transform(f, dup_strip([a, b]),
                         dup_strip([c, d]), K)

    if dup_sign_variations(f, K) != 1:
        raise RefinementFailed("there should be exactly one root in (%s, %s) interval" % (s, t))

    return dup_inner_refine_real_root(f, (a, b, c, d), K, eps=eps, steps=steps, disjoint=disjoint, fast=fast)

def dup_refine_real_root(f, s, t, K, eps=None, steps=None, disjoint=None, fast=False):
    """Refine real root's approximating interval to the given precision. """
    if K.is_QQ:
        (_, f), K = dup_clear_denoms(f, K, convert=True), K.get_ring()
    elif not K.is_ZZ:
        raise DomainError("real root refinement not supported over %s" % K)

    if s == t:
        return (s, t)

    if s > t:
        s, t = t, s

    negative = False

    if s < 0:
        if t <= 0:
            f, s, t, negative = dup_mirror(f, K), -t, -s, True
        else:
            raise ValueError("can't refine a real root in (%s, %s)" % (s, t))

    if negative and disjoint is not None:
        if disjoint < 0:
            disjoint = -disjoint
        else:
            disjoint = None

    s, t = dup_outer_refine_real_root(
        f, s, t, K, eps=eps, steps=steps, disjoint=disjoint, fast=fast)

    if negative:
        return (-t, -s)
    else:
        return ( s, t)

def dup_inner_isolate_real_roots(f, K, eps=None, fast=False):
    """Internal function for isolation positive roots up to given precision. 
       
       References:
       ===========
           1. <NAME> and <NAME>: A Comparative Study of Two Real Root         
           Isolation Methods . Nonlinear Analysis: Modelling and Control, Vol. 10, No. 4, 297-304,    
           2005.
           2. <NAME>, <NAME> and <NAME>: Improving the  
           Performance of the Continued Fractions Method Using new Bounds of Positive Roots. Nonlinear  
           Analysis: Modelling and Control, Vol. 13, No. 3, 265-279, 2008.
    """
    a, b, c, d = K.one, K.zero, K.zero, K.one

    k = dup_sign_variations(f, K)

    if k == 0:
        return []
    if k == 1:
        roots = [dup_inner_refine_real_root(
            f, (a, b, c, d), K, eps=eps, fast=fast, mobius=True)]
    else:
        roots, stack = [], [(a, b, c, d, f, k)]

        while stack:
            a, b, c, d, f, k = stack.pop()

            A = dup_root_lower_bound(f, K)

            if A is not None:
                A = K(int(A))
            else:
                A = K.zero

            if fast and A > 16:
                f = dup_scale(f, A, K)
                a, c, A = A*a, A*c, K.one

            if A >= K.one:
                f = dup_shift(f, A, K)
                b, d = A*a + b, A*c + d

                if not dup_TC(f, K):
                    roots.append((f, (b, b, d, d)))
                    f = dup_rshift(f, 1, K)

                k = dup_sign_variations(f, K)

                if k == 0:
                    continue
                if k == 1:
                    roots.append(dup_inner_refine_real_root(
                        f, (a, b, c, d), K, eps=eps, fast=fast, mobius=True))
                    continue

            f1 = dup_shift(f, K.one, K)

            a1, b1, c1, d1, r = a, a + b, c, c + d, 0

            if not dup_TC(f1, K):
                roots.append((f1, (b1, b1, d1, d1)))
                f1, r = dup_rshift(f1, 1, K), 1

            k1 = dup_sign_variations(f1, K)
            k2 = k - k1 - r

            a2, b2, c2, d2 = b, a + b, d, c + d

            if k2 > 1:
                f2 = dup_shift(dup_reverse(f), K.one, K)

                if not dup_TC(f2, K):
                    f2 = dup_rshift(f2, 1, K)

                k2 = dup_sign_variations(f2, K)
            else:
                f2 = None

            if k1 < k2:
                a1, a2, b1, b2 = a2, a1, b2, b1
                c1, c2, d1, d2 = c2, c1, d2, d1
                f1, f2, k1, k2 = f2, f1, k2, k1

            if not k1:
                continue

            if f1 is None:
                f1 = dup_shift(dup_reverse(f), K.one, K)

                if not dup_TC(f1, K):
                    f1 = dup_rshift(f1, 1, K)

            if k1 == 1:
                roots.append(dup_inner_refine_real_root(
                    f1, (a1, b1, c1, d1), K, eps=eps, fast=fast, mobius=True))
            else:
                stack.append((a1, b1, c1, d1, f1, k1))

            if not k2:
                continue

            if f2 is None:
                f2 = dup_shift(dup_reverse(f), K.one, K)

                if not dup_TC(f2, K):
                    f2 = dup_rshift(f2, 1, K)

            if k2 == 1:
                roots.append(dup_inner_refine_real_root(
                    f2, (a2, b2, c2, d2), K, eps=eps, fast=fast, mobius=True))
            else:
                stack.append((a2, b2, c2, d2, f2, k2))

    return roots

def _discard_if_outside_interval(f, M, inf, sup, K, negative, fast, mobius):
    """Discard an isolating interval if outside ``(inf, sup)``. """
    F = K.get_field()

    while True:
        u, v = _mobius_to_interval(M, F)

        if negative:
            u, v = -v, -u

        if (inf is None or u >= inf) and (sup is None or v <= sup):
            if not mobius:
                return u, v
            else:
                return f, M
        elif (sup is not None and u > sup) or (inf is not None and v < inf):
            return None
        else:
            f, M = dup_step_refine_real_root(f, M, K, fast=fast)

def dup_inner_isolate_positive_roots(f, K, eps=None, inf=None, sup=None, fast=False, mobius=False):
    """Iteratively compute disjoint positive root isolation intervals. """
    if sup is not None and sup < 0:
        return []

    roots = dup_inner_isolate_real_roots(f, K, eps=eps, fast=fast)

    F, results = K.get_field(), []

    if inf is not None or sup is not None:
        for f, M in roots:
            result = _discard_if_outside_interval(f, M, inf, sup, K, False, fast, mobius)

            if result is not None:
                results.append(result)
    elif not mobius:
        for f, M in roots:
            u, v = _mobius_to_interval(M, F)
            results.append((u, v))
    else:
        results = roots

    return results

def dup_inner_isolate_negative_roots(f, K, inf=None, sup=None, eps=None, fast=False, mobius=False):
    """Iteratively compute disjoint negative root isolation intervals. """
    if inf is not None and inf >= 0:
        return []

    roots = dup_inner_isolate_real_roots(dup_mirror(f, K), K, eps=eps, fast=fast)

    F, results = K.get_field(), []

    if inf is not None or sup is not None:
        for f, M in roots:
            result = _discard_if_outside_interval(f, M, inf, sup, K, True, fast, mobius)

            if result is not None:
                results.append(result)
    elif not mobius:
        for f, M in roots:
            u, v = _mobius_to_interval(M, F)
            results.append((-v, -u))
    else:
        results = roots

    return results

def _isolate_zero(f, K, inf, sup, basis=False, sqf=False):
    """Handle special case of CF algorithm when ``f`` is homogeneous. """
    j, f = dup_terms_gcd(f, K)

    if j > 0:
        F = K.get_field()

        if (inf is None or inf <= 0) and (sup is None or 0 <= sup):
            if not sqf:
                if not basis:
                    return [((F.zero, F.zero), j)], f
                else:
                    return [((F.zero, F.zero), j, [K.one, K.zero])], f
            else:
                return [(F.zero, F.zero)], f

    return [], f

def dup_isolate_real_roots_sqf(f, K, eps=None, inf=None, sup=None, fast=False, blackbox=False):
    """Isolate real roots of a square-free polynomial using the Vincent-Akritas-Strzebonski (VAS) CF approach. 
    
       References:
       ===========
       1. <NAME> and <NAME>: A Comparative Study of Two Real Root Isolation Methods. 
       Nonlinear Analysis: Modelling and Control, Vol. 10, No. 4, 297-304, 2005.
       2. <NAME>, <NAME> and <NAME>: Improving the Performance 
       of the Continued Fractions Method Using New Bounds of Positive Roots. 
        Nonlinear Analysis: Modelling and Control, Vol. 13, No. 3, 265-279, 2008.
    """
    if K.is_QQ:
        (_, f), K = dup_clear_denoms(f, K, convert=True), K.get_ring()
    elif not K.is_ZZ:
        raise DomainError("isolation of real roots not supported over %s" % K)

    if dup_degree(f) <= 0:
        return []

    I_zero, f = _isolate_zero(f, K, inf, sup, basis=False, sqf=True)

    I_neg = dup_inner_isolate_negative_roots(f, K, eps=eps, inf=inf, sup=sup, fast=fast)
    I_pos = dup_inner_isolate_positive_roots(f, K, eps=eps, inf=inf, sup=sup, fast=fast)
{'fraction_non_alphanumeric': 0.13124957018086789, 'fraction_numerical': 0.017330307406643285, 'mean_word_length': 1.7798700057350412, 'pattern_counts': {'":': 0, '<': 52, '<?xml version=': 0, '>': 66, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1050281', 'n_tokens_mistral': 11104, 'n_tokens_neox': 10402, 'n_words': 3305}