floor/ceil can be very slow at integral values #12121

sagetrac-dsm · 2011-12-06T15:35:19Z

Reported (in slightly different form) on 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'>

CC: @kcrisman @jdemeyer @pelegm

Component: basic arithmetic

Work Issues: test failures

Author: Vincent Delecroix

Branch/Commit: u/mmezzarobba/ticket/12121-rebased @ 1b1a32a

Reviewer: Marc Mezzarobba, Ralf Stephan

Issue created by migration from https://trac.sagemath.org/ticket/12121

The text was updated successfully, but these errors were encountered:

sagetrac-dsm · 2012-03-03T16:43:37Z

comment:3

Note to self (and others): we can use is_int to decide when we should test for equality. Test (once) the first time there's only one integer in the interval. If you have equality there, you're done. If not, you never will (or won't be able to prove it, anyway) and can carry on.

kini · 2012-06-22T19:10:45Z

comment:4

Apparently is_int is deprecated.

zimmermann6 · 2015-07-07T12:22:34Z

comment:9

I'm not sure if this should go to this ticket, but the following never returns:

sage: z
(11/9*sqrt(3)*sqrt(2) + 3)^(1/3) + 1/3/(11/9*sqrt(3)*sqrt(2) + 3)^(1/3) - 1
sage: floor(z)

Even floor(z, maximum_bits=53) loops infinitely.
Should I open a separate ticket?

sagetrac-ajagekar-akshay · 2016-02-11T20:15:53Z

Branch: u/ajagekar.akshay/Trac12121

sagetrac-ajagekar-akshay · 2016-02-11T20:17:44Z

New commits:

`6b75d32`	`Trac #12121: floor/ceil can be very slow at integral values`

sagetrac-ajagekar-akshay · 2016-02-11T20:17:44Z

Author: Akshay Ajagekar

sagetrac-ajagekar-akshay · 2016-02-11T20:17:44Z

Commit: 6b75d32

sagetrac-ajagekar-akshay · 2016-02-29T15:18:12Z

Changed commit from 6b75d32 to none

sagetrac-ajagekar-akshay · 2016-02-29T15:18:12Z

Changed author from Akshay Ajagekar to none

sagetrac-ajagekar-akshay · 2016-02-29T15:18:12Z

Changed branch from u/ajagekar.akshay/Trac12121 to none

videlec · 2016-03-09T18:53:08Z

comment:13

Replying to @zimmermann6:

I'm not sure if this should go to this ticket, but the following never returns:
sage: z
(11/9*sqrt(3)*sqrt(2) + 3)^(1/3) + 1/3/(11/9*sqrt(3)*sqrt(2) + 3)^(1/3) - 1
sage: floor(z)
Even floor(z, maximum_bits=53) loops infinitely.

Whereas the following actually works

sage: bool(z == 1)
True

Should I open a separate ticket?

I think that "very slow" includes "infinite amount of time". For me it is worth it to also fix this kind of endless loops in this ticket.

videlec · 2016-03-09T18:56:16Z

comment:14

@sagetrac-ajagekar-akshay: why did you remove your branch? The commit lacks some examples (as the one of comment:9).

sagetrac-git · 2016-09-17T13:51:29Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`0ef7b9e`	`Trac 12121: incremental rounding`
`60759c5`	`Trac 12121: use incremental_rounding in floor/ceil/round`
`e0396d8`	`Trac 12121: implement (broken) floor/ceil for expression`
`83c0257`	`Trac 12121: fix frac`

rwst · 2016-09-17T14:14:01Z

comment:71

You removed the symbolic property of frac() and you didn't give any justification for it.

rwst · 2016-09-17T14:24:16Z

comment:72

Please try to fix your code so previous frac doctests work.

sagetrac-git · 2016-09-17T16:19:27Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`5713b91`	`Trac 12121: fix frac`

sagetrac-git · 2016-09-17T16:19:27Z

Changed commit from 83c0257 to 5713b91

videlec · 2016-09-17T16:24:05Z

comment:74

Ralf, what do you call the "symbolic property" of frac?

On the other hand I have comments about the previous code of frac

it is the role of the function floor to call the method floor if needed. There is no need to redo it now and then
special casing int and float when the generic x - floor(x) does work is weird (not mentioning that this was not tested). In this case I would prefer that it behaves like floor and ceil (ie frac(float) returning float). The previous version returned Sage integer, why is that?

I let the frac(x + y) not be transformed in x + y - floor(x + y) in my new last commit. Please tell me if you like it better.

mezzarobba · 2016-09-17T17:04:42Z

comment:76

Replying to @videlec:

And is_trivial_zero could not be a solution anyway
sage: delta = (11/9*sqrt(3)*sqrt(2) + 3)^(1/3) + 1/3/(11/9*sqrt(3)*sqrt(2) + 3)^(1/3) - 2

Well, of course there will always be examples where the zero-test fails! Above I suggested to try both simplification followed by is_trivial_zero() and conversion to QQbar, this would take care of this example.

mezzarobba · 2016-09-17T17:07:11Z

comment:77

Replying to @videlec:

Even better

sage: (sin(1 - 10^(-100)) - sin(1)).is_zero()
True
age: bool(sin(1 - 10^(-100)) - sin(1) == 0)
True

Yes; I thought that was what the comment about is_zero() being unreliable was about.

videlec · 2016-09-17T19:03:59Z

comment:78

Replying to @mezzarobba:

Replying to @videlec:
Even better
sage: (sin(1 - 10^(-100)) - sin(1)).is_zero()
True
age: bool(sin(1 - 10^(-100)) - sin(1) == 0)
True
Yes; I thought that was what the comment about is_zero() being unreliable was about.

For me unreliable was "sometimes there are false negative". But it is not only that as there are "false positive". Meaning that

def is_zero(x):
    return randint(0, 1)

is equally good.

videlec · 2016-09-17T19:04:34Z

comment:79

If you have a reliable_is_zero_for_SR I will of course include it ;-)

rwst · 2016-09-18T06:18:29Z

comment:80

Replying to @videlec:

Ralf, what do you call the "symbolic property" of frac?

That it can be part of expressions. In the first version of your "fix frac" commit you unconditionally expanded frac(...) and forced the user to use hold=True to get the symbolic frac().

I let the frac(x + y) not be transformed in x + y - floor(x + y) in my new last commit. Please tell me if you like it better.

I do!

Marc:

Well, of course there will always be examples where the zero-test fails! Above I suggested to try both simplification followed by is_trivial_zero() and conversion to QQbar, this would take care of this example.

In #16397 I implemented this already in https://github.com/sagemath/sage-prod/blob/master/src/sage/symbolic/comparison.pyx#L291 to have some code usable for __nonzero__ later.

mezzarobba · 2016-09-20T07:50:31Z

Work Issues: test failures

mezzarobba · 2016-09-20T08:01:09Z

comment:82

A minor suggestion: perhaps make rounding() to _rounding()?

Also, I'm not sure how bad the existing implementation of floor() and friends is, but unless it is really terrible, I'd prefer to either avoid relying on is_zero() (even with known bugs marked as such) or to have is_zero() fixed before merging this ticket.

mezzarobba · 2016-09-20T08:18:48Z

comment:83

Replying to @rwst:

Well, of course there will always be examples where the zero-test fails! Above I suggested to try both simplification followed by is_trivial_zero() and conversion to QQbar, this would take care of this example.

In #16397 I implemented this already in https://github.com/sagemath/sage-prod/blob/master/src/sage/symbolic/comparison.pyx#L291 to have some code usable for __nonzero__ later.

I think I don't follow you, sorry. The code you link to looks like it is intended to sort expressions for printing etc., not to provide reliable mathematical results, isn't it? Besides (but this is starting to be off-topic for this ticket), I'm tempted to think that, for non-relational expressions at least, __nonzero__() should simply be the negation of is_trivial_zero(). As far as I understand, what __nonzero__() is intended to test is whether something is “empty”, “trivial”; it should be as fast as possible, and there is no expectation that it tries hard to prove the nullity of its argument. For a “mathematical” example, I'd find it entirely reasonable to have (x - x)*y + 1 ∈ SR[y] be considered a polynomial of degree one—and that's the kind of things __nonzero__() is for. I'm less certain about relational expressions: perhaps bool(expr == 0), unlike bool(expr), should keep trying hard to show that expr is zero.

mezzarobba · 2016-12-19T19:58:30Z

comment:85

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

floor/ceil can be very slow at integral values #12121

floor/ceil can be very slow at integral values #12121

sagetrac-dsm mannequin commented Dec 6, 2011

This comment has been minimized.

This comment has been minimized.

sagetrac-dsm mannequin commented Mar 3, 2012

kini commented Jun 22, 2012

zimmermann6 commented Jul 7, 2015

sagetrac-ajagekar-akshay mannequin commented Feb 11, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 11, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 11, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 11, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 29, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 29, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 29, 2016

videlec commented Mar 9, 2016

videlec commented Mar 9, 2016

sagetrac-git mannequin commented Sep 17, 2016

rwst commented Sep 17, 2016

rwst commented Sep 17, 2016

sagetrac-git mannequin commented Sep 17, 2016

sagetrac-git mannequin commented Sep 17, 2016

videlec commented Sep 17, 2016

mezzarobba commented Sep 17, 2016

mezzarobba commented Sep 17, 2016

videlec commented Sep 17, 2016

videlec commented Sep 17, 2016

rwst commented Sep 18, 2016

mezzarobba commented Sep 20, 2016

mezzarobba commented Sep 20, 2016

mezzarobba commented Sep 20, 2016

mezzarobba commented Dec 19, 2016

mezzarobba commented Sep 4, 2017

mezzarobba commented Sep 4, 2017

mezzarobba commented Sep 4, 2017

jdemeyer commented Sep 4, 2017

jdemeyer commented Nov 29, 2017

floor/ceil can be very slow at integral values #12121

floor/ceil can be very slow at integral values #12121

Comments

sagetrac-dsm mannequin commented Dec 6, 2011

This comment has been minimized.

This comment has been minimized.

sagetrac-dsm mannequin commented Mar 3, 2012

kini commented Jun 22, 2012

zimmermann6 commented Jul 7, 2015

sagetrac-ajagekar-akshay mannequin commented Feb 11, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 11, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 11, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 11, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 29, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 29, 2016

sagetrac-ajagekar-akshay mannequin commented Feb 29, 2016

videlec commented Mar 9, 2016

videlec commented Mar 9, 2016

sagetrac-git mannequin commented Sep 17, 2016

rwst commented Sep 17, 2016

rwst commented Sep 17, 2016

sagetrac-git mannequin commented Sep 17, 2016

sagetrac-git mannequin commented Sep 17, 2016

videlec commented Sep 17, 2016

mezzarobba commented Sep 17, 2016

mezzarobba commented Sep 17, 2016

videlec commented Sep 17, 2016

videlec commented Sep 17, 2016

rwst commented Sep 18, 2016

mezzarobba commented Sep 20, 2016

mezzarobba commented Sep 20, 2016

mezzarobba commented Sep 20, 2016

mezzarobba commented Dec 19, 2016

mezzarobba commented Sep 4, 2017

mezzarobba commented Sep 4, 2017

mezzarobba commented Sep 4, 2017

jdemeyer commented Sep 4, 2017

jdemeyer commented Nov 29, 2017