### Kinderr's blog

By Kinderr, history, 7 years ago,

The classical hashing way of hashing a number is keeping it as the reminder of the division with two distinct prime numbers i.e. hash(X) = (X mod prime1, X mod prime2), same thing with strings (considering them as polynomials). But modulo is a very heavy operation, and using a power of 2 (e.g. 2^64, using unsigned long long overflow) instead of a prime number fails when you hash a Thue-Morse sequence, so... Do you know any way of replacing the modulo with a smart bitwise operation or something else? I'd find it extremely useful :)

• +30

 » 7 years ago, # |   +6 You can use Mersenne primes https://en.wikipedia.org/wiki/Mersenne_prime for such purpose.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 Could you please explain how to find module fast for mersenne primes? OR operation on 2^31-1 is not right I guess because it gives mod on 2^31 not 2^31-1.
•  » » » 7 years ago, # ^ |   +49
•  » » » 7 years ago, # ^ |   +56 so write a number x as x = a2n + b and we have . For details, see "Matters Computational" section 39.2.
 » 7 years ago, # |   +2 The problem comes from 'I know your polynomial hash arguments' not from 'your mod is not prime' so you need randomization. I haven't made a research for hashing like mod (2^64 — 1) with random a.
•  » » 7 years ago, # ^ |   0 No, you can shuffle the alphabet and they won't know enough. The mod shouldn't necessarily be prime, but if it's a power of two, when given a Thue-Sequence it will converge to something specific, no matter the character codes :<
•  » » » 7 years ago, # ^ |   +16 I don't care on alphabet shuffle. I will use only {'a', 'b'} from alphabet.
•  » » » » 7 years ago, # ^ |   0 Right :<
 » 7 years ago, # |   +3 In my opinion, when the intended solution is to use hash, then the time limit will consider the "heaviness" of the mod operation so no need to worry.
•  » » 7 years ago, # ^ |   +3 Indeed. But mod operations are generally problematic sometimes when the intended solution does not rely on hashing. Nonetheless, I too, for instance would like to know more about this if there is a way around.