New submission from anon <[email protected]>:
Many numeric algorithms require knowing the number of bits an integer has (for
instance integer squareroots). For example this simple algorithm using shifts
is O(n^2):
def bitl(x):
x = abs(x)
n = 0
while x > 0:
n = n+1
x = x>>1
return n
A simple O(n) algorithm exists:
def bitl(x):
if x==0: return 0
return len(bin(abs(x)))-2
It should be possible find the bit-length of an integer in O(1) however. O(n)
algorithms with high constants simply don't cut it for many applications.
That's why I would propose adding an inbuilt function bitlength(n) to the math
module. bitlength(n) would be the integer satisfying
bitlength(n) = ceil(log2(abs(n)+1))
Python more than ever with PyPy progressing is becoming a great platform for
mathematical computation. This is an important building block for a huge number
of algorithms but currently has no elegant or efficient solution in plain
Python.
----------
components: Library (Lib)
messages: 165818
nosy: anon
priority: normal
severity: normal
status: open
title: Add bitlength function to the math module
type: enhancement
_______________________________________
Python tracker <[email protected]>
<http://bugs.python.org/issue15391>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
