better numerical accuracy testing

[robertwb]

If a line contains tol or tolerance, numerical results are only verified to the given tolerance. This may be prefixed by abs[olute] or rel[ative] to specify whether to measure absolute or relative error; defaults to relative error except when the expected value is exactly zero:

        sage: RDF(pi)                               # abs tol 1e-5 
        3.14159 
        sage: [10^n for n in [0.0 .. 4]]            # rel tol 2e-4 
        [0.9999, 10.001, 100.01, 999.9, 10001] 

This can be useful when the exact output is subject to rounding error and/or processor floating point arithmetic variation.

---

Related:

• .zero_at(epsilon) methods, to fix noisy (and signed) zeroes; see for example #11848.

---

Apply

1. 10952-tol-bin.2.patch​
2. trac_10952-ref.patch​

to the Sage scripts repository.

Apply

1. 10952-tol-doc.2.patch​
2. trac_10952-reviewer-docs-v3.patch​

to the Sage library repository.

[jason]

Amazing speed getting this up! Shouldn't "((?:abs(?:solute)?)" be "((?:abs(?:olute)?)" ?

[jason]

Nitpicky: This comment is now incorrect:

# following three: used only for parsing only_optional; list of comments 

Also, something should be added to the docs about this new option. Perhaps here: ​http://sagemath.org/doc/developer/conventions.html#further-conventions-for-automated-testing-of-examples

[robertwb]

apply only this patch to the bin repo

[robertwb]

Thanks for the comments, new patches attached.

[fbissey]

Would this works with test of that kind as well:

File "/usr/share/sage/devel/sage-main/sage/stats/hmm/chmm.pyx", line 579:
    sage: m.viterbi([-2,-1,.1,0.3])
Expected:
    ([1, 1, 1, 0], -9.5660236533785135)
Got:
    ([1, 1, 1, 0], -9.566023653378513)

or even

File "/usr/share/sage/devel/sage-main/sage/categories/examples/semigroups.py", line 32:
    sage: S.some_elements()
Expected:
    [3, 42, 'a', 3.3999999999999999, 'raton laveur']
Got:
    [3, 42, 'a', 3.4, 'raton laveur']

(test failures courtesy of my work on python-2.7)

[robertwb]

Yes, it would (though you do have to explicitly annotate the test with a tolerance, and if Python 2.7 consistently gives, e.g., 3.4 then we should change the doctest rather than make it fuzzy.)

[mariah]

In trying to review this ticket, I applied 10952-tol-bin.patch in the local/bin directory of a skynet/taurus (x86_64-Linux-nehalem) build of sage-4.7.rc2. I next did 'sage -b'. Yet I get

sage: print "The answers are", 1.5, 2, 1e-12 # tol 1e-3
The answers are 1.50000000000000 2 1.00000000000000e-12

Am I missing something?

[robertwb]

No, that is correct.

The example in the description is an example of something that would pass doctests (even though the true output doesn't match exactly, you're seeing what the actual output is).

[jason]

Another nitpicky: the doc patch misspells "arithmetic". Definitely not big enough to stop a positive review, but also not big enough to be worth my effort in making a new patch right now.

[robertwb]

Argh. Fixed.

[jason]

Thanks! If we had a github pull system, or a system where I could edit the patch inline, I would have fixed it.

[kcrisman]

Replying to jason:

Thanks! If we had a github pull system, or a system where I could edit the patch inline, I would have fixed it.

I have to admit that would be convenient. But wouldn't that create a privileged class of commit people who don't need review? At least that seems to be the model for the projects I'm familiar with.

[jason]

That person would be the release manager. He would be the only one able (or supposed to) merge into the master branch.

On the other hand, given our problems with finding release managers who could do the entire release process, maybe sharing the burden to commit patches to master wouldn't be a bad idea.

[mariah]

I applied 10952-tol-bin.patch in the local/bin directory of a skynet/taurus (x86_64-Linux-nehalem) build of sage-4.7.rc2. I next did 'sage -b'. I then modified a doctest to include the lines in the ticket description

sage: print "The answers are", 1.5, 2, 1e-12 # tol 1e-3
The answers are 1.499999 2.0001 0

I then did 'sage -b' again. When I run the doctest, I get

% ./sage -t  -long -force_lib "devel/sage/sage/symbolic/units.py"
sage -t -long -force_lib "devel/sage/sage/symbolic/units.py"
**********************************************************************
File "/home/mariah/sage/sage-4.7.rc2-x86_64-Linux-nehalem-fc-review-10952/devel/sage/sage/symbolic/units.py", line 13:
    sage: print "The answers are", 1.5, 2, 1e-12 # tol 1e-3
Exception raised:
    Traceback (most recent call last):
      File "/home/mariah/sage/sage-4.7.rc2-x86_64-Linux-nehalem-fc-review-10952/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/mariah/sage/sage-4.7.rc2-x86_64-Linux-nehalem-fc-review-10952/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/mariah/sage/sage-4.7.rc2-x86_64-Linux-nehalem-fc-review-10952/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[6]>", line 1
         res =  print "The answers are", RealNumber('1.5'), Integer(2), RealNumber('1e-12') # tol 1e-3###line 13:
    sage: print "The answers are", 1.5, 2, 1e-12 # tol 1e-3
                    ^
     SyntaxError: invalid syntax
**********************************************************************

Note that if I put the lines

    sage: RDF(pi)                               # abs tol 1e-5
    3.14159

in the doctest, then the doctest passes.

[robertwb]

True. It doesn't work with print (or other non-expression statements). I've created #11336 to generalize it.

I think that this is still plenty useful even with that limitation, and don't know when I'll have more time to work on it--we could either get this in and start using it now or hold off until has time to write a more complete implementation at some later date (which I'd like to get to someday, but that someday list is long...)

[mariah]

Replying to robertwb:

True. It doesn't work with print (or other non-expression statements). I've created #11336 to generalize it.

I think that this is still plenty useful even with that limitation

Agreed. I am just doing my "reviewer" duty.

Positive review.

[jdemeyer]

Which patches have to be applied?

[jdemeyer]

I think the documentation should be expanded a bit to show less trivial examples, for example complex numbers or polynomials with non-exact coefficients.

[jdemeyer]

Also matrices

[rbeezer]

I have added an "Apply" list for this ticket.

My patch fixes one typo in the documentation (a missing ]).

I have added some non-trivial tests.

Jeroen:

1. abs() for a matrix computes the determinant. Not useful for testing.

2. Is there a class of polynomials with numerical coefficients? Does it have abs() defined on it?

I am working on this as a high-priority ticket for Bug Days 32.

Rob

[was]

This ticket is pretty amazing.

Rob, this doctest you added seems very wrong:

   A relative tolerance on a root of a polynomial.
    
   ::
   
       sage: p = (y - 10^16)*(y-10^(-13))*(y-2); p
       y^3 + (-1e+16)*y^2 + (2e+16)*y - 2000.0
       sage: p.roots()
       sage: p.roots(multiplicities=False)[2]     # relative tol 1e-10
       10^16

In particular,

• it seems that y isn't defined
• the output of p.roots() is missing
• I get an output of 1e16 instead of 10^16.

[rbeezer]

Replying to was:

Rob, this doctest you added seems very wrong:

Yes, I think this was the patch missing a refresh. I'll clean it in the AM.

[rbeezer]

Reviewer documentation v2 patch cleans up the mess.

I used 10^16 intentionally. The tolerance feature does arithmetic with the output, so does not have to identically match as text. Maybe that deserves a comment?

Rob

[rbeezer]

Reviewer documentation v3 patch adds a comment about intended output being of any form, fixes some missing quotes and expands a bit more on how this works. Passes tests, so should be ready for review.

[was]

Nice. Game changer!!!! Sweet. It's about time. Great work! W00t. FTW. Frickin' awesome.

[leif]

Shouldn't the code only be included if the doctests actually contain # tol ...?

( +[0-9.e+-]+)? hardly matches what we want btw.

I've put this onto the 1337 ticket (#11337).

[jhpalmieri]

This doesn't work. Re Leif's comment, I think the regexp should something like ' ((\.[0-9]+|[0-9]+(\.[0-9]*)?)e[+-]?[0-9]+)', which adds another group to the match, so we need to make this change:

sage-doctest

@@ -217 +217 @@
 """ % dict
 
 NONE=0; LONG_TIME=1; RANDOM=2; OPTIONAL=3; NOT_IMPLEMENTED=4; NOT_TESTED=5; TOLERANCE=6
-tolerance_pattern = re.compile(r'\b((?:abs(?:olute)?)|(?:rel(?:ative)?))? *?tol(?:erance)?\b( +[0-9.e+-]+)?')
+tolerance_pattern = re.compile(r'\b((?:abs(?:olute)?)|(?:rel(?:ative)?))? *?tol(?:erance)?\b +((\.[0-9]+|[0-9]+(\.[0-9]*)?)e[+-]?[0-9]+)?')
 
 def comment_modifier(s):
     sind = s.find('#')
@@ -239 +239 @@
     m = tolerance_pattern.search(L)
     if m:
         v.append(TOLERANCE)
-        rel_or_abs, epsilon = m.groups()
+        rel_or_abs, epsilon, _, _ = m.groups()
         if rel_or_abs is not None:
             rel_or_abs = rel_or_abs[:3]
         if epsilon is None:

I think this should match any of "1.2e12", "1e-12", ".1e12", without matching "ee12e+-122", like the previous regexp.

In addition to this, the whole thing just flat doesn't work. I created a Python file with some tolerance tests in it, and they all fail, and the failures print badly: they include tracebacks, for example. I'm not sure why the rst file patched in the two "doc" patches isn't being doctested correctly, but as far as I can tell, no doctests are being run in that file -- just add an obviously wrong doctest, and tests still pass. Here is a test file:

"""
Here are some examples::

    sage: 3+3
    6
    sage: RDF(pi)                               # abs tol 1e-4
    3.14159

Here is another example::

    sage: [10^n for n in [0.0 .. 4]]            # rel tol 2e-4
    [0.9999, 10.001, 100.01, 999.9, 10001]

And another::

    sage: RDF(pi)                               # abs tol 1e-4
    3.14159

And that's the end.
"""

Save this as "new.py" and run "sage -t new.py" to see some bad behavior.

[leif]

Replying to jhpalmieri:

I think the regexp should something like

' ((\.[0-9]+|[0-9]+(\.[0-9]*)?)e[+-]?[0-9]+)'`

But that doesn't match 1ee7 :(

You can of course match funny things first, i.e. use more general patterns, but you then have to check the matched expression further before passing it to float().

The whole idea isn't that bad, but carries the danger that people simply increase the tolerance (too much) just to make doctests pass somehow, without caring where the variations originate from.

[jhpalmieri]

But float(1ee7) raises an error. Why would we want to match that?

Re the issue of raising tolerance, I hope that referees will keep an eye on that sort of thing. Dave Kirkby, for example, is a strong advocate of not arbitrarily raising tolerance.

[robertwb]

I've fixed the issue with blanklines terminating example blocks. As for the regular expression for floats, I don't see any need to make it more complicated--I'd rather match miss-typed numbers and raise an error than silently ignore them. If you feel strongly, this could be changed.

Referees should keep an eye on precision. This is back to my philosophy that a computer should run doctests and a human read the code (though we could add a patchbot plugin to flag drops in precision). It's not a new issue--we've been using "..." for quite a while now which is less flexible and more dangerous (as it can match more than just a single number).

[leif]

How about emitting the extra code only if # tol ... is used at all in the file?

That's a simple """... %s ...""" % (tolerance_code if uses_tol else "").

[robertwb]

You're talking about the check_with_tolerance function and helpers. One could add a variable to keep track of this and conditionally emit it; not sure if the added complexity is worth the tiny savings.

[leif]

Replying to robertwb:

You're talking about the check_with_tolerance function and helpers. One could add a variable to keep track of this and conditionally emit it; not sure if the added complexity is worth the tiny savings.

Added complexity? One boolean variable, initialized to false and set to True in only a few places?

This not only reduces the file size and run (import!) time but also avoids more potential name clashes.

Why should one add useless code to each and every file to doctest not using # tol?

[robertwb]

Either we make this variable a global (ugly) or return it on from call to doc_preparse along with the parsed docstring (also ugly). All to save a fraction of a block (~1KB) of an ephemeral file and < 1ms on an already fairly expensive operation. If we're looking to cut fat, it'd be better to avoid the quadratic-time creation of the doctest file string.

The name clash is a red herring--if we avoid it only because # tol is not used, that's a potentially latent bug in my mind. The function could be renamed if need be.

[jhpalmieri]

I don't see anything wrong with more complicated regular expressions, but I like regular expressions. So leave it as is if you want.

Meanwhile, the output for failures using tolerances isn't nice, compared to other sorts of failures:

sage -t  "builds/sage-4.7.2.alpha2/devel/sage-new/sage/homology/new.py"
**********************************************************************
File "/Applications/sage_builds/sage-4.7.2.alpha2/devel/sage-new/sage/homology/new.py", line 4:
    sage: 3+3
Expected:
    8
Got:
    6
**********************************************************************
File "/Applications/sage_builds/sage-4.7.2.alpha2/devel/sage-new/sage/homology/new.py", iled example:
    check_with_tolerance('''
        3.14159
    ''', res, 9.9999999999999998e-13, 'abs')
Exception raised:
    Traceback (most recent call last):
      File "/Applications/sage/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Applications/sage/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Applications/sage/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[11]>", line 3, in <module>
        ''', res, 9.9999999999999998e-13, 'abs')
      File "/Users/palmieri/.sage//tmp/new.py", line 35, in check_with_tolerance
        assert abs(expected_value - actual_value) < epsilon, "Out of tolerance %s vs %s" % (expected_value, actual_value)
    AssertionError: Out of tolerance 3.14159 vs 3.14159265359
**********************************************************************
1 items had failures:
   2 of  13 in __main__.example_0
***Test Failed*** 2 failures.
For whitespace errors, see the file /Users/palmieri/.sage//tmp/.doctest_new.py
	 [3.9 s]

Notice that the line number is missing and the traceback is present. I'm attaching a referee patch which tries to fix this. Please take a look. For me, this gives this sort of output (with a slightly different file):

sage -t  "builds/sage-4.7.2.alpha2/devel/sage-new/new.py"   
**********************************************************************
File "/Applications/sage_builds/sage-4.7.2.alpha2/devel/sage-new/new.py", line 4:
    sage: 3+3
Expected:
    8
Got:
    6
**********************************************************************
File "/Applications/sage_builds/sage-4.7.2.alpha2/devel/sage-new/new.py", line 6:
    sage: RDF(pi)                               # abs tol 1e-6
Out of tolerance 3.14159 vs 3.14159265359
**********************************************************************
File "/Applications/sage_builds/sage-4.7.2.alpha2/devel/sage-new/new.py", line 16:
    sage: RDF(pi)                               # abs tol 1e-8
Out of tolerance 3.14159 vs 3.14159265359
**********************************************************************
1 items had failures:
   3 of  16 in __main__.example_0
***Test Failed*** 3 failures.
For whitespace errors, see the file /Users/palmieri/.sage//tmp/.doctest_new.py
	 [4.2 s]

Since the whole ticket had a positive review earlier, I think if you're happy with my changes, you can switch it back to that status.

Finally, the issue with doctests in conventions.rst is, I think, that the various triple quotes """ confuse the parsing routine (the function pythonify_rst in particular). This belongs on another ticket. That file contains enough incomplete code stubs that I wonder if it shouldn't be doctested at all...

[jhpalmieri]

scripts repo; apply on top of other scripts patch

[leif]

Replying to jhpalmieri:

I don't see anything wrong with more complicated regular expressions, but I like regular expressions. So leave it as is if you want.

Yes, only

sage: foo   # tol 1ee7
anything

should always pass. ;-)

Meanwhile, the output for failures using tolerances isn't nice, compared to other sorts of failures [...]
Notice that the line number is missing and the traceback is present. I'm attaching a referee patch which tries to fix this. Please take a look.

Haven't tested your patch (nor looked at it), but the output you gave looks much better.

Since the whole ticket had a positive review earlier, I think if you're happy with my changes, you can switch it back to that status.

I won't object, though I in general don't like the idea of adding code (regardless how small the overhead or impact might be) unconditionally, i.e., if there's no need to do so.

We have similar situations all around, where everybody adds "just a little", IMHO.

[robertwb]

Replying to leif:

Replying to jhpalmieri:

I don't see anything wrong with more complicated regular expressions, but I like regular expressions. So leave it as is if you want.

Yes, only

sage: foo   # tol 1ee7
anything

should always pass. ;-)

Currently, it raises an error indicating that the *doctest* itself is bad.

Meanwhile, the output for failures using tolerances isn't nice, compared to other sorts of failures [...]
Notice that the line number is missing and the traceback is present. I'm attaching a referee patch which tries to fix this. Please take a look.

Haven't tested your patch (nor looked at it), but the output you gave looks much better.

Since the whole ticket had a positive review earlier, I think if you're happy with my changes, you can switch it back to that status.

I won't object, though I in general don't like the idea of adding code (regardless how small the overhead or impact might be) unconditionally, i.e., if there's no need to do so.

We have similar situations all around, where everybody adds "just a little", IMHO.

Yes, it's a tradeoff between adding "just a little" python parsing overhead to the testing infrastructure or "just a little" human parsing overhead to the testing infrastructure. I'd rather put the burden on machines than developers in this case.

The reviewer patches look good, certainly an improvement, so I'm setting this back to positive review unless there's something else that needs to be taken care of.

[kcrisman]

I'd like to draw the attention of folks here to comment:7:ticket:12493. Apparently one can't do only-optional tests along with tol tests at the same time. My guess is that not too many people use only-optional and the tol stuff is pretty new.

In fact, I only found one occurrence in 5.0.beta3. Can that be right? This has been in Sage for months!

sage: search_src(" tol ","#")
symbolic/integration/integral.py:587:        sage: error.numerical_approx() # abs tol 10e-10

Anyway, even if my analysis is wrong (let's hope it's easier than that), I figure the people here can give a quick diagnosis of #12493.

[kcrisman]

Actually, comment:8:ticket:12493 is even better! Optional and tol don't play well together.