Opened 6 years ago

Closed 2 years ago

# floor fails for certain expressions.

Reported by: Owned by: fwclarke major sage-duplicate/invalid/wontfix symbolics floor Jeroen Demeyer N/A u/deinst/15786-floor (Commits) 16e522fb6876ce646af7c52348056b94f3b8dfbc

### 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.

### comment:1 Changed 6 years ago by mmezzarobba

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

New commits:

 ​5a63916 `Trac #15786: Initial fix, TBI`

### comment:2 Changed 6 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:

 ​abbd146 `Trac #15786: Initial fix, TBI`

### comment:3 follow-up: ↓ 4 Changed 6 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: ↓ 5 Changed 6 years ago by mmezzarobba

• 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 6 years ago by 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 6 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 5 years ago by deinst

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

### comment:9 Changed 5 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:

 ​16e522f `17059 Ported the old fix to sage 6.7`

### comment:10 Changed 5 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 5 years ago by rws

• Component changed from basic arithmetic to symbolics

### comment:12 follow-up: ↓ 13 Changed 5 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 5 years ago by rws

Just to complete the picture:

... 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 5 years ago by rws (previous) (diff)

### comment:14 follow-up: ↓ 15 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 `Expression`s 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

... 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.