Блог пользователя -synx-

Mersenne Prime — M61 for Hashing
Автор -synx-, история, 7 лет назад, По-английски


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?

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

From http://mirror.codeforces.com/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;
}
→ Ответить