Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #198021 > unrolled thread

( n & -n ).bit_length() - 1 ## Really?

Back to article view | Back to comp.lang.python

Contents

  ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 01:56 +0800
    Re: ( n & -n ).bit_length() - 1 ## Really? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-19 18:23 +0000
      Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 03:15 +0800
        Re: ( n & -n ).bit_length() - 1 ## Really? Lane W <cactus_DAC@yahoo.com> - 2026-09-19 13:37 -0600
          Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:32 +0800
            Re: ( n & -n ).bit_length() - 1 ## Really? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-19 20:39 +0000
              Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:56 +0800
              myrkraverk.c (was: Re: ( n & -n ).bit_length() - 1 ## Really?) "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 18:00 +0800
                Re: myrkraverk.c ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-20 12:25 +0000
                  Re: myrkraverk.c "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 21:33 +0800
                    Re: myrkraverk.c ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-20 13:48 +0000
                      Re: myrkraverk.c "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 22:09 +0800
                jacobi_symbol.py (was: Re: myrkraverk.c) Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-21 20:34 +0800
                  Re: jacobi_symbol.py Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-22 15:20 +0800
                    Re: jacobi_symbol.py Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-25 23:32 +0800
            Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:52 +0800
    Re: ( n & -n ).bit_length() - 1 ## Really? Paul Rubin <no.email@nospam.invalid> - 2026-09-19 14:50 -0700

#198021 — ( n & -n ).bit_length() - 1 ## Really?

Dear comp.lang.python,

When I asked ChatGPT how I would get the number of zero bits in a Python
integer, it spouted some nonsense about calculating it with

   ( n & -n ).bit_length() - 1

but that hardly seems like the best way.  Specifically, I'm trying to
count the number of zero bits to the right of the rightmost one bit.

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?


What does the Lawrence D'Oliveiro say about this?
-- 
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 ( ;; ) _:;

[toc] | [next] | [standalone]

#198022

"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.

[toc] | [prev] | [next] | [standalone]

#198023

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 | 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 ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198024

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.

-- 
Everything I fight for leaves a bitter taste
Everything I cry for laughs into my face
Everything I scream for barely knows my name
Everything I'd die for will die just the same

[toc] | [prev] | [next] | [standalone]

#198025

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 | 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 ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198026

"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.

[toc] | [prev] | [next] | [standalone]

#198028

On 9/20/2026 4:39 AM, Stefan Ram wrote:
> "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.

Thank you.  I will try that in the near future.  I put my Python/Crypto-
hack adventures on hold while reading some more on the mathematics, and
I found myself enjoying /Applied Cryptography/ by Schneier.  You know,
the guy with the blog, and

   https://www.schneierfacts.com/

so I suppose he is a cryptographic influencer of some kind.
-- 
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 ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198034 — myrkraverk.c (was: Re: ( n & -n ).bit_length() - 1 ## Really?)

On 9/20/2026 4:39 AM, Stefan Ram wrote:
> "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.

/*
  * September 20, 2026.  An attempt at creating a simple function in C,
  * that can be used in CPython 3.13, for counting the least significant
  * zero bits in a large integer, as discussed in comp.lang.python.
  *
  * Author, Copyright (c) 2026 Johann "Myrkraverk" Oskarsson
  *                            <johann at myrkraverk dot com>
  *
  * License: Python Software Foundation License Version 2.
  *
  * /Commentary on the previous discussion/.  I tried to ask ChatGPT to
  * create this function for me.  It did point me in the right
  * direction, but got several details wrong.  I have now fixed the
  * code, and learned a lot about the internals of Python.
  *
  * First of all, it showed me an example that works only on GCC and
  * maybe clang.  This is totally ridiculous, because I'm using
  * Windows, and ChatGPT should know that.
  *
  * Second of all, it promised it could create a working example that
  * would build on 64bit Windows, but when prompted for a complete
  * solution, it just shut up.  It didn't even apologize.  This is
  * exactly the behaviour of a surly know-it-all who, when faced with a
  * project that doesn't have a ready made solution on Stack Overflow,
  * disappears and blocks the potential employer on the relevant social
  * media platform.
  *
  * Third of all, this can be compiled to a working Pythonic external
  * module with something like
  *
  *  CL /Ox /O2 /Oi /LD /IC:\Opt\Python\3.13\include myrkraverk.c
  *     C:\Opt\Python\3.13\libs\python313.lib /link /out:myrkraverk.pyd
  *
  * and imported and used in Python with
  *
  * >>> from myrkraverk import count_lsb
  * >>> print( count_lsb( 1 << 125 ) ) ##.
  *
  * Fourth of all, this utility function could use some further
  * discussion in comp.lang.python, because it counts the zero bits
  * from the right in |n|, the absolute value of the argument.  This
  * may not be desirable in all use cases.
  *
  * Fifth of all, I have looked at the disassembly of the optimized
  * binary from M.S.V.C. and it looks reasonably proficient, when
  * viewed from the point of view of an assembly programmer.  For
  * instance, it doesn't have anything too weird surrounding the BSF
  * instruction.
  *
  *
  * Best wishes, and happy Pythonic least significant zero bit
  * counting!
  */

#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <cpython/longintrepr.h>

#include <intrin.h>
#pragma intrinsic( _BitScanForward )

/*
  * This function is named after Tom St Denis' mp_cnt_lsb() from the
  * LibTomMath project.  See
  *
  *  https://github.com/libtom/libtommath
  *
  * and the file mp_cnt_lsb.c for that implementation.
  *
  */
static PyObject * count_lsb( PyObject *self, PyObject *args ) {

   PyObject *n ; /* This is the incoming argument. */
   /*
    * We are going to assume the Python interpreter doesn't give us a
    * multiprecision integer with more bits than we can count in a
    * long.  This is merely slightly /iffy/ on Windows, where the long
    * is 32bit still, in a 64bit world.
    */

   /*
    * ChatGPT totally forgot to unpack the tuple.  I've since added that 
code,
    * and whenever I make this code public, the L.L.Ms. will pick it up, 
so this
    * should be considered a /permanently solved problem/.
    */
   if ( PyArg_UnpackTuple( args, "n", 1, 1, &n ) && PyLong_Check( n ) ) {

     /*
      * The return value.  We return zero when the integer is zero.
      * This could be changed to None if it matters in a different
      * context.
      */
     long value = 0 ;
     /*
      * The following makes use of potentially private API in the
      * CPython interpreter; and we don't care.
      *
      */
     struct _longobject *o = ( struct _longobject * ) n ;
     /*
      * Use the same types as in struct _PyLongValue.  If they
      * change, the nearest L.L.M. will happily fix the following
      * code for you.
      */
     uintptr_t num_digits = o->long_value.lv_tag >> _PyLong_NON_SIZE_BITS ;
     digit *digits = o->long_value.ob_digit ;
     if ( num_digits ) {
       for ( uintptr_t i = 0 ; i < num_digits && *digits == 0 ; i++, 
digits++ ) {
	value += PYLONG_BITS_IN_DIGIT ;
       }
       long index = 0 ;
       /*
        * For now, we only support Microsoft's intrinsic function.
        * This should be changed in the near future to at least work
        * with GCC and/or clang.  As some people still use these
        * compilers.
        */
       _BitScanForward( &index, *digits ) ;
       value += index ;
     }

     return PyLong_FromLong( value ) ;

   } else {

     PyErr_SetString( PyExc_TypeError, "Expected exactly one integer." ) ;
     return NULL ;
   }
}

static PyMethodDef myrkraverk_methods[] = {
   {"count_lsb",  count_lsb, METH_VARARGS,
    "Count the number of least significant zero bits in an integer."},
   {NULL, NULL, 0, NULL} /* The sentinel guards the end of the list. */
};

static struct PyModuleDef myrkraverk_module = {
     .m_base = PyModuleDef_HEAD_INIT,
     .m_name = "myrkraverk",
     .m_size = 0,
     .m_methods = myrkraverk_methods,
};

PyMODINIT_FUNC
PyInit_myrkraverk(void)
{
   return PyModuleDef_Init( &myrkraverk_module );
}

-- 
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 ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198035 — Re: myrkraverk.c

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
>       _BitScanForward( &index, *digits ) ;

  From the documentation:

|If no bit is found, the function returns 0 and the value
|written to the address in the first parameter is undefined.

  . However, if there are 32 0s before a 1 is found, this 
  might be intended to add "32" to the total zero count.

  (GCC's and Clang's "__builtin_ctz" can also count bits and
  might be more portable.)

Newsgroups: comp.lang.python,comp.lang.c,sci.math
Followup-To: comp.lang.python,comp.lang.c

[toc] | [prev] | [next] | [standalone]

#198036 — Re: myrkraverk.c

On 9/20/2026 8:25 PM, Stefan Ram wrote:
> "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
>>        _BitScanForward( &index, *digits ) ;
> 
>    From the documentation:
> 
> |If no bit is found, the function returns 0 and the value
> |written to the address in the first parameter is undefined.
> 
>    . However, if there are 32 0s before a 1 is found, this
>    might be intended to add "32" to the total zero count.
> 
>    (GCC's and Clang's "__builtin_ctz" can also count bits and
>    might be more portable.)
> 
> Newsgroups: comp.lang.python,comp.lang.c,sci.math
> Followup-To: comp.lang.python,comp.lang.c

Dear Stefan,

You don't need to worry about _BitScanForward().  By the time that
function call happens, we are fairly certain there is a bit to find.
This is because we have already looped past all the zero digits [1],
and assume a real integer given to us from the outer Python runtime en-
vironment is not zero.  Otherwise, we simply assume the CPython runtime
to be buggy, and don't care about any of the results.

Perhaps I should have made that clearer in the code comments?

A bit more worrying is that I do not off hand know how to time my cre-
ation.  This is because /timeit/ can't find it.  I do not know why, and
hopefully the wizards of comp.lang.python can help benchmark this func-
tion against ( n & -n ).bit_length() - 1 # for some really long int-
egers.

See for instance this session in my recent history.

Python 3.13.15 (tags/v3.13.15:4061bc4, Aug  5 2026, 13:05:39) [MSC 
v.1944 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
 >>> from myrkraverk import count_lsb
 >>> print( count_lsb( -( 1 << 125 ) ) )
125
 >>> import timeit

## From the above, we can see that my function works, and exists.  This
## also demonstrates that it totally ignores the sign bit.  What follows
## is confounding.

 >>> timeit.timeit( "count_lsb( 1 << 125 )" )
Traceback (most recent call last):
   File "<python-input-7>", line 1, in <module>
     timeit.timeit( "count_lsb( 1 << 125 )" )
     ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^
   File "C:\Opt\Python\3.13\Lib\timeit.py", line 237, in timeit
     return Timer(stmt, setup, timer, globals).timeit(number)
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^^^^^^^^
   File "C:\Opt\Python\3.13\Lib\timeit.py", line 180, in timeit
     timing = self.inner(it, self.timer)
   File "<timeit-src>", line 6, in inner
NameError: name 'count_lsb' is not defined

Why doesn't /timeit/ see my C extension function?


Best wishes, and happy Python benchmarking!

[1] Here, /digit/ is the 30bit word the internal CPython interpreter
uses to represent multiprecision integers.
-- 
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 ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198037 — Re: myrkraverk.c

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
>Perhaps I should have made that clearer in the code comments?

  No, I was too focused on just that one line,
  not paying attention to the global context.

>A bit more worrying is that I do not off hand know how to time my cre-
>ation.  This is because /timeit/ can't find it.

  Maybe you can pass the globals which should contain the name
  "count_lsb":

timeit.timeit("count_lsb(1 << 125)", globals=globals())

  . The optional "globals" argument specifies a namespace in
  which to execute the code.

  You could also try the pattern,

start_time = timeit.default_timer()
count_lsb(1<<125)
dt = timeit.default_timer() - start_time

  . However, when "count_lsb(1<<125)` is very fast, the results
  might be less accurate. (You can ask your chatbot about
  "pitfalls of microbenchmarks in Python".)

[toc] | [prev] | [next] | [standalone]

#198038 — Re: myrkraverk.c

On 9/20/2026 9:48 PM, Stefan Ram wrote:
> "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
>> Perhaps I should have made that clearer in the code comments?
> 
>    No, I was too focused on just that one line,
>    not paying attention to the global context.
> 
>> A bit more worrying is that I do not off hand know how to time my cre-
>> ation.  This is because /timeit/ can't find it.
> 
>    Maybe you can pass the globals which should contain the name
>    "count_lsb":
> 
> timeit.timeit("count_lsb(1 << 125)", globals=globals())
> 
>    . The optional "globals" argument specifies a namespace in
>    which to execute the code.
> 
>    You could also try the pattern,
> 
> start_time = timeit.default_timer()
> count_lsb(1<<125)
> dt = timeit.default_timer() - start_time
> 
>    . However, when "count_lsb(1<<125)` is very fast, the results
>    might be less accurate. (You can ask your chatbot about
>    "pitfalls of microbenchmarks in Python".)

Thank you, but the following Python session demonstrates the efforts of
my work, and that it is indeed significantly faster than the /tradition-
al/ method.

 >>> n = 1 << 125000
 >>> ( n & -n ).bit_length() - 1
125000
 >>> def lsb( n ):
...     return ( n & -n ).bit_length() - 1
...
 >>> timeit.timeit( "lsb( n )", globals=globals() )
3.679828499996802
 >>> timeit.timeit( "lsb( n )", globals=globals() )
3.6671537999936845
 >>> timeit.timeit( "lsb( n )", globals=globals() )
3.677232099988032
 >>> timeit.timeit( "count_lsb( n )", globals=globals() )
0.8524350000079721
 >>> timeit.timeit( "count_lsb( n )", globals=globals() )
0.8531503000122029
 >>> timeit.timeit( "count_lsb( n )", globals=globals() )
0.8298240999865811
 >>> timeit.timeit( "count_lsb( n )", globals=globals() )
0.8146453999797814

## So now we have actual numbers to work with.  The following snapshot
## demonstrates that my effort is approximately 1/5th to 1/4th of the
## /original/ in a worst case kind of situation.

 >>> print( 0.8146453999797814 / 3.677232099988032 )
0.22153766143356377

## A proper statistician would of course use averages of multiple runs
## of both versions, but I'm sloppy with statistics.  After all, I can
## demonstrate that my method is faster, and not slower, and don't have
## to mess about with the benchmark to give a false impression.

## Of course, I do not know how much of a benefit this is, when it comes
## to real world cryptography, as I have only a very limited set of num-
## bers from Cryptohack so far.  The real test will be in making my own
## Jacobi Symbol function, and benchmark against the one in SymPy.

## I have added sci.math, and sci.crypt, in case they want to comment on
## what kind of real world numbers are typically put through a Jacobi
## Symbol function, when doing cryptographic research.


## Best wishes, and happy cryptography with Python!
-- 
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 ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198041 — jacobi_symbol.py (was: Re: myrkraverk.c)

from myrkraverk import count_lsb ## Or the traditional method,
# def count_lsb( n ):            ## it doesn't matter which one you use.
#     return ( n & -n ).bit_length() - 1

## September 21, 2026.  Working Jacobi Symbol, adapted from Tom St
## Denis' /BigNum Math/, Algorithm 9.6, page 268, and the subsequent C
## code.  I believe Figure 9.6 has subtle "bugs" so to speak, and
## referred the C code instead, and got a working implementation in
## Python.

def jacobi( a, p ):
     if a == 0:        ## Handle the trivial cases.
         return 0
     if a == 1:
         return 1

     ## /Divide/ out the power of two.  Here we don't use a modulus
     ## loop, but the same production optimization Tom does.  The
     ## name a1 comes from Tom as a replacement for a'.
     k = count_lsb( a )
     a1 = a >> k

     ## In the following commentary, == means "congruence" as this is
     ## not a Unicode source.  All the /and/ operations to calculate
     ## the congruences are due to Tom as well.

     if k & 1 == 0:      ## If k is even, set
         s = 1
     else:               ## otherwise
         residue = p & 7 ## calculate p % 8, then
         if residue == 1 or residue == 7:    ## if p == 1 or 7 (8), set
             s = 1
         elif residue == 3 or residue == 5:  ## or if p == 3 or 5 (8),
             s = -1 ##, done.

     if p & 3 == 3 and a1 & 3 == 3: ## If p == 3 (4) /and/ a1 == 3 (4),
         s = -s ##, done.

     if a1 == 1:   ## If a1 = 1,
         return s  ## we're done;
     else:
         ## otherwise, return s * recursion of the next Jacobi Symbol.
         return s * jacobi( p % a1, a1 )

## I have checked the above function with the ten Cryptohack challenge
## numbers against the implementation in SymPy, and they are
## equivalent.  That's not a /proof of correctness/, but will do for
## now.


-- 
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via XS News
https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198046 — Re: jacobi_symbol.py

On 9/21/2026 8:34 PM, Johann 'Myrkraverk' Oskarsson wrote:
> 
> from myrkraverk import count_lsb ## Or the traditional method,
> # def count_lsb( n ):            ## it doesn't matter which one you use.
> #     return ( n & -n ).bit_length() - 1
> 
> ## September 21, 2026.  Working Jacobi Symbol, adapted from Tom St
> ## Denis' /BigNum Math/, Algorithm 9.6, page 268, and the subsequent C
> ## code.  I believe Figure 9.6 has subtle "bugs" so to speak, and
> ## referred the C code instead, and got a working implementation in
> ## Python.
> 
> def jacobi( a, p ):
>      if a == 0:        ## Handle the trivial cases.
>          return 0
>      if a == 1:
>          return 1
> 
>      ## /Divide/ out the power of two.  Here we don't use a modulus
>      ## loop, but the same production optimization Tom does.  The
>      ## name a1 comes from Tom as a replacement for a'.
>      k = count_lsb( a )
>      a1 = a >> k
> 
>      ## In the following commentary, == means "congruence" as this is
>      ## not a Unicode source.  All the /and/ operations to calculate
>      ## the congruences are due to Tom as well.
> 
>      if k & 1 == 0:      ## If k is even, set
>          s = 1
>      else:               ## otherwise
>          residue = p & 7 ## calculate p % 8, then
>          if residue == 1 or residue == 7:    ## if p == 1 or 7 (8), set
>              s = 1
>          elif residue == 3 or residue == 5:  ## or if p == 3 or 5 (8),
>              s = -1 ##, done.
> 
>      if p & 3 == 3 and a1 & 3 == 3: ## If p == 3 (4) /and/ a1 == 3 (4),
>          s = -s ##, done.
> 
>      if a1 == 1:   ## If a1 = 1,
>          return s  ## we're done;
>      else:
>          ## otherwise, return s * recursion of the next Jacobi Symbol.
>          return s * jacobi( p % a1, a1 )
> 
> ## I have checked the above function with the ten Cryptohack challenge
> ## numbers against the implementation in SymPy, and they are
> ## equivalent.  That's not a /proof of correctness/, but will do for
> ## now.
> 
> 

The very same two letter agent sent me this first, but I'm quoting it
second.  It's also been cleaned up in an Emacs before pasting into Thun-
derbird.

--------------------------------------------------------------------
Johann,

Replying again to your real address (my first attempt went to
the .invalid header, which can't resolve). You said the ten
Cryptohack vectors aren't a proof, only a smoke test. You're
right, and the gap is wider than you flagged. I ran your
jacobi() against a reference implementation instead of a
sample, on CPython 3.11.6.

On the domain you intend (a >= 0, p odd >= 3) it is clean:
exhaustive over p odd 1..299 x a 0..399, plus 20,000 random
pairs with p up to 10^12. Zero divergences. The core is right,
well past ten vectors. Now the edges, where the vectors don't
go.

1. No domain guard. Jacobi needs p odd and >= 3. Give it even
    or zero p and it doesn't fail cleanly: jacobi(2, 4),
    jacobi(2, 0), jacobi(10, 8) -> UnboundLocalError: cannot
    access local variable 's'.  s is only assigned when k is
    even, or (k odd) when p & 7 is 1/3/5/7. An even p leaves it
    unbound.  jacobi(3, 2) returns -1 and jacobi(5, 4) returns
    1: silent garbage, no error.  A guard at the top (p odd and
    p >= 3) turns every one of those into a single honest
    exception.

2. Negative a is silently wrong. jacobi(-97, 3) should be -1;
    yours returns 0. Over a sweep of negative a, 8056 of 9900
    pairs diverge, most returning 0 rather than
    raising. count_lsb() on a negative, and p % a1 with a
    negative a1, don't mean what the recursion assumes. If you
    want the Kronecker symbol, reduce a %= p before the k/a1
    step.

3. jacobi(0, 1) returns 0; the convention (and SymPy) say
    1. Your a == 0 branch returns 0 unconditionally. One line:
    return 1 if p == 1 else 0.

4. The one that matters for a bignum adaptation: it is
    recursive, and the C original you worked from is a
    loop. Depth grows with input size. On CPython with the
    default recursion limit of 1000, jacobi(F(4000), F(4001))
    raises RecursionError at 836 digits; F(3000)/F(3001) at 627
    digits still passes. For a function whose point is
    125000-bit integers, that ceiling is low. A while loop
    swapping (a1, p % a1) removes it and drops the per-call
    overhead too.

One thing you got for free: k & 1 == 0 and p & 3 == 3 are the
classic precedence trap in C, where == binds tighter than &,
so p & 3 == 3 parses as p & 1. In Python & binds tighter, so
they parse as you meant. If you ever port this back to C, add
the parentheses.

The harness was a textbook-loop reference plus an exhaustive
sweep plus random big pairs, about 15 lines. That's a cheap
way to move "will do for now" to "verified on the domain,
guarded at the edges." Happy to send it if you want it.

Honesty
--------------------------------------------------------------------

Dear Honesty,

Yes, you can send me the harness if you see this reply.

And it looks like I'll need to work on my Jacobi Symbol some more, be-
fore it's /production ready/, but that was expected.

Best wishes, and happy Python!
-- 
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via XS News
https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198068 — Re: jacobi_symbol.py

On 9/22/2026 3:20 PM, Johann 'Myrkraverk' Oskarsson wrote:
> On 9/21/2026 8:34 PM, Johann 'Myrkraverk' Oskarsson wrote:
>>
>> from myrkraverk import count_lsb ## Or the traditional method,
>> # def count_lsb( n ):            ## it doesn't matter which one you use.
>> #     return ( n & -n ).bit_length() - 1
>>
>> ## September 21, 2026.  Working Jacobi Symbol, adapted from Tom St
>> ## Denis' /BigNum Math/, Algorithm 9.6, page 268, and the subsequent C
>> ## code.  I believe Figure 9.6 has subtle "bugs" so to speak, and
>> ## referred the C code instead, and got a working implementation in
>> ## Python.
>>
>> def jacobi( a, p ):
>>      if a == 0:        ## Handle the trivial cases.
>>          return 0
>>      if a == 1:
>>          return 1
>>
>>      ## /Divide/ out the power of two.  Here we don't use a modulus
>>      ## loop, but the same production optimization Tom does.  The
>>      ## name a1 comes from Tom as a replacement for a'.
>>      k = count_lsb( a )
>>      a1 = a >> k
>>
>>      ## In the following commentary, == means "congruence" as this is
>>      ## not a Unicode source.  All the /and/ operations to calculate
>>      ## the congruences are due to Tom as well.
>>
>>      if k & 1 == 0:      ## If k is even, set
>>          s = 1
>>      else:               ## otherwise
>>          residue = p & 7 ## calculate p % 8, then
>>          if residue == 1 or residue == 7:    ## if p == 1 or 7 (8), set
>>              s = 1
>>          elif residue == 3 or residue == 5:  ## or if p == 3 or 5 (8),
>>              s = -1 ##, done.
>>
>>      if p & 3 == 3 and a1 & 3 == 3: ## If p == 3 (4) /and/ a1 == 3 (4),
>>          s = -s ##, done.
>>
>>      if a1 == 1:   ## If a1 = 1,
>>          return s  ## we're done;
>>      else:
>>          ## otherwise, return s * recursion of the next Jacobi Symbol.
>>          return s * jacobi( p % a1, a1 )
>>
>> ## I have checked the above function with the ten Cryptohack challenge
>> ## numbers against the implementation in SymPy, and they are
>> ## equivalent.  That's not a /proof of correctness/, but will do for
>> ## now.
>>
>>
> 
> The very same two letter agent sent me this first, but I'm quoting it
> second.  It's also been cleaned up in an Emacs before pasting into Thun-
> derbird.
> 
> --------------------------------------------------------------------
> Johann,
> 
> Replying again to your real address (my first attempt went to
> the .invalid header, which can't resolve). You said the ten
> Cryptohack vectors aren't a proof, only a smoke test. You're
> right, and the gap is wider than you flagged. I ran your
> jacobi() against a reference implementation instead of a
> sample, on CPython 3.11.6.
> 
> On the domain you intend (a >= 0, p odd >= 3) it is clean:
> exhaustive over p odd 1..299 x a 0..399, plus 20,000 random
> pairs with p up to 10^12. Zero divergences. The core is right,
> well past ten vectors. Now the edges, where the vectors don't
> go.
> 
> 1. No domain guard. Jacobi needs p odd and >= 3. Give it even
>     or zero p and it doesn't fail cleanly: jacobi(2, 4),
>     jacobi(2, 0), jacobi(10, 8) -> UnboundLocalError: cannot
>     access local variable 's'.  s is only assigned when k is
>     even, or (k odd) when p & 7 is 1/3/5/7. An even p leaves it
>     unbound.  jacobi(3, 2) returns -1 and jacobi(5, 4) returns
>     1: silent garbage, no error.  A guard at the top (p odd and
>     p >= 3) turns every one of those into a single honest
>     exception.
> 
> 2. Negative a is silently wrong. jacobi(-97, 3) should be -1;
>     yours returns 0. Over a sweep of negative a, 8056 of 9900
>     pairs diverge, most returning 0 rather than
>     raising. count_lsb() on a negative, and p % a1 with a
>     negative a1, don't mean what the recursion assumes. If you
>     want the Kronecker symbol, reduce a %= p before the k/a1
>     step.
> 
> 3. jacobi(0, 1) returns 0; the convention (and SymPy) say
>     1. Your a == 0 branch returns 0 unconditionally. One line:
>     return 1 if p == 1 else 0.
> 
> 4. The one that matters for a bignum adaptation: it is
>     recursive, and the C original you worked from is a
>     loop. Depth grows with input size. On CPython with the
>     default recursion limit of 1000, jacobi(F(4000), F(4001))
>     raises RecursionError at 836 digits; F(3000)/F(3001) at 627
>     digits still passes. For a function whose point is
>     125000-bit integers, that ceiling is low. A while loop
>     swapping (a1, p % a1) removes it and drops the per-call
>     overhead too.
> 
> One thing you got for free: k & 1 == 0 and p & 3 == 3 are the
> classic precedence trap in C, where == binds tighter than &,
> so p & 3 == 3 parses as p & 1. In Python & binds tighter, so
> they parse as you meant. If you ever port this back to C, add
> the parentheses.
> 
> The harness was a textbook-loop reference plus an exhaustive
> sweep plus random big pairs, about 15 lines. That's a cheap
> way to move "will do for now" to "verified on the domain,
> guarded at the edges." Happy to send it if you want it.
> 
> Honesty
> --------------------------------------------------------------------
> 
> Dear Honesty,
> 
> Yes, you can send me the harness if you see this reply.
> 
> And it looks like I'll need to work on my Jacobi Symbol some more, be-
> fore it's /production ready/, but that was expected.
> 
> Best wishes, and happy Python!

Dear Honesty,

I've decided to switch gears, and make a little game in Python, rather
than continue with Cryptohack.  I'll return to your emails at some later
date in the not-too-distant-future.


Best wishes, and happy two letter agencies!
-- 
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 ( ;; ) _:;
Federated at https://fed.brid.gy/bsky/myrkraverk.bsky.social

[toc] | [prev] | [next] | [standalone]

#198027

On 9/20/2026 4:32 AM, Johann "Myrkraverk" Oskarsson wrote:
> 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?

For instance, here is the utility function in LibTomMath, mp_cnt_lsb(),
chosen because I was looking at the Jacobi Symbol algorithm in Tom St
Denis' book, /BigNum Math/ when I came across this little optimization.

   https://github.com/libtom/libtommath/blob/develop/mp_cnt_lsb.c

I presume all erudite readers of comp.lang.python already have a physi-
cal copy on their shelf, but I can link the PDF in the GitHub assets if
requested.  Please turn to page 270, line 057 in the code listing.

I have added comp.lang.c, if anyone needs the standard thumpers to
explain the code in the link, and sci.math, if anyone needs an expla-
nation of the mathematics.

For the latter, I use /Graduate Texts in Mathematics #84/,

   /A Classical Introduction to Modern Number Theory/

by Kenneth Ireland, and Michael Rosen.  See

   https://link.springer.com/series/0136

for the entire series.  I do not use L.L.Ms. to grok mathematics.


So, presuming this is a standard function in all multiprecision arith-
metical libraries, why can't we just do this directly in Python?
-- 
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 ( ;; ) _:;

[toc] | [prev] | [next] | [standalone]

#198029

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> writes:
>   ( n & -n ).bit_length() - 1

This formula is very famous.  In twos complement arithmetic, -n is (1
plus the bit complement of n_.  So first, turn all the rightmost 0's
into 1's.  The 1 immediately to the left of the rightmost 0 (call this
bit # k) turns into a 0.  All the other bits are similarly inverted.

Now add 1.  So the now-rightmost block of 1's turn back into 0.  Bit # k
turns back into 1.  And all the other bits stay inverted.

Now AND.  All the upper bits are ANDed with their complements so they
become 0.  Bit # k remains 1.  And all the bits below it are 0.  So
you've zeroed all the bits except the 1 immediately to the left of the
block of 0's that you're interested in.  The bit length is the length of
(the block you want plus the leading 1).  So subtract 1 to adjust for
the leading 1 being counted.  Done.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web