RNR's blog

By RNR, history, 7 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RNR (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

typedef long long unsigned int llui;

typedef long long int lli;

typedef long double float64;

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;

}

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RNR (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RNR (previous revision, new revision, compare).