#12121: floor/ceil can be very slow at integral values
-------------------------------------+-------------------------------------
Reporter: dsm | Owner: AlexGhitza
Type: defect | Status: needs_work
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 | 602e5158c5f37c6900a1dee8e27a228114af1319
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by mmezzarobba):
* status: needs_review => needs_work
Comment:
Okay, I'm back. Sorry that it took so long.
Replying to [comment:41 vdelecroix]:
> > * what don't you like about `unique_integer()`?
>
> an `assert` does not cost anything. And `unique_integer` silently fails
if the interval does not enclose a unique integer.
Uh? No, it doesn't.
> > * is it really better to have an absolute bound for the diameter that
makes us suspect we found an exact integer, rather than something that
depends on the precision?
>
> the precision of what? there is the field used for the evaluation which
is different from the diameter of the interval. If you have more than one
integer in your interval which one are you using to test equality?
The precision of the interval computation, i.e. `bits`. The idea being
that if we found an interval of width (say) 2⁻²⁰ containing an integer by
computing with 1000 bits of precision, we may want to see if the width of
the interval keeps decreasing when the precision increases and only run
the symbolic part of the algorithm if that's the case. But I agree that
this is a very minor issue at best.
> > * why do you insist on using `==` on symbolic expressions instead of
`is_trivial_zero()`?
>
> Because I want to check equality with an integer. Not if it is a trivial
equality.
I mean using `is_trivial_zero()` after calling `full_simplify()` & co, as
in my version: this is safer than relying on `==` and essentially as
powerful.
> > * do we really need two loops that do essentially the same thing
(including raising errors with the exact same message)?
>
> The equality test is potentially costly. And we want to avoid it as much
as possible. In particular, it makes no sense to test this equality within
each step of the loop as it is in your version.
Yes—as I said, my version was just a rough sketch of the changes I'd b
tempted to make, nothing finished. As the code I was starting with used to
loop forever in the typical situation where mine would do the symbolic
test repeatedly (that is, `x` ∈ ℤ integer but we don't manage to prove
it), I thought the additional cost would be acceptable. `;-)` But anyway,
it is not hard to do the test only once while avoiding the code
duplication.
> On a related note, I noticed that for `round` you need to test equality
with elements of `ZZ + 1/2`.
Couldn't you just compute ceil(x-1/2)?
------
Now for some comments on the current code:
* To summarize the above, I still think the main logic in
`incremental_rounding()` could be shortened to something like (not
tested):
{{{
unique_rounding = getattr(RealIntervalFieldElement, 'unique_' + mode)
r = RR.one() >> 20
bits = 64
candidate = None
while bits < maximum_bits:
interval = RealIntervalField(bits)(x) # may raise a TypeError
try:
return unique_rounding(interval)
except ValueError:
pass
if candidate is None and interval.absolute_diameter() > r:
candidate = interval.unique_integer()
try:
delta = x - candidate
if (delta.is_zero()
or
SR(delta).full_simplify().canonicalize_radical()
.is_trivial_zero()
or QQbar(delta).is_zero()):
return candidate
except (TypeError, ValueError):
pass
bits *= 2
}}}
* I'd also make `incremental_rounding()` private and dispense with the
argument checking (and perhaps move it to `real_mpfi` if your plan is to
use it from elsewhere)—but I'm okay with keeping it as it is. An advantage
of making it private is that you could take the “unique rounding” function
on intervals as input instead of accessing it via `getattr()`. Another
option would be to introduce a common base class for `Function_floor`,
`Function_ceil` and `Function_round`.
* I'm a little uneasy about the changes you made to
`BuiltinFunction.__call__()`. The fact that it used to convert non-Element
inputs to Elements looks intentional and pretty reasonable to me. Is it
really necessary to change that behavior? That being said, I'm a bit lost
in the maze of `Function.__call__`, `BuiltinFunction.__call__`, `_eval_`,
`_evalf_`, `_evalf_try_` and friends, so if you tell me you are confident
that the change is correct I'll trust you!
* If these changes stay, then I guess this
{{{
if module is not None:
func = getattr(module, self._name, None)
if func is None and self._alt_name is not None:
func = getattr(module, self._name, None)
^^^^^
}}}
should be `_alt_name`.
* Note that these changes also make
{{{
sage: sin(numpy.int32(0))
0.0
}}}
which is at odds with
{{{
sage: sin(ZZ(0)).parent()
Integer Ring
}}}
(perhaps not ideal, but predictable at least).
* In `Function_*`, what is the point of calling `_evalf_()` from
`_eval_()`?
* And why isn't the logic for choosing `maximum_bits` in `_evalf_()` the
same in `floor`, `ceil` and `round`?
* I wouldn't bother with checking that `x` is not a relation. First,
`_eval_()` methods of individual functions are probably not the right
place for that (either `BuiltinFunction.__call__()` or perhaps methods
`ceil()`, `floor()` etc. in a future subclass `RelationalExpression` of
`Expression` would be more reasonable). Besides, various other nonsensical
inputs (e.g. series, booleans) are accepted without error, so it is a bit
strange to have an ad hoc check dealing with this one.
--
Ticket URL: <http://trac.sagemath.org/ticket/12121#comment:49>
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.
