Changes between Version 2 and Version 34 of Ticket #12121


Ignore:
Timestamp:
03/24/16 18:36:02 (5 years ago)
Author:
vdelecroix
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #12121

    • Property Status changed from new to needs_review
    • Property Authors changed from to Vincent Delecroix
    • Property Branch changed from to u/vdelecroix/12121
    • Property Milestone changed from sage-5.11 to sage-7.2
    • Property Commit changed from to a5ef94a5b27b302d813ac83538558b39a39c7267
  • Ticket #12121 – Description

    v2 v34  
    11Reported (in slightly different form) on [http://ask.sagemath.org/question/964/lenlist-ceillog42-bugs ask.sagemath.org]:
    2 
    3 
    42{{{
    53sage: %timeit floor(log(3)/log(2))
     
    75sage: %timeit floor(log(4)/log(2))
    865 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 loop
    11 sage: %timeit ceil(log(4)/log(2))
    12 5 loops, best of 3: 3.79 s per loop
    137}}}
    148
    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.
     9This 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.
    1610
    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 
     11The 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