Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 2011-12-05 15:41:51 -0600

DSM gravatar image

(1) This is almost certainly a case of len being overwritten. The fact that it worked when cut and pasted is a giveaway. 90% of the time when something that usually works stops working, this is the problem. (The other 10% often involves Maxima, at least for me -- I have very bad luck with it.)

(2) Yeah, that looks like a performance bug. Here's what's going on, and it's kind of quirky..

In some cases, log(n,b) is automatically simplified. If you use the (default) Sage Integers, for example:

sage: time log(4,2)
2
Time: CPU 0.00 s, Wall: 0.00 s
sage: time ceil(log(4,2))
2
Time: CPU 0.00 s, Wall: 0.00 s

so it's not surprising ceil is so fast. OTOH, if you do the same with Python ints, or you break the log apart, this doesn't happen:

sage: log(int(4),2)
log(4)/log(2)
sage: log(4)/log(2)
log(4)/log(2)

So in these cases Sage has to try harder. First it checks to see if this object has its own ceiling method, and it doesn't. So it builds a RealInterval object out of log(4)/log(2), and it turns out that this is about the worst thing it could do! It checks to see whether the lower and upper parts of the interval agree (so that it knows for certain what the ceiling is). But in this case, this is always going to look like:

sage: y = log(4)/log(2)
sage: rif = RealIntervalField(53)(y)
sage: rif
2.000000000000000?
sage: rif.endpoints()
(1.99999999999999, 2.00000000000001)

These two aren't equal, so it keeps increasing the precision (to 20000 bits) to see if it can prove that they are, but by construction it's never going to work. Finally Sage gives up and tries to simplify it, which succeeds:

sage: time (log(4)/log(2)).full_simplify()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s

This is a little perverse: the very cases that give Sage the most trouble are precisely the integer cases, which should be the easiest!

It's actually a little unclear what the right way to address the problem is in general. One way might be to call full_simplify earlier in the process to see if we can short-circuit the more common cases (and looking at integers is definitely a common enough use case to optimize.)

(1) This is almost certainly a case of len being accidentally overwritten. The fact that it worked when cut and pasted is a giveaway. 90% of the time when something that usually works stops working, this is the problem. (The other 10% often involves Maxima, at least for me -- I have very bad luck with it.)

If you could show a worksheet that demonstrates that it wasn't this, I'd be happy to have a look.

(2) Yeah, that looks like a performance bug. Here's what's going on, and it's kind of quirky..

In some cases, log(n,b) is automatically simplified. If you use the (default) Sage Integers, for example:

sage: time log(4,2)
2
Time: CPU 0.00 s, Wall: 0.00 s
sage: time ceil(log(4,2))
2
Time: CPU 0.00 s, Wall: 0.00 s

so it's not surprising ceil is so fast. OTOH, if you do the same with Python ints, or you break the log apart, this doesn't happen:

sage: log(int(4),2)
log(4)/log(2)
sage: log(4)/log(2)
log(4)/log(2)

So in these cases Sage has to try harder. First it checks to see if this object has its own ceiling method, and it doesn't. So it builds a RealInterval object out of log(4)/log(2), and it turns out that this is about the worst thing it could do! It checks to see whether the lower and upper parts of the interval agree (so that it knows for certain what the ceiling is). But in this case, this is always going to look like:

sage: y = log(4)/log(2)
sage: rif = RealIntervalField(53)(y)
sage: rif
2.000000000000000?
sage: rif.endpoints()
(1.99999999999999, 2.00000000000001)

These two aren't equal, so it keeps increasing the precision (to 20000 bits) to see if it can prove that they are, but by construction it's never going to work. Finally Sage gives up and tries to simplify it, which succeeds:

sage: time (log(4)/log(2)).full_simplify()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s

This is a little perverse: the very cases that give Sage the most trouble are precisely the integer cases, which should be the easiest!

It's actually a little unclear what the right way to address the problem is in general. One way might be to call full_simplify earlier in the process to see if we can short-circuit the more common cases (and looking at integers is definitely a common enough use case to optimize.)

(BTW, one of the things that I like most about Sage is that I don't have to wonder what it's doing: I simply typed "ceil??" and looked at the actual algorithm, and it became pretty clear pretty quickly what was happening. Warning: it can become addictive. :^)

(1) This is almost certainly a case of len being accidentally overwritten. The fact that it worked when cut and pasted is a giveaway. 90% of the time when something that usually works stops working, this is the problem. (The other 10% often involves Maxima, at least for me -- I have very bad luck with it.)

If you could show a worksheet that demonstrates that it wasn't this, I'd be happy to have a look.

(2) Yeah, that looks like a performance bug. Here's what's going on, and it's kind of quirky..

In some cases, log(n,b) is automatically simplified. If you use the (default) Sage Integers, for example:

sage: time log(4,2)
2
Time: CPU 0.00 s, Wall: 0.00 s
sage: time ceil(log(4,2))
2
Time: CPU 0.00 s, Wall: 0.00 s

so it's not surprising ceil is so fast. OTOH, if you do the same with Python ints, ints (such as the bare "range" command produces) or you break the log apart, this doesn't happen:

sage: log(int(4),2)
log(4)/log(2)
sage: log(4)/log(2)
log(4)/log(2)

So in these cases Sage has to try harder. First it checks to see if this object has its own ceiling method, and it doesn't. So it builds a RealInterval object out of log(4)/log(2), and it turns out that this is about the worst thing it could do! It checks to see whether the lower and upper parts of the interval agree (so that it knows for certain what the ceiling is). But in this case, this is always going to look like:

sage: y = log(4)/log(2)
sage: rif = RealIntervalField(53)(y)
sage: rif
2.000000000000000?
sage: rif.endpoints()
(1.99999999999999, 2.00000000000001)

These two aren't equal, so it keeps increasing the precision (to 20000 bits) to see if it can prove that they are, but by construction it's never going to work. Finally Sage gives up and tries to simplify it, which succeeds:

sage: time (log(4)/log(2)).full_simplify()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s

This is a little perverse: the very cases that give Sage the most trouble are precisely the integer cases, which should be the easiest!

It's actually a little unclear what the right way to address the problem is in general. One way might be to call full_simplify earlier in the process to see if we can short-circuit the more common cases (and looking at integers is definitely a common enough use case to optimize.)

(BTW, one of the things that I like most about Sage is that I don't have to wonder what it's doing: I simply typed "ceil??" and looked at the actual algorithm, and it became pretty clear pretty quickly what was happening. Warning: it can become addictive. :^)

(1) This is almost certainly a case of len being accidentally overwritten. The fact that it worked when cut and pasted is a giveaway. 90% of the time when something that usually works stops working, this is the problem. (The other 10% often involves Maxima, at least for me -- I have very bad luck with it.)

If you could show a worksheet that demonstrates that it wasn't this, I'd be happy to have a look.

(2) Yeah, that looks like a performance bug. Here's what's going on, and it's kind of quirky..

In some cases, log(n,b) is automatically simplified. If you use the (default) Sage Integers, for example:

sage: time log(4,2)
2
Time: CPU 0.00 s, Wall: 0.00 s
sage: time ceil(log(4,2))
2
Time: CPU 0.00 s, Wall: 0.00 s

so it's not surprising ceil is so fast. OTOH, if you do the same with Python ints (such as the bare "range" command produces) or you break the log apart, this doesn't happen:

sage: log(int(4),2)
log(4)/log(2)
sage: log(4)/log(2)
log(4)/log(2)

So in these cases Sage has to try harder. First it checks to see if this object has its own ceiling method, and it doesn't. So it builds a RealInterval object out of log(4)/log(2), and it turns out that this is about the worst thing it could do! It checks to see whether the lower and upper parts of the interval agree (so that it knows for certain what the ceiling is). But in this case, this is always going to look like:

sage: y = log(4)/log(2)
sage: rif = RealIntervalField(53)(y)
sage: rif
2.000000000000000?
sage: rif.endpoints()
(1.99999999999999, 2.00000000000001)

These two bounds aren't equal, so it keeps increasing the precision (to 20000 bits) to see if it can prove that they are, but by construction it's never going to work. Finally Sage gives up and tries to simplify it, which succeeds:

sage: time (log(4)/log(2)).full_simplify()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s

This is a little perverse: the very cases that give Sage the most trouble are precisely the integer cases, which should be the easiest!

It's actually a little unclear what the right way to address the problem is in general. One way might be to call full_simplify earlier in the process to see if we can short-circuit the more common cases (and looking at integers is definitely a common enough use case to optimize.)

(BTW, one of the things that I like most about Sage is that I don't have to wonder what it's doing: I simply typed "ceil??" and looked at the actual algorithm, and it became pretty clear pretty quickly what was happening. Warning: it can become addictive. :^)

(1) This is almost certainly a case of len being accidentally overwritten. The fact that it worked when cut and pasted is a giveaway. 90% of the time when something that usually works stops working, this is the problem. (The other 10% often involves Maxima, at least for me -- I have very bad luck with it.)

If you could show a worksheet that demonstrates that it wasn't this, I'd be happy to have a look.

(2) Yeah, that looks like a performance bug. Here's what's going on, and it's kind of quirky..

In some cases, log(n,b) is automatically simplified. If you use the (default) Sage Integers, for example:

sage: time log(4,2)
2
Time: CPU 0.00 s, Wall: 0.00 s
sage: time ceil(log(4,2))
2
Time: CPU 0.00 s, Wall: 0.00 s

so it's not surprising ceil is so fast. OTOH, if you do the same with Python ints (such as the bare "range" command produces) or you break the log apart, this doesn't happen:

sage: log(int(4),2)
log(4)/log(2)
sage: log(4)/log(2)
log(4)/log(2)

So in these cases Sage has to try harder. First it checks to see if this object has its own ceiling method, and it doesn't. So it builds a RealInterval object out of log(4)/log(2), and it turns out that this is about the worst thing it could do! It checks to see whether the lower and upper parts of the interval agree (so that it knows for certain what the ceiling is). But in this case, this is always going to look like:

sage: y = log(4)/log(2)
sage: rif = RealIntervalField(53)(y)
sage: rif
2.000000000000000?
sage: rif.endpoints()
(1.99999999999999, 2.00000000000001)

These two bounds aren't equal, so it keeps increasing the precision (to 20000 bits) to see if it can prove that they are, but by construction it's never going to work. Finally Sage gives up and tries to simplify it, which succeeds:

sage: time (log(4)/log(2)).full_simplify()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s

This is a little perverse: the very cases that give Sage the most trouble are precisely the integer cases, which should be the easiest!

It's actually a little unclear what the right way to address the problem is in general. One way might be to call full_simplify earlier in the process to see if we can short-circuit the more common cases (and looking at integers is definitely a common enough use case to optimize.)optimize.) Alternatively, we could try bool(x == round(x)), which seems a little faster. I'd probably try one or two interval rounds first, to make sure we're not increasing the burden too much for noninteger cases.

(BTW, one of the things that I like most about Sage is that I don't have to wonder what it's doing: I simply typed "ceil??" and looked at the actual algorithm, and it became pretty clear pretty quickly what was happening. Warning: it can become addictive. :^)

(1) This is almost certainly a case of len being accidentally overwritten. The fact that it worked when cut and pasted is a giveaway. 90% of the time when something that usually works stops working, this is the problem. (The other 10% often involves Maxima, at least for me -- I have very bad luck with it.)

If you could show a worksheet that demonstrates that it wasn't this, I'd be happy to have a look.

(2) Yeah, that looks like a performance bug. Here's what's going on, and it's kind of quirky..

In some cases, log(n,b) is automatically simplified. If you use the (default) Sage Integers, for example:

sage: time log(4,2)
2
Time: CPU 0.00 s, Wall: 0.00 s
sage: time ceil(log(4,2))
2
Time: CPU 0.00 s, Wall: 0.00 s

so it's not surprising ceil is so fast. OTOH, if you do the same with Python ints (such as the bare "range" command produces) or you break the log apart, this doesn't happen:

sage: log(int(4),2)
log(4)/log(2)
sage: log(4)/log(2)
log(4)/log(2)

So in these cases Sage has to try harder. First it checks to see if this object has its own ceiling method, and it doesn't. So it builds a RealInterval object out of log(4)/log(2), and it turns out that this is about the worst thing it could do! It checks to see whether the lower and upper parts of the interval agree [on the ceiling, I mean] (so that it knows for certain what the ceiling is). But in this case, this is always going to look like:

sage: y = log(4)/log(2)
sage: rif = RealIntervalField(53)(y)
sage: rif
2.000000000000000?
sage: rif.endpoints()
(1.99999999999999, 2.00000000000001)

These two bounds [have ceilings which] aren't equal, so it keeps increasing the precision (to 20000 bits) to see if it can prove that they are, but by construction it's never going to work. Finally Sage gives up and tries to simplify it, which succeeds:

sage: time (log(4)/log(2)).full_simplify()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s

This is a little perverse: the very cases that give Sage the most trouble are precisely the integer cases, which should be the easiest!

It's actually a little unclear what the right way to address the problem is in general. One way might be to call full_simplify earlier in the process to see if we can short-circuit the more common cases (and looking at integers is definitely a common enough use case to optimize.) Alternatively, we could try bool(x == round(x)), which seems a little faster. I'd probably try one or two interval rounds first, to make sure we're not increasing the burden too much for noninteger cases.

(BTW, one of the things that I like most about Sage is that I don't have to wonder what it's doing: I simply typed "ceil??" and looked at the actual algorithm, and it became pretty clear pretty quickly what was happening. Warning: it can become addictive. :^)