Opened 2 years ago

Closed 10 months ago

#29935 closed enhancement (fixed)

implicitly fuzz RNG-dependent doctests with a random random seed

Reported by: dimpase Owned by:
Priority: major Milestone: sage-9.5
Component: doctest framework Keywords: fuzz, random, seed
Cc: gh-kliem, mjo, gh-DaveWitteMorris, slelievre, mantepse Merged in:
Authors: Jonathan Kliem Reviewers: Michael Orlitzky
Report Upstream: N/A Work issues:
Branch: 047379c (Commits, GitHub, GitLab) Commit: 047379c56890113ff59c9eb59276eeca274f4b79
Dependencies: #32667 Stopgaps:

Status badges

Description (last modified by gh-kliem)

Our documentation and tests include a variety of examples and tests involving randomness.

Those depend on a randomness seed, and up to Sage 9.1 they always used the same one: 0. Thus every run of sage -t or make [p]test[all][long] would run those "random" doctests deterministically. In many cases, the output of those tests even relied on that. As a result, random examples and tests were actually testing that they were run non-randomly!

This is reminiscent of an xkcd comic illustration of random number generators.

Based on these considerations and the related sage-devel discussion, we propose to:

  • allow specifying a randomness when running tests (#29962),
  • adapt tests involving randomness, making sure they test mathematical functionality independent of the randomness seed used to run them (see roadmap),
  • default to a random randomness seed when none is specified (present ticket),

thus making those tests more robust and more useful, by becoming more likely to reveal bugs in a variety of cases including corner cases.

The first step (see #29962, merged in Sage 9.2) adds a --random-seed flag to sage -t, allowing:

sage -t --long --random-seed=9876543210 src/sage/

Still, when no randomness seed is specified, the default seed 0 is used. This means most testers test with the same randomness seed, making "random" doctests still mostly deterministic in practice.

Here is a way to pick a random randomness seed and run tests with it (can be used to work on the tickets in the roadmap):

$ randseed() {
    sage -c "import sage.misc.randstate as randstate; \
             randstate.set_random_seed(); \
             print(randstate.initial_seed())";
    }
$ SEED=$(randseed)
$ DIR=src/sage
$ echo "$ sage -t --long --random-seed=${SEED} ${DIR}" \
  && ./sage -t --long --random-seed=${SEED} ${DIR}

Once examples and tests involving randomness have been adapted, the present ticket puts the final touch by making it so that when running tests with no seed specified, a random one will be used:

sage -t src/sage/all.py 
Running doctests with ID 2020-06-23-23-19-03-8003eea5.
...
sage -t --warn-long 89.5 --random-seed=273987373473433732996760115183658447263 src/sage/all.py
    [16 tests, 0.73 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.8 seconds
    cpu time: 0.7 seconds
    cumulative wall time: 0.7 seconds

Being displayed in the output, the seed used can be used again if needed:

sage -t --warn-long 89.5 --random-seed=273987373473433732996760115183658447263 src/sage/all.py

allowing to explore any problematic case revealed by running the tests with that seed.

Roadmap:

Follow-up:

  • #32544: Meta-ticket: Fix unstable doctests detected after #29935
  • Remove set_random_seed in doctests where possible.

Errors discovered by this ticket:

  • #29936: Hyperbolic geometry bugs revealed by fuzzing
  • #29945: Failing doctest in src/sage/coding/linear_code.py (just a wrong doctest, will be fixed here)
  • #29954: Unstable plotting
  • #29956: Bug in KlyachkoBundle_class.random_deformation
  • #29957: Bug in ContinuedFraction rounding
  • #29958: Too many strong articulation points
  • #29961: Random symbolic expression is completely unstable
  • #30045: Bug in Reed-Solomon encoder and error-erasure decoder
  • Index error with random derangement (fixed in #29974)
  • #31890: simplify_hypergeometric is unstable
  • #31891: ZeroDivisonError when creating polynomial system
  • #31892: Conic parametrization broken
  • #32075: Polynomial generic power trunk broken
  • #32083: Various errors with polybori including segmentation fault
  • #32084 _nth_root_naive fails for integer mod
  • #32085: Errors when computing norms of padic elements
  • #32086: apply_homography unstable for continue fraction
  • #32095: DiFUB algorithm fails on some random graph
  • #32108: Fix random tree on one or less vertices
  • #32109: Fix 0/0 in ore function field
  • #32111: Unstable minimal polynomial for element of 2-adic Eisenstein Extension Field in pi defined by x4 - 2*a
  • #32117: Random relative number field checks only irreducibility over QQ
  • #32118: AlgebraicForm? checks invariance with random matrix that can be the identity
  • #32124: SL2Z.random_element unstable
  • #32125: random Ore polynomials do not respect minimum degree bound
  • #32126: padic QpLC.random_element is broken
  • #32127: gosper_iterator of continued fractions is unstable
  • #32129: sage_input is unreliable for elements of ComplexField?
  • #32131: Cut width of graph with one edge incorrect
  • #32132: Wrong gyration orbit length
  • #32138: is_groebner fails over fraction fields
  • #32141: Unstable doctest involving permutation groups
  • #32169: Bug in edge disjoint spanning trees
  • #32185: Failing weak order assertion on random symbolic expression
  • #32186: Random bounded tolerance graph
  • #32187: permutation group generated by list perms in L of degree n incorrect when compared to GAP
  • #32657: plot_vector_field unstable

Attachments (1)

timeout.txt (94.7 KB) - added by mantepse 11 months ago.
timeout

Download all attachments as: .zip

Change History (185)

comment:1 Changed 2 years ago by dimpase

  • Description modified (diff)

comment:2 Changed 2 years ago by dimpase

  • Cc gh-kliem mjo added

comment:3 Changed 2 years ago by gh-kliem

  • Work issues set to modify coding conventions

Just so that we don't forget that we will have to update

https://doc.sagemath.org/html/en/developer/coding_basics.html

comment:4 Changed 2 years ago by gh-kliem

  • Dependencies set to #29904

comment:5 follow-up: Changed 2 years ago by gh-kliem

geometry/hyperbolic_space/hyperbolic_geodesic.py makes some claims on how good approximations work, which doesn't seem to work. I had this thing run 7 times now and not one time did all tests pass. E.g. there is one test that gives me absolute errors of 0.7 when running this in the shell, but the test claims it is below 10**-9.

There is also #29904. Other than that the geometry module appears to ready.

Edit: And there is some place where you need to add set_random_seed(0) now or similar.

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:6 in reply to: ↑ 5 Changed 2 years ago by dimpase

Replying to gh-kliem:

geometry/hyperbolic_space/hyperbolic_geodesic.py makes some claims on how good approximations work, which doesn't seem to work. I had this thing run 7 times now and not one time did all tests pass. E.g. there is one test that gives me absolute errors of 0.7 when running this in the shell, but the test claims it is below 10**-9.

this is a great example of fuzzing catching an apparent error, it seems.

There is also #29904. Other than that the geometry module appears to ready.

Edit: And there is some place where you need to add set_random_seed(0) now or similar.

comment:7 Changed 2 years ago by gh-kliem

  • Branch set to public/29935
  • Commit set to b2954ceea638b4510e99d90cea3f99fa9a49338a

New commits:

d5fc5bestart from a "random" random seed for doctesting
5c7e562fix double description of hypercube
6b41bdbMerge branch 'public/29904' of git://trac.sagemath.org/sage into public/29935
b2954cefix random test in geometry/linear_expression

comment:8 follow-up: Changed 2 years ago by gh-kliem

Even in the developer guide there is an example, where it is confusing:

sage: M = matrix.identity(3) + random_matrix(RR,3,3)/10^3
sage: M^2 # abs tol 1e-2
[1 0 0]
[0 1 0]
[0 0 1]

There is no mentioning there that only one particular matrix is tested.

comment:9 Changed 2 years ago by git

  • Commit changed from b2954ceea638b4510e99d90cea3f99fa9a49338a to dc49dd0bd06dae1bca0a24b11b94f3f6d0fa2112

Branch pushed to git repo; I updated commit sha1. New commits:

dc49dd0update developer guide

comment:10 Changed 2 years ago by gh-kliem

  • Work issues modify coding conventions deleted

comment:11 in reply to: ↑ 8 Changed 2 years ago by dimpase

Replying to gh-kliem:

Even in the developer guide there is an example, where it is confusing:

sage: M = matrix.identity(3) + random_matrix(RR,3,3)/10^3
sage: M^2 # abs tol 1e-2
[1 0 0]
[0 1 0]
[0 0 1]

There is no mentioning there that only one particular matrix is tested.

indeed it assumes (?) that the entries of the random matrix are small in abs value

comment:12 Changed 2 years ago by gh-kliem

Nothing to assume there. random_matrix(RR,3,3) has entries between -1 and 1. After dividing we are good.

comment:13 Changed 2 years ago by gh-kliem

  • Dependencies changed from #29904 to #29904, #29936

comment:14 Changed 2 years ago by mkoeppe

How about making the random seed an option to sage-runtests. Then people can fuzz the doctests if they want.

comment:15 Changed 2 years ago by gh-kliem

Will people do that? Especially enough to find incorrect claims. If you look into #29936 we have been claiming a preciseness that is far from true. Even if you consider the relative error instead of the absolute error. fuzzed doctests would have easily detected that. Even worse. Maybe the situation was better at some point and we never caught on about the regression.

comment:16 Changed 2 years ago by dimpase

it is not a "real" (time-consuming) fuzzing, it is making the main random seed nondeterministic in tests. making it optional is akin to making tests optional.

we already found a couple of examples which show usefulness of this change in detecting bugs in Sage.

comment:17 Changed 2 years ago by mkoeppe

The option that I propose to add needs to be added in any case, so that when a failure is revealed by a random random seeds, we can reproduce the failure with that seed.

comment:18 Changed 2 years ago by dimpase

it is a good point - and the non-det. seed needs to be logged - if this is not yet in the branch it should get there.

comment:19 Changed 2 years ago by mkoeppe

So I would suggest to use this ticket to introduce the option, not change the default.

Last edited 2 years ago by mkoeppe (previous) (diff)

comment:20 Changed 2 years ago by dimpase

no, I don't agree, it makes no sense to test less if one can test more, and also not having it default would not force people to make their tests robust.

comment:21 Changed 2 years ago by mkoeppe

By the way I don't think most doctests have the ambition to demonstrate correctness of mathematical claims. In my opinion, if a doctest intends to do that, it should run an explicit loop of several tests. Still deterministically.

Last edited 2 years ago by mkoeppe (previous) (diff)

comment:22 Changed 2 years ago by mkoeppe

Why would creating the option and changing the default have to be done on the same ticket? I think it's best practices to separate the two steps on two tickets.

comment:23 Changed 2 years ago by gh-kliem

Feel free to do with the branch whatever you think is reasonable.

comment:24 Changed 2 years ago by gh-kliem

What I think would be great if running we could run each file at some "random" seed, e.g.

sage -t src/sage/all.py 
Running doctests with ID 2020-06-22-18-56-54-668a26f3.
Git branch: public/29935
Using --optional=4ti2,bliss,build,dochtml,e_antic,flask,flask_autoindex,flask_babel,flask_oldsessions,flask_openid,flask_silk,latte_int,lidia,lrslib,memlimit,normaliz,pynormaliz,python_openid,sage,speaklater,twisted
Doctesting 1 file.
sage -t --warn-long 91.5 --seed 123456 src/sage/all.py
    [16 tests, 0.76 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.8 seconds
    cpu time: 0.8 seconds
    cumulative wall time: 0.8 seconds

You can reproduce this test with

sage -t --warn-long 91.5 --seed 123456 src/sage/all.py

Is a bit annoying, as seeds can be long though. Then whenever a bot or someone discovers a failure, you can reproduce it. At least if it really was caused by the random seed.

comment:25 follow-up: Changed 2 years ago by mjo

Just to weigh in:

  1. The default should be to use a randomly-chosen seed.
  2. Failures should be reproducible:
    1. It should be possible to pass a seed to the test runner with e.g. --seed.
    2. Any test failures should log/echo the current seed so that the failing test can be reproduced easily using the option in (2.a.).

The sooner we can push this through the better. Tests that don't work due to bugs can even be deleted and replaced with trac tickets saying "this never worked" IMO.

comment:26 follow-up: Changed 2 years ago by gh-kliem

With #29904 (already pulled into this branch), #29936 (not yet pulled) and b2954ceea638b4510e99d90cea3f99fa9a49338 (commit from above) geometry should be ready for this.

Edit: The updated branch of #29904 (not yet pulled) doesn't have set_random_seed anymore. But there is plenty of set_random_seed for cones doctests? Should I remove those as well or do we do this somewhere else?

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:27 Changed 2 years ago by git

  • Commit changed from dc49dd0bd06dae1bca0a24b11b94f3f6d0fa2112 to bac708e0be8cbceb786906d6d1d08a6040775d20

Branch pushed to git repo; I updated commit sha1. New commits:

bac708emake graphs ready for fuzz doctests

comment:28 in reply to: ↑ 26 Changed 2 years ago by mkoeppe

Replying to gh-kliem:

there is plenty of set_random_seed for cones doctests? Should I remove those as well or do we do this somewhere else?

Not on the same ticket.

comment:29 Changed 2 years ago by git

  • Commit changed from bac708e0be8cbceb786906d6d1d08a6040775d20 to b5e9896efbe68fc3a374965ea9be5200e6d99cfb

Branch pushed to git repo; I updated commit sha1. New commits:

b5e9896make algebras fuzz ready

comment:30 Changed 2 years ago by git

  • Commit changed from b5e9896efbe68fc3a374965ea9be5200e6d99cfb to 8babc2a801d725b1f1687fac6c2082346778efb7

Branch pushed to git repo; I updated commit sha1. New commits:

8babc2amake arith fuzz ready

comment:31 Changed 2 years ago by gh-kliem

Please tell me, if I should open seperate tickets for those or something else. I just felt like starting with those. I'm done for today.

comment:32 in reply to: ↑ 25 Changed 2 years ago by gh-mwageringel

Replying to mjo:

  1. The default should be to use a randomly-chosen seed.
  2. Failures should be reproducible:
    1. It should be possible to pass a seed to the test runner with e.g. --seed.
    2. Any test failures should log/echo the current seed so that the failing test can be reproduced easily using the option in (2.a.).

+1.

Also note that Sage still uses a verbatim copy of the Python-2 version of the Random module during doctesting, which was necessary in order to obtain consistent results between Python 2 and 3. This is why the bug in #29550 went unnoticed, for example. Now that support for Python 2 has been removed, we should switch to the Python 3 version of Random. This will require updating lots of doctests, but I assume this ticket here will simplify this if it makes doctests less dependent on the seed/RNG.

comment:33 Changed 2 years ago by gh-kliem

Apparently LinearCodeSyndromeDecoder.decode_to_code is broken.

See #29945.

comment:34 Changed 2 years ago by git

  • Commit changed from 8babc2a801d725b1f1687fac6c2082346778efb7 to c7d16e9e58748d7627eb891df152ed9f2beafb76

Branch pushed to git repo; I updated commit sha1. New commits:

815c288make categories fuzz ready
c7d16e9make coding fuzz ready

comment:35 Changed 2 years ago by git

  • Commit changed from c7d16e9e58748d7627eb891df152ed9f2beafb76 to e5c54af8747ceb223147c4b84975e8773d3c0c04

Branch pushed to git repo; I updated commit sha1. New commits:

39edfdcmake random seed reproducible
e5c54afdocument random_seed

comment:36 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:37 Changed 2 years ago by gh-kliem

I specified random_seed to distinguish from --randorder=SEED. If after --randorder=SEED the next option is --seed=SEED that sounds a bit weird to me. Although random_seed is not much better.

comment:38 Changed 2 years ago by gh-kliem

Standard bracked lyndon words are set up incorrectly. I don't know if that should be consider a bug:

sage: SBLW33 = StandardBracketedLyndonWords(3,3)
sage: TestSuite(SBLW33).run()
Failure in _test_an_element:
Traceback (most recent call last):
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/misc/sage_unittest.py", line 296, in run
    test_method(tester=tester)
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/categories/sets_cat.py", line 1093, in _test_an_element
    tester.assertTrue(an_element in self, "self.an_element() is not in self")
  File "/home/jonathan/Applications/sage/local/lib/python3.7/unittest/case.py", line 692, in assertTrue
    raise self.failureException(msg)
AssertionError: self.an_element() is not in self
------------------------------------------------------------
Failure in _test_enumerated_set_contains:
Traceback (most recent call last):
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/misc/sage_unittest.py", line 296, in run
    test_method(tester=tester)
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/categories/enumerated_sets.py", line 945, in _test_enumerated_set_contains
    tester.assertIn(w, self)
  File "/home/jonathan/Applications/sage/local/lib/python3.7/unittest/case.py", line 1106, in assertIn
    self.fail(self._formatMessage(msg, standardMsg))
  File "/home/jonathan/Applications/sage/local/lib/python3.7/unittest/case.py", line 680, in fail
    raise self.failureException(msg)
AssertionError: [1, [1, 2]] not found in Standard bracketed Lyndon words from an alphabet of size 3 of length 3
------------------------------------------------------------
Failure in _test_some_elements:
Traceback (most recent call last):
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/misc/sage_unittest.py", line 296, in run
    test_method(tester=tester)
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/categories/sets_cat.py", line 1385, in _test_some_elements
    "the object %s in self.some_elements() is not in self")%(x,))
  File "/home/jonathan/Applications/sage/local/lib/python3.7/unittest/case.py", line 692, in assertTrue
    raise self.failureException(msg)
AssertionError: the object [1, [1, 2]] in self.some_elements() is not in self
------------------------------------------------------------
The following tests failed: _test_an_element, _test_enumerated_set_contains, _test_some_elements

comment:39 Changed 2 years ago by git

  • Commit changed from e5c54af8747ceb223147c4b84975e8773d3c0c04 to 93415f39a9691a3815e46ab5a4b51835b78b34fd

Branch pushed to git repo; I updated commit sha1. New commits:

93415f3make combinat fuzz ready

comment:40 Changed 2 years ago by git

  • Commit changed from 93415f39a9691a3815e46ab5a4b51835b78b34fd to dbd7f6ce5d5e631445443d24be2b070a4ea8a7c1

Branch pushed to git repo; I updated commit sha1. New commits:

dbd7f6cfix doctest in sage/coding/linear_code

comment:41 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:42 Changed 2 years ago by git

  • Commit changed from dbd7f6ce5d5e631445443d24be2b070a4ea8a7c1 to 00dc135d18892c4310013a630757423d6f31605f

Branch pushed to git repo; I updated commit sha1. New commits:

72cd0acmake crypto fuzz ready
00dc135make documentation fuzz ready

comment:43 Changed 2 years ago by gh-kliem

In src/sage/plot/multigraphics.py is a doctest that fails with the precicion:

1294             sage: g1 = plot(sin(x), (x, -pi, pi))
1295             sage: g2 = circle((0,1), 1.)
1296             sage: G = graphics_array([g1, g2])
1297             sage: G.position(0)  # tol 1.0e-13
1298             (0.023437500000000003,
1299              0.03415488992713045,
1300              0.4627803348994754,
1301              0.9345951100728696)
1302             sage: G.position(1)  # tol 1.0e-13
1303             (0.5136230468749999,
1304              0.19293222169724827,
1305              0.46278033489947534,
1306              0.617040446532634)

when running on set_random_seed(151058820726654196682836430928254760259). The precision is somewhere around 1e-3 then. Is this a bug?

comment:44 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:45 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:46 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:47 Changed 2 years ago by git

  • Commit changed from 00dc135d18892c4310013a630757423d6f31605f to a17092718667b3c9598939391cbcf36e1169c996

Branch pushed to git repo; I updated commit sha1. New commits:

4c540c6make dynamics fuzz ready
23ed583fix doctest in hyperbolic_space/hyperbolic_point
5283dc4use abs tol flag
7b244c0modify doctests to the extend that they hold with fuzz
84ba6d5Merge branch 'public/29936' of git://trac.sagemath.org/sage into public/29935
36ea095make finance fuzz ready
bfe9c2abug in connectivity
a170927make groups fuzz ready

comment:48 Changed 2 years ago by jhpalmieri

It may be too late for this, but I would suggest a staged approach:

  • ticket 1: implement optional random seed but don't make it the default
  • tickets 2-n: fix doctests when using random seeds in various parts of the Sage library
  • ticket n+1: make random seed standard, if that is what people think should be done

Doing everything all at once is likely to lead to a patch bomb, which will lead to merge conflicts and in general be hard to deal with.

comment:49 Changed 2 years ago by gh-kliem

There is a reason that I have the fixes grouped by parts of sage. So that isn't spoiled yet.

That completely makes sense. We still need the last ticket to have the bots test everything.

comment:50 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:51 Changed 2 years ago by git

  • Commit changed from a17092718667b3c9598939391cbcf36e1169c996 to 18e980dc63337149b1e708a2078ec2978f0ead7d

Branch pushed to git repo; I updated commit sha1. New commits:

38b4557another file for combinat
8ec8298make symbolix fuzz ready
e8d4776make schemes fuzz ready
9b5bef8make plot fuzz ready
98e34d3partially make rings fuzz ready
6f33e4apartially make matrix fuzz ready
e6dc532partially make modular fuzz ready
18e980dpartially make modules fuzz ready

comment:52 Changed 2 years ago by gh-kliem

  • Dependencies changed from #29904, #29936 to #29904, #29936, #29962
  • Description modified (diff)

comment:53 Changed 2 years ago by git

  • Commit changed from 18e980dc63337149b1e708a2078ec2978f0ead7d to 0a4f42f4dcf7531c35bd32dd4ab2dcc724f26712

Branch pushed to git repo; I updated commit sha1. New commits:

da1c6bestart from a "random" random seed for doctesting
b7b836dmake random seed reproducible
eedbe5edocument random_seed
998b1b9default random seed 0 for now
0a4f42freanable making fuzzing default

comment:54 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:55 Changed 2 years ago by git

  • Commit changed from 0a4f42f4dcf7531c35bd32dd4ab2dcc724f26712 to fc25017e8ea86bb4bfac215ce1471952087d6235

Branch pushed to git repo; I updated commit sha1. New commits:

fc25017dash instead of underscore for command line options

comment:56 Changed 2 years ago by gh-kliem

  • Description modified (diff)

New commits:

fc25017dash instead of underscore for command line options

comment:57 Changed 2 years ago by gh-kliem

  • Dependencies changed from #29904, #29936, #29962 to #29945, #29963, #29964, #29965, #29967, #29968, #29969, #29970, #29971, #29972, #29973, #29974, #29975, #29976, #29977, #29978, #29979, #29980, #29981, #29982, #29983, #29984, #29985, #29986
  • Description modified (diff)

comment:58 Changed 2 years ago by gh-kliem

We had a little discussion on #29971, how we treat doctests as

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element()
1

If we tag this as # random and maybe test instead containment in C, the doctest we will essentially remove the doctest and add another. Is this what we want?

Matthias Koeppe suggested inventing a new tag maybe # random-seed=0. If we implicitly fuzz all doctests this would only be tested if we run the test block twice?!

I think we should agree on a something here. Depending on the agreement it needs to be taken care of with #29962 already.

IMO tests as C.random_element() should run at least once with fuzzing (with checking that the object is consistent). We can run it twice to obtain our old test, but I would appreciate some help with that.

comment:59 Changed 2 years ago by mjo

This will do the job, and doesn't depend on the literal output of the random function:

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element() in C
True

comment:60 follow-ups: Changed 2 years ago by gh-kliem

In principal I agree.

I prefer

sage: C = FiniteEnumeratedSets().example()
sage: n = C.random_element(); n  # random
1
sage: n in C
True

as this makes it a bit easier for the user to see, what will/might happen. But that is only minor.

However, I just noticed, that there are problems with that approach. The representation of those random things will never be checked. In principal (almost) all random events should be reproducible with some random seed (doesn't work for e.g. hashing). By tagging something as # random, we might document nonsense or outdated information and no one will catch on.

E.g. in #29981 I fixed a documentation mistake along the way: Solve a linear equation system with A\v with A a random matrix. A should be non-singular of course, which was never thought of because the doctest is only tested for one matrix, which happens to be non-singular. In #29981, A is defined as A = random_matrix(QQ, 3, algorithm='unimodular'). However, I forgot to update the representation of A to some unimodular matrix and the doctests never caught on.

Now if you tag something as # random-seed=0 and we find some way to test this (both seed 0 and different), it would mean that the printed representations stay up to date and consistent and it is also tested, if those thing work for "random" input.

I found many examples where functions where tested assuming random seed 0. One could make use of the double testing framework:

def foo(y):
   r"""
   EXAMPLES::

      sage: M = random(); M  # random-seed=0
      <some random input>
      sage: N = foo(M); N  # random-seed=0
      <some random output>
      sage: check_for_consistency(M, N)
   """
   return _foo(y)

It is still checked, that foo works exactly for some example that hopefully was verified by someone. But it is also checked, that the method in principal works on "random" input and that the output appears to be correct.

comment:61 Changed 2 years ago by mjo

If we want to check the printed/string representation of something, can't we just... check it? In other words, instead of

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element()
1

we could do

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element() in C
True
sage: C[0]
1

This has the (big, in my opinion) added benefit of actually being a runnable example. If a user runs

sage: C = FiniteEnumeratedSets().example()
sage: n = C.random_element(); n  # random

then he's not going to see what the documentation says he should see, because # random does nothing on the command-line.

comment:62 in reply to: ↑ 60 ; follow-up: Changed 2 years ago by gh-mwageringel

IMO, it is not necessary to test the printing of random elements, as the repr of those elements is already tested elsewhere. We do not make any promises about the precise elements that are returned with a seed of 0, so we should not bake that into the doctests. As we cannot test the randomness, we can only test that random_element returns an element of the parent. The following check could be used for that:

sage: C.random_element().parent() is C

Unlike __contains__, this does not implicitly coerce the element into C.

comment:63 in reply to: ↑ 62 Changed 2 years ago by mjo

Replying to gh-mwageringel:

IMO, it is not necessary to test the printing of random elements, as the repr of those elements is already tested elsewhere. We do not make any promises about the precise elements that are returned with a seed of 0, so we should not bake that into the doctests. As we cannot test the randomness, we can only test that random_element returns an element of the parent. The following check could be used for that:

sage: C.random_element().parent() is C

Unlike __contains__, this does not implicitly coerce the element into C.

Sounds good to me.

comment:64 in reply to: ↑ 60 ; follow-up: Changed 2 years ago by gh-kliem

Replying to gh-kliem:

Sounds good to me. As for the documentation of random_element, I don't think a user cares about the precise value of set_random_seed(0); C.random_element().

Two more cases that I would like to discuss.

  • Basically from comment:60. How do we deal with something like this:
    def foo(y):
       r"""
       EXAMPLES::
    
          sage: M = random(); M
          <some random input>
          sage: foo(M)
          <some random output>
       """
    
    It appears to me that there are many examples, where someone did not write down a concrete element to doctest. I would propose having two doctests, if possible:
    • Explicitly obtain the old test.
    • Have a "random" test with a consistency check. (Even without a consistency check, it's probably worth checking that the function terminates without an error usually.)
  • The other one is a concrete example from #29981 (linear algrebra tutorial). The original test is
        sage: A=random_matrix(QQ,3)
        sage: v=vector([2,3,1])
        sage: A,v
        (
        [ 0 -1  1]
        [-1 -1 -1]
        [ 0  2  2], (2, 3, 1)
        )
        sage: x=A\v; x
        (-7/2, -3/4, 5/4)
        sage: A*x
        (2, 3, 1)
    
    As mentioned already, this does not work. I see basically two ways of fixing this. One is to explicitly write down A. The other one is similar to what I did. Use a correct random approach (e.g. random unimodular) and check that indeed A*x == v. Optionally one can print x and A and tag this as random. To be honest, I don't see how a user would profit from the printing. What a 3 by 3 matrix looks like should be clear by then.

comment:65 in reply to: ↑ 64 ; follow-up: Changed 2 years ago by mjo

Replying to gh-kliem:

  • Basically from comment:60. How do we deal with something like this:
    def foo(y):
       r"""
       EXAMPLES::
    
          sage: M = random(); M
          <some random input>
          sage: foo(M)
          <some random output>
       """
    

If the point isn't to demonstrate the random() function, then the "random" element can just be replaced with whatever it winds up with now (i.e. the fixed element you get with a seed of zero). The TESTS block can contain some truly random test of a property that the output from foo() should satisfy, like

sage: foo(random()) in RR
True
  • The other one is a concrete example from #29981 (linear algrebra tutorial). The original test is
        sage: A=random_matrix(QQ,3)
        sage: v=vector([2,3,1])
        sage: A,v
        (
        [ 0 -1  1]
        [-1 -1 -1]
        [ 0  2  2], (2, 3, 1)
        )
        sage: x=A\v; x
        (-7/2, -3/4, 5/4)
        sage: A*x
        (2, 3, 1)
    

How about...

sage: A = random_matrix(QQ,3)
sage: while not A.is_invertible():
....:     A = random_matrix(QQ,3)
....:     
sage: v=vector([2,3,1])
sage: x=A\v
sage: A*x - v == 0
True

comment:66 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:67 in reply to: ↑ 65 Changed 2 years ago by gh-kliem

Replying to mjo:

Replying to gh-kliem:

  • Basically from comment:60. How do we deal with something like this:
    def foo(y):
       r"""
       EXAMPLES::
    
          sage: M = random(); M
          <some random input>
          sage: foo(M)
          <some random output>
       """
    

If the point isn't to demonstrate the random() function, then the "random" element can just be replaced with whatever it winds up with now (i.e. the fixed element you get with a seed of zero). The TESTS block can contain some truly random test of a property that the output from foo() should satisfy, like

sage: foo(random()) in RR
True
  • The other one is a concrete example from #29981 (linear algrebra tutorial). The original test is
        sage: A=random_matrix(QQ,3)
        sage: v=vector([2,3,1])
        sage: A,v
        (
        [ 0 -1  1]
        [-1 -1 -1]
        [ 0  2  2], (2, 3, 1)
        )
        sage: x=A\v; x
        (-7/2, -3/4, 5/4)
        sage: A*x
        (2, 3, 1)
    

How about...

sage: A = random_matrix(QQ,3)
sage: while not A.is_invertible():
....:     A = random_matrix(QQ,3)
....:     
sage: v=vector([2,3,1])
sage: x=A\v
sage: A*x - v == 0
True

Sounds reasonable to me. I will adhere to those suggestions.

comment:68 Changed 2 years ago by gh-kliem

  • Branch changed from public/29935 to public/29935-reb
  • Commit changed from fc25017e8ea86bb4bfac215ce1471952087d6235 to 36365975b2d783a16acc15f035d3c893a04d3189

New commits:

1d7b00edash instead of underscore for command line options
b31e2d5Merge branch 'public/29962' of git://trac.sagemath.org/sage into public/29962-reb
2f30dd9small fixes
b62f781doctests do not start from a random seed by default yet
263d605Revert "doctests do not start from a random seed by default yet"
3636597Revert "default random seed 0 for now"

comment:69 follow-up: Changed 2 years ago by gh-kliem

Maybe it makes sense to restrict the size of the random seed, so that one can still read the output of doctesting.

comment:70 in reply to: ↑ 69 Changed 2 years ago by dimpase

Replying to gh-kliem:

Maybe it makes sense to restrict the size of the random seed, so that one can still read the output of doctesting.

it's not clear to me what you mean here.

comment:71 Changed 2 years ago by gh-kliem

sage -t src/sage/all.py 
Running doctests with ID 2020-06-23-23-19-03-8003eea5.
...
sage -t --warn-long 89.5 --random-seed=273987373473433732996760115183658447263 src/sage/all.py
    [16 tests, 0.73 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.8 seconds
    cpu time: 0.7 seconds
    cumulative wall time: 0.7 seconds

Currently this output is the plan. This might be very annoying for patchbots and so on. If we instead restrict to fewer digits, we will still test a reasonable amount of different inputs and you can still read this line (even if working on a non-huge screen).

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:72 Changed 2 years ago by dimpase

I think it is ok - compare this with very long lists of optional packages which are there sometimes.

comment:73 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:74 Changed 2 years ago by gh-kliem

  • Dependencies changed from #29945, #29963, #29964, #29965, #29967, #29968, #29969, #29970, #29971, #29972, #29973, #29974, #29975, #29976, #29977, #29978, #29979, #29980, #29981, #29982, #29983, #29984, #29985, #29986 to 29936, #29945, #29963, #29964, #29965, #29967, #29968, #29969, #29970, #29971, #29972, #29973, #29974, #29975, #29976, #29977, #29978, #29979, #29980, #29981, #29982, #29983, #29984, #29985, #29986
  • Description modified (diff)

comment:75 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:76 Changed 2 years ago by gh-kliem

  • Dependencies changed from 29936, #29945, #29963, #29964, #29965, #29967, #29968, #29969, #29970, #29971, #29972, #29973, #29974, #29975, #29976, #29977, #29978, #29979, #29980, #29981, #29982, #29983, #29984, #29985, #29986 to #29936, #29945, #29963, #29964, #29965, #29967, #29968, #29969, #29970, #29971, #29972, #29973, #29974, #29975, #29976, #29977, #29978, #29979, #29980, #29981, #29982, #29983, #29984, #29985, #29986

comment:77 Changed 2 years ago by gh-kliem

  • Work issues set to document range of random-seed

comment:78 Changed 22 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:79 Changed 19 months ago by gh-DaveWitteMorris

  • Cc gh-DaveWitteMorris added

comment:80 Changed 17 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

comment:81 Changed 16 months ago by slelievre

  • Cc slelievre added
  • Description modified (diff)
  • Keywords fuzz random seed added
  • Summary changed from implicitly fuzz RNG-dependent doctests to Meta-ticket: implicitly fuzz RNG-dependent doctests with a random random seed

Marking this as a meta-ticket.

comment:82 Changed 15 months ago by gh-kliem

  • Description modified (diff)

comment:83 Changed 15 months ago by gh-kliem

  • Description modified (diff)

comment:84 Changed 15 months ago by gh-kliem

  • Description modified (diff)

comment:85 Changed 14 months ago by slelievre

  • Description modified (diff)

Expanding the ticket description, adding a code snippet giving a way to set a random randomness seed, which I find useful for working on the (few remaining) dependencies of this ticket.

comment:86 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:87 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:88 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:89 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:90 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:91 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29936, #29945, #29963, #29964, #29965, #29967, #29968, #29969, #29970, #29971, #29972, #29973, #29974, #29975, #29976, #29977, #29978, #29979, #29980, #29981, #29982, #29983, #29984, #29985, #29986 to #29979, #29978, #29977, #29980

comment:92 Changed 14 months ago by gh-kliem

  • Authors set to Jonathan Kliem
  • Status changed from new to needs_review
  • Summary changed from Meta-ticket: implicitly fuzz RNG-dependent doctests with a random random seed to implicitly fuzz RNG-dependent doctests with a random random seed

comment:93 Changed 14 months ago by gh-kliem

  • Status changed from needs_review to needs_work

A couple of new tests fail yet.

comment:94 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:95 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29978, #29977, #29980 to #29979, #29978, #29977, #29980, #32084

comment:96 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29978, #29977, #29980, #32084 to #29979, #29978, #29977, #29980, #32084, 32107
  • Description modified (diff)

comment:97 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29978, #29977, #29980, #32084, 32107 to #29979, #29978, #29977, #29980, #32084, #32107

comment:98 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:99 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29978, #29977, #29980, #32084, #32107 to #29979, #29978, #29977, #29980, #32084, #32107, 980, #32084, #32108

comment:100 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29978, #29977, #29980, #32084, #32107, 980, #32084, #32108 to #29979, #29978, #29977, #29980, #32084, #32107, 980, #32084, #32108, #32109
  • Description modified (diff)

comment:101 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29978, #29977, #29980, #32084, #32107, 980, #32084, #32108, #32109 to #29979, #29978, #29977, #29980, #32084, #32107, #32084, #32108, #32109

comment:102 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29978, #29977, #29980, #32084, #32107, #32084, #32108, #32109 to #29979, #29978, #29977, #29980, #32084, #32107, #32108, #32109

comment:103 Changed 14 months ago by gh-kliem

  • Branch changed from public/29935-reb to public/29935
  • Commit changed from 36365975b2d783a16acc15f035d3c893a04d3189 to 453ffc80512f229d1c7bae2581cc7d0500640b22
  • Dependencies changed from #29979, #29978, #29977, #29980, #32084, #32107, #32108, #32109 to #29979, #29977, #29980, #32084, #32107, #32108, #32109
  • Work issues document range of random-seed deleted

Last 10 new commits:

0994f0ftrac 32084 fix nth root
226fe84trac 32084 fix nth root
71ab842Merge branch 'public/32084r2' of git://trac.sagemath.org/sage into public/29935
960ce8bmake groups ready for random seeds
5592c58make some_elements of affine group ready for random seeds
dc4ed63Merge branch 'public/32107' of git://trac.sagemath.org/sage into public/29935
a732a3ffix random tree on less than two vertices
5b19d31Merge branch 'public/32108' of git://trac.sagemath.org/sage into public/29935
9e53965fix 0/0 in ore function field
453ffc8Merge branch 'public/32109' of git://trac.sagemath.org/sage into public/29935

comment:104 Changed 14 months ago by git

  • Commit changed from 453ffc80512f229d1c7bae2581cc7d0500640b22 to f16765a4ac7806da4401b058f80e9737cca24c3d

Branch pushed to git repo; I updated commit sha1. New commits:

7a393c2remove bug tag from 32095
89c210etrac #32095: sorted is not inplace
f16765aMerge branch 'public/graphs/32095_fix_DiFUB_with_boost' of git://trac.sagemath.org/sage into public/29935

comment:105 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29977, #29980, #32084, #32107, #32108, #32109 to #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095

comment:106 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:107 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:108 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:109 Changed 14 months ago by git

  • Commit changed from f16765a4ac7806da4401b058f80e9737cca24c3d to 97e015ccd9b2160a84db686658e9ec7876893f17

Branch pushed to git repo; I updated commit sha1. New commits:

75fad77Merge branch 'public/29979' of git://trac.sagemath.org/sage into public/29979-reb
e280083Merge branch 'public/32084r2' of git://trac.sagemath.org/sage into public/29979-reb
192b564add ticked number to test
b20059cMerge branch 'public/32109' of git://trac.sagemath.org/sage into public/29979-reb
ce98d48two more doctests
34a233dpull in 32117
cfe869bmodulo n better be for n > 0
3752b9csome more remaining tests
97e015cMerge branch 'public/29979-reb' of git://trac.sagemath.org/sage into public/29935

comment:110 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:111 Changed 14 months ago by gh-mwageringel

  • Description modified (diff)

comment:112 Changed 14 months ago by gh-mwageringel

  • Description modified (diff)

comment:113 Changed 14 months ago by gh-mwageringel

  • Description modified (diff)

comment:114 Changed 14 months ago by gh-mwageringel

  • Description modified (diff)

comment:115 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:116 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:117 Changed 14 months ago by git

  • Commit changed from 97e015ccd9b2160a84db686658e9ec7876893f17 to 7f39bf05c30856655554d656b7079153420b9edc

Branch pushed to git repo; I updated commit sha1. New commits:

e6a697atruely ignore ignored bounds for ZZ.random_element
36c7c58pull 32124
0bcab06Merge branch 'public/29979-reb' of git://trac.sagemath.org/sage into public/29935
7f39bf0fix orbit lenght of gyration

comment:118 Changed 14 months ago by git

  • Commit changed from 7f39bf05c30856655554d656b7079153420b9edc to cb037caa90caffd1eac962f5ca05f5acd37c2a35

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

cb037cafix orbit lenght of gyration

comment:119 Changed 14 months ago by git

  • Commit changed from cb037caa90caffd1eac962f5ca05f5acd37c2a35 to 01f98ac411218ecd1ff02e6ce79f084f6f153c1a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

01f98acfix orbit lenght of gyration

comment:120 Changed 14 months ago by git

  • Commit changed from 01f98ac411218ecd1ff02e6ce79f084f6f153c1a to b8e9e8eceabcd942fc1fe4b42d9fa3df9ba1cd15

Branch pushed to git repo; I updated commit sha1. New commits:

ee49444one more doctest in rings
b8e9e8etwo more doctests in graphs

comment:121 Changed 14 months ago by git

  • Commit changed from b8e9e8eceabcd942fc1fe4b42d9fa3df9ba1cd15 to 49ddba993d062a9036f3130f8c68c0e0f93d29dd

Branch pushed to git repo; I updated commit sha1. New commits:

be3e05f29979: a few more fixes
49ddba9merge 29979

comment:122 Changed 14 months ago by git

  • Commit changed from 49ddba993d062a9036f3130f8c68c0e0f93d29dd to 431397b861d0ff8324d49949b908fa8200389a75

Branch pushed to git repo; I updated commit sha1. New commits:

aa5276atrac #32131: fix cutwidth for single edge graph
8488bf4trac #32131: fix method for non connected graphs
8d9abe0Merge branch 'public/graphs/32131_fix_cutwidth' of git://trac.sagemath.org/sage into public/29935
431397ba few more tests

comment:123 Changed 14 months ago by gh-kliem

  • Dependencies changed from #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095 to #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131

comment:124 Changed 14 months ago by gh-mwageringel

  • Description modified (diff)

comment:125 Changed 14 months ago by gh-kliem

  • Description modified (diff)

comment:126 Changed 14 months ago by git

  • Commit changed from 431397b861d0ff8324d49949b908fa8200389a75 to 692aba8371d7808ba571504210a6b3607e033a59

Branch pushed to git repo; I updated commit sha1. New commits:

ac0dca7one more missing test from groups
fcdc025one more test from modular
008c6e1one more failing test in coding
5f0f5dc29979: mark failing tests as not tested
bc1e14a29979: minor tweaks of doctests
692aba8Merge branch 'public/29979-reb' of git://trac.sagemath.org/sage into public/29935

comment:127 Changed 14 months ago by git

  • Commit changed from 692aba8371d7808ba571504210a6b3607e033a59 to 2ca52c60cc3dbc5356e9b6f8f4599f64ebae3d7b

Branch pushed to git repo; I updated commit sha1. New commits:

2ca52c6two more doctests

comment:128 Changed 14 months ago by gh-kliem

  • Status changed from needs_work to needs_review

This is getting more and more stable.

I can now run it on 8 random seeds without failure (or without failure that doesn't appear on random seed 0). There are probably still failing examples, but its getting to a point, where it won't prevent patchbots from working and it's not too much of a burden to report failures because of this.

comment:129 Changed 14 months ago by gh-mwageringel

We should also remember to try the optional tests at some point, but I assume the majority of them does not use randomness.

comment:130 Changed 14 months ago by gh-kliem

Right, I forgot about the optional packages.

I hope this helps a bit:

https://github.com/kliem/sage/pull/48/checks

comment:131 Changed 13 months ago by gh-kliem

  • Description modified (diff)

comment:132 Changed 13 months ago by git

  • Commit changed from 2ca52c60cc3dbc5356e9b6f8f4599f64ebae3d7b to 20336ccf999c8aa7961312b25b7ac78076a03d95

Branch pushed to git repo; I updated commit sha1. New commits:

20336ccvarious small fixes

comment:133 Changed 13 months ago by git

  • Commit changed from 20336ccf999c8aa7961312b25b7ac78076a03d95 to 5f4cabad17709abd0925203e1013bce7bfbf5ecc

Branch pushed to git repo; I updated commit sha1. New commits:

836be04remove bug tag as 32169 has been resolved
7f082eea few more fixes for various doctests
76ce723trac #32169: new ILP formulation
047afdatrac #32169: enforce equality in the number of incoming edges
5f4cabaMerge branch 'public/graphs/32169_new_ILP' of git://trac.sagemath.org/sage into public/29935

comment:134 Changed 13 months ago by gh-kliem

  • Dependencies changed from #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131 to #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131, #32169

comment:135 Changed 13 months ago by git

  • Commit changed from 5f4cabad17709abd0925203e1013bce7bfbf5ecc to 474490ef8a950f5867d581e6dff11afc5613b005

Branch pushed to git repo; I updated commit sha1. New commits:

474490efix ValueError when obtaining random bounded tolerance graph

comment:136 Changed 13 months ago by git

  • Commit changed from 474490ef8a950f5867d581e6dff11afc5613b005 to f0f9cd58cbb130a530366c70b666c12e02576241

Branch pushed to git repo; I updated commit sha1. New commits:

f0f9cd5two more doctests

comment:137 Changed 13 months ago by gh-kliem

  • Dependencies changed from #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131, #32169 to #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131, #32169, #32186
  • Description modified (diff)

comment:138 Changed 13 months ago by gh-kliem

  • Dependencies changed from #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131, #32169, #32186 to #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131, #32169, #32186, #32188
  • Description modified (diff)

I outsourced many of the small fixes to #32188, to make review here easier.

comment:139 follow-up: Changed 13 months ago by nbruin

Note that doctesting with a fixed seed is publicly documented behaviour in sage. Quoting from Developer guide:

However, most functions generating pseudorandom output do not need this tag since the doctesting framework guarantees the state of the pseudorandom number generators (PRNGs) used in Sage for a given doctest.

I would think that tests explicitly relying on this behaviour are rather weak and I wouldn't mind changing this "policy", but we shouldn't forget to update the developer guide as well.

comment:140 Changed 13 months ago by gh-kliem

  • Dependencies changed from #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131, #32169, #32186, #32188 to #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131, #32169, #32186, #32188, #32216
  • Description modified (diff)

comment:141 in reply to: ↑ 139 Changed 13 months ago by gh-kliem

Replying to nbruin:

Note that doctesting with a fixed seed is publicly documented behaviour in sage. Quoting from Developer guide:

However, most functions generating pseudorandom output do not need this tag since the doctesting framework guarantees the state of the pseudorandom number generators (PRNGs) used in Sage for a given doctest.

I would think that tests explicitly relying on this behaviour are rather weak and I wouldn't mind changing this "policy", but we shouldn't forget to update the developer guide as well.

Thanks for the pointer. This is now #32216.

comment:142 Changed 12 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:143 Changed 11 months ago by gh-kliem

  • Branch changed from public/29935 to public/29935-reb
  • Commit changed from f0f9cd58cbb130a530366c70b666c12e02576241 to 84ca9564b4dd0466e0c2078f651970ece6fc4fad
  • Dependencies #29979, #29977, #29980, #32084, #32107, #32108, #32109, #32095, #32131, #32169, #32186, #32188, #32216 deleted

I'll leave #32169 for later and would just like to get this in.


New commits:

669a08cimplicitly fuzz RNG-dependent doctests
84ca956reduce vertices for edge disjoint spanning trees

comment:144 Changed 11 months ago by mjo

I think this,

         ....:     n = ZZ.random_element().abs() + 5
+        ....:     if n > 5000:  # avoid timeouts
+        ....:         continue

can be simplified by passing (5,5001) as the bound to ZZ.random_element(), without abs.

And the fix for this has already been merged:

+        sage: test_symbolic_expression_order(10000)  # long time,  # not tested, known bug (see :trac:`32185`)

comment:145 Changed 11 months ago by git

  • Commit changed from 84ca9564b4dd0466e0c2078f651970ece6fc4fad to 5405f18a8cb56b0e4654ebc16a5e647dbdbe8a1a

Branch pushed to git repo; I updated commit sha1. New commits:

180d945do not remove fixed doctest
5405f18simplify doctest

comment:146 Changed 11 months ago by git

  • Commit changed from 5405f18a8cb56b0e4654ebc16a5e647dbdbe8a1a to 950eaeb6b02cc9da0ce9160e9921112a07720a06

Branch pushed to git repo; I updated commit sha1. New commits:

950eaebfix unstable doctests

comment:147 Changed 11 months ago by git

  • Commit changed from 950eaeb6b02cc9da0ce9160e9921112a07720a06 to 512a10d844686464b8c4686c13e8003d8fd41f67

Branch pushed to git repo; I updated commit sha1. New commits:

512a10dfixed some doctests for disjoint spanning trees

comment:148 follow-up: Changed 11 months ago by mjo

  • Reviewers set to https://github.com/orlitzky/sage/actions/runs/1250536890, https://github.com/orlitzky/sage/actions/runs/1250536887

Looks OK now, but there's really no way to be 100% certain. We will probably discover a few instances where e.g. a ptestlong happens to generate four relatively hard problems at once, leading to intermittent timeouts. But regardless, I think the sooner we can get this in, the better. I started some GH actions for added test cycles.

comment:149 in reply to: ↑ 148 Changed 11 months ago by gh-DaveWitteMorris

Replying to mjo:

... I think the sooner we can get this in, the better. ...

+1

comment:150 Changed 11 months ago by git

  • Commit changed from 512a10d844686464b8c4686c13e8003d8fd41f67 to 1d255256033dbdc7dd7480edd162dd86f23a7629

Branch pushed to git repo; I updated commit sha1. New commits:

1d25525fix unstable doctest in book_stein_ent

comment:151 Changed 11 months ago by gh-kliem

I also think this is ready. It is rather stable now.

We should open a new (meta?) ticket, to collect all those failures, I think.

comment:152 Changed 11 months ago by mjo

  • Reviewers changed from https://github.com/orlitzky/sage/actions/runs/1250536890, https://github.com/orlitzky/sage/actions/runs/1250536887 to Michael Orlitzky
  • Status changed from needs_review to positive_review

Let's just do it before beta2 happens.

Thanks for all your work on this, I never had the courage to try it myself.

comment:153 Changed 11 months ago by gh-kliem

Thank you.

comment:154 Changed 11 months ago by gh-kliem

  • Description modified (diff)

I created #32544 for the errors appearing now that this is positively reviewed. There already is a ticket on it (#32543).

comment:155 Changed 11 months ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long --warn-long 45.3 --random-seed=58740356065403116296055203326248101103 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 23499, in sage.graphs.generic_graph.GenericGraph.edge_polytope
Failed example:
    P.is_combinatorially_isomorphic(product(components))
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of  24 in sage.graphs.generic_graph.GenericGraph.edge_polytope
    [3598 tests, 1 failure, 22.29 s]
----------------------------------------------------------------------
sage -t --long --warn-long 45.3 --random-seed=58740356065403116296055203326248101103 src/sage/graphs/generic_graph.py  # 1 doctest failed
----------------------------------------------------------------------

comment:156 Changed 11 months ago by gh-kliem

  • Cc mantepse added

So this ticket got rejected because it detected my own mistake in #32498. That's fair I guess.

What I claimed is complete nonsense, but it did work for seed 0 I guess. The (symmetric) edge polytope of a graph is of course the join of the (symmetric) edge polytopes of the connecting compoments.

comment:157 Changed 11 months ago by gh-kliem

No, that is not the join, it is the subdirect sum. It is really worth reading the definitions once in a while...

comment:158 Changed 11 months ago by git

  • Commit changed from 1d255256033dbdc7dd7480edd162dd86f23a7629 to 7e487e5a7b5ae14ba862763217f4a2fe27485e79

Branch pushed to git repo; I updated commit sha1. New commits:

36939d5Merge branch 'develop' of git://trac.sagemath.org/sage into public/29935-reb
7e487e5fix mistake from #32498

comment:159 Changed 11 months ago by gh-kliem

  • Status changed from needs_work to needs_review

@Martin Rubey: Can you please check the fix of #32498, everything else should still be fine.

comment:160 Changed 11 months ago by mantepse

I'm afraid there is a MemoryError reported by the bot. I'll check whether it is reproducible.

Last edited 11 months ago by mantepse (previous) (diff)

comment:161 Changed 11 months ago by mantepse

sage -t --random-seed=306431873350217748498615142104107167501 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 23601, in sage.graphs.generic_graph.GenericGraph.symmetric_edge_polytope
Failed example:
    P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))
Exception raised:
    Traceback (most recent call last):
      File "/home/martin/sage-develop/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 694, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/martin/sage-develop/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 1088, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.symmetric_edge_polytope[20]>", line 1, in <module>
        P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))
      File "/home/martin/sage-develop/local/lib/python3.8/site-packages/sage/geometry/polyhedron/base.py", line 10715, in is_combinatorially_isomorphic
        return G_self.is_isomorphic(G_other)
      File "/home/martin/sage-develop/local/lib/python3.8/site-packages/sage/graphs/generic_graph.py", line 22672, in is_isomorphic
        isom = isomorphic(GC, GC2, partition, partition2, (self._directed or self.has_loops()), 1)
      File "sage/groups/perm_gps/partn_ref/refinement_graphs.pyx", line 163, in sage.groups.perm_gps.partn_ref.refinement_graphs.isomorphic (build/cythonized/sage/groups/perm_gps/partn_ref/refinement_graphs.c:6775)
        cdef bint isomorphic = double_coset(<void *>GS1, <void *>GS2, part, ordering, n, &all_children_are_equivalent, &refine_by_degree, &compare_graphs, NULL, NULL, output)
      File "sage/groups/perm_gps/partn_ref/double_coset.pyx", line 364, in sage.groups.perm_gps.partn_ref.double_coset.double_coset (build/cythonized/sage/groups/perm_gps/partn_ref/double_coset.c:5618)
        raise MemoryError
    MemoryError
**********************************************************************
1 item had failures:
   1 of  53 in sage.graphs.generic_graph.GenericGraph.symmetric_edge_polytope
    [3558 tests, 1 failure, 42.09 s]
----------------------------------------------------------------------
sage -t --random-seed=306431873350217748498615142104107167501 src/sage/graphs/generic_graph.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 43.1 seconds
    cpu time: 40.1 seconds
    cumulative wall time: 42.1 seconds
Pytest is not installed, skip checking tests that rely on it.

comment:162 Changed 11 months ago by gh-kliem

Looks like I need to reduce the number of vertices.

comment:163 Changed 11 months ago by git

  • Commit changed from 7e487e5a7b5ae14ba862763217f4a2fe27485e79 to 150225d2a183b76540bf06da75084b04959e65f2

Branch pushed to git repo; I updated commit sha1. New commits:

150225dreasonable graph size for doctets

comment:164 Changed 11 months ago by gh-kliem

Previously I decomposed random graphs of up to 12 vertices. Now I take the disjoint union of random graphs and need to go down with the number of vertices.

Changed 11 months ago by mantepse

timeout

comment:165 Changed 11 months ago by mantepse

It seems that there is still a problem. With some seeds, testing generic_graph.py takes about 16 seconds on my computer. However,

sage -t --random-seed=236024484355828254371843550334759500607 src/sage/graphs/generic_graph.py

times out. I attached the log. The last line executed is

sage: trees = g.edge_disjoint_spanning_trees(k) ## line 6282 ##

Of course, this should not have anything to do with the SEP.

comment:166 Changed 11 months ago by gh-kliem

Yes, that is #32169. I was wondering why it did not happen in this case.

comment:167 Changed 11 months ago by git

  • Commit changed from 150225d2a183b76540bf06da75084b04959e65f2 to 2609cb529eeb3ce1d3c5c4be41c54dff0f2f03dc

Branch pushed to git repo; I updated commit sha1. New commits:

2609cb5edge disjoint spanning tree not as fast as claimed, see #32169

comment:168 Changed 10 months ago by git

  • Commit changed from 2609cb529eeb3ce1d3c5c4be41c54dff0f2f03dc to 138f038113e191703a14b153d31e627ba388c7b5

Branch pushed to git repo; I updated commit sha1. New commits:

138f038fix doctest failure for random matrix

comment:169 Changed 10 months ago by git

  • Commit changed from 138f038113e191703a14b153d31e627ba388c7b5 to 8117091a8217210dd1221a212cfa3cde9667f0c1

Branch pushed to git repo; I updated commit sha1. New commits:

8117091one more unstable doctest

comment:170 Changed 10 months ago by gh-kliem

  • Description modified (diff)

New commits:

8117091one more unstable doctest

comment:171 Changed 10 months ago by git

  • Commit changed from 8117091a8217210dd1221a212cfa3cde9667f0c1 to 5739ef7ff468e4186ac352dbafaf7a7593b4b97f

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

db8daf9implicitly fuzz RNG-dependent doctests
e1a487freduce vertices for edge disjoint spanning trees
d311adfdo not remove fixed doctest
accdc2bsimplify doctest
4ad6665fix unstable doctests
c2326fcfixed some doctests for disjoint spanning trees
361b203fix unstable doctest in book_stein_ent
e45603fedge disjoint spanning tree not as fast as claimed, see #32169
eba3bc7fix doctest failure for random matrix
5739ef7one more unstable doctest

comment:172 Changed 10 months ago by gh-kliem

  • Dependencies set to #32498

Rebased on #32498, which fixes the error with (symmetric) edge polytopes.

comment:173 Changed 10 months ago by gh-kliem

  • Dependencies changed from #32498 to #32667

Correct ticket.

comment:174 Changed 10 months ago by mjo

  • Status changed from needs_review to positive_review

comment:175 Changed 10 months ago by gh-kliem

Thank you.

comment:176 follow-up: Changed 10 months ago by mjo

No problem, you'll have to rebase this onto the typo-fix too I think.

comment:177 Changed 10 months ago by git

  • Commit changed from 5739ef7ff468e4186ac352dbafaf7a7593b4b97f to 2c478d1c375f10f4e6f7e95fcb71feff74d13653
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. Last 10 new commits:

3cfe235implicitly fuzz RNG-dependent doctests
1980561reduce vertices for edge disjoint spanning trees
e6dd027do not remove fixed doctest
22c2b66simplify doctest
e32986cfix unstable doctests
7b1bd36fixed some doctests for disjoint spanning trees
812b555fix unstable doctest in book_stein_ent
74e505bedge disjoint spanning tree not as fast as claimed, see #32169
44cd7aefix doctest failure for random matrix
2c478d1one more unstable doctest

comment:178 Changed 10 months ago by gh-kliem

  • Status changed from needs_review to positive_review

comment:179 in reply to: ↑ 176 Changed 10 months ago by gh-kliem

Replying to mjo:

No problem, you'll have to rebase this onto the typo-fix too I think.

I don't know, if this is necessary, but it sure doesn't hurt.

comment:180 Changed 10 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:181 Changed 10 months ago by gh-kliem

This is the merge conflict, which permits a trivial solution (at least trivial for a human being):

diff --cc src/bin/sage-runtests
index d1fe6567e7,4fc2062b15..0000000000
--- a/src/bin/sage-runtests
+++ b/src/bin/sage-runtests
@@@ -64,59 -55,60 +55,97 @@@ if __name__ == "__main__"
               'if "external" is listed, will also run tests for available external software; '
               'if "build" is listed, will also run tests specific to Sage\'s build/packaging system; '
               'if set to "all", then all tests will be run')
++<<<<<<< HEAD
 +    parser.add_option("--randorder", type=int, metavar="SEED", help="randomize order of tests")
 +    parser.add_option("--random-seed", dest="random_seed", type=int, metavar="SEED", help="random seed (integer) for fuzzing doctests")
 +    parser.add_option("--global-iterations", "--global_iterations", type=int, default=0, help="repeat the whole testing process this many times")
 +    parser.add_option("--file-iterations", "--file_iterations", type=int, default=0, help="repeat each file this many times, stopping on the first failure")
 +    parser.add_option("--environment", type=str, default="sage.repl.ipython_kernel.all_jupyter", help="name of a module that provides the global environment for tests")
 +
 +    parser.add_option("-i", "--initial", action="store_true", default=False, help="only show the first failure in each file")
 +    parser.add_option("--exitfirst", action="store_true", default=False, help="end the test run immediately after the first failure or unexpected exception")
 +    parser.add_option("--force_lib", "--force-lib", action="store_true", default=False, help="do not import anything from the tested file(s)")
 +    parser.add_option("--abspath", action="store_true", default=False, help="print absolute paths rather than relative paths")
 +    parser.add_option("--verbose", action="store_true", default=False, help="print debugging output during the test")
 +    parser.add_option("-d", "--debug", action="store_true", default=False, help="drop into a python debugger when an unexpected error is raised")
 +    parser.add_option("--only-errors", action="store_true", default=False, help="only output failures, not test successes")
 +
 +    parser.add_option("--gdb", action="store_true", default=False, help="run doctests under the control of gdb")
 +    parser.add_option("--valgrind", "--memcheck", action="store_true", default=False,
 +                      help="run doctests using Valgrind's memcheck tool.  The log "
 +                         "files are named sage-memcheck.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--massif", action="store_true", default=False,
 +                      help="run doctests using Valgrind's massif tool.  The log "
 +                         "files are named sage-massif.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--cachegrind", action="store_true", default=False,
 +                      help="run doctests using Valgrind's cachegrind tool.  The log "
 +                         "files are named sage-cachegrind.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--omega", action="store_true", default=False,
 +                      help="run doctests using Valgrind's omega tool.  The log "
 +                         "files are named sage-omega.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +
 +    parser.add_option("-f", "--failed", action="store_true", default=False,
++=======
+     parser.add_argument("--randorder", type=int, metavar="SEED", help="randomize order of tests")
+     parser.add_argument("--random-seed", dest="random_seed", type=int, metavar="SEED", help="random seed for fuzzing doctests")
+     parser.add_argument("--global-iterations", "--global_iterations", type=int, default=0, help="repeat the whole testing process this many times")
+     parser.add_argument("--file-iterations", "--file_iterations", type=int, default=0, help="repeat each file this many times, stopping on the first failure")
+     parser.add_argument("--environment", type=str, default="sage.repl.ipython_kernel.all_jupyter", help="name of a module that provides the global environment for tests")
+ 
+     parser.add_argument("-i", "--initial", action="store_true", default=False, help="only show the first failure in each file")
+     parser.add_argument("--exitfirst", action="store_true", default=False, help="end the test run immediately after the first failure or unexpected exception")
+     parser.add_argument("--force_lib", "--force-lib", action="store_true", default=False, help="do not import anything from the test
...
Last edited 10 months ago by gh-kliem (previous) (diff)

comment:182 Changed 10 months ago by git

  • Commit changed from 2c478d1c375f10f4e6f7e95fcb71feff74d13653 to 047379c56890113ff59c9eb59276eeca274f4b79

Branch pushed to git repo; I updated commit sha1. New commits:

047379cfix merge conflict

comment:183 Changed 10 months ago by gh-kliem

  • Status changed from needs_work to positive_review

comment:184 Changed 10 months ago by vbraun

  • Branch changed from public/29935-reb to 047379c56890113ff59c9eb59276eeca274f4b79
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.