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: sage-8.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 jdemeyer)

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 jdemeyer

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

comment:2 Changed 3 years ago by jdemeyer

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

comment:3 Changed 3 years ago by jdemeyer

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

comment:4 Changed 3 years ago by jdemeyer

  • 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 jdemeyer

  • Description modified (diff)

comment:6 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:7 follow-up: Changed 3 years ago by mmezzarobba

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

comment:8 in reply to: ↑ 7 ; follow-up: Changed 2 years ago by jdemeyer

  • 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 mmezzarobba

  • 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() 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: Changed 2 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 2 years ago by mmezzarobba

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.

comment:12 Changed 2 years ago by jdemeyer

  • Branch set to u/jdemeyer/infinite_loop_in_ceil___function

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

4e1cd2cNew implementation of floor/ceil

comment:14 Changed 2 years ago by jdemeyer

  • Description modified (diff)

comment:15 Changed 2 years ago by jdemeyer

  • Cc mmezzarobba added

comment:16 Changed 2 years ago by jdemeyer

  • Description modified (diff)

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

b11c9ceNew implementation of floor/ceil

comment:19 Changed 2 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:20 Changed 2 years ago by jdemeyer

This passes tests on the patchbot.

comment:21 follow-ups: Changed 2 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 2 years ago by rws

Have you opened a bug ticket?

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

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 initially-simple fix until I ended up with this.

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

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 jdemeyer

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 git

  • Commit changed from b11c9ce31e4e4866a9a9bdd140e1fc7600369a83 to 554fa6211ad06bdc54fd944080e69cb53ef62680

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

554fa62New implementation of floor/ceil

comment:27 Changed 2 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 2 years ago by vdelecroix

typo the taregt number

comment:29 Changed 2 years ago by vdelecroix

About

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 2 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 2 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:

5f6b998New implementation of floor/ceil

comment:32 Changed 2 years ago by rws

  • Status changed from needs_review to needs_work

Does not apply.

comment:33 Changed 2 years ago by jdemeyer

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

comment:34 Changed 2 years ago by rws

Yes. It's time to get that done.

comment:35 Changed 2 years ago by git

  • Commit changed from 5f6b9984d500aed37ed8a8b618dcc70df5f97739 to 3678400db638d01a6447a1d8a2cef7e354e2bc72

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

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

comment:36 Changed 2 years ago by git

  • Commit changed from 3678400db638d01a6447a1d8a2cef7e354e2bc72 to 740930b09b183c439ae422f176a5f23f93a7ad19

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

740930bFix comment

comment:37 Changed 2 years ago by jdemeyer

  • Status changed from needs_work to needs_review

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

727b99cFix comments and add tests

comment:40 Changed 2 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:41 Changed 2 years ago by vbraun

  • Status changed from positive_review to needs_work

conflicts with #22024

comment:42 Changed 2 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 2 years ago by rws

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

New commits:

7f79a2dMerge branch 'u/rws/24062' of git://trac.sagemath.org/sage into t/22024/symbolic_placeholder_for_complex_root
ba171aa22024: symbolic placeholder for complex root
8fddcfdMerge 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 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.