Modulo Multiplication:
Difference between en2 and en3, changed 27 character(s)
How does this work?↵
↵
- llui 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 &mdash; 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 imagcode 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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English RNR 2017-10-05 21:20:21 20 Tiny change: 'lui r = x &mdash; y;\n- ' -> 'lui r = x - y;\n- '
en3 English RNR 2017-10-05 21:19:11 27 Tiny change: 'the above image cause ov' -> 'the above code cause ov'
en2 English RNR 2017-10-05 21:14:36 269
en1 English RNR 2017-10-05 21:12:58 438 Initial revision (published)