floor/ceil can be very slow at integral values
|Reported by:||dsm||Owned by:||AlexGhitza|
|Report Upstream:||N/A||Work issues:|
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.