def __init__(self):
     self.cols = random.randint(_sage_const_1 , _sage_const_5 )
     self.rows = random.randint(_sage_const_1 , _sage_const_5 )
     ring = random.choice([QQ])
     self.A = random_matrix(ring, self.rows, self.cols)
     self.B = random_matrix(ring, self.rows, self.cols)
     self.game = NormalFormGame([self.A, self.B])

def random_chain_complex(level=1):
    """
    Return a random chain complex, defined by specifying a single
    random matrix in a random degree, with differential of degree
    either 1 or -1.  The matrix is randomly sparse or dense.

    :param level: measure of complexity: the larger this is, the
      larger the matrix can be, and the larger its degree can be in
      the chain complex.
    :type level: positive integer; optional, default 1

    EXAMPLES::

        sage: from sage.homology.tests import random_chain_complex
        sage: C = random_chain_complex()
        sage: C
        Chain complex with at most 2 nonzero terms over Integer Ring
        sage: C.degree_of_differential() # random: either 1 or -1
        1
    """
    bound = 50*level
    nrows = randint(0, bound)
    ncols = randint(0, bound)
    sparseness = bool(randint(0, 1))
    mat = random_matrix(ZZ, nrows, ncols, sparse=sparseness)
    dim = randint(-bound, bound)
    deg = 2 * randint(0, 1) - 1  # -1 or 1
    return ChainComplex({dim: mat}, degree = deg)

def det_padic(A, proof=True, stabilize=2):
    """
    Return the determinant of A, computed using a p-adic/multimodular
    algorithm.

    INPUTS:

    - ``A`` -- a square matrix

    - ``proof`` -- boolean

    - ``stabilize`` (default: 2) -- if proof False, number of successive primes so that
      CRT det must stabilize.

    EXAMPLES::

        sage: import sage.matrix.matrix_integer_dense_hnf as h
        sage: a = matrix(ZZ, 3, [1..9])
        sage: h.det_padic(a)
        0
        sage: a = matrix(ZZ, 3, [1,2,5,-7,8,10,192,5,18])
        sage: h.det_padic(a)
        -3669
        sage: a.determinant(algorithm='ntl')
        -3669
    """
    if not A.is_square():
        raise ValueError("A must be a square matrix")
    r = A.rank()
    if r < A.nrows():
        return ZZ(0)
    v = random_matrix(ZZ, A.nrows(), 1)
    d = A._solve_right_nonsingular_square(v, check_rank=False).denominator()
    return det_given_divisor(A, d, proof=proof, stabilize=stabilize)

def random_inequalities(d, n):
    """
    Random collections of inequalities for testing purposes.

    INPUT:

    - ``d`` -- integer. The dimension.

    - ``n``  -- integer. The number of random inequalities to generate.

    OUTPUT:

    A random set of inequalites as a :class:`StandardAlgorithm` instance.

    EXAMPLES::

        sage: from sage.geometry.polyhedron.double_description import random_inequalities
        sage: P = random_inequalities(5, 10)
        sage: P.run().verify()
    """
    from sage.matrix.constructor import random_matrix
    while True:
        A = random_matrix(QQ, n, d)
        if A.rank() == min(n, d) and not any(a == 0 for a in A.rows()):
            break
    return StandardAlgorithm(A)

def random_lattice(dimension):
    """
    Construct a random ZZ-lattice of a given dimension.
    
    INPUT:
    
    - ``dimension`` -- dimension of the constructed lattice.
    
    OUTPUT:
    
    A lattice with integer basis vectors.
    
    EXAMPLES::
    
        sage: random_lattice(3)
        ZZ-lattice of degree 3 and rank 3
        Inner product matrix:
        [   2    0    0]
        [   0   66  -22]
        [   0  -22 4246]
        Basis matrix:
        [ 0  1 -1]
        [-8  1  1]
        [14 45 45]
        sage: random_lattice(100).dimension()
        100
    """
    basis = random_matrix(ZZ, dimension, dimension)
    return Lattice(basis)

    def bigraphical(self, G, A=None, K=QQ, names=None):
        r"""
        Return a bigraphical hyperplane arrangement.

        INPUT:

        - ``G`` -- graph

        - ``A`` -- list, matrix, dictionary (default: ``None``
          gives semiorder), or the string 'generic'

        - ``K`` -- field (default: `\QQ`)

        - ``names`` -- tuple of strings or ``None`` (default); the
          variable names for the ambient space

        OUTPUT:

        The hyperplane arrangement with hyperplanes `x_i - x_j =
        A[i,j]` and `x_j - x_i = A[j,i]` for each edge `v_i, v_j` of
        ``G``.  The indices `i,j` are the indices of elements of
        ``G.vertices()``.

        EXAMPLES::

            sage: G = graphs.CycleGraph(4)
            sage: G.edges()
            [(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]
            sage: G.edges(labels=False)
            [(0, 1), (0, 3), (1, 2), (2, 3)]
            sage: A = {0:{1:1, 3:2}, 1:{0:3, 2:0}, 2:{1:2, 3:1}, 3:{2:0, 0:2}}
            sage: HA = hyperplane_arrangements.bigraphical(G, A)
            sage: HA.n_regions()
            63
            sage: hyperplane_arrangements.bigraphical(G, 'generic').n_regions()
            65
            sage: hyperplane_arrangements.bigraphical(G).n_regions()
            59

        REFERENCES:

        ..  [BigraphicalArrangements] S. Hopkins, D. Perkinson.
            "Bigraphical Arrangements".
            :arxiv:`1212.4398`
        """
        n = G.num_verts()
        if A is None:  # default to G-semiorder arrangement
            A = matrix(K, n, lambda i, j: 1)
        elif A == 'generic':
            A = random_matrix(ZZ, n, x=10000)
            A = matrix(K, A)
        H = make_parent(K, n, names)
        x = H.gens()
        hyperplanes = []
        for e in G.edges():
            i = G.vertices().index(e[0])
            j = G.vertices().index(e[1])
            hyperplanes.append( x[i] - x[j] - A[i][j])
            hyperplanes.append(-x[i] + x[j] - A[j][i])
        return H(*hyperplanes)

def random_low_weight_bases(N,p,m,NN,weightbound):
    r"""
    Returns list of random integral bases of modular forms of level `N` and
    (even) weight at most weightbound with coefficients reduced modulo
    `(p^m,q^{NN})`.

    INPUT:

    - ``N`` -- positive integer (level).
    - ``p`` -- prime.
    - ``m``, ``NN`` -- positive integers.
    - ``weightbound`` -- (even) positive integer.

    OUTPUT:

    - list of lists of `q`-expansions modulo `(p^m,q^{NN})`.

    EXAMPLES::

        sage: from sage.modular.overconvergent.hecke_series import random_low_weight_bases
        sage: S = random_low_weight_bases(3,7,2,5,6); S # random
        [[4 + 48*q + 46*q^2 + 48*q^3 + 42*q^4 + O(q^5)],
        [3 + 5*q + 45*q^2 + 22*q^3 + 22*q^4 + O(q^5),
        1 + 3*q + 27*q^2 + 27*q^3 + 23*q^4 + O(q^5)],
        [2*q + 4*q^2 + 16*q^3 + 48*q^4 + O(q^5),
        2 + 6*q + q^2 + 3*q^3 + 43*q^4 + O(q^5),
        1 + 2*q + 6*q^2 + 14*q^3 + 4*q^4 + O(q^5)]]
        sage: S[0][0].parent()
        Power Series Ring in q over Ring of integers modulo 49
        sage: S[0][0].prec()
        5

    """
    LWB = low_weight_bases(N,p,m,NN,weightbound)
    # this is "approximately" row reduced (it's the mod p^n reduction of a
    # matrix over ZZ in Hermite form)
    RandomLWB = []
    for i in xrange(len(LWB)):
        n = len(LWB[i])
        c = random_matrix(Zmod(p**m), n)
        while c.det() % p == 0:
            c = random_matrix(Zmod(p**m), n)
        RandomLWB.append([ sum([c[j, k] * LWB[i][k] for k in xrange(n)]) for j in xrange(n) ])

    return RandomLWB

def benchmark_hnf(nrange, bits=4):
    """
    Run benchmark program.

    EXAMPLES:
        sage: import sage.matrix.matrix_integer_dense_hnf as hnf
        sage: hnf.benchmark_hnf([50,100],32)
        ('sage', 50, 32, ...),
        ('sage', 100, 32, ...),
    """
    b = 2**bits
    for n in nrange:
        a = random_matrix(ZZ, n, x=-b,y=b)
        t = cputime()
        h,_ = hnf(a, proof=False)
        tm = cputime(t)
        print '%s,'%(('sage', n, bits, tm),)

def hnf_with_transformation_tests(n=10, m=5, trials=10):
    """
    Use this to randomly test that hnf with transformation matrix
    is working.

    EXAMPLES:
        sage: from sage.matrix.matrix_integer_dense_hnf import hnf_with_transformation_tests
        sage: hnf_with_transformation_tests(n=15,m=10, trials=10)
        0 1 2 3 4 5 6 7 8 9
    """
    import sys
    for i in range(trials):
        print i,
        sys.stdout.flush()
        a = random_matrix(ZZ, n, m)
        w = hnf_with_transformation(a)
        assert w[0] == w[1]*a
        w = hnf_with_transformation(a, proof=False)
        assert w[0] == w[1]*a

def hnf_with_transformation_tests(n=10, m=5, trials=10):
    """
    Use this to randomly test that hnf with transformation matrix
    is working.

    EXAMPLES::

        sage: from sage.matrix.matrix_integer_dense_hnf import hnf_with_transformation_tests
        sage: hnf_with_transformation_tests(n=15,m=10, trials=10)
        0 1 2 3 4 5 6 7 8 9
    """
    import sys
    for i in range(trials):
        print(i, end=" ")
        sys.stdout.flush()
        A = random_matrix(ZZ, n, m)
        H, U = hnf_with_transformation(A)
        assert H == U * A
        H, U = hnf_with_transformation(A, proof=False)
        assert H == U * A

def solve_system_with_difficult_last_row(B, A):
    """
    Solve the matrix equation B*Z = A when the last row of $B$
    contains huge entries.

    INPUT:

    - B -- a square n x n nonsingular matrix with painful big bottom row.
    - A -- an n x k matrix.

    OUTPUT:

    the unique solution to B*Z = A.

    EXAMPLES::

        sage: from sage.matrix.matrix_integer_dense_saturation import solve_system_with_difficult_last_row
        sage: B = matrix(ZZ, 3, [1,2,3, 3,-1,2,939239082,39202803080,2939028038402834]); A = matrix(ZZ,3,2,[1,2,4,3,-1,0])
        sage: X = solve_system_with_difficult_last_row(B, A); X
        [  290668794698843/226075992027744         468068726971/409557956572]
        [-226078357385539/1582531944194208       1228691305937/2866905696004]
        [      2365357795/1582531944194208           -17436221/2866905696004]
        sage: B*X == A
        True
    """
    # See the comments in the function of the same name in matrix_integer_dense_hnf.py.
    # This function is just a generalization of that one to A a matrix.
    C = copy(B)
    while True:
        C[C.nrows()-1] = random_matrix(ZZ,1,C.ncols()).row(0)
        try:
            X = C.solve_right(A)
        except ValueError:
            verbose("Try difficult solve again with different random vector")
        else:
            break
    D = B.matrix_from_rows(range(C.nrows()-1))
    N = D._rational_kernel_flint()
    if N.ncols() != 1:
        verbose("Difficult solve quickly failed.  Using direct approach.")
        return B.solve_right(A)

    tm = verbose("Recover correct linear combinations")
    k = N.matrix_from_columns([0])

    # The sought for solution Z to B*Z = A is some linear combination
    #       Z = X + alpha*k
    #  Let w be the last row of B; then Z satisfies
    #       w * Z = A'
    # where A' is the last row of A.  Thus
    #       w * (X + alpha*k) = A'
    # so    w * X + alpha*w*k = A'
    # so    alpha*w*k  = A' - w*X.
    w = B[-1]  # last row of B
    A_prime = A[-1]  # last row of A
    lhs = w*k
    rhs = A_prime - w * X

    if lhs[0] == 0:
        verbose("Difficult solve quickly failed.  Using direct approach.")
        return B.solve_right(A)

    for i in range(X.ncols()):
        alpha = rhs[i] / lhs[0]
        X.set_column(i, (X.matrix_from_columns([i]) + alpha*k).list())
    verbose("Done getting linear combinations.", tm)
    return X

def solve_system_with_difficult_last_row(B, a):
    """
    Solve B*x = a when the last row of $B$ contains huge entries using
    a clever trick that reduces the problem to solve C*x = a where $C$
    is $B$ but with the last row replaced by something small, along
    with one easy null space computation.  The latter are both solved
    $p$-adically.

    INPUT:

    - B -- a square n x n nonsingular matrix with painful big bottom row.
    - a -- an n x 1 column matrix

    OUTPUT:

    - the unique solution to B*x = a.

    EXAMPLES::

        sage: from sage.matrix.matrix_integer_dense_hnf import solve_system_with_difficult_last_row
        sage: B = matrix(ZZ, 3, [1,2,4, 3,-4,7, 939082,2930982,132902384098234])
        sage: a = matrix(ZZ,3,1, [1,2,5])
        sage: z = solve_system_with_difficult_last_row(B, a)
        sage: z
        [ 106321906985474/132902379815497]
        [132902385037291/1329023798154970]
        [        -5221794/664511899077485]
        sage: B*z
        [1]
        [2]
        [5]
    """
    # Here's how:
    # 1. We make a copy of B but with the last *nasty* row of B replaced
    #    by a random very nice row.
    C = copy(B)
    while True:
        C[C.nrows()-1] = random_matrix(ZZ,1,C.ncols()).row(0)
        # 2. Then we find the unique solution to C * x = a
        try:
            x = C.solve_right(a)
        except ValueError:
            verbose("Try difficult solve again with different random vector")
        else:
            break


    # 3. We next delete the last row of B and find a basis vector k
    #    for the 1-dimensional kernel.
    D = B.matrix_from_rows(range(C.nrows()-1))
    N = D._rational_kernel_iml()
    if N.ncols() != 1:
        verbose("Try difficult solve again with different random vector")
        return solve_system_with_difficult_last_row(B, a)

    k = N.matrix_from_columns([0])

    # 4. The sought for solution z to B*z = a is some linear combination
    #
    #       z = x + alpha*k
    #
    #  of x and k, where k is the above fixed basis for the kernel of D.
    #  Setting w to be the last row of B, this column vector z satisfies
    #
    #       w * z = a'
    #
    # where a' is the last entry of a.  Thus
    #
    #       w * (x + alpha*k) = a'
    #
    # so    w * x + alpha*w*k = a'
    # so    alpha*w*k  = a' - w*x.

    w = B[-1]  # last row of B
    a_prime = a[-1]
    lhs = w*k
    rhs = a_prime - w * x

    if lhs[0] == 0:
        verbose("Try difficult solve again with different random vector")
        return solve_system_with_difficult_last_row(B, a)

    alpha = rhs[0] / lhs[0]
    z = x + alpha*k
    return z

def sanity_checks(times=50, n=8, m=5, proof=True, stabilize=2, check_using_magma = True):
    """
    Run random sanity checks on the modular p-adic HNF with tall and wide matrices
    both dense and sparse.

    INPUT:

    - times -- number of times to randomly try matrices with each shape
    - n -- number of rows
    - m -- number of columns
    - proof -- test with proof true
    - stabilize -- parameter to pass to hnf algorithm when proof is False
    - check_using_magma -- if True use Magma instead of PARI to check
      correctness of computed HNF's. Since PARI's HNF is buggy and slow (as of
      2008-02-16 non-pivot entries sometimes aren't normalized to be
      nonnegative) the default is Magma.

    EXAMPLES::

        sage: import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
        sage: matrix_integer_dense_hnf.sanity_checks(times=5, check_using_magma=False)
        small 8 x 5
        0 1 2 3 4  (done)
        big 8 x 5
        0 1 2 3 4  (done)
        small 5 x 8
        0 1 2 3 4  (done)
        big 5 x 8
        0 1 2 3 4  (done)
        sparse 8 x 5
        0 1 2 3 4  (done)
        sparse 5 x 8
        0 1 2 3 4  (done)
        ill conditioned -- 1000*A -- 8 x 5
        0 1 2 3 4  (done)
        ill conditioned -- 1000*A but one row -- 8 x 5
        0 1 2 3 4  (done)
    """
    import sys
    def __do_check(v):
        """
        This is used internally by the sanity check code.
        """
        for i,a in enumerate(v):
            global sanity
            sanity = a
            print i,
            sys.stdout.flush()
            if check_using_magma:
                if magma(hnf(a)[0]) != magma(a).EchelonForm():
                    print "bug computing hnf of a matrix"
                    print 'a = matrix(ZZ, %s, %s, %s)'%(a.nrows(), a.ncols(), a.list())
                    return
            else:
                if hnf(a)[0] != a.echelon_form(algorithm = 'pari'):
                    print "bug computing hnf of a matrix"
                    print 'a = matrix(ZZ, %s, %s, %s)'%(a.nrows(), a.ncols(), a.list())
                    return
        print " (done)"

    print "small %s x %s"%(n,m)
    __do_check([random_matrix(ZZ, n, m, x=-1,y=1) for _ in range(times)])
    print "big %s x %s"%(n,m)
    __do_check([random_matrix(ZZ, n, m, x=-2^32,y=2^32) for _ in range(times)])

    print "small %s x %s"%(m,n)
    __do_check([random_matrix(ZZ, m, n, x=-1,y=1) for _ in range(times)])
    print "big %s x %s"%(m,n)
    __do_check([random_matrix(ZZ, m, n, x=-2^32,y=2^32) for _ in range(times)])

    print "sparse %s x %s"%(n,m)
    __do_check([random_matrix(ZZ, n, m, density=0.1) for _ in range(times)])
    print "sparse %s x %s"%(m,n)
    __do_check([random_matrix(ZZ, m, n, density=0.1) for _ in range(times)])

    print "ill conditioned -- 1000*A -- %s x %s"%(n,m)
    __do_check([1000*random_matrix(ZZ, n, m, x=-1,y=1) for _ in range(times)])

    print "ill conditioned -- 1000*A but one row -- %s x %s"%(n,m)
    v = []
    for _ in range(times):
        a = 1000*random_matrix(ZZ, n, m, x=-1,y=1)
        a[a.nrows()-1] = a[a.nrows()-1]/1000
        v.append(a)
    __do_check(v)