-synx-'s blog

Mersenne Prime — M61 for Hashing
By -synx-, history, 7 years ago, In English


It is easy to calculate modulus using this prime (with bitwise operations, it is well known)!
My question is how can we efficiently calculate , where a and b can both have at most 61 bits.

UPD: Found a function here that multiplies 64 bit with 32 bit while maintaining modulo. Can it be extended for 64 bit multiplied with 64 bit efficiently?

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From http://codeforces.net/blog/entry/1729?locale=ru#comment-32989

long long mul( long long a, long long b, long long m ) {
  long long q = (long double)a * (long double)b / (long double)m;
  long long r = a * b - q * m;
  return (r + 5 * m) % m;
}
→ Reply