classification
Title: create a numbits() method for int and long types
Type: enhancement Stage: commit review
Components: Interpreter Core Versions: Python 3.1, Python 2.7
process
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: fredrikj, haypo, mark.dickinson, orsenthil, pitrou, rhettinger, terry.reedy, zooko
Priority: normal Keywords: needs review, patch

Created on 2008-07-24 17:20 by fredrikj, last changed 2010-06-23 07:53 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
numbits.diff fredrikj, 2008-07-24 23:12
numbits-6.patch haypo, 2008-12-11 23:05
bit_length_pybench.patch mark.dickinson, 2008-12-13 15:06 Temporary patch to pybench, for comparisons.
bit_length10.patch mark.dickinson, 2008-12-16 20:39
bit_length11.patch mark.dickinson, 2008-12-16 20:45
Messages (95)
msg70216 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-07-24 17:20
Python 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.
msg70221 - (view) Author: Martin v. Löwis (loewis) * (Python committer) Date: 2008-07-24 19:41
Would you like to work on a patch?
msg70223 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-07-24 19:47
I prefer your idea to expose PyLong_Numbits().  IMO, frexp() is very 
much a floating point concept and should probably remain that way.
msg70228 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-07-24 21:39
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).
msg70230 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-07-24 23:12
Raymond, 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.
msg70231 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-07-25 00:11
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
msg70312 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-07-27 06:29
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).
msg71115 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-08-14 09:22
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.
msg71116 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-08-14 09:47
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.
msg71376 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-08-18 20:41
Wow, 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)?
msg71384 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-08-18 21:28
> 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.rst
msg74383 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2008-10-06 17:41
To 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.
msg74725 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-10-14 10:38
Some 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.)
msg74729 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-10-14 11:07
I changed the title since I agree that numbits() with long integer is 
not related to floats.
msg74749 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-10-14 15:07
Accidentally removed the following message from Victor Stinner;  
apologies.  (Time to turn off tap-to-click on my trackpad, methinks.)

> See also issue #3724 which proposes to support long integers for 
> math.log2().

One other note:  in Fredrik's patch there's commented out code for a 
numbits *property* (rather than a method).  Is there any good reason to 
make this a property?  I don't have a good feeling for when something 
should be a method and when it should be a property, but in this case 
I'd be inclined to leave numbits as a method.

Are there general guidelines for making things properties?
msg74750 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-10-14 15:13
> Accidentally removed the following message from Victor Stinner

No problem.

> Is there any good reason to make this a property?

Since numbits() cost is O(n) with n: number of digits. I prefer a 
method than a property because, IMHO, reading a property should be 
O(1) (*read* an attribute is different than *compute* a value).
msg74751 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-10-14 15:38
> One other note:  in Fredrik's patch there's commented out code for a 
> numbits *property* (rather than a method).  Is there any good reason to 
> make this a property?

Aesthetically, I think numbits as a function would make more sense.
(Maybe if the hypothetical imath module comes along...)

> Since numbits() cost is O(n) with n: number of digits. I prefer a 
> method than a property because, IMHO, reading a property should be 
> O(1) (*read* an attribute is different than *compute* a value).

Unless I missed something, numbits() is O(1). Only the topmost word in a
number needs to be examined.

> reading a property should be O(1) (*read* an attribute is different
> than *compute* a value).

O(1) is necessary but not sufficient. My sense is that an attribute
should access an existing "part" of an object while an operation that
involves creating a "new" object should be a method. Compare
complex.real/.imag and complex.conjugate().
msg74754 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-10-14 16:20
> Unless I missed something, numbits() is O(1).

Ooops, you're right. I looked quickly at the patch and I 
read "while(n)" but n is a digit, not the number of digits! So it's 
very quick to compute number of bits.
msg74755 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2008-10-14 17:09
I consider .numbits to be an internal property of ints and would prefer
it accessed that way.  To me, this sort of thing is what property() is for.

Guido has said that the nuisance of tacking on otherwise unnecessary
empty parens is a warning to the user that getting the answer might take
a long time.  

Another tack is to notice that numbits is the length of the bit sequence
representation of an int (excepting 0) and give ints a .__len__ method
;-).  I would not expect that suggestion to fly very far, though.
msg74756 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-10-14 17:19
> Another tack is to notice that numbits is the length of the bit sequence
> representation of an int (excepting 0) and give ints a .__len__ method
> ;-).  I would not expect that suggestion to fly very far, though.

FWIW, I'm one of the people who'd additionally find indexing and slicing
of the bits of integers very useful. It's not going to happen, though!
msg74757 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-10-14 17:31
A property /looks/ like an attribute and an user might try to change 
its value: "x=1; x.numbits = 2" (gives 3 or 4 ? :-))
msg74759 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-10-14 18:03
Properties can be made read-only.  Also, there is a good precedent: 
c=4+5j; print c.real
msg74766 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-10-14 19:29
One more minor deficiency in the patch: it gives incorrect results for 
very large integers.  For example, on a 32-bit build of the trunk:

>>> x = 1 << 2**31-1
>>> x <<= 2**31-1
>>> x.numbits()  # expect 4294967295
4294967295L
>>> x <<= 2
>>> x.numbits()  # expect 4294967297
4294967295L

It would be nicer if the OverflowError from _PyLong_NumBits were 
propagated, so that the second case raises OverflowError instead of giving 
an incorrect result.

Alternatively, in case of OverflowError one could recompute numbits 
correctly, without overflow, by using Python longs instead of a C size_t;  
but this would mean adding little-used, and probably little-tested, extra 
code for what must be a very rare special case.  Probably not worth it.
msg75498 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-04 18:15
> It would be nicer if the OverflowError from _PyLong_NumBits 
> were propagated, so that the second case raises OverflowError
> instead of giving an incorrect result

Why not, but I prefer your second proposition: return a long integer. 
Attached patch implements this solution.

>>> x=1<<(2**31-1)
>>> n=x.numbits(); n, n.numbits()
(2147483648L, 32L)
>>> x<<=(2**31-1)
>>> n=x.numbits(); n, n.numbits()
(4294967295L, 32L)
>>> x<<=1
>>> n=x.numbits(); n, n.numbits()
(4294967296L, 33L) # yeah!

With my patch, there are two functions:
 - _PyLong_NumBits(long)->size_t: may overflow
 - long_numbits(long)->long: don't raise overflow error, but may raise 
other errors like memory error
msg75751 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-11-11 17:15
Hi, Victor!  Thanks for the updated patch.

Your patch still hangs on:

>>> from sys import maxint
>>> (-maxint-1).numbits()

on my 32-bit machine.
msg75753 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-11 18:15
> (-maxint-1).numbits() hangs

Ooops, nice catch! It was an integer overflow, already present in 
fredrikj's original patch. The new patch fixes this bug but also 
included a documentation patch ;-)
msg75767 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-11-11 23:00
The latest patch from Victor looks good.  A few comments:

(1) the number of bits should be computed first directly using C 
arithmetic, and only recomputed using PyLong arithmetic if the C 
computations overflow.  For one thing, overflow is going to be very rare 
in practice;  for another, in the sort of applications that use 
.numbits(), speed of numbits() is often critical.

(2) Just as a matter of style, I think "if (x == NULL)" is preferable
to "if (!x)".  At any rate, the former style is much more common in
Python source.

(3) the reference counting all looks good.

(4) I quite like the idea of having numbits be a property rather than a 
method---might still be worth considering?
msg75770 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-11-12 00:02
In stdtypes.rst, x.numbits should be listed in the table under
"Bit-string Operations on Integer Types" and not in the table of
operations supported by all numeric types.

> (1) the number of bits should be computed first directly using C 
> arithmetic, and only recomputed using PyLong arithmetic if the C 
> computations overflow.

+1

> (4) I quite like the idea of having numbits be a property rather than a 
> method---might still be worth considering?

I'm not against.
msg75771 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-12 00:33
[Mark Dickinson]
> (1) the number of bits should be computed first directly using ...

_PyLong_NumBits() : done. But the result type is always long.

> (2) Just as a matter of style, I think "if (x == NULL)" is preferable

done

> (4) I quite like the idea of having numbits be a property rather than a
> method---might still be worth considering?

I agree, so in the new patch, numbits is now a property.

[Fredrik Johansson]
> In stdtypes.rst, x.numbits should be listed in the table under
> "Bit-string Operations on Integer Types"

done

--

10
>>> x=1023L; x.numbits
10L
>>> x=2**(2**10); n=x.numbits; n, n.numbits
(1025L, 11L)
msg77221 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-07 12:35
I plan to change my patch to come back to a method (x.numbits()) 
because other integer implementations like Decimal may be slower.
msg77407 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-09 12:28
New version of my patch using a method instead of a property.
msg77630 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-11 21:12
Victor,

Thanks for the updated patch.

I think you need to do a PyErr_Clear after the 'return PyLong_FromSize_t' line.

To be safe, you should probably check the exception type first, and either 
do a PyErr_Clear and continue if it's an OverflowError, or just return 
NULL if it's some other exception.  It's true that _PyLong_NumBits can't 
raise anything other than OverflowError at the moment, but you never know 
when that might change. :)

I'm also getting a 'malformed table' warning when building the 
documentation.
msg77632 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-11 21:22
Alternatively, you could just ignore _PyLong_NumBits entirely and put the 
whole calculation into long_numbits.  You're already halfway there with 
the calculation of msd_bits anyway, and I suspect the code will look 
cleaner (and run faster) that way.
msg77636 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-11 23:05
Oops, you're right Mark: PyErr_Clear() is needed! New patch:
 - don't catch error different than PyExc_OverflowError in 
long_numbits()
 - clear error in long_numbits()
 - fix doc indentation

About the indentation: i'm using >>svndiff='svn 
diff --diff-cmd="/usr/bin/diff" -x "-ub"'<< instead of svn diff 
because my editor removes trailing spaces.

I prefer to keep the "fast path" (use _PyLong_NumBits) as *you* 
proposed in another message: Message75767.
msg77675 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-12 16:50
Victor,

This looks good.  If it's okay with you, I'll work on the documentation 
a little (we need an entry in whatsnew, and a description of the 
semantics of numbits for 0 and negative integers.) Then I think this 
will be ready.

> I prefer to keep the "fast path" (use _PyLong_NumBits) as *you* 
> proposed in another message: Message75767.

Sorry---I wasn't clear.  I wasn't suggesting getting rid of the fast 
path---I was suggesting inlining the _PyLong_NumBits code in 
long_numbits (leaving _PyLong_NumBits itself intact, of course).  It 
would eliminate all the messing around with exceptions.  But I think the 
current code is fine.
msg77676 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-12 16:56
> I'll work on the documentation

Ok, cool.

> a description of the semantics of numbits for 0 and negative 
integers

About the negative integer: the documentation should be "number of 
bits of the *absolute value* of x" and "by convention, 0.numbits() is 
0". But you're right, the documentation is not clear.
msg77677 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-12 17:26
Here's Victor's patch, but with extra documentation.  No code has been 
changed.

Two more questions about the code, Victor;  specifically about 
long_numbits:

- why do you use PyLong_FromSize_t rather than PyInt_FromSize_t?

- isn't the if (ndigits == 0) check redundant?
msg77678 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-12 17:26
Oops. Here's the patch.
msg77681 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-12 18:03
> - why do you use PyLong_FromSize_t rather than PyInt_FromSize_t?

I choosed to use consistent result type. But now I would prefer int :-) I see 
that PyInt_FromSize_t() returns a long if the value doesn't fit in an int. So 
it's correct.

> - isn't the if (ndigits == 0) check redundant?

I'm paranoid: if _PyLong_NumBits() fails but the number is zero, the function 
may crash. But this case is impossible: _PyLong_NumBits() can only fails with 
an OverflowError.

Can you fix these two issues (use PyInt_FromSize_t and remove the if)?
msg77682 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-12 18:10
> I choosed to use consistent result type. But now I would prefer int :-) I see 
> that PyInt_FromSize_t() returns a long if the value doesn't fit in an int. So 
> it's correct.

Cool.  I think int is better, simply because the result is almost always going to fit 
into an int in practice, and because calculations with ints are faster.

> I'm paranoid

Yeah, me too.  I removed the check, but also changed the assert to check that
Py_SIZE is nonzero.

> Can you fix these two issues (use PyInt_FromSize_t and remove the if)?

Done.
msg77685 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-12 19:50
As far as I'm concerned, this patch is ready to be applied.

Raymond, care to give a second opinion?
msg77689 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-12 22:47
The code looks fine.

For speed, you could insert the following just before the while-loop:

    while (n >= 256) {
        n >>= 8;
        result += 8;
    }

Am not sure the "numbits" is the right-name.  Is there precedent in
other languages or texts on bit-twiddling techniques?  For
numbits(0b0100), I could forsee people predicting a result of 4, 3, or 1
depending on their world-view of what numbits might mean.  Personally, I
tend to think in term of high-bit location or somesuch.
msg77714 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-13 04:23
FWIW, here is a link to faster algorithms:

  http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLog
msg77721 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 09:26
About the name:

Java's Bignum has a 'significantBits' method, which apparently returns 
the position of the MSB (i.e., numbits - 1).

GMP has mpz_sizeinbase;  mpz_sizeinbase(n, 2) is almost the same as 
numbits, except that mpz_sizeinbase(0, 2) is 1, not 0.

Mathematica has BitLength.  I quite like this.

Googling for 'ilog2' returns a good few relevant hits; again, this is 
really numbits - 1, not numbits.

How about n.bitlength?
msg77722 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-13 09:57
Perhaps n.bit_length() with an underscore.  The name sounds good to my
ear and sensibilities.
msg77723 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 10:35
> Perhaps n.bit_length() with an underscore.

I thought I recalled Guido having a preference for float.fromhex over 
float.from_hex when that got implemented.  But either spelling seems good 
to me.
msg77724 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 10:43
> I thought I recalled Guido having a preference for float.fromhex over 

Can't find anything to back this up.  It looks like I'm just making this 
up.
msg77725 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-13 10:53
It was probably true.  The issue is how well the words self-separate
visually and whether an underscore would create a detrimental mental
pause.  So fromkeys() and fromhex() read fine and would feel awkward
with an underscore.  But bitlength causes me a mental double-take when
my mind searches for the word separation.  It that case, PEP 8 suggests
that an underscore be added for clarity.  This is probably why
Mathematica chose BitLength in titlecase instead of Bitlength.  Logic
aside, bit_length() just looks and feels better to me.

Did you look at the O(lg n) algorithm yet?  Any thoughts?
msg77726 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 11:19
> Did you look at the O(lg n) algorithm yet?  Any thoughts?

So there are two places this could be applied:  the int_numbits method 
and _PyLong_NumBits.  I'd be quite surprised if this offered any 
noticeable speedup in either case.  Might be worth a try, though---I'll 
see if I can get some timings.

For int_numbits, it would have to be implemented in a way that works for 
32-bit and 64-bit C longs.  And if it also just happens to work for 
other sizes, that would be good, too.  I'd probably try something like:

while (v > 0xFFFFFFFF) {
     bitcount += 32;
     v >>= 32;
}

before doing a 32-bit bitcount on what's left.  On a 32-bit machine,
the whole while loop should just be optimized away to nothing.  

Similarly, in _PyLong_NumBits it would be good if it could be 
implemented in a way that doesn't have to change if/when PyLong_SHIFT is 
changed.

I prefer the second variant given (the non-branching version).
msg77728 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 13:10
Three files:
(1) bit_length7.patch just does the numbits->bit_length renaming;
    otherwise it's the same as numbits-6b.patch.
(2) bit_length7_opt.patch uses the fast bitcount method that Raymond
    pointed out.
(3) bit_length_pybench.patch adds a test for bit_length to pybench.

On my system (OS X 10.5.5/Core 2 Duo), on a 32-bit non-debug build of 
the trunk, pybench is showing me a 4-5% speedup for the optimized 
version.

(I also tried a version that uses gcc's __builtin_clzl function;  this 
was around 10% faster than the basic version, but of course it's not 
portable.)
msg77730 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-13 13:57
Well, I don't think bit_length() warrants a specific test which will
slow down the whole pybench suite. pybench tracks interpreter speed for
common and generally useful operations, while I think bit_length() is
only a niche method.
msg77738 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 14:54
> Well, I don't think bit_length() warrants a specific test which will
> slow down the whole pybench suite.

Me neither.  It's a temporary patch to pybench, to establish whether it's 
worth applying optimizations to bit_length.  I didn't intend that it 
should be applied to the trunk.
msg77741 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 15:02
Slightly improved optimized version.
msg77742 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 15:06
Added another test to pybench;  it makes sense to consider cases where the 
input n is uniformly distributed in [0, 2**31) as well as cases where the 
output n.bit_length() is uniformly distributed in [0, 32).
msg77747 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 15:34
I think I've found the happy medium:

bit_length7_opt2.patch achieves nearly the same performance gains as 
bit_length7_opt.patch (around 7% for uniformly-distributed inputs, 3.5% 
for uniformly-distributed outputs), but is much more straightforward and 
readable.  It's pretty much what Raymond suggested in the first place, 
plus a table lookup.
msg77750 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-13 16:04
If there's not a hurry, would like to review this a bit more when I get
back early next week.
msg77754 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-12-13 16:43
FYI, Brent & Zimmermann call this function nbits(n) in "Modern Computer
Arithmetic": http://www.loria.fr/~zimmerma/mca/pub226.html

I don't really care much about the name though.

In the documentation, should "same value as ``x.bit_length``" not be
"same value as ``x.bit_length()``"?
msg77756 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-13 17:50
> In the documentation, should "same value as ``x.bit_length``" not be
> "same value as ``x.bit_length()``"?

Yes, of course.  Thanks!
msg77782 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-14 10:24
Update both patches:

(1) change PyLong_FromLong(ndigits-1) to PyLong_FromSsize_t(ndigits-1) in 
both patches (it's possible to have a 32-bit long and 64-bit Py_ssize_t), and

(2) in the optimized patch, add the table lookup optimization for 
long_bit_length.
msg77897 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 12:41
In the whatsnew docs, add two lines showing the binary representation of
37.  That will provide clarification as to why the answer is six:

      >>> n = 37
+     >>> bin(37)
+     '0b100101'
      >>> n.bit_length()
      6

Also, the main entry in the docs should be built-out just a bit.  I like
that the current entry provides a precise mathematical spec that is
easily validated, but it should also mention the more intuitive notion
of the "number of bits in a number's binary representation excluding
leading zeros (for example the decimal number 37, which is 0b100101 in
binary, has six binary digits)."

Possibly, the BitLengthTables can be dropped in favor of the old
shift-one, add-one code (to be inserted right after the shift-eight,
add-eight code).  The two tables consume a lot of memory and the
relevant entry is not likely to be in cache when needed (cache misses
are very slow).  It is simpler and possibly faster to skip the table
lookup unless the table is made much smaller.  Plus, it makes the code a
bit more maintainable and self-evidently correct (not requiring as
extensive test coverage to validate the whole table).

My own crack at optimization looks like this:

        static const char BitLengthTable[32] =
            {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
             5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5};
        while (n >= 32) { r += 5;   n >>= 5; }
        r += (long)(BitLengthTable[n]);

If you don't adopt mine, at least consider making a table of chars
instead of longs (this will give a 4:1 or 8:1 table compression,
reducing the memory footprint and increasing the likelihood of a cache hit).

I would feel better about the test code if it also directly validated
the definitions in docs and thoroughly exercised the tables:

for x in range(-65000, 65000):
    k = x.numbits
    if x > 0:
         assert 2 ** (k-1) <= x < 2**k
         assert k == 1 + math.floor(math.log(x) / math.log(2))
    elif x == 0:
         assert k == 0
    else:
         assert k == (-x).numbits()



Other than that, I'm basically happy with the patch.
msg77898 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 12:47
Oops, forgot one part of the doc definition in the proposed additional
tests:

for x in range(-65000, 65000):
    k = x.numbits()
    assert k == len(bin(x).lstrip('-0b'))
    if x > 0:
        assert 2 ** (k-1) <= x < 2**k
        assert k == 1 + math.floor(math.log(x) / math.log(2))
    elif x == 0:
        assert k == 0
    else:
        assert k == (-x).numbits()
msg77905 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-16 13:56
x.numbits() is:
  math.ceil(math.log(abs(x)) / math.log(2)) if x != 0
  0 otherwise

and not 1 + math.floor(math.log(x) / math.log(2))

(16).numbits() is 4, not 5.
msg77907 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-16 13:57
Le mardi 16 décembre 2008 à 13:56 +0000, STINNER Victor a écrit :
> (16).numbits() is 4, not 5.

Well, I do hope (16).numbits() returns 5...
msg77908 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-16 14:00
Ooops, you're right! (15).numbits() -> 4 and (16).numbits() -> 5. I'm 
tired.
msg77909 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 14:04
One other thought on the docs.  I would like to continue the style of
supplying pure python equivalents to help precisely explain what a
function does (see the itertools docs for an example, also a few
builtins are explained that way and namedtuples too):

+  Equivalent to::
+
+      def numbits(x):
+          'Number of binary bits necessary to represent the integer n'
+          return len(bin(x).lstrip('-0b'))
msg77911 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-12-16 14:11
When did the name change back to numbits? Anyway, I think this reference
implementation is better:

def numbits(x):
    x = abs(x)
    n = 0
    while x:
        n += 1
        x //= 2
    return n

(//= 2 could be changed to >>= 1)
msg77913 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-16 14:53
Please don't promote this ugly code "len(bin(x).lstrip('-0b'))". It's 
not the best way to compute the number of bits... I prefer fredrikj's 
proposition (with // 2, few people understand >> 1).
msg77918 - (view) Author: Skip Montanaro (skip.montanaro) * (Python committer) Date: 2008-12-16 18:33
Regarding the last few posts:

 * Raymond's implementation, while ugly, provides a completely orthogonal
   way to test compute numbits, useful in unit tests if nothing else.

 * Using x >> 1 in a reference implementation is perfectly reasonable.
   If the person using the reference implementation to produce a real
   C-based implementation doesn't understand the equivalence of x // 2
   and x >> 1, heaven help us.

Skip
msg77920 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-16 19:41
Thanks for all the comments.  Here's an updated patch, with quite a few 
changes:

code:
 - drop lookup tables in favour of "while(x) {x >>= 1; count += 1;}"
 - add example to docstring, and use PyDoc_STRVAR macro for docstrings

docs:
 - add "bin(37)" to whatsnew example
 - move main documentation out of the bit operations table into its own
   subsection, so that it can be indexed properly.
 - expand main documentation with examples, informal definition,
   equivalent Python code
 - I dropped the 1 + math.floor(...) definition from the docs, judging
   that 1 informal, 1 formal and 1 Python definition should be enough.

tests:
 - as proposed by Raymond, directly check equivalence with formal
   definition, equivalent Python code, and two other possible definitions.

(FWIW I prefer 'x>>1' over 'x//2' in the Python code, because it's more 
immediately related to the intended sense:  the operation should be 
thought of as a bit shift rather than a division.)
msg77922 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 19:44
Of course, the name should have been bit_length() instead of numbits().

For the code equivalent, I'm aiming for something less process oriented
and more focused on what it does.  bit_length IS the number of bits in a
binary representation without the sign or leading zeroes -- that
definition IS a correct mental picture and does not require special
cases for zero or for negatives.  

The purpose of the code equivalent is not efficiency or beauty; it to
help communicate was a function does.  If you want it to be more
beautiful, it can be broken into multiple lines.

I don't think you gain ANY explanatory power with code that says:
bit_length is the number of right-shifts (or floor divisions by two) of
the absolute value of a number until that number becomes zero.  Tell
that description to a high school student and prepare for a blank stare.

FWIW, I think having a mental picture that was too process oriented was
behind last night's mistake of thinking the (16).bit_length() was 5
instead of 4.  I theorize that error wouldn't have occurred if the
mental picture was of len('10000') instead of power-of-two mental model
where people (including some of the commenter here) tend to get the edge
cases wrong.

It would be better to have no code equivalent at all than to present the
repeated //2 method as a definition.  That is a process, but not a
useful mental picture to help explain what bit_length is all about. 
Think about it, bit_length() is about the length in bits of a binary
representation -- any code provided needs to translate directly to that
definition.

def bit_length(x):
    '''Length of a binary representation without the sign or leading zeroes:

    >>> (-37).numbits()
    6
    '''

    s = bin(x)          # binary representation:  bin(-37) --> '-0b100101'
    s = s.lstrip('-0b') # remove leading zeros and sign
    return len(s)
msg77923 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-16 19:51
Okay;  I don't have strong feelings about the form the Python code takes;  
I'll let you guys argue it out and then fix things accordingly
msg77924 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 20:16
IMO, the choices are something like my version or none at all.  The
repeated floor division by two of abs(x) has ZERO explanatory power and
may even detract from a beginner's ability to understand what the method
does.  Show that code to most finance people and they will avoid the
method entirely.

Anyone who disagrees needs to show both code fragments to some junior
programmers and see which best leads to understanding the method and
being able to correctly predict the edge cases bordering powers of two,
the zero case, and how negatives are handled.  

No fair trying this experiment on assembly language programmers ;-)
msg77925 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-16 20:20
> Show that code to most finance people and they will avoid the
> method entirely.

Why would finance people be interested in bit_length()?

I think this discussion begins to feel like bikeshedding. Documentation
can always be improved afterwards.
msg77926 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 20:30
Antoine, it's not bike-shedding at all.  Communicative docs are
important to users other than assembly language programmers.  BTW, I am
a finance person (a CPA).

Yes, you're correct, I can fix-up the docs after the patch is posted.
msg77928 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-16 20:34
Updated patch.
msg77929 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-16 20:39
Bah.  Fix test_int so that it actually works.
msg77930 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-16 20:45
...and use proper unittest methods instead of asserts...
msg77932 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 21:00
Looks good.  Marking as accepted.

Before applying, consider adding back the part of the docs with the '1 +
floor(...' definition.  I think it provides a useful alternative way to
look at what the method does.  Also, it gives a useful mathematical
expression that can be used in reasoning about invariants.  More
importantly, we should provide it because it is so easy to make a
mistake when rolling your own version of the formula (i.e. using ceil
instead of floor or having an off by one error).
msg77935 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-16 21:38
> Before applying, consider adding back the part of the docs with the '1 +
> floor(...' definition.

My only (minor) objection to this definition is that a straight Python
translation of it doesn't work, thanks to roundoff error and
the limited precision of floating-point:

>>> from math import floor, log
>>> n = 2**101
>>> n.bit_length()
102
>>> 1 + floor(log(n)/log(2))
101.0
>>> n = 2**80-1
>>> n.bit_length()
80
>>> 1 + floor(log(n)/log(2))
81.0

But as you say, it provides another perspective;  I'm fine with
putting it back in.
msg77937 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 21:45
Also, consider writing it in the two argument form:

   1 + floor(log(n, 2))

and using the word "approximately" or somesuch.
msg77970 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-17 16:20
Committed to trunk in r67822, py3k in r67824.
msg77980 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-17 18:44
> Committed

Really? YEAH! Great job everybody ;-) I read the code and it looks 
valid. Micro optimisation (for smaller memory footprint): would it be 
possible to share the 32 int table (BitLengthTable) between int and 
long (in Python 2.x)?
msg77984 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-17 21:23
32 bytes isn't worth sharing between modules.
msg78056 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-19 09:13
Posted some doc cleanups in r67850 and r67851.
msg78066 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-19 16:57
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
msg78067 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-19 18:16
Other possible wording:

 ... so that ``k`` is approximately ``1 + int(log(abs(x), 2))``.
msg78072 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-19 22:19
> ... so that ``k`` is approximately ``1 + 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-complex

and 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()."
msg108322 - (view) Author: Zooko O'Whielacronx (zooko) Date: 2010-06-21 22:04
There 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
msg108333 - (view) Author: Senthil Kumaran (orsenthil) * (Python committer) Date: 2010-06-22 02:45
> There is a small mistake in the docs:

Yes there was. Fixed in 82146.
msg108397 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2010-06-22 17:13
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.
msg108401 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-06-22 18:00
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.
msg108402 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-06-22 18:00
Aargh!
'a new builtin trunk' -> 'a new builtin trunc'
msg108418 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2010-06-22 21:09
Please open a new issue for the documentation problems, it's no more related to "numbits()" method and this issue is closed.
msg108422 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2010-06-22 21:34
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 that ``k`` is approximately ``1 + 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.
msg108437 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-06-23 07:53
Ah; sorry for misunderstanding.  Thanks for the explanation, Terry!
History
Date User Action Args
2010-06-23 07:53:24mark.dickinsonsetmessages: + msg108437
2010-06-22 21:34:16terry.reedysetmessages: + msg108422
2010-06-22 21:09:47hayposetmessages: + msg108418
2010-06-22 18:00:51mark.dickinsonsetmessages: + msg108402
2010-06-22 18:00:01mark.dickinsonsetmessages: + msg108401
2010-06-22 17:13:10terry.reedysetmessages: + msg108397
2010-06-22 02:45:26orsenthilsetnosy: + orsenthil
messages: + msg108333
2010-06-21 22:04:03zookosetnosy: + zooko
messages: + msg108322
2008-12-19 22:19:50mark.dickinsonsetmessages: + msg78072
2008-12-19 18:16:39rhettingersetassignee: mark.dickinson -> rhettinger
messages: + msg78067
2008-12-19 16:57:43mark.dickinsonsetmessages: + msg78066
2008-12-19 09:13:04rhettingersetmessages: + msg78056
2008-12-17 21:23:36rhettingersetmessages: + msg77984
2008-12-17 18:44:06hayposetmessages: + msg77980
2008-12-17 16:20:52mark.dickinsonsetstatus: open -> closed
messages: + msg77970
2008-12-17 15:43:18skip.montanarosetnosy: - skip.montanaro
2008-12-16 21:45:09rhettingersetmessages: + msg77937
2008-12-16 21:38:29mark.dickinsonsetmessages: + msg77935
2008-12-16 21:00:30rhettingersetresolution: accepted
messages: + msg77932
2008-12-16 20:45:26mark.dickinsonsetfiles: + bit_length11.patch
messages: + msg77930
2008-12-16 20:39:25mark.dickinsonsetfiles: - bit_length9.patch
2008-12-16 20:39:17mark.dickinsonsetfiles: + bit_length10.patch
messages: + msg77929
2008-12-16 20:37:05loewissetnosy: - loewis
2008-12-16 20:34:47mark.dickinsonsetfiles: - bit_length8.patch
2008-12-16 20:34:43mark.dickinsonsetfiles: - bit_length7_opt2.patch
2008-12-16 20:34:37mark.dickinsonsetfiles: - bit_length7.patch
2008-12-16 20:34:30mark.dickinsonsetfiles: + bit_length9.patch
messages: + msg77928
2008-12-16 20:30:02rhettingersetmessages: + msg77926
2008-12-16 20:20:27pitrousetmessages: + msg77925
2008-12-16 20:16:58rhettingersetmessages: + msg77924
2008-12-16 19:51:54mark.dickinsonsetmessages: + msg77923
2008-12-16 19:44:03rhettingersetmessages: + msg77922
2008-12-16 19:42:21mark.dickinsonsetcomponents: + Interpreter Core, - Library (Lib)
2008-12-16 19:41:52mark.dickinsonsetfiles: + bit_length8.patch
messages: + msg77920
2008-12-16 18:33:19skip.montanarosetnosy: + skip.montanaro
messages: + msg77918
2008-12-16 14:53:56hayposetmessages: + msg77913
2008-12-16 14:11:06fredrikjsetmessages: + msg77911
2008-12-16 14:04:05rhettingersetmessages: + msg77909
2008-12-16 14:00:02hayposetmessages: + msg77908
2008-12-16 13:57:21pitrousetmessages: + msg77907
2008-12-16 13:56:08hayposetmessages: + msg77905
2008-12-16 12:47:12rhettingersetmessages: + msg77898
2008-12-16 12:41:42rhettingersetassignee: rhettinger -> mark.dickinson
messages: + msg77897
2008-12-14 10:25:16mark.dickinsonsetfiles: - bit_length7_opt2.patch
2008-12-14 10:25:09mark.dickinsonsetfiles: + bit_length7_opt2.patch
2008-12-14 10:24:44mark.dickinsonsetfiles: - bit_length7.patch
2008-12-14 10:24:32mark.dickinsonsetfiles: + bit_length7.patch
messages: + msg77782
2008-12-13 17:54:06mark.dickinsonsetfiles: - bit_length7_opt.patch
2008-12-13 17:51:08mark.dickinsonsetfiles: - bit_length7_opt2.patch
2008-12-13 17:50:52mark.dickinsonsetfiles: + bit_length7_opt2.patch
messages: + msg77756
2008-12-13 16:43:32fredrikjsetmessages: + msg77754
2008-12-13 16:12:25mark.dickinsonsetfiles: - numbits-6b.patch
2008-12-13 16:04:58rhettingersetmessages: + msg77750
2008-12-13 15:34:43mark.dickinsonsetfiles: + bit_length7_opt2.patch
messages: + msg77747
2008-12-13 15:07:23mark.dickinsonsetfiles: - bit_length_pybench.patch
2008-12-13 15:06:02mark.dickinsonsetfiles: + bit_length_pybench.patch
messages: + msg77742
2008-12-13 15:04:08mark.dickinsonsetfiles: - bit_length7_opt.patch
2008-12-13 15:02:58mark.dickinsonsetfiles: + bit_length7_opt.patch
messages: + msg77741
2008-12-13 14:54:32mark.dickinsonsetmessages: + msg77738
2008-12-13 13:57:26pitrousetnosy: + pitrou
messages: + msg77730
2008-12-13 13:11:20mark.dickinsonsetfiles: + bit_length_pybench.patch
2008-12-13 13:11:10mark.dickinsonsetfiles: + bit_length7_opt.patch
2008-12-13 13:10:10mark.dickinsonsetfiles: + bit_length7.patch
messages: + msg77728
2008-12-13 11:19:18mark.dickinsonsetmessages: + msg77726
2008-12-13 10:53:22rhettingersetmessages: + msg77725
2008-12-13 10:43:34mark.dickinsonsetmessages: + msg77724
2008-12-13 10:35:39mark.dickinsonsetmessages: + msg77723
2008-12-13 09:57:54rhettingersetmessages: + msg77722
2008-12-13 09:26:11mark.dickinsonsetmessages: + msg77721
2008-12-13 04:23:58rhettingersetmessages: + msg77714
2008-12-12 22:47:53rhettingersetmessages: + msg77689
2008-12-12 19:50:09mark.dickinsonsetassignee: mark.dickinson -> rhettinger
messages: + msg77685
stage: patch review -> commit review
2008-12-12 18:10:51mark.dickinsonsetfiles: - numbits-6a.patch
2008-12-12 18:10:45mark.dickinsonsetfiles: + numbits-6b.patch
messages: + msg77682
2008-12-12 18:03:14hayposetmessages: + msg77681
2008-12-12 17:26:36mark.dickinsonsetfiles: + numbits-6a.patch
messages: + msg77678
2008-12-12 17:26:05mark.dickinsonsetmessages: + msg77677
2008-12-12 16:56:32hayposetmessages: + msg77676
2008-12-12 16:50:14mark.dickinsonsetmessages: + msg77675
2008-12-11 23:05:46hayposetfiles: - numbits-5.patch
2008-12-11 23:05:40hayposetfiles: + numbits-6.patch
messages: + msg77636
2008-12-11 21:22:13mark.dickinsonsetmessages: + msg77632
2008-12-11 21:12:14mark.dickinsonsetmessages: + msg77630
2008-12-09 12:28:54hayposetfiles: + numbits-5.patch
messages: + msg77407
2008-12-09 12:28:30hayposetfiles: - numbits-4.patch
2008-12-09 12:28:27hayposetfiles: - numbits-3.patch
2008-12-07 12:35:12hayposetmessages: + msg77221
2008-12-06 15:08:14mark.dickinsonsetassignee: mark.dickinson
2008-11-12 00:33:11hayposetfiles: + numbits-4.patch
messages: + msg75771
2008-11-12 00:02:50fredrikjsetmessages: + msg75770
2008-11-11 23:00:13mark.dickinsonsetmessages: + msg75767
2008-11-11 18:15:50hayposetfiles: - numbits-2.diff
2008-11-11 18:15:42hayposetfiles: + numbits-3.patch
messages: + msg75753
2008-11-11 17:15:51mark.dickinsonsetmessages: + msg75751
2008-11-11 02:45:41hayposetkeywords: + needs review
stage: patch review
2008-11-04 18:15:59hayposetfiles: + numbits-2.diff
messages: + msg75498
2008-10-14 19:29:01mark.dickinsonsetmessages: + msg74766
2008-10-14 18:03:24rhettingersetmessages: + msg74759
2008-10-14 17:31:28hayposetmessages: + msg74757
2008-10-14 17:19:18fredrikjsetmessages: + msg74756
2008-10-14 17:09:32terry.reedysetmessages: + msg74755
2008-10-14 16:20:34hayposetmessages: + msg74754
2008-10-14 15:38:20fredrikjsetmessages: + msg74751
2008-10-14 15:13:40hayposetmessages: + msg74750
2008-10-14 15:07:22mark.dickinsonsetmessages: + msg74749
2008-10-14 15:00:02mark.dickinsonsetmessages: - msg74728
2008-10-14 11:07:52hayposetmessages: + msg74729
title: math.frexp and obtaining the bit size of a large integer -> create a numbits() method for int and long types
2008-10-14 11:04:02hayposetnosy: + haypo
messages: + msg74728
2008-10-14 10:38:45fredrikjsetmessages: + msg74725
2008-10-06 17:41:56terry.reedysetnosy: + terry.reedy
messages: + msg74383
2008-08-18 21:28:47mark.dickinsonsetmessages: + msg71384
2008-08-18 20:41:41fredrikjsetmessages: + msg71376
2008-08-14 09:47:10mark.dickinsonsetmessages: + msg71116
2008-08-14 09:22:50mark.dickinsonsetmessages: + msg71115
2008-07-27 06:29:53mark.dickinsonsetnosy: + mark.dickinson
messages: + msg70312
2008-07-25 00:11:05rhettingersetmessages: + msg70231
versions: + Python 3.1, Python 2.7, - Python 2.6, Python 3.0
2008-07-24 23:12:20fredrikjsetfiles: + numbits.diff
keywords: + patch
messages: + msg70230
2008-07-24 21:39:57rhettingersetmessages: + msg70228
2008-07-24 19:47:09rhettingersetnosy: + rhettinger
messages: + msg70223
2008-07-24 19:41:58loewissetnosy: + loewis
messages: + msg70221
2008-07-24 17:20:43fredrikjcreate