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
comment:4 Changed 4 years ago by kini
Apparently is_int is deprecated.
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
- Commit set to 6b75d32ab5cc279a8566f0bc67acc2501bbb833e
- Status changed from new to needs_review
New commits:
6b75d32 | Trac #12121: floor/ceil can be very slow at integral values |
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.