Modulo Multiplication:

Revision en1, by RNR, 2017-10-05 21:12:58

How does this work?

/predownloaded/68/b2/68b25c98d31cb928ad6742739a829415a4af44e6.png

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

Tags modular arithmetic, multiplication, c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English RNR 2017-10-05 21:20:21 20 Tiny change: 'lui r = x — 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)