@Aamir: Something like this might work:
n %= p;
m %= p;
result = 0;
while( m )
{
if( m & 1 )
{
result += n;
if( result >= p )
result -= p;
}
m >>= 1;
n <<= 1;
if( n >= p )
n -= p;
}
What this does is similar to the elementary school method of
multiplying multi-digit numbers, in this case in binary, and where
arithmetic is mod p. I'm assuming that m, n, and p are positive, and
that 2*n and 2*p each fit in a long long.
Dave
On Oct 21, 12:26 pm, Aamir Khan <[email protected]> wrote:
> Lets say n,m and p are three long long integers.
>
> i want to calculate (n*m)%p.
>
> If (n*m) overflows the limit of long long then the answer would be wrong.
> Moreover if i do ((n%p)*(m%p))%p then also there is no certainty of getting
> correct answer.
>
> How should i do this in C++ ?
>
> --
> Aamir Khan | 3rd Year | Computer Science & Engineering | IIT Roorkee
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
