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 :)
You can use Mersenne primes https://en.wikipedia.org/wiki/Mersenne_prime for such purpose.
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.
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.
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 :<
I don't care on alphabet shuffle. I will use only {'a', 'b'} from alphabet.
Right :<
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.
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.