on writing a number as 2^s * q, where q is odd

[jak]

Oscar Benjamin ha scritto:
> On Sun, 3 Dec 2023 at 10:25, Julieta Shem via Python-list
> <python-list at python.org> wrote:
>>
>> Alan Bawden <alan at csail.mit.edu> 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=0xFFFFFFFFFFFFFFFF
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 = 0xFFFFFFFFFFFFFFFFF
     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)