I was reading Robert Sedgewick's book, in the Chapter 16 Hashing, the author says that using Horner's method and according to mod function's arithmetic properties, we can compute hash function for a big integer without overflow.

Here is the number and the function

 
((((((((((22*32 + 5)*32) + 18)*32 +25)*32 + 12)*32 + 14)*32 + 7)*32 + 11)*32 + 5)*32 + 25)
 
unsigned hash(char *v) {
  int h;
  for (h = 0 ; *v != '\0'; v++) {
    h = (32*h + *v) % M;
  }
  return h;
}
 

The Horner's method indicate that we can write down a polynomial as the form above.

To understand the algorithm, we need two principles of mod function arithmetic.

 
1.(a + b) % p = (a % p + b % p) % p
1.(a * b) % p = (a % p * b % p) % p 
 

Lets see why this algorithm works. To make it simple we start with two digit.

 
(v1*32) + v2
 

We should prove that

 
str[0] = v1;
str[1] = v2;
((v1*32) + v2 ) % M = hash(str)
 

Observing the algorithm, the computation process is the same as

 
(32 * (v1 % M) + v2) % M
 

Lets apply the two principles on these two formula

 
(v1*32 + v2) % M
->
((v1*32) % M + v2 % M ) % M
->
((v1%M * 32%M) % M + v2 % M ) % M
 
and
 
(32 * (v1 % M) + v2) % M
->
((32 * (v1 % M)) % M + v2 %M ) % M
->
(32%M * (v1%M)%M) % M + v2 %M ) % M
 

The only difference between the two results is (v1%M)%M and v1%M.

One of the rule about mod function is you can repeatedly apply the same mod function on a number but the result is the same.

For example 5 % 3 = 2, (5 % 3) % 3 = 2, ((5 % 3) % 3) % 3 = 2. Thus

 
(v1%M)%M == v1%M
 

So the algorithm will works. Proving process is the same for more digits.