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 = v1;
str = 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.