Repository navigation
create a numbits() method for int and long types #47689
Description
Activity
fredrikj commented
on Jul 24, 2008 fredrikjmannequinMannequinAuthorPython 3.0b2 (r30b2:65106, Jul 18 2008, 18:44:17) [MSC v.1500 32 bit (Intel)] on win32 Type "help", "copyright", "credits" or "license" for more information. >>> import math >>> math.frexp(10**100) (0.5714936956411375, 333) >>> math.frexp(10**1000) Traceback (most recent call last): File "<stdin>", line 1, in <module> OverflowError: Python int too large to convert to C double >>>
(Same behavior in Python 2.5.2, and presumably 2.6 although I haven't
checked the latter.)I think it should be easy to make frexp work for large integers by
calling PyLong_AsScaledDouble and adding the exponents. It would be
logical to fix this since math.log(n) already works for large integers.My reason for requesting this change is that math.frexp is the fastest
way I know of to accurately count the number of bits in a Python integer
(it is more robust than math.log(n,2) and makes it easy to verify that
the computed size is exact) and this is something I need to do a lot.Actually, it would be even more useful to have a standard function to
directly obtain the bit size of an integer. If I'm not mistaken,
PyLong_NumBits does precisely this, and would just have to be wrapped.
Aside from my own needs (which don't reflect those of the Python
community), there is at least one place in the standard library where
this would be useful: decimal.py contains an inefficient implementation
(_nbits) that could removed.loewis commented
on Jul 24, 2008 loewismannequinMannequinWould you like to work on a patch?
I prefer your idea to expose PyLong_Numbits(). IMO, frexp() is very
much a floating point concept and should probably remain that way.Another reason to leave frexp() untouched is that it is tightly
coupled to ldexp() as its inverse, for a lossless roundtrip:assert ldexp(*frexp(pi)) == pi
This relationship is bound to get mucked-up or confused if frexp starts
accepting large integers that are no exactly representable as floats
(i.e. 2**100+1).fredrikj commented
on Jul 24, 2008 fredrikjmannequinMannequinAuthorRaymond, yes, I think that a separate numbits function would better,
although exposing this functionality would not prevent also changing the
behavior of frexp. As I said, math.log already knows about long
integers, so handling long integers similarly in frexp would not be all
that unnatural. (On the other hand, it is true that math.sqrt, math.pow,
math.cos, etc could all theoretically be "fixed" to work with
larger-than-double input, and that slippery slope is probably better
avoided.)Good point about roundtripping, but the problem with that argument is
that frexp already accepts integers that cannot be represented exactly,
e.g.:>>> ldexp(*frexp(10**100)) == 10**100 False
Anyway, if there is support for exposing _PyLong_Numbits, should it be a
method or a function? (And if a function, placed where? Should it accept
floating-point input?)I'm attaching a patch (for the trunk) that adds a numbits method to the
int and long types. My C-fu is limited, and I've never hacked on Python
before, so the code is probably broken or otherwise bad in several ways
(but in that case you can tell me about it and I will learn something
:-). I did not bother to optimize the implementation for int, and the
tests may be redundant/incomplete/placed wrongly.A slight problem is that _PyLong_NumBits is restricted to a size_t, so
it raises an OverflowError on 32-bit platforms for some easily
physically representable numbers:>>> (1<<3*10**9).numbits() Traceback (most recent call last): File "<stdin>", line 1, in <module> OverflowError: long int too large to convert to int
This would need to be fixed somehow.
If numbits becomes a method, should it also be added to the Integral
ABC? GMPY's mpz type, by the way, defines a method numdigits(self,
base). This generalization would possibly be overkill, but it's worth
considering.If it's too late to add this method/function for 2.6 and 3.0, please
update the issue version field as appropriate.numbers.Integral is already way too fat of an API. Am -1 on expanding
it further. Recommend sticking with the simplest, least invasive,
least pervasive version of your request, a numbits() method for ints.FWIW, in Py2.6 you can already write:
def numbits(x): return len(bin(abs(x))) - 2
I'd also be interested in having _PyLong_NumBits exposed to Python in some
way or another. It's something I've needed many times before, and it's
used in the decimal module, for example.My favorite workaround uses hex instead of bin:
4*len('%x'%x) - correction_dictionary[first_hexdigit_of_x]
but this is still O(log x) rather than O(1).
With the patch, the following code causes a
non-keyboard-interruptible interpreter hang.>> from sys import maxint
>> (-maxint-1).numbits()[... interpreter hang ...]
The culprit is, of course, the statement
if (n < 0)
n = -n;in int_numbits: LONG_MIN is negated to itself (this may
even be undefined behaviour according to the C standards).The patch also needs documentation, and that documentation
should clearly spell out what happens for zero and for
negative numbers. It's not at all clear that everyone
will expect (0).numbits() to be 0, though I agree that this
is probably the most useful definition in practice.One could make a case for (0).numbits() raising ValueError:
for some algorithms, what one wants is an integer k such
that 2**(k-1) <= abs(n) < 2**k; when n == 0 no such
integer exists.Other than those two things, I think the patch looks fine.
One possible fix would be to compute the absolute value
of n as an unsigned long. I *think* the following is
portable and avoids any undefined behaviour coming
from signed arithmetic overflow.unsigned long absn;
if (n < 0)
absn = 1 + (unsigned long)(-1-n);
else
absn = (unsigned long)n;Might this work?
Perhaps it would also be worth changing the tests
in test_int from e.g.self.assertEqual((-a).numbits(), i+1)
to
self.assertEqual(int(-a).numbits(), i+1)
This would have caught the -LONG_MAX error.
fredrikj commented
on Aug 18, 2008 fredrikjmannequinMannequinAuthorWow, newbie error. Thanks for spotting!
In every case I can think of, I've wanted (0).numbits() to be 0. The
explanation in the docstring can probably be improved. What other
documentation is needed (where)?In every case I can think of, I've wanted (0).numbits() to be 0.
Me too, in most cases, though I've encountered the occasional case where
raising ValueError would be more appropriate and would catch some bugs
that might otherwise pass silently.So I agree that (0).numbits() should be 0, but I think there's enough
potential ambiguity that there should be a sentence in the documentation
making this explicit. Two of the most obvious (wrong) formulas for
numbits are: (1) numbits(n) = ceiling(log_2(n)), and (2) numbits(n) =
len(bin(n))-2, but neither of these formulas gives the right result for
0, or for negative numbers for that matter.The explanation in the docstring can probably be improved. What other
documentation is needed (where)?The docstring looked okay to me. There should be more comprehensive
ReST documentation in the Doc/ directory somewhere, probably in
Doc/library/stdtypes.rstTo add support to the proposal: there is currently yet another thread on
c.l.p on how to calculate numbits efficiently. The OP needs it for
prototyping cryptographic algorithms and found Python-level code slower
than he wanted.fredrikj commented
on Oct 14, 2008 fredrikjmannequinMannequinAuthorSome elaboration (that perhaps could be adapted into the documentation
or at least source comments).There are two primary uses for numbits, both of which justify
(0).numbits() == 0.The first is that for positive k, n = k.numbits() gives the minimum
width of a register that can hold k, where a register can hold the 2**n
integers 0, 1, ..., 2**n-1 (inclusive). This definition continues to
make sense for k = 0, n = 0 (the empty register holds the 2**0 = 1
values 0).In Python terms, one could say that self.numbits() "returns the smallest
n such that abs(self) is in range(2**n)". Perhaps this would make a
clearer docstring?Second, k.numbits() (plus/minus 1, or perhaps multiplied by a constant
factor) measures the number of steps required to solve a problem of size
k using various divide-and-conquer algorithms. The problem of size k = 0
is trivial and therefore requires (0).numbits() == 0 steps.In particular, if L is a sorted list, then len(L).numbits() exactly
gives the maximum number of comparisons required to find an insertion
point in L using binary search.Finally, the convention (-k).numbits() == k.numbits() is useful in
contexts where the number k itself is the input to a mathematical
function. For example, in a function for multiplying two integers, one
might want to choose a different algorithm depending on the sizes of the
inputs, and this choice is likely to be independent of signs (if not,
one probably needs to check signs anyway.)79 remaining items
Posted some doc cleanups in r67850 and r67851.
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
Other possible wording:
... so that
kis approximately1 + int(log(abs(x), 2)).... so that
kis approximately1 + int(log(abs(x), 2)).I guess that could work.
One other thing: the docs for the trunk seem to suggest that we should
be using trunc here, rather than int. I'm looking at:http://docs.python.org/dev/library/stdtypes.html#numeric-types-int-
float-long-complexand particularly the note (2), that says of int(x) and long(x):
"Deprecated since version 2.6: Instead, convert floats to long
explicitly with trunc()."zooko commented
on Jun 21, 2010 zookomannequinMannequinThere is a small mistake in the docs:
def bit_length(x): 'Number of bits necessary to represent self in binary.' s = bin(x) # binary representation: bin(-37) --> '-0b100101' s = s.lstrip('-0b') # remove leading zeros and minus sign return len(s) # len('100101') --> 6
is probably supposed to be:
def bit_length(x): 'Number of bits necessary to represent x in binary.' s = bin(x) # binary representation: bin(-37) --> '-0b100101' s = s.lstrip('-0b') # remove leading zeros and minus sign return len(s) # len('100101') --> 6
There is a small mistake in the docs:
Yes there was. Fixed in 82146.
Minor addendum to Mark's last message: in the near release version of 2.7 (rc2), note 2 in 5.4. "Numeric Types — int, float, long, complex" now starts "Conversion from floats using int() or long() truncates toward zero like the related function, math.trunc()" and no longer marks the usage of long as deprecated.
So there are two issues here:
- deprecation of int(my_float) and long(my_float)
- removal of long in 3.x
I'm not sure which Terry is referring to here.
On the first, I don't think use of int() with float arguments actually *is* deprecated in any meaningful way. At one point there was a push (related to PEP-3141) to deprecate truncating uses of int and introduce a new builtin trunk, but it never really took hold (and trunc ended up being relegated to the math module0; I certainly don't expect to see such deprecation happen within the lifetime of Python 3.x, so I don't think it would be appropriate to mention it in the 2.x docs.
On the second, it's possible that there should be a mention somewhere in the 2.x docs that long() no longer exists in 3.x, and that for almost all uses int() works just as well. A separate issue should probably be opened for this.
Aargh!
'a new builtin trunk' -> 'a new builtin trunc'Please open a new issue for the documentation problems, it's no more related to "numbits()" method and this issue is closed.
Whoops, sorry to create confusion when I was trying to put this issue to rest completely. Let me try better.
In his last message, Raymond said "Other possible wording:
... so thatkis approximately1 + int(log(abs(x), 2))."That is what the current 2.7rc2 doc says.
In response, Mark said "I guess that could work." but quoted footnote 2, which implied that 'int' should be changed to 'trunc' in the example above.
This implied to me that there was a lingering .numbits doc issue.
But footnote 2 is now changed, so I not longer think there is a doc issue, so I reported that, so no one else would think so.I hope this is the end of this.
Ah; sorry for misunderstanding. Thanks for the explanation, Terry!
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields: