About the footnote:
floor(log(n, 2)) is poor code. This is not supposed to be a dramatic
statement, just a statement of fact. Its correctness is dependent on
minute details of floating point. It is poor code in exactly the same way
that "while x < 1.0: x += 0.1" is poor code---behaviour in boundary cases
is almost entirely unpredictable.
If 1 + floor(log(n, 2)) happens to give the correct result in the common
corner case where x is a power of 2, then that's due to little more than
sheer luck. Correct rounding by itself is nowhere near enough to
guarantee correct results.
In the case of IEEE 754 doubles, a large part of the luck is that the
closest double to log(2) just happens to be *smaller* than log(2) itself,
so that the implicit division by log(2) in log(x, 2) tends to give a
larger result than the true one; if things were the other way around, the
formula above would likely fail for many (even small) n.
So I don't like seeing this poor code in the Python reference manual, for
two reasons: (1) it might get propagated to real world code, and (2) its
presence in the docs reflects poorly on the numerical competence of the
Python developers.
IMO, either: (1) the warning needs to be stronger, or (2) the formulation
should be given purely mathematically, without any explicit code, or (3)
the formula should be left out of the docs altogether.
Mark |