[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: Ah; sorry for misunderstanding. Thanks for the explanation, Terry! -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Terry J. Reedy tjre...@udel.edu added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: Aargh! 'a new builtin trunk' - 'a new builtin trunc' -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor victor.stin...@haypocalc.com added the comment: Please open a new issue for the documentation problems, it's no more related to numbits() method and this issue is closed. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Terry J. Reedy tjre...@udel.edu added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Zooko O'Whielacronx zo...@zooko.com added the comment:
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
--
nosy: +zooko
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Senthil Kumaran orsent...@gmail.com added the comment: There is a small mistake in the docs: Yes there was. Fixed in 82146. -- nosy: +orsenthil ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Posted some doc cleanups in r67850 and r67851. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Other possible wording: ... so that ``k`` is approximately ``1 + int(log(abs(x), 2))``. -- assignee: marketdickinson - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: ... 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(). ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Skip Montanaro s...@pobox.com: -- nosy: -skip.montanaro ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor victor.stin...@haypocalc.com added the comment: 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)? ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: Committed to trunk in r67822, py3k in r67824. -- status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: 32 bytes isn't worth sharing between modules. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment:
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.
--
assignee: rhettinger - marketdickinson
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Antoine Pitrou pit...@free.fr added the comment: Le mardi 16 décembre 2008 à 13:56 +, STINNER Victor a écrit : (16).numbits() is 4, not 5. Well, I do hope (16).numbits() returns 5... ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Fredrik Johansson fredrik.johans...@gmail.com added the comment: 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) ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor victor.stin...@haypocalc.com added the comment:
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).
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment:
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()
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment:
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'))
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor victor.stin...@haypocalc.com added the comment: Ooops, you're right! (15).numbits() - 4 and (16).numbits() - 5. I'm tired. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Skip Montanaro s...@pobox.com added the comment: 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 -- nosy: +skip.montanaro ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor victor.stin...@haypocalc.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment:
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 'x1' 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.)
Added file: http://bugs.python.org/file12362/bit_length8.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: -- components: +Interpreter Core -Library (Lib) ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment:
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('1') 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)
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: 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 ;-) ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Antoine Pitrou pit...@free.fr added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: Updated patch. Added file: http://bugs.python.org/file12363/bit_length9.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12348/bit_length7.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12349/bit_length7_opt2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12362/bit_length8.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: Bah. Fix test_int so that it actually works. Added file: http://bugs.python.org/file12364/bit_length10.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12363/bit_length9.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Martin v. Löwis mar...@v.loewis.de: -- nosy: -loewis ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: ...and use proper unittest methods instead of asserts... Added file: http://bugs.python.org/file12365/bit_length11.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: 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). -- resolution: - accepted ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Also, consider writing it in the two argument form: 1 + floor(log(n, 2)) and using the word approximately or somesuch. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12336/bit_length7.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12343/bit_length7_opt2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. Added file: http://bugs.python.org/file12348/bit_length7.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Added file: http://bugs.python.org/file12349/bit_length7_opt2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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? ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Perhaps n.bit_length() with an underscore. The name sounds good to my ear and sensibilities. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: 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? ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment:
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 0x) {
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).
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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.) Added file: http://bugs.python.org/file12336/bit_length7.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Added file: http://bugs.python.org/file12337/bit_length7_opt.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Added file: http://bugs.python.org/file12338/bit_length_pybench.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Antoine Pitrou pit...@free.fr added the comment: 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. -- nosy: +pitrou ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: Slightly improved optimized version. Added file: http://bugs.python.org/file12339/bit_length7_opt.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12337/bit_length7_opt.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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). Added file: http://bugs.python.org/file12340/bit_length_pybench.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12338/bit_length_pybench.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. Added file: http://bugs.python.org/file12342/bit_length7_opt2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: If there's not a hurry, would like to review this a bit more when I get back early next week. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12332/numbits-6b.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Fredrik Johansson fredrik.johans...@gmail.com added the comment: 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()``? ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: In the documentation, should same value as ``x.bit_length`` not be same value as ``x.bit_length()``? Yes, of course. Thanks! Added file: http://bugs.python.org/file12343/bit_length7_opt2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12342/bit_length7_opt2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12339/bit_length7_opt.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor victor.stin...@haypocalc.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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? ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: Oops. Here's the patch. Added file: http://bugs.python.org/file12331/numbits-6a.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor victor.stin...@haypocalc.com added the comment: - 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)? ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. Added file: http://bugs.python.org/file12332/numbits-6b.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson dicki...@gmail.com: Removed file: http://bugs.python.org/file12331/numbits-6a.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: As far as I'm concerned, this patch is ready to be applied. Raymond, care to give a second opinion? -- assignee: marketdickinson - rhettinger stage: patch review - commit review ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment:
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.
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3439
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: FWIW, here is a link to faster algorithms: http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLog ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson dicki...@gmail.com added the comment: 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. ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by STINNER Victor victor.stin...@haypocalc.com: Removed file: http://bugs.python.org/file12302/numbits-5.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by STINNER Victor [EMAIL PROTECTED]: Removed file: http://bugs.python.org/file11988/numbits-3.patch ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor [EMAIL PROTECTED] added the comment: New version of my patch using a method instead of a property. Added file: http://bugs.python.org/file12302/numbits-5.patch ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by STINNER Victor [EMAIL PROTECTED]: Removed file: http://bugs.python.org/file11990/numbits-4.patch ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor [EMAIL PROTECTED] added the comment: I plan to change my patch to come back to a method (x.numbits()) because other integer implementations like Decimal may be slower. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson [EMAIL PROTECTED]: -- assignee: - marketdickinson ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor [EMAIL PROTECTED] added the comment: (-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 ;-) Added file: http://bugs.python.org/file11988/numbits-3.patch ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by STINNER Victor [EMAIL PROTECTED]: Removed file: http://bugs.python.org/file11939/numbits-2.diff ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson [EMAIL PROTECTED] added the comment: Hi, Victor! Thanks for the updated patch. Your patch still hangs on: from sys import maxint (-maxint-1).numbits() on my 32-bit machine. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson [EMAIL PROTECTED] added the comment: 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? ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Fredrik Johansson [EMAIL PROTECTED] added the comment: 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. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor [EMAIL PROTECTED] added the comment:
[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)
Added file: http://bugs.python.org/file11990/numbits-4.patch
___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3439
___Index: Objects/intobject.c
===
--- Objects/intobject.c (révision 67177)
+++ Objects/intobject.c (copie de travail)
@@ -1138,6 +1138,27 @@
return NULL;
}
+static PyObject *
+int_numbits(PyIntObject *v)
+{
+ unsigned long n;
+ long result = 0;
+
+ if (v-ob_ival 0) {
+ /* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then
+ ANSI C says that the result of -ival is undefined when ival
+ == LONG_MIN. Hence the following workaround. */
+ n = (unsigned long)(-1 - v-ob_ival) + 1;
+ } else {
+ n = (unsigned long)v-ob_ival;
+ }
+ while (n) {
+ ++result;
+ n = 1;
+ }
+ return PyInt_FromLong(result);
+}
+
#if 0
static PyObject *
int_is_finite(PyObject *v)
@@ -1161,6 +1182,10 @@
};
static PyGetSetDef int_getset[] = {
+ {numbits,
+(getter)int_numbits, (setter)NULL,
+Returns the number of binary digits in self.,
+NULL},
{real,
(getter)int_int, (setter)NULL,
the real part of a complex number,
Index: Objects/longobject.c
===
--- Objects/longobject.c(révision 67177)
+++ Objects/longobject.c(copie de travail)
@@ -3451,6 +3451,64 @@
return PyInt_FromSsize_t(res);
}
+static PyObject *
+long_numbits(PyLongObject *v)
+{
+ PyLongObject *result, *x, *y;
+ Py_ssize_t ndigits, msd_bits;
+ digit msd;
+ size_t nbits;
+
+ assert(v != NULL);
+ assert(PyLong_Check(v));
+
+ nbits = _PyLong_NumBits((PyObject*)v);
+ if (nbits != (size_t)-1 || !PyErr_Occurred())
+ return PyLong_FromSize_t(nbits);
+
+ ndigits = ABS(Py_SIZE(v));
+ assert(ndigits == 0 || v-ob_digit[ndigits - 1] != 0);
+
+ if (ndigits == 0)
+ return PyLong_FromLong(0);
+
+ msd = v-ob_digit[ndigits - 1];
+ msd_bits = 0;
+ do {
+ ++msd_bits;
+ msd = 1;
+ } while (msd);
+
+ result = (PyLongObject *)PyLong_FromLong(ndigits - 1);
+ if (result == NULL)
+ return NULL;
+ x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
+ if (x == NULL)
+ goto error;
+ y = (PyLongObject *)long_mul(result, x);
+ Py_DECREF(x);
+ if (y == NULL)
+ goto error;
+ Py_DECREF(result);
+ result = y;
+
+ x = (PyLongObject *)PyLong_FromLong(msd_bits);
+ if (x == NULL)
+ goto error;
+ y = (PyLongObject *)long_add(result, x);
+ Py_DECREF(x);
+ if (y == NULL)
+ goto error;
+ Py_DECREF(result);
+ result = y;
+
+ return (PyObject *)result;
+
+error:
+ Py_DECREF(result);
+ return NULL;
+}
+
#if 0
static PyObject *
long_is_finite(PyObject *v)
@@ -3476,6 +3534,10 @@
};
static PyGetSetDef long_getset[] = {
+{numbits,
+ (getter)long_numbits, (setter)NULL,
+ returns the number of binary digits in self.,
+ NULL},
{real,
(getter)long_long, (setter)NULL,
the real part of a complex number,
Index: Lib/test/test_int.py
===
--- Lib/test/test_int.py(révision 67177)
+++ Lib/test/test_int.py(copie de travail)
@@ -240,6 +240,21 @@
self.assertEqual(int('2br45qc', 35), 4294967297L)
self.assertEqual(int('1z141z5', 36), 4294967297L)
+def test_numbits(self):
+self.assertEqual((0).numbits(), 0)
+self.assertEqual((1).numbits(), 1)
+self.assertEqual((-1).numbits(), 1)
+self.assertEqual((2).numbits(), 2)
+self.assertEqual((-2).numbits(), 2)
+for i in [2, 3, 15, 16, 17, 31, 32, 33, 63, 64]:
+a = 2**i
+self.assertEqual((a-1).numbits(), i)
+self.assertEqual((1-a).numbits(), i)
+self.assertEqual((a).numbits(), i+1)
+
[issue3439] create a numbits() method for int and long types
Changes by STINNER Victor [EMAIL PROTECTED]: -- keywords: +needs review stage: - patch review ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor [EMAIL PROTECTED] added the comment: 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 Added file: http://bugs.python.org/file11939/numbits-2.diff ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor [EMAIL PROTECTED] added the comment: I changed the title since I agree that numbits() with long integer is not related to floats. -- title: math.frexp and obtaining the bit size of a large integer - create a numbits() method for int and long types ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Changes by Mark Dickinson [EMAIL PROTECTED]: ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
Mark Dickinson [EMAIL PROTECTED] added the comment: 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? ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor [EMAIL PROTECTED] added the comment: 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). ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue3439] create a numbits() method for int and long types
STINNER Victor [EMAIL PROTECTED] added the comment: 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. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3439 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
