New implementation of floor()/ceil()

[rwst]

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))
(no answer....)

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))
(no answer....)

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.

CC: @videlec @mezzarobba

Component: symbolics

Author: Jeroen Demeyer

Branch/Commit: 8fddcfd

Reviewer: Ralf Stephan

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

[jdemeyer]

comment:2

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

[mezzarobba]

comment:7

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

[jdemeyer]

comment:8

Replying to @mezzarobba:

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()?

[mezzarobba]

comment:9

Replying to @jdemeyer:

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!)

[jdemeyer]

comment:10

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

[mezzarobba]

comment:11

Replying to @jdemeyer:

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.

[jdemeyer]

Branch: u/jdemeyer/infinite_loop_in_ceil___function

[jdemeyer]

New commits:

4e1cd2c

New implementation of floor/ceil

[jdemeyer]

Commit: 4e1cd2c

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

comment:33

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

[rwst]

comment:34

Yes. It's time to get that done.

[sagetrac-git]

Changed commit from 5f6b998 to 3678400

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 3678400 to 740930b

[sagetrac-git]

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

740930b

Fix comment

[rwst]

comment:38

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 floor/ceil can be very slow at integral values #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.

[rwst]

Reviewer: Ralf Stephan

[sagetrac-git]

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

727b99c

Fix comments and add tests

[sagetrac-git]

Changed commit from 740930b to 727b99c

[vbraun]

comment:41

conflicts with #22024

[rwst]

Changed branch from u/jdemeyer/infinite_loop_in_ceil___function to u/rws/infinite_loop_in_ceil___function

[rwst]

Changed commit from 727b99c to 8fddcfd

[rwst]

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

[vbraun]

Changed branch from u/rws/infinite_loop_in_ceil___function to 8fddcfd