Opened 4 years ago

Closed 3 years ago

# New implementation of floor()/ceil()

Reported by: Owned by: rws major sage-8.2 symbolics vdelecroix, mmezzarobba Jeroen Demeyer Ralf Stephan N/A 8fddcfd (Commits) 8fddcfd99c77664454e283390379aa2118c5f45e

The `ceil` function calls itself if 20000 bits of precision is not enough, which is an obvious infinite loop.

```sage: ceil(SR(2^20000+1))
```

and

```sage: ceil(Infinity)
...
TypeError: maximum recursion depth exceeded while calling a Python object
```

and

```sage: ceil(NaN)
...
TypeError: maximum recursion depth exceeded while calling a Python object
```

One consequence is that conversion to `int` is also an infinite loop:

```sage: int(SR(2^20000+1))
```

and

```sage: int(NaN)
...
TypeError: maximum recursion depth exceeded in __instancecheck__
```

I propose a new implementation of `floor()` and `ceil()`. The basic idea is to remove the limit on the number of bits and instead put a limit on the number of attempts of computing the floor/ceil. In each attempt, the algorithm tries to determine why computing the floor/ceil did not work.

This fixes all issues that I know with the `floor()`/`ceil()` algorithm. Of course, the algorithm is still heuristic, so there will always be corner cases that won't work.

### comment:1 Changed 4 years ago by jdemeyer

• Description modified (diff)
• Summary changed from Arb NaN infinite loop to NaN -> int infinite loop

### comment:2 Changed 4 years ago by jdemeyer

This had nothing to do with arb. The problem is the conversion `NaN` -> Python `int`.

### comment:3 Changed 4 years ago by jdemeyer

• Description modified (diff)
• Summary changed from NaN -> int infinite loop to ceil(NaN) infinite loop

### comment:4 Changed 4 years ago by jdemeyer

• Description modified (diff)
• Summary changed from ceil(NaN) infinite loop to Infinite loop in ceil() function

### comment:5 Changed 4 years ago by jdemeyer

• Description modified (diff)

### comment:6 Changed 4 years ago by jdemeyer

• Description modified (diff)

### comment:7 follow-up: ↓ 8 Changed 4 years ago by mmezzarobba

Will hopefully be fixed by the rewrite in progress at #12121.

### comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 3 years ago by jdemeyer

• Description modified (diff)

Will hopefully be fixed by the rewrite in progress at #12121.

... which is still not fixed.

I just got hit by this again. Do you have any objections to just remove the "infinite loop" block from `ceil()` and `floor()`?

### comment:9 in reply to: ↑ 8 Changed 3 years ago by mmezzarobba

• Cc vdelecroix added; mmezzarobba removed

I just got hit by this again. Do you have any objections to just remove the "infinite loop" block from `ceil()` and `floor()`?

I don't, but maybe you should ask Vincent. (I just rebased his code from #12121 to see how far we are from a solution there, more news on that hopefully after I run the tests!)

### comment:10 follow-up: ↓ 11 Changed 3 years ago by jdemeyer

I am also working on a proper solution both for this ticket and for #12121. Hang on...

### comment:11 in reply to: ↑ 10 Changed 3 years ago by mmezzarobba

I am also working on a proper solution both for this ticket and for #12121. Hang on...

Ok. I pushed the rebased branch (builds, not tested) to `u/mmezzarobba/ticket/12121-rebased` just in case.

### comment:12 Changed 3 years ago by jdemeyer

• Branch set to u/jdemeyer/infinite_loop_in_ceil___function

### comment:13 Changed 3 years ago by jdemeyer

• Authors set to Jeroen Demeyer
• Commit set to 4e1cd2cdeaa05a07fee8aabbcdb97b96266a17b3
• Description modified (diff)
• Status changed from new to needs_review
• Summary changed from Infinite loop in ceil() function to New implementation of floor()/ceil()

New commits:

 ​4e1cd2c `New implementation of floor/ceil`

### comment:14 Changed 3 years ago by jdemeyer

• Description modified (diff)

### comment:16 Changed 3 years ago by jdemeyer

• Description modified (diff)

### comment:17 Changed 3 years ago by jdemeyer

• Milestone changed from sage-7.5 to sage-8.1
• Status changed from needs_review to needs_work

### comment:18 Changed 3 years ago by git

• Commit changed from 4e1cd2cdeaa05a07fee8aabbcdb97b96266a17b3 to b11c9ce31e4e4866a9a9bdd140e1fc7600369a83

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

 ​b11c9ce `New implementation of floor/ceil`

### comment:19 Changed 3 years ago by jdemeyer

• Status changed from needs_work to needs_review

### comment:20 Changed 3 years ago by jdemeyer

This passes tests on the patchbot.

### comment:21 follow-ups: ↓ 23 ↓ 24 ↓ 25 Changed 3 years ago by vdelecroix

How is this different from the function `incremental_rounding` of #12121 (that proposes a useful `maximum_bits` argument)!? It would be definitely more coherent to work on only one ticket...

I just stopped working on #12121 because of the unreliable equality tests of the symbolic ring. Did you know that pi was a rational number

```sage: n = continued_fraction(pi).convergent(20)
sage: num = n.numerator()
sage: den = n.denominator()
sage: print bool(den*pi == num)
```

### comment:22 Changed 3 years ago by rws

Have you opened a bug ticket?

### comment:23 in reply to: ↑ 21 Changed 3 years ago by jdemeyer

It would be definitely more coherent to work on only one ticket...

Right. It was not really my intention to start a "competing" implementation. I initially intented to do a simple fix but then realized that a simple fix wasn't possible. So I continue working on my initially-simple fix until I ended up with this.

### comment:24 in reply to: ↑ 21 Changed 3 years ago by jdemeyer

I just stopped working on #12121 because of the unreliable equality tests of the symbolic ring.

My branch doesn't require equality tests in the symbolic ring.

### comment:25 in reply to: ↑ 21 Changed 3 years ago by jdemeyer

that proposes a useful `maximum_bits` argument

Right, I do see the point of that.

### comment:26 Changed 3 years ago by git

• Commit changed from b11c9ce31e4e4866a9a9bdd140e1fc7600369a83 to 554fa6211ad06bdc54fd944080e69cb53ef62680

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

 ​554fa62 `New implementation of floor/ceil`

### comment:27 Changed 3 years ago by jdemeyer

Now with a `bits` argument (easier to type and less confusing than `maximum_bits`)

Sorry for duplicating part of #12121. I did not intend to do that, it just ended up that way. Anyway, this ticket here fixes real problems so please consider it for review.

### comment:28 Changed 3 years ago by vdelecroix

typo `the taregt number`

### comment:29 Changed 3 years ago by vdelecroix

```if isinstance(x, (float, complex)):
m = getattr(math, method)
return Integer(m(x))
```

Two questions:

• with complex inputs, the `math` library gives an error
```sage:
sage: math.floor(0jr)
Traceback (most recent call last):
...
TypeError: can't convert complex to float
sage: math.ceil(0jr)
Traceback (most recent call last):
...
TypeError: can't convert complex to float
```

hence there is a bit of contradiction here.

• why would you convert to an `Integer` and not just use the result of whatever `math.floor`, `math.ceil` is actually giving you. That would be more Python friendly. As an example the result of `cos` is not a Sage floating point
```sage: cos(1.0r)
0.5403023058681398
sage: type(_)
<type 'float'>
```

### comment:30 Changed 3 years ago by jdemeyer

You may or may not be right, but I consider that outside the scope of this ticket. I am not changing the return types or handling of complex numbers here.

### comment:31 Changed 3 years ago by git

• Commit changed from 554fa6211ad06bdc54fd944080e69cb53ef62680 to 5f6b9984d500aed37ed8a8b618dcc70df5f97739

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

 ​5f6b998 `New implementation of floor/ceil`

### comment:32 Changed 3 years ago by rws

• Status changed from needs_review to needs_work

Does not apply.

### comment:33 Changed 3 years ago by jdemeyer

Do you plan to review this ticket if I fix the conflict?

### comment:34 Changed 3 years ago by rws

Yes. It's time to get that done.

### comment:35 Changed 3 years ago by git

• Commit changed from 5f6b9984d500aed37ed8a8b618dcc70df5f97739 to 3678400db638d01a6447a1d8a2cef7e354e2bc72

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

 ​3678400 `Merge tag '8.1.rc3' into t/22079/infinite_loop_in_ceil___function`

### comment:36 Changed 3 years ago by git

• Commit changed from 3678400db638d01a6447a1d8a2cef7e354e2bc72 to 740930b09b183c439ae422f176a5f23f93a7ad19

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

 ​740930b `Fix comment`

### comment:37 Changed 3 years ago by jdemeyer

• Status changed from needs_work to needs_review

### comment:38 Changed 3 years ago by rws

• Milestone changed from sage-8.1 to sage-8.2
• Reviewers set to Ralf Stephan

Patchbot is green, the documentation looks good. The code is well documented and improves the present implementation. This all represents my minimum criterion to include code in Sage. There are a few things I'd ask you to change/add:

• there is one typo (`immediatly`)
• the ticket makes #12121 mostly a duplicate, and it would be nice if you could add the most relevant doctests from there, I'd suggest
```sage: floor(log(4) / log(2))
2
sage: a = floor(5.4 + x); a
floor(x + 5.40000000000000)
sage: a.subs(x==2)
7
sage: floor(log(2**(3/2)) / log(2) + 1/2)
2
sage: floor(log(2**(-3/2)) / log(2) + 1/2)
-1
sage: e1 = pi - continued_fraction(pi).convergent(2785)
sage: e2 = e - continued_fraction(e).convergent(1500)
sage: f = e1/e2
sage: f = 1 / (f - continued_fraction(f).convergent(1000))
sage: f = f - continued_fraction(f).convergent(1)
sage: floor(f, bits=40000)
-1
sage: ceil(f, bits=40000)
0
```

You can set positive after the above changes. If you don't agree with my above criterion however then don't.

Finally for a later ticket, one doctest from #12121 cannot be solved. I agree not everything can be solved. This one however would be easy if you had some heuristic to call QQbar on algebraic expressions:

```sage: z = (11/9*sqrt(3)*sqrt(2) + 3)^(1/3) + 1/3/(11/9*sqrt(3)*sqrt(2) + 3)^(1/3) - 1
sage: ceil(z, bits=400000)
...fails
```

This is still better than current Sage so we should think of a way to limit or predict the effort QQbar is making, e.g. by predicting the degree of the minimal polynomial involved and calling QQbar from `floor()` when it does not take forever.

### comment:39 Changed 3 years ago by git

• Commit changed from 740930b09b183c439ae422f176a5f23f93a7ad19 to 727b99caf6f7b28728f42260b5f64ba2835957ac

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

 ​727b99c `Fix comments and add tests`

### comment:40 Changed 3 years ago by jdemeyer

• Status changed from needs_review to positive_review

### comment:41 Changed 3 years ago by vbraun

• Status changed from positive_review to needs_work

conflicts with #22024

### comment:42 Changed 3 years ago by rws

• Branch changed from u/jdemeyer/infinite_loop_in_ceil___function to u/rws/infinite_loop_in_ceil___function

### comment:43 Changed 3 years ago by rws

• Commit changed from 727b99caf6f7b28728f42260b5f64ba2835957ac to 8fddcfd99c77664454e283390379aa2118c5f45e
• Status changed from needs_work to positive_review

New commits:

 ​7f79a2d `Merge branch 'u/rws/24062' of git://trac.sagemath.org/sage into t/22024/symbolic_placeholder_for_complex_root` ​ba171aa `22024: symbolic placeholder for complex root` ​8fddcfd `Merge branch 'u/rws/symbolic_placeholder_for_complex_root' of git://trac.sagemath.org/sage into t/22079/infinite_loop_in_ceil___function`

### comment:44 Changed 3 years ago by vbraun

• Branch changed from u/rws/infinite_loop_in_ceil___function to 8fddcfd99c77664454e283390379aa2118c5f45e
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.