-synx-'s blog

By -synx-, history, 6 months 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  

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

From http://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;
}
  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you for your reply!
    I am aware of this solution, but it is indeed slow due to floating point multiplication!
    I was looking for a solution involving some bitwise trick to calculate the following two things:

    (c»61) and (c&M61)