Opened 5 years ago

Closed 22 months ago

#15786 closed defect (worksforme)

floor fails for certain expressions.

Reported by: fwclarke Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: symbolics Keywords: floor
Cc: Merged in:
Authors: Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: u/deinst/15786-floor (Commits) Commit: 16e522fb6876ce646af7c52348056b94f3b8dfbc
Dependencies: Stopgaps:

Description

x = -(1725033*pi - 5419351)/(25510582*pi - 80143857)
sage: floor(x)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-400-b214ffda37c2> in <module>()
----> 1 floor(x)

/Users/mafwc/sage-6.1/local/lib/python2.7/site-packages/sage/functions/other.pyc in __call__(self, x, maximum_bits)
    579         try:
    580             x_interval = RealIntervalField(bits)(x)
--> 581             upper_floor = x_interval.upper().floor()
    582             lower_floor = x_interval.lower().floor()
    583 

/Users/mafwc/sage-6.1/local/lib/python2.7/site-packages/sage/rings/real_mpfr.so in sage.rings.real_mpfr.RealNumber.floor (sage/rings/real_mpfr.c:17150)()

ValueError: Calling floor() on infinity or NaN

The problem is that in this case x_interval.upper() is infinite at line 581 of sage/functions/other.py:

sage: RealIntervalField(53)(x)
[1.2500000000000000 .. +infinity]

A simple change to deal with this possibility should fix it.

Change History (17)

comment:1 Changed 5 years ago by mmezzarobba

  • Branch set to u/mmezzarobba/15786-floor
  • Commit set to 5a639167fd546ae48e212f82b868a0204c9cf119

New commits:

5a63916Trac #15786: Initial fix, TBI

comment:2 Changed 5 years ago by git

  • Commit changed from 5a639167fd546ae48e212f82b868a0204c9cf119 to abbd1464a6fc770478446a106d25876523974822

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

abbd146Trac #15786: Initial fix, TBI

comment:3 follow-up: Changed 5 years ago by fwclarke

The new code seems to work well. But unfortunately I'm unable to test this fully because I can't currently rebuild sage. A few comments:

  • It would be good practice to use xrange rather than range
  • The unique_floor method for Real Interval Field elements can be used to simplify the code. Thus that the key part could read:
        for bits in xrange(53, maximum_bits, 100):
            try:
                return RealIntervalField(bits)(x).unique_floor()
            except ValueError:
                continue
    
  • Corresponding changes should be made for the ceil function.
  • Doctests will, of course, be needed.

comment:4 in reply to: ↑ 3 ; follow-up: Changed 5 years ago by mmezzarobba

Thnaks for your comments.

Replying to fwclarke:

  • It would be good practice to use xrange rather than range

I wasn't too sure about that as the correponding range will always be very short, but why not.

  • The unique_floor method for Real Interval Field elements can be used to simplify the code.

Good point, thanks!

  • Corresponding changes should be made for the ceil function.

Sure. And we should make sure that round() does the right thing too.

I would also be tempted to double the precision each time the comparison is inconclusive, instead of increasing it by a fixed amount (at least for large values of bits). In many cases, the complexity of RealIntervalField(bits)(x) will be roughly linear in bits, so the total running time wrt the necessary precision would drop from essentially quadratic to essentially linear. What do you think?

comment:5 in reply to: ↑ 4 Changed 5 years ago by fwclarke

Replying to mmezzarobba:

Replying to fwclarke:

  • It would be good practice to use xrange rather than range

I wasn't too sure about that as the correponding range will always be very short, but why not

I agree, but it would prevent a user wasting time by giving a ridiculously large value to maximum_bits.

  • Corresponding changes should be made for the ceil function.

Sure. And we should make sure that round() does the right thing too.

Yes.

I would also be tempted to double the precision each time the comparison is inconclusive, instead of increasing it by a fixed amount (at least for large values of bits). In many cases, the complexity of RealIntervalField(bits)(x) will be roughly linear in bits, so the total running time wrt the necessary precision would drop from essentially quadratic to essentially linear. What do you think?

Sounds convincing, but I'm no expert on interval arithmetic.

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 4 years ago by deinst

  • Branch changed from u/mmezzarobba/15786-floor to u/deinst/15786-floor

comment:9 Changed 4 years ago by deinst

  • Commit changed from abbd1464a6fc770478446a106d25876523974822 to 16e522fb6876ce646af7c52348056b94f3b8dfbc

Ok, this updates the above fix so that it merges with a recent sage.

It also incorporates the review suggestions.

Both ceil and floor have FIXME: notes saying to move the guts of __call__ to _eval_. I'm willing to do that if it is only a cosmetic change, but I have next to no idea about what is going on with the dispatching.


New commits:

16e522f17059 Ported the old fix to sage 6.7

comment:10 Changed 4 years ago by deinst

  • Authors set to David Einstein
  • Milestone changed from sage-6.4 to sage-6.8
  • Status changed from new to needs_review

comment:11 Changed 4 years ago by rws

  • Component changed from basic arithmetic to symbolics

comment:12 follow-up: Changed 4 years ago by deinst

OK, I think I've figured out why no one has moved the code from __call__ to _eval. If we do the replacement (returning None if we cannot simplify) then if we call ceil or floor with a nonnumeric argument then BuiltinFunction.__call__ delegates to Function.__call__ which coerces its result to an expression as follows

        return new_Expression_from_GEx(SR, res)

So the result of floor or ceil is an expression (that consists of just an integer.)

At first glance, this seems harmless enough, but for to coerce an expression into an integer we call floor or ceil, and that wont work if floor or ceil is not returning an integer then we don't accomplish much. Although the Expression object has an is_integer method, it does not seem to have any way of getting that integer other than calling floor or ceil.

comment:13 in reply to: ↑ 12 Changed 4 years ago by rws

Just to complete the picture:

Replying to deinst:

... Although the Expression object has an is_integer method, it does not seem to have any way of getting that integer other than calling floor or ceil.

is_integer calls Pynac and performs a call to ex::info(info_flags::integer) which is virtual so you have methods named info() for all subclasses of basic, see http://www.ginac.de/tutorial/#The-class-hierarchy. In fact, only add, mul, and numeric have any handling of that flag, the relevant code is here:

The last calls back Sage's function symbolic/pynac.pyx:cdef public bint py_is_integer() which is

   return isinstance(x, int) or isinstance(x, long) or isinstance(x, Integer) or \
           (isinstance(x, Element) and
            ((<Element>x)._parent.is_exact() or (<Element>x)._parent == ring.SR) and
            (x in ZZ))
Last edited 4 years ago by rws (previous) (diff)

comment:14 follow-up: Changed 4 years ago by deinst

  • Status changed from needs_review to needs_work

After a bit of thought, it seemed like the best thing to do would be to move the guts to _eval_ and replace __call__ with something like

    def __call__(self, *args, **kwds):
        res = super(Function_floor, self).__call__(*args, **kwds)

        # Convert to Integer if the output was of type "int" and any of
        # the inputs was a Sage Element
        if isinstance(res, Expression) and res.is_integer():
            return res.pyobject()
        else:
            return res

This should please everyone that expects floor to return an integer type instead of an expression type, while having the functionality routed in the standard way. Unforturnately, we now run into coersion problems on the other end, people are calling floor with values that BuiltinFunction cannot handle. For example, in prime_pi.py there is a doctest

            sage: prime_pi._eval_(str(-2^100))

Which ends up taking floor(str(-2^100)). This works in the current implementation, as str(-2^100) can be coerced to an element of RealIntervalField, but if we route the call through BuiltinFunction.__call__ it dies because str(-2^100) cannot be coerced to an element of SR (this somewhat surprises me).

The obvious answer would be to add some coersion at the front of Function_floor.__call__, but I don't know how far we should take treating floor and ceil as functions needing special care and handling.

There is still the problem of a potential infinite loop in the recursive call

                return floor(SR(x).full_simplify().canonicalize_radical())

I don't know of any Expressions that evaluate to integers, but that maxima cannot simplify, but I'd be surprised if they don't exist. I'm still rummaging about on the border of pynac to figure out how to stop the recursion. If nothing else I can use the substitute trick, but that seems too kludgy.

comment:15 in reply to: ↑ 14 Changed 4 years ago by rws

Replying to deinst:

... but if we route the call through BuiltinFunction.__call__ it dies because str(-2^100) cannot be coerced to an element of SR (this somewhat surprises me).

Possibly related to #17790.

comment:16 Changed 3 years ago by mmezzarobba

See also #12121.

comment:17 Changed 22 months ago by jdemeyer

  • Authors David Einstein deleted
  • Milestone changed from sage-6.8 to sage-duplicate/invalid/wontfix
  • Resolution set to worksforme
  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_work to closed

This works in Sage 8.1.beta3

Note: See TracTickets for help on using tickets.