round of symbolic expression (precision issue due to RR)

[dkrenn]

We have

sage: u = sqrt(43203735824841025516773866131535024) #add one digit
sage: floor(u)
207855083711803944
sage: round(u) # ?? smaller than floor(u)! No warning message...
207855083711803936
sage: r = round(u)
sage: ceil(u)
207855083711803945

Numbers with one digit less work

sage: t=sqrt(4320373582484102551677386613153502)
sage: floor(t)
65729548777426599
sage: round(t) #everything as expected, floor ≤ round ≤ ceil
65729548777426600
sage: ceil(t)
65729548777426600

The docstring/source code of the symbolic round mentions that behavior

Definition:     u.round(self)
Source:
    def round(self):
        """
        Round this expression to the nearest integer.

        This method evaluates an expression in ``RR`` first and rounds
        the result. This may lead to misleading results.

        EXAMPLES::

            sage: t = sqrt(Integer('1'*1000)).round(); t
            3333333333333333056287287783757109595393...

         This is off by a huge margin::

            sage: (Integer('1'*1000) - t^2).ndigits()
            984
        """
        #FIXME: can we do better?

This was reported on sage-support by Lorenzo. I created a ticket here, since I didn't find one for that behavior (but maybe I missed it...).

Apply attachment: trac_12968.patch.

CC: @kcrisman @orlitzky

Component: symbolics

Keywords: round symbolic precision RR beginner, sd40.5

Author: Mike Hansen

Reviewer: Burcin Erocal, Karl-Dieter Crisman

Merged: sage-5.1.beta5

Issue created by migration from https://trac.sagemath.org/ticket/12968

[burcin]

comment:1

This is the same problem as in #9627 and #9953. We should change those tickets to mention round() and close this one. Perhaps floor() and ceil() can be mentioned there as well. The implementation of floor.__call__() in sage/functions/other.py might help here.

[mwhansen]

comment:4

It might be best to do something along the lines of:

def round(self):
    return floor(self+1/2)

but there's the possibility that that addition causes problems with inexact arithmetic.

[mwhansen]

Author: Mike Hansen

[mwhansen]

comment:5

I've put a patch up which should fix these issues.

[burcin]

Reviewer: Burcin Erocal

[burcin]

comment:6

Thanks Mike! This looks great.

Just by reading the code, I have one minor problem: Isn't the test self > 0 too costly if the expression still contains variables? Maybe we should convert to RR first and do the comparison there, similar to the way Gonzalo handled this in #9627. This would also raise an error earlier instead of going through maxima for the comparison and waiting for floor or ceil to complain.

[mwhansen]

comment:7

Replying to @burcin:

Just by reading the code, I have one minor problem: Isn't the test self > 0 too costly if the expression still contains variables? Maybe we should convert to RR first and do the comparison there

Maybe you could try converting to RIF first instead and then do the full test if that interval contains zero. Checking to see if there are variables should also be really quick. I'll put up a patch that does this.

[mwhansen]

comment:8

I've posted a new patch which should be better.

[burcin]

comment:9

Looks good to me.

Patchbot, apply attachment: trac_12968.patch.

[jdemeyer]

comment:10

This causes a doctest failure (see also the Patchbot):

sage -t  -force_lib devel/sage/sage/rings/polynomial/polynomial_rational_flint.pyx
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.1.beta2/devel/sage-main/sage/rings/polynomial/polynomial_rational_flint.pyx", line 596:
    sage: f.reverse(I)
Expected:
    Traceback (most recent call last):
    ...
    TypeError: can't convert complex to int; use int(abs(z))
Got:
    Traceback (most recent call last):
      File "/padic/scratch/jdemeyer/merger/sage-5.1.beta2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/padic/scratch/jdemeyer/merger/sage-5.1.beta2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/padic/scratch/jdemeyer/merger/sage-5.1.beta2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_17[19]>", line 1, in <module>
        f.reverse(I)###line 596:
    sage: f.reverse(I)
      File "polynomial_rational_flint.pyx", line 608, in sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint.reverse
 (sage/rings/polynomial/polynomial_rational_flint.cpp:7922)
        len = <unsigned long> n
      File "expression.pyx", line 751, in sage.symbolic.expression.Expression.__int__ (sage/symbolic/expression.cpp:4932)
    ValueError: cannot convert I to int
**********************************************************************

[mwhansen]

Attachment: trac_12968.patch.gz

[mwhansen]

Changed keywords from round symbolic precision RR beginner to round symbolic precision RR beginner, sd40.5

[mwhansen]

comment:11

I've posted a new patch which fixes this issue. If someone could look over it, it's just a matter of changing the doctest.

[kcrisman]

comment:12

Yes, this is clearly the same behavior for the error. This test passes now, as do many other relevant ones.

[kcrisman]

Changed reviewer from Burcin Erocal to Burcin Erocal, Karl-Dieter Crisman

[sagetrac-dsm]

comment:13

Just before we put this to bed, I noticed a quirk involving negative numbers. We typically truncate toward zero, like Python:

Python 2.7.2 (v2.7.2:8527427914a2, Jun 11 2011, 15:22:34) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from fractions import Fraction
>>> int(-1)
-1
>>> int(-0.99)
0
>>> int(Fraction(-99, 100))
0

But our int-ing is a little more sensitive:

sage: int(-1)
-1
sage: int(-0.99)
0
sage: int(SR(-99/100))
0
sage: -0.99 == -99/100
True
sage: int(-99/100) # ??
-1

[mwhansen]

comment:14

This is due to the default rounding mode for rationals, which is independent of this code. We could make a ticket for changing that,

[sagetrac-dsm]

comment:15

Yeah, since the behaviour precedes this patch and this patch makes things better, I left it as positive review. If it were a one-line change (i.e. this behaviour wasn't possibly deliberate) we could have done it here, but instead I'll open a new ticket.

[jdemeyer]

Merged: sage-5.1.beta5