Opened 3 years ago
Closed 2 years ago
#22079 closed defect (fixed)
New implementation of floor()/ceil()
Reported by:  rws  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  symbolics  Keywords:  
Cc:  vdelecroix, mmezzarobba  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Ralf Stephan 
Report Upstream:  N/A  Work issues:  
Branch:  8fddcfd (Commits)  Commit:  8fddcfd99c77664454e283390379aa2118c5f45e 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (44)
comment:1 Changed 3 years ago by
 Description modified (diff)
 Summary changed from Arb NaN infinite loop to NaN > int infinite loop
comment:2 Changed 3 years ago by
comment:3 Changed 3 years ago by
 Description modified (diff)
 Summary changed from NaN > int infinite loop to ceil(NaN) infinite loop
comment:4 Changed 3 years ago by
 Cc mmezzarobba added
 Description modified (diff)
 Summary changed from ceil(NaN) infinite loop to Infinite loop in ceil() function
comment:5 Changed 3 years ago by
 Description modified (diff)
comment:6 Changed 3 years ago by
 Description modified (diff)
comment:7 followup: ↓ 8 Changed 3 years ago by
Will hopefully be fixed by the rewrite in progress at #12121.
comment:8 in reply to: ↑ 7 ; followup: ↓ 9 Changed 2 years ago by
 Description modified (diff)
Replying to mmezzarobba:
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 2 years ago by
 Cc vdelecroix added; mmezzarobba removed
Replying to jdemeyer:
I just got hit by this again. Do you have any objections to just remove the "infinite loop" block from
ceil()
andfloor()
?
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 followup: ↓ 11 Changed 2 years ago by
I am also working on a proper solution both for this ticket and for #12121. Hang on...
comment:11 in reply to: ↑ 10 Changed 2 years ago by
comment:12 Changed 2 years ago by
 Branch set to u/jdemeyer/infinite_loop_in_ceil___function
comment:13 Changed 2 years ago by
 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 2 years ago by
 Description modified (diff)
comment:15 Changed 2 years ago by
 Cc mmezzarobba added
comment:16 Changed 2 years ago by
 Description modified (diff)
comment:17 Changed 2 years ago by
 Milestone changed from sage7.5 to sage8.1
 Status changed from needs_review to needs_work
comment:18 Changed 2 years ago by
 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 2 years ago by
 Status changed from needs_work to needs_review
comment:20 Changed 2 years ago by
This passes tests on the patchbot.
comment:21 followups: ↓ 23 ↓ 24 ↓ 25 Changed 2 years ago by
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 2 years ago by
Have you opened a bug ticket?
comment:23 in reply to: ↑ 21 Changed 2 years ago by
Replying to vdelecroix:
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 initiallysimple fix until I ended up with this.
comment:24 in reply to: ↑ 21 Changed 2 years ago by
Replying to vdelecroix:
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 2 years ago by
Replying to vdelecroix:
that proposes a useful
maximum_bits
argument
Right, I do see the point of that.
comment:26 Changed 2 years ago by
 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 2 years ago by
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 2 years ago by
typo the taregt number
comment:29 Changed 2 years ago by
About
if isinstance(x, (float, complex)): m = getattr(math, method) return Integer(m(x))
Two questions:
 with complex inputs, the
math
library gives an errorsage: 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 whatevermath.floor
,math.ceil
is actually giving you. That would be more Python friendly. As an example the result ofcos
is not a Sage floating pointsage: cos(1.0r) 0.5403023058681398 sage: type(_) <type 'float'>
comment:30 Changed 2 years ago by
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 2 years ago by
 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:33 Changed 2 years ago by
Do you plan to review this ticket if I fix the conflict?
comment:34 Changed 2 years ago by
Yes. It's time to get that done.
comment:35 Changed 2 years ago by
 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 2 years ago by
 Commit changed from 3678400db638d01a6447a1d8a2cef7e354e2bc72 to 740930b09b183c439ae422f176a5f23f93a7ad19
Branch pushed to git repo; I updated commit sha1. New commits:
740930b  Fix comment

comment:37 Changed 2 years ago by
 Status changed from needs_work to needs_review
comment:38 Changed 2 years ago by
 Milestone changed from sage8.1 to sage8.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 2 years ago by
 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 2 years ago by
 Status changed from needs_review to positive_review
comment:41 Changed 2 years ago by
 Status changed from positive_review to needs_work
conflicts with #22024
comment:42 Changed 2 years ago by
 Branch changed from u/jdemeyer/infinite_loop_in_ceil___function to u/rws/infinite_loop_in_ceil___function
comment:43 Changed 2 years ago by
 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 2 years ago by
 Branch changed from u/rws/infinite_loop_in_ceil___function to 8fddcfd99c77664454e283390379aa2118c5f45e
 Resolution set to fixed
 Status changed from positive_review to closed
This had nothing to do with arb. The problem is the conversion
NaN
> Pythonint
.