Modulo Multiplication:

Revision en2, by RNR, 2017-10-05 21:14:36

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 — 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

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 &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)