Opened 3 years ago
Last modified 3 weeks 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 2 years ago by dsm
comment:4 Changed 2 years ago by kini
Apparently is_int is deprecated.
comment:5 Changed 13 months ago by jdemeyer
- Milestone changed from sage-5.11 to sage-5.12
comment:6 Changed 7 months ago by vbraun_spam
- Milestone changed from sage-6.1 to sage-6.2
comment:7 Changed 4 months ago by vbraun_spam
- Milestone changed from sage-6.2 to sage-6.3
comment:8 Changed 3 weeks ago by vbraun_spam
- Milestone changed from sage-6.3 to sage-6.4
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.