#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: Marc Mezzarobba
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/12121 | 313c497daaec6324dfe4ffdeb684844e301a3f61
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by vdelecroix:
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
> }}}
>
> 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
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
With the branch applied `math.floor` and `numpy.floor` are used directly
{{{
sage: floor(1.2r)
1.0
sage: type(_)
<type 'float'>
}}}
which is distinct from the current Sage behavior
{{{
sage: floor(1.2r)
1
sage: type(_)
<type 'sage.rings.integer.Integer'>
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/12121#comment:44>
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.
