def rank2_GF(n=500, p=16411, system='sage'):
    """
    Rank over GF(p): Given a (n + 10) x n matrix over GF(p) with
    random entries, compute the rank.

    INPUT:

    - ``n`` - matrix dimension (default: 300)
    - ``p`` - prime number (default: ``16411``)
    - ``system`` - either 'magma' or 'sage' (default: 'sage')

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.rank2_GF(500)
        sage: tm = b.rank2_GF(500, system='magma')  # optional - magma
    """
    if system == 'sage':
        A = random_matrix(GF(p), n+10, n)
        t = cputime()
        v = A.rank()
        return cputime(t)
    elif system == 'magma':
        code = """
n := %s;
A := Random(MatrixAlgebra(GF(%s), n));
t := Cputime();
K := Rank(A);
s := Cputime(t);
"""%(n,p)
        if verbose: print code
        magma.eval(code)
        return float(magma.eval('s'))
    else:
        raise ValueError, 'unknown system "%s"'%system

def charpoly_GF(n=100, p=16411, system='sage'):
    """
    Given a n x n matrix over GF with random entries, compute the
    charpoly.

    INPUT:

    - ``n`` - matrix dimension (default: 100)
    - ``p`` - prime number (default: ``16411``)
    - ``system`` - either 'magma' or 'sage' (default: 'sage')

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.charpoly_GF(100)
        sage: tm = b.charpoly_GF(100, system='magma')  # optional - magma
    """
    if system == 'sage':
        A = random_matrix(GF(p), n, n)
        t = cputime()
        v = A.charpoly()
        return cputime(t)
    elif system == 'magma':
        code = """
n := %s;
A := Random(MatrixAlgebra(GF(%s), n));
t := Cputime();
K := CharacteristicPolynomial(A);
s := Cputime(t);
"""%(n,p)
        if verbose: print code
        magma.eval(code)
        return magma.eval('s')
    else:
        raise ValueError, 'unknown system "%s"'%system

    def test(self, name, seconds=0):
        """
        Repeatedly run 'test_name', where name is passed as an
        argument. If seconds is nonzero, run for that many seconds. If
        seconds is 0, run indefinitely.

        EXAMPLES::

            sage: from sage.modular.arithgroup.tests import Test
            sage: T = Test()
            sage: T.test('relabel',seconds=1)
            test_relabel
            ...
            sage: T.test('congruence_groups',seconds=1)
            test_congruence_groups
            ...
            sage: T.test('contains',seconds=1)
            test_contains
            ...
            sage: T.test('todd_coxeter',seconds=1)
            test_todd_coxeter
            ...
        """
        seconds = float(seconds)
        total = cputime()
        n = 1
        while seconds == 0 or cputime(total) < seconds:
            s = "** test_dimension: number %s"%n
            if seconds > 0:
                s += " (will stop after about %s seconds)"%seconds
            t = cputime()
            self._do(name)
            print "\ttime=%s\telapsed=%s"%(cputime(t),cputime(total))
            n += 1

def invert_hilbert_QQ(n=40, system='sage'):
    """
    Runs the benchmark for calculating the inverse of the hilbert
    matrix over rationals of dimension n.

    INPUT:

    - ``n`` - matrix dimension (default: ``300``)
    - ``system`` - either 'sage' or 'magma' (default: 'sage')

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.invert_hilbert_QQ(30)
        sage: tm = b.invert_hilbert_QQ(30, system='magma')  # optional - magma
    """
    if system == 'sage':
        A = hilbert_matrix(n)
        t = cputime()
        d = A**(-1)
        return cputime(t)
    elif system == 'magma':
        code = """
h := HilbertMatrix(%s);
tinit := Cputime();
d := h^(-1);
s := Cputime(tinit);
delete h;
"""%n
        if verbose: print code
        magma.eval(code)
        return float(magma.eval('s'))

def render_curve_webpage_by_label(label):
    from sage.misc.misc import cputime
    cpt0 = cputime()
    t0 = time.time()
    data = WebEC.by_label(label)
    if data == "Invalid label":
        return elliptic_curve_jump_error(label, {}, wellformed_label=False)
    if data == "Curve not found":
        return elliptic_curve_jump_error(label, {}, wellformed_label=True)
    try:
        lmfdb_label = data.lmfdb_label
    except AttributeError:
        return elliptic_curve_jump_error(label, {}, wellformed_label=False)

    data.modform_display = url_for(".modular_form_display", label=lmfdb_label, number="")

    code = data.code()
    code['show'] = {'magma':'','pari':'','sage':''} # use default show names
    T =  render_template("ec-curve.html",
                           properties2=data.properties,
                           credit=ec_credit(),
                           data=data,
                           # set default show names but actually code snippets are filled in only when needed
                           code=code,
                           bread=data.bread, title=data.title,
                           friends=data.friends,
                           downloads=data.downloads,
                           learnmore=learnmore_list())
    ec_logger.debug("Total walltime: %ss"%(time.time() - t0))
    ec_logger.debug("Total cputime: %ss"%(cputime(cpt0)))
    return T

def test_stat(rangs, longueurs, puissance):
    """
    TESTS::

        sage: from train_track.test_train_track import *
        sage: test_stat([2,3], [3,2], 1) # long time (80s ) # random
        rang:  2 longueur:  3  time:  0.084  train-tracks: 100.0
        rang:  2 longueur:  2  time:  0.076  train-tracks: 100.0
        rang:  3 longueur:  3  time:  0.012  train-tracks: 0.0
        rang:  3 longueur:  2  time:  0.00800000000004  train-tracks: 0.0

    AUTHORS:

    - Thierry Coulbois
    """
    for n in rangs:
        F = FreeGroup(n)
        for l in longueurs:
            stat = 0
            t = cputime()
            for i in range(puissance):
                phi = FreeGroupAutomorphism.random_automorphism(F, l)
                try:
                    f = phi.train_track(relative=True, stable=True)
                    if len(f._strata) == 1:
                        stat += 1
                except Exception as err:
                    print(phi)
                    print(err)
            print("rang: ", n, "longueur: ", l, " time: ",
                   cputime(t) / puissance,
                   " train-tracks: %.1f" % (stat / puissance * 100))

def test(rang, longueur, nombre):
    """
    TESTS::

        sage: from train_track.test_train_track import *
        sage: test(3, 1, 1) # long time (80s on sage.math, 2016) # random
        0 : a->a,b->b,c->ac
        Graph self map:
        Marked graph: a: 0->0, b: 0->0, c: 0->0
        Marking: a->a, b->b, c->c
        Edge map: a->a, b->b, c->ac
        Strata: [set(['a']), set(['c']), set(['b'])]
        -------------------------
        rang:  3 longueur:  1  time:  0.024  train-tracks: 0.0

    AUTHORS:

    - Thierry Coulbois
    """
    F = FreeGroup(rang)

    stat = 0
    t = cputime()

    for i in range(nombre):
        phi = FreeGroupAutomorphism.random_automorphism(F, longueur)
        print(i, ":", phi)
        f = phi.train_track(stable=True, relative=True)
        if len(f._strata) == 1:
            stat = stat + 1
        print(f)
        print("-------------------------")

    print("rang: ", rang, "longueur: ", longueur, " time: ",
           cputime(t) / nombre, " train-tracks: %.1f" % (stat/nombre*100))

def nullspace_GF(n=300, p=16411, system='sage'):
    """
    Given a n+1 x n  matrix over GF(p) with random
    entries, compute the nullspace.

    INPUT:

    - ``n`` - matrix dimension (default: 300)
    - ``p`` - prime number (default: ``16411``)
    - ``system`` - either 'magma' or 'sage' (default: 'sage')

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.nullspace_GF(300)
        sage: tm = b.nullspace_GF(300, system='magma')  # optional - magma
    """
    if system == 'sage':
        A = random_matrix(GF(p), n, n+1)
        t = cputime()
        v = A.kernel()
        return cputime(t)
    elif system == 'magma':
        code = """
n := %s;
A := Random(RMatrixSpace(GF(%s), n, n+1));
t := Cputime();
K := Kernel(A);
s := Cputime(t);
"""%(n,p)
        if verbose: print code
        magma.eval(code)
        return magma.eval('s')
    else:
        raise ValueError, 'unknown system "%s"'%system

def test_cycl(fixed_var, bound, start_var = 7, leap = 1, fixed_degree = False):
    if not fixed_degree:
        p = fixed_var
        n = start_var
        print '#n t_cycl o'

        for i in range(bound):
            R = PolynomialRing(GF(p), name='X')
            f = R.irreducible_element(n, algorithm='random')
            g = R.irreducible_element(n, algorithm='random')
            if f == g:
                g = R.irreducible_element(n, algorithm='random')

            k1 = GF(p**n, name = 'x', modulus = f)
            k2 = GF(p**n, name = 'y', modulus = g)

            w = cputime()
            find_gens_cyclotomic(k1, k2)
            t_cycl = cputime(w)

            o = find_root_order(p, n)[0]

            if i:
                print '%s %s %s' % (n, t_cycl, o)

            for j in range(leap):
                n = next_prime(n)
    else:
        n = fixed_var
        p = start_var
        print '#p t_cycl o'

        for i in range(bound):
            R = PolynomialRing(GF(p), name='X')
            f = R.irreducible_element(n, algorithm='random')
            g = R.irreducible_element(n, algorithm='random')
            if f == g:
                g = R.irreducible_element(n, algorithm='random')

            k1 = GF(p**n, name = 'x', modulus = f)
            k2 = GF(p**n, name = 'y', modulus = g)

            w = cputime()
            find_gens_cyclotomic(k1, k2)
            t_cycl = cputime(w)

            o = find_root_order(p, n)[0]

            if i:
                print '%s %s %s' % (p, t_cycl, o)

            for j in range(leap):
                p = next_prime(p)

def test_ell(fixed_var, bound, start_var = 7, leap = 1, fixed_degree = False):
    if not fixed_degree:
        p = fixed_var
        n = start_var
        print '#n t_ell m'

        for i in range(bound):
            R = PolynomialRing(GF(p), name='X')
            f = R.irreducible_element(n, algorithm='random')
            g = R.irreducible_element(n, algorithm='random')
            if f == g:
                g = R.irreducible_element(n, algorithm='random')

            k1 = GF(p**n, name = 'x', modulus = f)
            k2 = GF(p**n, name = 'y', modulus = g)

            w = cputime()
            isom_elliptic(k1, k2)
            t_ell = cputime(w)

            m = find_m(n, GF(p))[0]

            if i:
                print '%s %s %s' % (n, t_ell, m)

            for j in range(leap):
                n = next_prime(n)
    else:
        n = fixed_var
        p = start_var
        print '#p t_ell m'

        for i in range(bound):
            R = PolynomialRing(GF(p), name='X')
            f = R.irreducible_element(n, algorithm='random')
            g = R.irreducible_element(n, algorithm='random')
            if f == g:
                g = R.irreducible_element(n, algorithm='random')

            k1 = GF(p**n, name = 'x', modulus = f)
            k2 = GF(p**n, name = 'y', modulus = g)

            w = cputime()
            isom_elliptic(k1, k2)
            t_ell = cputime(w)

            m = find_m(n, GF(p))[0]

            if i:
                print '%s %s %s' % (p, t_ell, m)

            for j in range(leap):
                p = next_prime(p)

 def test(self, name, seconds=0):
     """
     Repeatedly run 'test_name', where name is passed as an
     argument. If seconds is nonzero, run for that many seconds. If
     seconds is 0, run indefinitely.
     """
     seconds = float(seconds)
     total = cputime()
     n = 1
     while seconds == 0 or cputime(total) < seconds:
         s = "** test_dimension: number %s"%n
         if seconds > 0:
             s += " (will stop after about %s seconds)"%seconds
         t = cputime()
         self._do(name)
         print("\ttime=%s\telapsed=%s" % (cputime(t), cputime(total)))
         n += 1

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 matrix_add_ZZ(n=200, min=-9, max=9, system='sage', times=50):
    """
    Matrix addition over ZZ
    Given an n x n matrix A and B over ZZ with random entries between
    ``min`` and ``max``, inclusive, compute A + B ``times`` times.

    INPUT:

    - ``n`` - matrix dimension (default: ``200``)
    - ``min`` - minimal value for entries of matrix (default: ``-9``)
    - ``max`` - maximal value for entries of matrix (default: ``9``)
    - ``system`` - either 'sage' or 'magma' (default: 'sage')
    - ``times`` - number of experiments (default: ``50``)

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.matrix_add_ZZ(200)
        sage: tm = b.matrix_add_ZZ(200, system='magma')  # optional - magma
    """
    if system == 'sage':
        A = random_matrix(ZZ, n, n, x=min, y=max+1)
        B = random_matrix(ZZ, n, n, x=min, y=max+1)
        t = cputime()
        for z in range(times):
            v = A + B
        return cputime(t)/times
    elif system == 'magma':
        code = """
n := %s;
min := %s;
max := %s;
A := MatrixAlgebra(IntegerRing(), n)![Random(min,max) : i in [1..n^2]];
B := MatrixAlgebra(IntegerRing(), n)![Random(min,max) : i in [1..n^2]];
t := Cputime();
for z in [1..%s] do
    K := A + B;
end for;
s := Cputime(t);
"""%(n,min,max,times)
        if verbose: print code
        magma.eval(code)
        return float(magma.eval('s'))/times
    else:
        raise ValueError, 'unknown system "%s"'%system

def vecmat_ZZ(n=300, min=-9, max=9, system='sage', times=200):
    """
    Vector matrix multiplication over ZZ.

    Given an n x n  matrix A over ZZ with random entries
    between min and max, inclusive, and v the first row of A,
    compute the product v * A.

    INPUT:

    - ``n`` - matrix dimension (default: ``300``)
    - ``min`` - minimal value for entries of matrix (default: ``-9``)
    - ``max`` - maximal value for entries of matrix (default: ``9``)
    - ``system`` - either 'sage' or 'magma' (default: 'sage')
    - ``times`` - number of runs (default: ``200``)

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.vecmat_ZZ(300)  # long time
        sage: tm = b.vecmat_ZZ(300, system='magma')  # optional - magma
    """
    if system == 'sage':
        A = random_matrix(ZZ, n, n, x=min, y=max+1)
        v = A.row(0)
        t = cputime()
        for z in range(times):
            w = v * A
        return cputime(t)/times
    elif system == 'magma':
        code = """
n := %s;
A := MatrixAlgebra(IntegerRing(), n)![Random(%s,%s) : i in [1..n^2]];
v := A[1];
t := Cputime();
for z in [1..%s] do
    K := v * A;
end for;
s := Cputime(t);
"""%(n,min,max,times)
        if verbose: print code
        magma.eval(code)
        return float(magma.eval('s'))/times
    else:
        raise ValueError, 'unknown system "%s"'%system

def test_E_nbtrace(fixed_var, bound, start_var = 3, leap = 1, fixed_degree = False):
# Evolution of other parameters with p fixed.
    if not fixed_degree:
        p = fixed_var
        n = start_var
        print '#n m len(S_t) t_E compteur'

        for i in range(borne_nbn):
            m, S_t = find_m(n, GF(p))
            k1 = GF(p**n, name = 'x', modulus =
                    PolynomialRing(GF(p), name='X').irreducible_element(n,
                    algorithm='random'))

            w = cputime()
            n_E = find_elliptic_curve(GF(p), k1, (m, S_t))[-1]
            w_t = cputime(w)
            if i :
                #The degree, the value of m, the number of trace candidates,
                # time to find an E, number of elliptic curves tested.
                print '%s %s %s %s %s' % (n, m, len(S_t), w_t, n_E)

            for j in range(leap):
                n = next_prime(n)
# Evolution of other parameters with n fixed.
    else:
        n = fixed_var
        p = start_var
        print '#p m len(S_t) t_E compteur'

        for i in range(borne_nbn):
            m, S_t = find_m(n, GF(p))
            k1 = GF(p**n, name = 'x', modulus =
                    PolynomialRing(GF(p), name='X').irreducible_element(n,
                    algorithm='random'))

            w = cputime()
            n_E = find_elliptic_curve(GF(p), k1, (m, S_t))[-1]
            w_t = cputime(w)
            if i :
                #The degree, the value of m, the number of trace candidates,
                # time to find an E, number of elliptic curves tested.
                print '%s %s %s %s %s' % (p, m, len(S_t), w_t, n_E)

            for j in range(leap):
                p = next_prime(p)

def manyvars(s, num=70000, inlen=1, step=2000):
    """
    Test that > 65,000 variable names works in each system.
    """
    print "Testing -- %s"%s
    t = '"%s"'%('9'*int(inlen))
    try:
        t = cputime()
        w = walltime()
        v = []
        for i in range(num):
            if i%step==0:
                sys.stdout.write('%s '%i)
                sys.stdout.flush()
            v.append(s(t))
        print '\nsuccess -- time = cpu: %s, wall: %s'%(cputime(t), walltime(w))
    except Exception:
        print "%s -- failed!"%s

def MatrixVector_QQ(n=1000,h=100,system='sage',times=1):
    """
    Compute product of square ``n`` matrix by random vector with num and
    denom bounded by ``h`` the given number of ``times``.

    INPUT:

    - ``n`` - matrix dimension (default: ``300``)
    - ``h`` - numerator and denominator bound (default: ``bnd``)
    - ``system`` - either 'sage' or 'magma' (default: 'sage')
    - ``times`` - number of experiments (default: ``1``)

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.MatrixVector_QQ(500)
        sage: tm = b.MatrixVector_QQ(500, system='magma')  # optional - magma
    """
    if system=='sage':
        V=QQ**n
        v=V.random_element(h)
        M=random_matrix(QQ,n)
        t=cputime()
        for i in range(times):
            w=M*v
        return cputime(t)
    elif system == 'magma':
        code = """
            n:=%s;
            h:=%s;
            times:=%s;
            v:=VectorSpace(RationalField(),n)![Random(h)/(Random(h)+1) : i in [1..n]];
            M:=MatrixAlgebra(RationalField(),n)![Random(h)/(Random(h)+1) : i in [1..n^2]];
            t := Cputime();
            for z in [1..times] do
                W:=v*M;
            end for;
            s := Cputime(t);
        """%(n,h,times)
        if verbose: print code
        magma.eval(code)
        return float(magma.eval('s'))
    else:
        raise ValueError, 'unknown system "%s"'%system

def test_gens_cyclotomic(p, n):
    '''
    Test routine for `find_gens_cyclotomic`. Constructs two random
    extensions of F_p of degree n, then calls find_gens_cyclotomic and
    tests that the returned elements have the same minimal polynomial
    over F_p, and that the polynomial has degree n.
    '''
    c, w = cputime(), walltime()
    k1 = GF(p**n, 'z1', modulus='random')
    k2 = GF(p**n, 'z2', modulus='random')
    print "Field creation: CPU %s, Wall %s" % (cputime(c), walltime(w))

    c, w = cputime(), walltime()
    a, b = find_gens_cyclotomic(k1, k2)
    print "Rains' algorithm: CPU %s, Wall %s" % (cputime(c), walltime(w))

    P = a.minpoly()
    assert(P.degree() == n)
    assert(P(b) == 0)

def matrix_multiply_QQ(n=100, bnd=2, system='sage', times=1):
    """
    Given an n x n matrix A over QQ with random entries
    whose numerators and denominators are bounded by bnd,
    compute A * (A+1).

    INPUT:

    - ``n`` - matrix dimension (default: ``300``)
    - ``bnd`` - numerator and denominator bound (default: ``bnd``)
    - ``system`` - either 'sage' or 'magma' (default: 'sage')
    - ``times`` - number of experiments (default: ``1``)

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.matrix_multiply_QQ(100)
        sage: tm = b.matrix_multiply_QQ(100, system='magma')  # optional - magma
    """
    if system == 'sage':
        A = random_matrix(QQ, n, n, num_bound=bnd, den_bound=bnd)
        B = A + 1
        t = cputime()
        for z in range(times):
            v = A * B
        return cputime(t)/times
    elif system == 'magma':
        A = magma(random_matrix(QQ, n, n, num_bound=bnd, den_bound=bnd))
        code = """
n := %s;
A := %s;
B := A + 1;
t := Cputime();
for z in [1..%s] do
    K := A * B;
end for;
s := Cputime(t);
"""%(n, A.name(), times)
        if verbose: print code
        magma.eval(code)
        return float(magma.eval('s'))/times
    else:
        raise ValueError, 'unknown system "%s"'%system

def matrix_multiply_GF(n=100, p=16411, system='sage', times=3):
    """
    Given an n x n matrix A over GF(p) with random entries, compute
    A * (A+1).

    INPUT:

    - ``n`` - matrix dimension (default: 100)
    - ``p`` - prime number (default: ``16411``)
    - ``system`` - either 'magma' or 'sage' (default: 'sage')
    - ``times`` - number of experiments (default: ``3``)

    EXAMPLES::

        sage: import sage.matrix.benchmark as b
        sage: ts = b.matrix_multiply_GF(100, p=19)
        sage: tm = b.matrix_multiply_GF(100, p=19, system='magma')  # optional - magma
    """
    if system == 'sage':
        A = random_matrix(GF(p), n)
        B = A + 1
        t = cputime()
        for n in range(times):
            v = A * B
        return cputime(t) / times
    elif system == 'magma':
        code = """
n := %s;
A := Random(MatrixAlgebra(GF(%s), n));
B := A + 1;
t := Cputime();
for z in [1..%s] do
    K := A * B;
end for;
s := Cputime(t);
"""%(n,p,times)
        if verbose: print code
        magma.eval(code)
        return float(magma.eval('s'))/times
    else:
        raise ValueError, 'unknown system "%s"'%system