Randomized tests of GiNaC / PyNaC

sage.symbolic.random_tests.assert_strict_weak_order(a, b, c, cmp_func)[source]

Check that cmp_func is a strict weak order on the elements a,b,c.

A strict weak order is a binary relation < such that

  • For all \(x\), it is not the case that \(x < x\) (irreflexivity).

  • For all \(x\not=y\), if \(x < y\) then it is not the case that \(y < x\) (asymmetry).

  • For all \(x\), \(y\), and \(z\), if \(x < y\) and \(y < z\) then \(x < z\) (transitivity).

  • For all \(x\), \(y\), and \(z\), if x is incomparable with \(y\), and \(y\) is incomparable with \(z\), then \(x\) is incomparable with \(z\) (transitivity of incomparability).

INPUT:

  • a, b, c – anything that can be compared by cmp_func

  • cmp_func – function of two arguments that returns their comparison (i.e. either True or False)

OUTPUT:

Nothing. Raises a ValueError if cmp_func is not a strict weak order on the three given elements.

REFERENCES:

Wikipedia article Strict_weak_ordering

EXAMPLES:

The usual ordering of integers is a strict weak order:

sage: from sage.symbolic.random_tests import assert_strict_weak_order
sage: a, b, c = [randint(-10, 10) for i in range(3)]
sage: assert_strict_weak_order(a, b, c, lambda x, y: x < y)

sage: x = [-SR(oo), SR(0), SR(oo)]
sage: cmp_M = matrix(3, 3, 0)
sage: for i in range(3):
....:     for j in range(3):
....:         if x[i] < x[j]:
....:             cmp_M[i, j] = -1
....:         elif x[i] > x[j]:
....:             cmp_M[i, j] = 1
sage: cmp_M
[ 0 -1 -1]
[ 1  0 -1]
[ 1  1  0]

>>> from sage.all import *
>>> from sage.symbolic.random_tests import assert_strict_weak_order
>>> a, b, c = [randint(-Integer(10), Integer(10)) for i in range(Integer(3))]
>>> assert_strict_weak_order(a, b, c, lambda x, y: x < y)

>>> x = [-SR(oo), SR(Integer(0)), SR(oo)]
>>> cmp_M = matrix(Integer(3), Integer(3), Integer(0))
>>> for i in range(Integer(3)):
...     for j in range(Integer(3)):
...         if x[i] < x[j]:
...             cmp_M[i, j] = -Integer(1)
...         elif x[i] > x[j]:
...             cmp_M[i, j] = Integer(1)
>>> cmp_M
[ 0 -1 -1]
[ 1  0 -1]
[ 1  1  0]
sage.symbolic.random_tests.choose_from_prob_list(lst)[source]

INPUT:

  • lst – list of tuples, where the first element of each tuple is a nonnegative float (a probability), and the probabilities sum to one

OUTPUT:

A tuple randomly selected from the list according to the given probabilities.

EXAMPLES:

sage: from sage.symbolic.random_tests import *
sage: v = [(0.1, False), (0.9, True)]
sage: choose_from_prob_list(v)  # random
(0.900000000000000, True)
sage: true_count = 0
sage: total_count = 0
sage: def more_samples():
....:     global true_count, total_count
....:     for _ in range(10000):
....:         total_count += 1.0
....:         if choose_from_prob_list(v)[1]:
....:             true_count += 1.0
sage: more_samples()
sage: while abs(true_count/total_count - 0.9) > 0.01:
....:     more_samples()

>>> from sage.all import *
>>> from sage.symbolic.random_tests import *
>>> v = [(RealNumber('0.1'), False), (RealNumber('0.9'), True)]
>>> choose_from_prob_list(v)  # random
(0.900000000000000, True)
>>> true_count = Integer(0)
>>> total_count = Integer(0)
>>> def more_samples():
...     global true_count, total_count
...     for _ in range(Integer(10000)):
...         total_count += RealNumber('1.0')
...         if choose_from_prob_list(v)[Integer(1)]:
...             true_count += RealNumber('1.0')
>>> more_samples()
>>> while abs(true_count/total_count - RealNumber('0.9')) > RealNumber('0.01'):
...     more_samples()
sage.symbolic.random_tests.normalize_prob_list(pl, extra=())[source]

INPUT:

  • pl – list of tuples, where the first element of each tuple is a floating-point number (representing a relative probability). The second element of each tuple may be a list or any other kind of object.

  • extra – tuple which is to be appended to every tuple in pl

This function takes such a list of tuples (a “probability list”) and normalizes the probabilities so that they sum to one. If any of the values are lists, then those lists are first normalized; then the probabilities in the list are multiplied by the main probability and the sublist is merged with the main list.

For example, suppose we want to select between group A and group B with 50% probability each. Then within group A, we select A1 or A2 with 50% probability each (so the overall probability of selecting A1 is 25%); and within group B, we select B1, B2, or B3 with probabilities in a 1:2:2 ratio.

EXAMPLES:

sage: from sage.symbolic.random_tests import *
sage: A = [(0.5, 'A1'), (0.5, 'A2')]
sage: B = [(1, 'B1'), (2, 'B2'), (2, 'B3')]
sage: top = [(50, A, 'Group A'), (50, B, 'Group B')]
sage: normalize_prob_list(top)
[(0.250000000000000, 'A1', 'Group A'), (0.250000000000000, 'A2', 'Group A'), (0.1, 'B1', 'Group B'), (0.2, 'B2', 'Group B'), (0.2, 'B3', 'Group B')]

>>> from sage.all import *
>>> from sage.symbolic.random_tests import *
>>> A = [(RealNumber('0.5'), 'A1'), (RealNumber('0.5'), 'A2')]
>>> B = [(Integer(1), 'B1'), (Integer(2), 'B2'), (Integer(2), 'B3')]
>>> top = [(Integer(50), A, 'Group A'), (Integer(50), B, 'Group B')]
>>> normalize_prob_list(top)
[(0.250000000000000, 'A1', 'Group A'), (0.250000000000000, 'A2', 'Group A'), (0.1, 'B1', 'Group B'), (0.2, 'B2', 'Group B'), (0.2, 'B3', 'Group B')]
sage.symbolic.random_tests.random_expr(size, nvars=1, ncoeffs=None, var_frac=0.5, internal=[(0.6, [(0.3, <built-in function add>), (0.1, <built-in function sub>), (0.3, <built-in function mul>), (0.2, <built-in function truediv>), (0.1, <built-in function pow>)], 2), (0.2, [(0.8, <built-in function neg>), (0.2, <built-in function inv>)], 1), (0.2, [(1.0, Ei, 1), (1.0, Order, 1), (1.0, _swap_harmonic, 2), (1.0, abs, 1), (1.0, airy_ai, 1), (1.0, airy_ai_prime, 1), (1.0, airy_bi, 1), (1.0, airy_bi_prime, 1), (1.0, arccos, 1), (1.0, arccosh, 1), (1.0, arccot, 1), (1.0, arccoth, 1), (1.0, arccsc, 1), (1.0, arccsch, 1), (1.0, arcsec, 1), (1.0, arcsech, 1), (1.0, arcsin, 1), (1.0, arcsinh, 1), (1.0, arctan, 1), (1.0, arctan2, 2), (1.0, arctanh, 1), (1.0, arg, 1), (1.0, bessel_I, 2), (1.0, bessel_J, 2), (1.0, bessel_K, 2), (1.0, bessel_Y, 2), (1.0, beta, 2), (1.0, binomial, 2), (1.0, ceil, 1), (1.0, chebyshev_T, 2), (1.0, chebyshev_U, 2), (1.0, complex_root_of, 2), (1.0, conjugate, 1), (1.0, cos, 1), (1.0, cos_integral, 1), (1.0, cosh, 1), (1.0, cosh_integral, 1), (1.0, cot, 1), (1.0, coth, 1), (1.0, csc, 1), (1.0, csch, 1), (1.0, dickman_rho, 1), (1.0, dilog, 1), (1.0, dirac_delta, 1), (1.0, elliptic_e, 2), (1.0, elliptic_ec, 1), (1.0, elliptic_eu, 2), (1.0, elliptic_f, 2), (1.0, elliptic_kc, 1), (1.0, elliptic_pi, 3), (1.0, erf, 1), (1.0, erfc, 1), (1.0, erfi, 1), (1.0, erfinv, 1), (1.0, exp, 1), (1.0, exp_integral_e, 2), (1.0, exp_integral_e1, 1), (1.0, exp_polar, 1), (1.0, factorial, 1), (1.0, floor, 1), (1.0, frac, 1), (1.0, fresnel_cos, 1), (1.0, fresnel_sin, 1), (1.0, gamma_inc_lower, 2), (1.0, gegenbauer, 3), (1.0, gen_laguerre, 3), (1.0, gen_legendre_P, 3), (1.0, gen_legendre_Q, 3), (1.0, hahn, 5), (1.0, hankel1, 2), (1.0, hankel2, 2), (1.0, harmonic_number, 1), (1.0, heaviside, 1), (1.0, hermite, 2), (1.0, hurwitz_zeta, 2), (1.0, hypergeometric_M, 3), (1.0, hypergeometric_U, 3), (1.0, imag_part, 1), (1.0, integrate, 4), (1.0, inverse_jacobi_cd, 2), (1.0, inverse_jacobi_cn, 2), (1.0, inverse_jacobi_cs, 2), (1.0, inverse_jacobi_dc, 2), (1.0, inverse_jacobi_dn, 2), (1.0, inverse_jacobi_ds, 2), (1.0, inverse_jacobi_nc, 2), (1.0, inverse_jacobi_nd, 2), (1.0, inverse_jacobi_ns, 2), (1.0, inverse_jacobi_sc, 2), (1.0, inverse_jacobi_sd, 2), (1.0, inverse_jacobi_sn, 2), (1.0, jacobi_P, 4), (1.0, jacobi_am, 2), (1.0, jacobi_cd, 2), (1.0, jacobi_cn, 2), (1.0, jacobi_cs, 2), (1.0, jacobi_dc, 2), (1.0, jacobi_dn, 2), (1.0, jacobi_ds, 2), (1.0, jacobi_nc, 2), (1.0, jacobi_nd, 2), (1.0, jacobi_ns, 2), (1.0, jacobi_sc, 2), (1.0, jacobi_sd, 2), (1.0, jacobi_sn, 2), (1.0, krawtchouk, 4), (1.0, kronecker_delta, 2), (1.0, laguerre, 2), (1.0, lambert_w, 2), (1.0, legendre_P, 2), (1.0, legendre_Q, 2), (1.0, log, 2), (1.0, log_gamma, 1), (1.0, log_integral, 1), (1.0, log_integral_offset, 1), (1.0, meixner, 4), (1.0, polylog, 2), (1.0, prime_pi, 1), (1.0, product, 4), (1.0, real_nth_root, 2), (1.0, real_part, 1), (1.0, sec, 1), (1.0, sech, 1), (1.0, sgn, 1), (1.0, sin, 1), (1.0, sin_integral, 1), (1.0, sinh, 1), (1.0, sinh_integral, 1), (1.0, spherical_bessel_J, 2), (1.0, spherical_bessel_Y, 2), (1.0, spherical_hankel1, 2), (1.0, spherical_hankel2, 2), (1.0, spherical_harmonic, 4), (1.0, stieltjes, 1), (1.0, struve_H, 2), (1.0, struve_L, 2), (1.0, sum, 4), (1.0, tan, 1), (1.0, tanh, 1), (1.0, unit_step, 1), (1.0, zeta, 1), (1.0, zetaderiv, 2)])], nullary=[(1.0, pi), (1.0, e), (0.05, golden_ratio), (0.05, log2), (0.05, euler_gamma), (0.05, catalan), (0.05, khinchin), (0.05, twinprime), (0.05, mertens)], nullary_frac=0.2, coeff_generator=<bound method RationalField.random_element of Rational Field>, verbose=False)[source]

Produce a random symbolic expression of the given size. By default, the expression involves (at most) one variable, an arbitrary number of coefficients, and all of the symbolic functions and constants (from the probability lists full_internal and full_nullary). It is possible to adjust the ratio of leaves between symbolic constants, variables, and coefficients (var_frac gives the fraction of variables, and nullary_frac the fraction of symbolic constants; the remaining leaves are coefficients).

The actual mix of symbolic constants and internal nodes can be modified by specifying different probability lists.

To use a different type for coefficients, you can specify coeff_generator, which should be a function that will return a random coefficient every time it is called.

This function will often raise an error because it tries to create an erroneous expression (such as a division by zero).

EXAMPLES:

sage: from sage.symbolic.random_tests import *
sage: some_functions = [arcsinh, arctan, arctan2, arctanh,
....: arg, beta, binomial, ceil, conjugate, cos, cosh, cot, coth,
....: elliptic_pi, erf, exp, factorial, floor, heaviside, imag_part,
....: sech, sgn, sin, sinh, tan, tanh, unit_step, zeta, zetaderiv]
sage: my_internal = [(0.6, full_binary, 2), (0.2, full_unary, 1),
....: (0.2, [(1.0,f,f.number_of_arguments()) for f in some_functions])]
sage: set_random_seed(1)
sage: random_expr(50, nvars=3, internal=my_internal,  # not tested  # known bug
....:             coeff_generator=CDF.random_element)
(v1^(0.9713408427702117 + 0.195868299334218*I)/cot(-pi + v1^2 + v3) + tan(arctan(v2 + arctan2(-0.35859061674557324 + 0.9407509502498164*I, v3) - 0.8419115504372718 + 0.30375717982404615*I) + arctan2((0.2275357305882964 - 0.8258002386106038*I)/factorial(v2), -v3 - 0.7604559947718565 - 0.5543672548552057*I) + ceil(1/arctan2(v1, v1))))/v2
sage: random_expr(5, verbose=True)  # not tested  # known bug
About to apply <built-in function inv> to [31]
About to apply sgn to [v1]
About to apply <built-in function add> to [1/31, sgn(v1)]
sgn(v1) + 1/31

>>> from sage.all import *
>>> from sage.symbolic.random_tests import *
>>> some_functions = [arcsinh, arctan, arctan2, arctanh,
... arg, beta, binomial, ceil, conjugate, cos, cosh, cot, coth,
... elliptic_pi, erf, exp, factorial, floor, heaviside, imag_part,
... sech, sgn, sin, sinh, tan, tanh, unit_step, zeta, zetaderiv]
>>> my_internal = [(RealNumber('0.6'), full_binary, Integer(2)), (RealNumber('0.2'), full_unary, Integer(1)),
... (RealNumber('0.2'), [(RealNumber('1.0'),f,f.number_of_arguments()) for f in some_functions])]
>>> set_random_seed(Integer(1))
>>> random_expr(Integer(50), nvars=Integer(3), internal=my_internal,  # not tested  # known bug
...             coeff_generator=CDF.random_element)
(v1^(0.9713408427702117 + 0.195868299334218*I)/cot(-pi + v1^2 + v3) + tan(arctan(v2 + arctan2(-0.35859061674557324 + 0.9407509502498164*I, v3) - 0.8419115504372718 + 0.30375717982404615*I) + arctan2((0.2275357305882964 - 0.8258002386106038*I)/factorial(v2), -v3 - 0.7604559947718565 - 0.5543672548552057*I) + ceil(1/arctan2(v1, v1))))/v2
>>> random_expr(Integer(5), verbose=True)  # not tested  # known bug
About to apply <built-in function inv> to [31]
About to apply sgn to [v1]
About to apply <built-in function add> to [1/31, sgn(v1)]
sgn(v1) + 1/31
sage.symbolic.random_tests.random_expr_helper(n_nodes, internal, leaves, verbose)[source]

Produce a random symbolic expression of size n_nodes (or slightly larger). Internal nodes are selected from the internal probability list; leaves are selected from leaves. If verbose is True, then a message is printed before creating an internal node.

EXAMPLES:

sage: from sage.symbolic.random_tests import *
sage: a = random_expr_helper(9, [(0.5, operator.add, 2),
....:     (0.5, operator.neg, 1)], [(0.5, 1), (0.5, x)], True)
About to apply <built-in function ...

>>> from sage.all import *
>>> from sage.symbolic.random_tests import *
>>> a = random_expr_helper(Integer(9), [(RealNumber('0.5'), operator.add, Integer(2)),
...     (RealNumber('0.5'), operator.neg, Integer(1))], [(RealNumber('0.5'), Integer(1)), (RealNumber('0.5'), x)], True)
About to apply <built-in function ...

In small cases we will see all cases quickly:

sage: def next_expr():
....:     return random_expr_helper(
....:         6, [(0.5, operator.add, 2), (0.5, operator.neg, 1)],
....:         [(0.5, 1), (0.5, x)], False)
sage: all_exprs = set()
sage: for a in range(-4, 5):
....:     for b in range(-4+abs(a), 5-abs(a)):
....:         if a % 2 and abs(a) + abs(b) == 4 and sign(a) != sign(b):
....:             continue
....:         all_exprs.add(a*x + b)
sage: our_exprs = set()
sage: while our_exprs != all_exprs:
....:    our_exprs.add(next_expr())

>>> from sage.all import *
>>> def next_expr():
...     return random_expr_helper(
...         Integer(6), [(RealNumber('0.5'), operator.add, Integer(2)), (RealNumber('0.5'), operator.neg, Integer(1))],
...         [(RealNumber('0.5'), Integer(1)), (RealNumber('0.5'), x)], False)
>>> all_exprs = set()
>>> for a in range(-Integer(4), Integer(5)):
...     for b in range(-Integer(4)+abs(a), Integer(5)-abs(a)):
...         if a % Integer(2) and abs(a) + abs(b) == Integer(4) and sign(a) != sign(b):
...             continue
...         all_exprs.add(a*x + b)
>>> our_exprs = set()
>>> while our_exprs != all_exprs:
...    our_exprs.add(next_expr())
sage.symbolic.random_tests.random_integer_vector(n, length)[source]

Give a random list of length length, consisting of nonnegative integers that sum to n.

This is an approximation to IntegerVectors(n, length).random_element(). That gives values uniformly at random, but might be slow; this routine is not uniform, but should always be fast.

(This routine is uniform if length is 1 or 2; for longer vectors, we prefer approximately balanced vectors, where all the values are around \(n/{length}\).)

EXAMPLES:

sage: from sage.symbolic.random_tests import *
sage: a = random_integer_vector(100, 2); a  # random
[11, 89]
sage: len(a)
2
sage: sum(a)
100

sage: b = random_integer_vector(10000, 20)
sage: len(b)
20
sage: sum(b)
10000

>>> from sage.all import *
>>> from sage.symbolic.random_tests import *
>>> a = random_integer_vector(Integer(100), Integer(2)); a  # random
[11, 89]
>>> len(a)
2
>>> sum(a)
100

>>> b = random_integer_vector(Integer(10000), Integer(20))
>>> len(b)
20
>>> sum(b)
10000

The routine is uniform if length is 2:

sage: true_count = 0
sage: total_count = 0
sage: def more_samples():
....:     global true_count, total_count
....:     for _ in range(1000):
....:         total_count += 1.0
....:         if a == random_integer_vector(100, 2):
....:             true_count += 1.0
sage: more_samples()
sage: while abs(true_count/total_count - 0.01) > 0.01:
....:     more_samples()

>>> from sage.all import *
>>> true_count = Integer(0)
>>> total_count = Integer(0)
>>> def more_samples():
...     global true_count, total_count
...     for _ in range(Integer(1000)):
...         total_count += RealNumber('1.0')
...         if a == random_integer_vector(Integer(100), Integer(2)):
...             true_count += RealNumber('1.0')
>>> more_samples()
>>> while abs(true_count/total_count - RealNumber('0.01')) > RealNumber('0.01'):
...     more_samples()
sage.symbolic.random_tests.test_symbolic_expression_order(repetitions=100)[source]

Test whether the comparison of random symbolic expressions satisfies the strict weak order axioms.

This is important because the C++ extension class uses std::sort() which requires a strict weak order. See also Issue #9880.

EXAMPLES:

sage: from sage.symbolic.random_tests import test_symbolic_expression_order
sage: test_symbolic_expression_order(200)
sage: test_symbolic_expression_order(10000)  # long time

>>> from sage.all import *
>>> from sage.symbolic.random_tests import test_symbolic_expression_order
>>> test_symbolic_expression_order(Integer(200))
>>> test_symbolic_expression_order(Integer(10000))  # long time