#12121: floor/ceil can be very slow at integral values
-------------------------------------+-------------------------------------
Reporter: dsm | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-7.2
Component: basic arithmetic | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/12121 | a5ef94a5b27b302d813ac83538558b39a39c7267
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* milestone: sage-7.1 => sage-7.2
Old description:
> Reported (in slightly different form) on
> [http://ask.sagemath.org/question/964/lenlist-ceillog42-bugs
> 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.
New description:
Reported (in slightly different form) on
[http://ask.sagemath.org/question/964/lenlist-ceillog42-bugs
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
}}}
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.
The proposal is to:
- first found an interval of reasonably small diameter (arbitrarily set
to 2^-30^) and see whether this is enough to decide the ceiling
- then check equality with the only available candidate (possibly doing
some simplification)
- start further refinement of the interval
--
--
Ticket URL: <http://trac.sagemath.org/ticket/12121#comment:34>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
