Oscar Benjamin ha scritto:
On Sun, 3 Dec 2023 at 10:25, Julieta Shem via Python-list
wrote:
Alan Bawden writes:
def powers_of_2_in(n):
bc = (n ^ (n - 1)).bit_count() - 1
return bc, n >> bc
That's pretty fancy and likely the fastest.
It might be the fastest but it depends how big you expect n to be and
how many trailing zeros you expect. If n is a very large integer then
this does three large integer operations in (n^(n-1)).bit_count().
They are relatively fast operations but all linear in bit size. By
contrast a check like n & 1 is O(1) and half the time proves that no
further steps are necessary.
The mpmath library needs this exact operation and is generally
intended for the large n case so I checked how it is implemented
there:
https://github.com/mpmath/mpmath/blob/f13ea4dc925d522062ac734bd19a0a3cc23f9c04/mpmath/libmp/libmpf.py#L160-L177
That code is:
# Strip trailing bits
if not man & 1:
t = trailtable[man & 255]
if not t:
while not man & 255:
man >>= 8
exp += 8
bc -= 8
t = trailtable[man & 255]
man >>= t
exp += t
bc -= t
The trailtable variable is a pre-initialised list of shifts needed to
remove zeros from an 8-bit integer. The bc variable here is just
bc=man.bit_length() which is redundant but this code predates the
addition of the int.bit_length() method.
In principle this could use a large number of man>>=8 shifts which
would potentially be quadratic in the bit size of man. In practice the
probability of hitting the worst case is very low so the code is
instead optimised for the expected common case of large man with few
trailing zeros.
--
Oscar
HI,
I would turn the question to you: how big do you expect the value to
manage?
In a 'big numbers' context or when you need to convert a large amount of
values at the same time, your comment is absolutely valid, it is less
valid if the values can be represented with 64 bits.
I'll try to imagine the worst case in 64 bit:
b64Max=0x
i=1
while True:
i *= 2
if not i <= b64Max:
break
else:
n=i
n
9223372036854775808
If we now use the function being discussed:
powers_of_2_in(n)
(63, 1)
we can see that the bit_count() method had to do 63 iterations to count
the bits. It probably had to find the highest bit first but what if it
had a simple algorithm inside like this:
def h_bit(val):
tbits = 0
bits = 64 // 2
b64Max = 0xF
while bits > 0:
if (b64Max << bits) & val:
val >>= bits
tbits += bits
bits //= 2
return tbits
would only add 6 more iterations for values needing 64 bits (7
interactions for 128 bits, 3 if 8 bits)
If we use the library you suggest for a single value or a non-'big
numbers' value (e.g. 2048 bit) the initialization alone would be slower
than the function in question. The table you are talking about is
initialized in the following way:
trailtable = [trailing(n) for n in range(256)]
(it calls a function 256 times)
This is why I think that what you said is true but it depends a lot on
the context and to all this I would add that the best cases are much
greater than the worst cases.
e.g.:
powers_of_2_in(n + 1)
(0, 9223372036854775809)
powers_of_2_in(n - 1)
(0, 9223372036854775807)
(probably only 1 interaction)
--
https://mail.python.org/mailman/listinfo/python-list
