Newbie questions about hash

Python Help
7

That works fine, but division by a single digit goes pretty fast regardless. 64-bit CPython uses 30-bit “digits” under the covers, and multi-digit operations are much slower. For mod 7, this code works without division (& much the same works to compute mod 2**k-1 for any k > 1, prime or not):

def mod7(n):
    assert n >= 0
    result = 0
    while n:
        result += n & 0b111
        n >>= 3
        if result >= 7:
            result -= 7
    return result

from itertools import chain
start = 897987987987987987016874685654
for n in chain(range(100), range(start, start + 1_000_000)):
    assert n % 7 == mod7(n), n

but takes O(n.bit_length()) time. Just peeling off the last 3 bits (as CPython actually does) takes tiny constant time regardless of how large n is.

1 Like