Opened 3 years ago

Last modified 4 months ago

#12121 new 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: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
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 (8)

comment:1 Changed 3 years ago by dsm

  • Description modified (diff)

comment:2 Changed 3 years ago by dsm

  • Description modified (diff)

comment:3 Changed 3 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 2 years ago by kini

comment:5 Changed 16 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 11 months ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 8 months ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 4 months ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.