Calculate modulo of a large number represented as a string

Question

Suppose I have a large number (around 10^5 digits) and I have to calculate num % a where a is less than 10^9 i.e. it is in the int range of C++. There's this code :-

int res = 0;

//num contains the large number stored as a string
for (int i = 0; i < num.length(); i++) {
    res = (res*10 + (int)num[i] - '0') % a; 
    }

return res;

I know that this solution uses modular arithmetic but I don't get why we are multiplying res by 10 at every iteration.

Suppose I have a number 32471. According to this code first step will be (0 * 10 + 3) % a

Why this 10? Should it not be (0 % a + (3 * 10^4) % a) % a and so on, according to modular arithmetic?

Can someone explain how we arrived at this?

Answer 1

I'll be using the following formulas to elaborate your example

A. [a + b] % n = [(a % n) + (b % n)] % n

B. [a * b] % n = [(a % n) * (b % n)] % n

C. [a % n] % n = a % n

So using your example 32471 % a:

1. At first you have 0 + 3 % a which is equal to 3 % a
2. Then you end up doing ((3 % a) * 10 + 2) % a. We can express the following:

Original statement

((3 % a) * 10 + 2) % a

Using formula A

= (((3 % a) * 10) % a + 2 % a) %a

Using formula B

= (((3 % a) % a * 10 % a) % a + 2 % a) %a

Using formula C

= (((3 % a * 10 % a) % a + 2 % a) %a

Using formula B

= ((30 % a + 2 % a) %a

Using formula A

= 32 % a

3. So now you have ((32 % a) * 10 + 4) % a which is, using the similar logic expressed above, equal to 324 % a
4. And then ((324 % a) * 10 + 7) % a which is equal to 3247 % a

And finally you would end up with ((3247 % a) * 10 + 1) % a which is equal to 32471 % a