Message165818
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. |
|
Date |
User |
Action |
Args |
2012-07-18 23:32:23 | anon | set | recipients:
+ anon |
2012-07-18 23:32:23 | anon | set | messageid: <1342654343.1.0.00342933769834.issue15391@psf.upfronthosting.co.za> |
2012-07-18 23:32:22 | anon | link | issue15391 messages |
2012-07-18 23:32:20 | anon | create | |
|