Changes between Version 2 and Version 34 of Ticket #12121
 Timestamp:
 03/24/16 18:36:02 (5 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #12121

Property
Status
changed from
new
toneeds_review

Property
Authors
changed from
to
Vincent Delecroix

Property
Branch
changed from
to
u/vdelecroix/12121

Property
Milestone
changed from
sage5.11
tosage7.2

Property
Commit
changed from
to
a5ef94a5b27b302d813ac83538558b39a39c7267

Property
Status
changed from

Ticket #12121 – Description
v2 v34 1 1 Reported (in slightly different form) on [http://ask.sagemath.org/question/964/lenlistceillog42bugs ask.sagemath.org]: 2 3 4 2 {{{ 5 3 sage: %timeit floor(log(3)/log(2)) … … 7 5 sage: %timeit floor(log(4)/log(2)) 8 6 5 loops, best of 3: 3.79 s per loop 9 sage: %timeit ceil(log(3)/log(2))10 625 loops, best of 3: 586 µs per loop11 sage: %timeit ceil(log(4)/log(2))12 5 loops, best of 3: 3.79 s per loop13 7 }}} 14 8 15 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.9 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 (2  epsilon, 2 + epsilon) and endpoints have different ceilings. 16 10 17 One possible solution would be to try 18 19 {{{ 20 sage: %timeit bool(log(4)/log(2) == round(log(4)/log(2))) 21 125 loops, best of 3: 5.57 ms per loop 22 }}} 23 24 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. 25 26 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. 27 11 The proposal is to: 12  first found an interval of reasonably small diameter (arbitrarily set to 2^30^) and see whether this is enough to decide the ceiling 13  then check equality with the only available candidate (possibly doing some simplification) 14  start further refinement of the interval