#12121: floor/ceil can be very slow at integral values
-------------------------------------+-------------------------------------
Reporter: dsm | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-7.3
Component: basic arithmetic | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers: Marc Mezzarobba
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/12121 | 6f392b8e7b2d562debabca7f99fa1b54180f83cb
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* commit: 9bd70406da71c6e1083fc25cd57435788689018e =>
6f392b8e7b2d562debabca7f99fa1b54180f83cb
* branch: public/12121 => u/vdelecroix/12121
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
>
> 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'>
> }}}
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.
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'>
}}}
--
Comment:
New commits:
||[https://git.sagemath.org/sage.git/commit?id=08ecc069c3f88c11060df2ca2383bcb92b2caf27
08ecc06]||{{{Trac 12121: Fix floor/ceil}}}||
||[https://git.sagemath.org/sage.git/commit?id=b2c5fbe9501e43e6e5e117aae4412db1f21bf1f2
b2c5fbe]||{{{Trac 12121: change __call__ and workaround}}}||
||[https://git.sagemath.org/sage.git/commit?id=82ad3039d0913329de3e3ed514c6397483b7b93a
82ad303]||{{{Trac 12121: fix doctests}}}||
||[https://git.sagemath.org/sage.git/commit?id=194ba9976c58c367d01b767f405f4b4dae1dcad7
194ba99]||{{{Trac 12121: _evalf_ more consistent}}}||
||[https://git.sagemath.org/sage.git/commit?id=2719621b352b267d4aa31d95d8f0c22c08cd1c73
2719621]||{{{Trac 12121: do not check for relation}}}||
||[https://git.sagemath.org/sage.git/commit?id=6f392b8e7b2d562debabca7f99fa1b54180f83cb
6f392b8]||{{{Trac 12121: fix ._name -> ._alt_name}}}||
--
Ticket URL: <https://trac.sagemath.org/ticket/12121#comment:57>
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.
