"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
The above formula seems to work, given a few spot checks, but I thought
this should be a utility function in the underlying multiprecision lib-
rary in Python. Is the calculation n & -n really necessary?
While "n & -n" might take some time for large Python integers,
I see no way to do it faster in Python.
In C, one might be able to access the segments of large numbers
(the "limbs") starting with the least significant one to shortcut
the operation as soon as a "1" is found.
On 9/20/2026 2:23 AM, Stefan Ram wrote:
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or
quoted:
The above formula seems to work, given a few spot checks, but I thought
this should be a utility function in the underlying multiprecision lib-
rary in Python.ÿ Is the calculation n & -n really necessary?
ÿÿ While "n & -n" might take some time for large Python integers,
ÿÿ I see no way to do it faster in Python.
ÿÿ In C, one might be able to access the segments of large numbers
ÿÿ (the "limbs") starting with the least significant one to shortcut
ÿÿ the operation as soon as a "1" is found.
Yes, this is perplexing.ÿ I'm working with /arbitrary large numbers/ in Cryptohack, for cryptographic purposes, and need a utility function to
count the number of zero bits from the right.
The toy implementations of the Jacobi Symbol I've seen online, in Python
and otherwise, all seem to use a loop to repeatedly divide by two, which
is presumably much slower, so I'm /sort of happy/ with this method.
For practical applications, I resorted to the jacobi_symbol() function
in SymPy, since I have not finished a correct implementation myself.
But more on that in a later post.
Johann "Myrkraverk" Oskarsson wrote:
On 9/20/2026 2:23 AM, Stefan Ram wrote:
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote
or quoted:
The above formula seems to work, given a few spot checks, but I thought >>>> this should be a utility function in the underlying multiprecision lib- >>>> rary in Python.ÿ Is the calculation n & -n really necessary?
ÿÿ While "n & -n" might take some time for large Python integers,
ÿÿ I see no way to do it faster in Python.
ÿÿ In C, one might be able to access the segments of large numbers
ÿÿ (the "limbs") starting with the least significant one to shortcut
ÿÿ the operation as soon as a "1" is found.
Yes, this is perplexing.ÿ I'm working with /arbitrary large numbers/ in
Cryptohack, for cryptographic purposes, and need a utility function to
count the number of zero bits from the right.
The toy implementations of the Jacobi Symbol I've seen online, in Python
and otherwise, all seem to use a loop to repeatedly divide by two, which
is presumably much slower, so I'm /sort of happy/ with this method.
For practical applications, I resorted to the jacobi_symbol() function
in SymPy, since I have not finished a correct implementation myself.
But more on that in a later post.
Negative values are stored by flipping all bits of n and adding 1. This
is exactly why negating numbers with trailing zeros causes long carry chains, and negating numbers with trailing ones does not.
On 9/20/2026 3:37 AM, Lane W wrote:
Johann "Myrkraverk" Oskarsson wrote:
On 9/20/2026 2:23 AM, Stefan Ram wrote:
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote
or quoted:
The above formula seems to work, given a few spot checks, but I
thought
this should be a utility function in the underlying multiprecision
lib-
rary in Python.ÿ Is the calculation n & -n really necessary?
ÿÿ While "n & -n" might take some time for large Python integers,
ÿÿ I see no way to do it faster in Python.
ÿÿ In C, one might be able to access the segments of large numbers
ÿÿ (the "limbs") starting with the least significant one to shortcut
ÿÿ the operation as soon as a "1" is found.
Yes, this is perplexing.ÿ I'm working with /arbitrary large numbers/ in
Cryptohack, for cryptographic purposes, and need a utility function to
count the number of zero bits from the right.
The toy implementations of the Jacobi Symbol I've seen online, in Python >>> and otherwise, all seem to use a loop to repeatedly divide by two, which >>> is presumably much slower, so I'm /sort of happy/ with this method.
For practical applications, I resorted to the jacobi_symbol() function
in SymPy, since I have not finished a correct implementation myself.
But more on that in a later post.
Negative values are stored by flipping all bits of n and adding 1.
This is exactly why negating numbers with trailing zeros causes long
carry chains, and negating numbers with trailing ones does not.
Thank you for that exposition.ÿ This is precisely why I am perplexed and befuddled.ÿ For arbitrary long integers -- in bits -- this chain of
carries over unknown machine words internally to the Python interpreter
seems completely unnecessary, and it really should be simpler to just
count the zero bits in the underlying C code.
Why can't we do that?
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
it really should be simpler to just
count the zero bits in the underlying C code.
Why can't we do that?
You /can/ ask your chatbot to generate a C extension that does this
and explain how to compile and call it from Python.
( n & -n ).bit_length() - 1
| Sysop: | Jacob Catayoc |
|---|---|
| Location: | Pasay City, Metro Manila, Philippines |
| Users: | 5 |
| Nodes: | 4 (0 / 4) |
| Uptime: | 498677:07:45 |
| Calls: | 212 |
| Calls today: | 3 |
| Files: | 910 |
| D/L today: |
31 files (22,593K bytes) |
| Messages: | 69,826 |