f=lambda x,n,b=1,i=1:n and f(x,n-1,b-(b&i)*~-x,i+i)or b%i
Outgolfed all you snek users (except for the
pow(x, -1, 2**n) cheapshots) with nothing but pure algorithm.
Try it online! (Only uses Python 3.8 for comparison against
def func(value, shift, acc = 1, mask = 1):
if value != 0:
return func(value, shift - 1, acc - (acc & mask) * (value - 1), mask << 1)
return acc & (mask - 1)
Or, as a loop with size hacks removed:
def func(value, exponent):
value -= 1
acc = 1
for i in range(exponent):
if acc & (1 << i):
acc -= value << i
return acc & ((1 << i) - 1)
The function is a lambda called
f. It takes two positive integers, and returns either the multiplicative modular inverse or zero.
You may be wondering what the heck is going on. This uses a different, faster, and smaller algorithm for modular inverse for powers of 2 instead of the Euclidian approach.
I'm not going to go too far into the details of why it works, as it is really complex and explained better by others. Translation: even I don't fully understand it.
This set of algorithms is explained here on algassert with a related algorithm explained here on Crypto SE with some interesting papers linked.
This algorithm actually uses no true multiplication (just shifts), the multiplication is just a shortcut for size.
This naturally returns
0 for even numbers, as the odd subtraction (we start with
x - 1) causes a chain reaction of trailing with
0b0, which, when masked off, turns the result to zero. No need for a manual sentinel.
0000 0001 - 0000 1101 -> 1111 0010
1111 0010 - 0001 1010 -> 1110 0000