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" <[email protected]> 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 | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com
https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;
--
https://mail.python.org/mailman3//lists/python-list.python.org
