def test_binomial_coefficients_list():
    assert binomial_coefficients_list(0) == [1]
    assert binomial_coefficients_list(1) == [1, 1]
    assert binomial_coefficients_list(2) == [1, 2, 1]
    assert binomial_coefficients_list(3) == [1, 3, 3, 1]
    assert binomial_coefficients_list(4) == [1, 4, 6, 4, 1]
    assert binomial_coefficients_list(5) == [1, 5, 10, 10, 5, 1]
    assert binomial_coefficients_list(6) == [1, 6, 15, 20, 15, 6, 1]

 def _compute_num_chambers(self):
     """Computes the number of chambers defined by the hyperplanes
     corresponding to the normal vectors."""
     d = self.rank
     n = self.num_normal_vectors
     raw_cfs = sp.binomial_coefficients_list(n)
     cfs = np.array([(-1)**i * raw_cfs[i] for i in range(n + 1)])
     powers = np.array([max(entry, 0)
                        for entry in [d - k for k in range(n + 1)]])
     ys = np.array([-1] * len(powers))
     return (-1)**d * sum(cfs * (ys**powers))

def mu(f,a,n,x,y):
    binom = sympy.binomial_coefficients_list(n)
    binom = map(numpy.double, binom)
    normf = numpy.sqrt(sum(numpy.abs(a[k](x))**2 * 1/binom[k] 
                           for k in xrange(n+1)
                           )
                       )
    Delta = numpy.sqrt(numpy.double(n)) * (1 + numpy.abs(y))
    normy = 1 + numpy.abs(y)

    return normf * Delta / (2 * normy)

def _new_polynomial(F,X,Y,tau,l):
    """
    Computes the next iterate of the newton-puiseux algorithms. Given
    the Puiseux data `\tau = (q,\mu,m,\beta)` ``_new_polynomial``
    returns .. math:
    
        \tilde{F} = F(\mu X^q,X^m(\beta+Y))/X \in \mathbb{L}(\mu,\beta)(X)[Y]

    In this algorithm, the choice of parameters will always result in
    .. math:

        \tilde{F} \in \mathbb{L}(\mu,\beta)[X,Y]

    Algorithm:

    Calling sympy.Poly() with new generators (i.e. [x,y]) takes a long
    time.  Hence, the technique below.
    """
    q,mu,m,beta,eta = tau
    d = {}
    
    # for each monomial of the form
    #
    #     c * x**a * y**b
    #
    # compute the appropriate new terms after applying the
    # transformation
    #
    #     x |--> mu * x**q
    #     y |--> eta * x**m * (beta+y)
    #
    for (a,b),c in F.as_dict().iteritems():
        binom = sympy.binomial_coefficients_list(b)
        new_a = int(q*a + m*b)
        for i in xrange(b+1):
            # the coefficient of the x***(qa+mb) * y**i term
            new_c = c * (mu**a) * (eta**b) * (binom[i]) * (beta**(b-i))
            try:
                d[(new_a,i)] += new_c
            except KeyError:
                d[(new_a,i)] = new_c

    # now perform the polynomial division by x**l. In the case when
    # the curve is singular there will be a cancellation resulting in
    # a term of the form (0,0):0 . Creating a new polynomial
    # containing such a term will result in the zero polynomial.
    new_d = dict([((a-l,b),c) for (a,b),c in d.iteritems()])
    Fnew = sympy.Poly.from_dict(new_d, gens=[X,Y], domain=sympy.EX)
    return Fnew

def test_binomial_coefficients():
    for n in range(15):
        c = binomial_coefficients(n)
        l = [c[k] for k in sorted(c)]
        assert l == binomial_coefficients_list(n)