### -synx-'s blog

By -synx-, history, 12 months ago, ,

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
•

 » 12 months ago, # |   0 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; } 
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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)