Modulus of a Big number

 How to Evaluate Modulus of  very large numbers ?

We know the modular addition property which is:

IF N = a + b, then N % n = ( a + b ) % n . Which can be written as :
 

N % n = ( ( a % n ) + ( b % n) ) % n

Lets say we want to calculate 123456 % 7 . Let's consider  :

For a number 123 % 7 it can be evaluated as  ( 120 + 3 ) %7

Now 12 = 12 + 12 + 12 + ............ + 12 ; adding 12, 10 times will give us 120. So

Applying the modular addition formula we get :

 ( ( 12 +12+12+.........+12)  + 3 ) ) % 7

(  ( 12 % 7 ) + ( 12  % 7 ) + ........ + ( 12 % 7 ) + ( 3 % 7 ) ) % 7

( ( 12 % 7) * 10  + ( 3 % 10 ) ) % 7

Now the modulus of the number 123456 can be represented like this:

1 % 7 -> ( 0 *10 + 1 ) % 7

12 % 7 -> ( 10+2 ) % 7= ( 1 % 7 )*10 + ( 2 % 7) ) % 7  

123 -> ( 120+3 ) % 7 = ( (12 % 7 ) * 10 + ( 3 % 7 ) ) % 7

1234 -> ( 1230+4 ) % 7 = ( (123 % 7 ) * 10 + ( 4 % 7 ) ) % 7

12345 -> ( 12340 + 5 ) % 7 = ( (1234 % 7 ) * 10 + ( 5 % 7 ) ) % 7

123456-> ( 123450 + 6 ) % 7 = ( (12345  % 7 ) * 10 + ( 6 % 7 ) ) % 7

We find a pattern that if we take all the digits before the last digit and then multiply it's modulus to 10 , then add it to the modulus of the last digit then take it's modulus we find the modulus of the original number . If we do it from a bottom up approach we can find the modulus of the first digit then multiplying it by 10 then adding to the modulus of the next digit we get the modulus of the number made  from  the first two digits. If we recursively keep doing that till the last digit then we will get the modulus of the entire number . 


So this process can be formulized into an algorithm: 

int res = 0 ;
 
for ( int i = 0 ; i < n.size() ; ++ i )
{

    res = res *10 + n[i] - '0' ) % m ;

}

cout<<res;

The time complexity will be O(N) the size of the string of the number.