Opened 4 years ago

Last modified 41 hours ago

#12121 needs_review defect

floor/ceil can be very slow at integral values

Reported by: dsm Owned by: AlexGhitza
Priority: major Milestone: sage-6.4
Component: basic arithmetic Keywords:
Cc: kcrisman Merged in:
Authors: Akshay Ajagekar Reviewers:
Report Upstream: N/A Work issues:
Branch: u/ajagekar.akshay/Trac12121 (Commits) Commit: 6b75d32ab5cc279a8566f0bc67acc2501bbb833e
Dependencies: Stopgaps:

Description (last modified by dsm)

Reported (in slightly different form) on ask.sagemath.org:

sage: %timeit floor(log(3)/log(2))
625 loops, best of 3: 586 µs per loop
sage: %timeit floor(log(4)/log(2))
5 loops, best of 3: 3.79 s per loop
sage: %timeit ceil(log(3)/log(2))
625 loops, best of 3: 586 µs per loop
sage: %timeit ceil(log(4)/log(2))
5 loops, best of 3: 3.79 s per loop

This happens because ceil and floor first try to increase the precision of a coercion of the input argument to a RealInterval by 100 bits from 53 to 20000 before finally trying a full_simplify, which succeeds. The RealInterval rounds all fail because the interval is always of the form (1.99999, 2.0000), and endpoints have different ceilings.

One possible solution would be to try

sage: %timeit bool(log(4)/log(2) == round(log(4)/log(2)))
125 loops, best of 3: 5.57 ms per loop

after some number (maybe even 1?) of RealInterval attempts, and then get back to increasing the precision. Trying to think of use cases, ceil and floor are probably called 95%+ of the time on things which only require a round or two at most to determine the answer, so it makes sense to optimize that end.

As well, the "+100 bits" approach (rather than going up by some factor each time, say) probably penalizes numbers requiring lots of bits too much relative to those requiring only a few, but the integer case is probably more important.

Change History (11)

comment:1 Changed 4 years ago by dsm

  • Description modified (diff)

comment:2 Changed 4 years ago by dsm

  • Description modified (diff)

comment:3 Changed 4 years ago by dsm

Note to self (and others): we can use is_int to decide when we should test for equality. Test (once) the first time there's only one integer in the interval. If you have equality there, you're done. If not, you never will (or won't be able to prove it, anyway) and can carry on.

comment:4 Changed 4 years ago by kini

comment:5 Changed 3 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 2 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 22 months ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 18 months ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 7 months ago by zimmerma

I'm not sure if this should go to this ticket, but the following never returns:

sage: z
(11/9*sqrt(3)*sqrt(2) + 3)^(1/3) + 1/3/(11/9*sqrt(3)*sqrt(2) + 3)^(1/3) - 1
sage: floor(z)

Even floor(z, maximum_bits=53) loops infinitely.
Should I open a separate ticket?

comment:10 Changed 41 hours ago by ajagekar.akshay

  • Branch set to u/ajagekar.akshay/Trac12121

comment:11 Changed 41 hours ago by ajagekar.akshay

  • Authors set to Akshay Ajagekar
  • Commit set to 6b75d32ab5cc279a8566f0bc67acc2501bbb833e
  • Status changed from new to needs_review

New commits:

6b75d32Trac #12121: floor/ceil can be very slow at integral values
Note: See TracTickets for help on using tickets.