How does this work?↵
↵
/predownloaded/68/b2/68b25c98d31cb928ad6742739a829415a4af44e6.pngllui mul_mod(llui a, llui b, llui m){↵
llui y = (llui)((float64)a*(float64)b/m+(float64)1/2);↵
y = y * m;↵
llui x = a * b;↵
llui r = x — y;↵
if ( (lli)r < 0 ){↵
r = r + m; y = y — 1;↵
}↵
return r;↵
}↵
↵
For example if we do c = (a+b)%m;↵
↵
What if a+b itself causes the overflow that is a+b is larger than the size of typeof a or b.↵
↵
Doesn’t x in the above image cause overflow that is a*b is larger than a size of llui.↵
↵
Here llui means long long unsigned int and lli means long long int and float64 stands for long double
↵
llui y = (llui)((float64)a*(float64)b/m+(float64)1/2);↵
y = y * m;↵
llui x = a * b;↵
llui r = x — y;↵
if ( (lli)r < 0 ){↵
r = r + m; y = y — 1;↵
}↵
return r;↵
}↵
↵
For example if we do c = (a+b)%m;↵
↵
What if a+b itself causes the overflow that is a+b is larger than the size of typeof a or b.↵
↵
Doesn’t x in the above image cause overflow that is a*b is larger than a size of llui.↵
↵
Here llui means long long unsigned int and lli means long long int and float64 stands for long double
