len(list) & ceil(log(4,2)) bugs

edit

(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 ... (more)