I am trying to hash an $n$-character string into one of $m$ slots by treating the string as radix-128 number without overflowing a 32-bit word, where $0 < m < 2^{31}$.

I utilize the properties of modular arithmetic and horner's method for computing polynomials to get the following procedure.

for i=0...n-1
    s = (((s mod m)*(128 mod m)) mod m + string[i] mod m) mod m
return s

However, for $m>128$, some mod calculations simplify and our largest possible value is 128*(m-1). Thus to avoid overflow we should have

$128(m-1) \leq 2^{32}-1$

$m \leq 2^{25} + 127/128$

What am I doing wrong here?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.