0
$\begingroup$

I'm studying the Rabin Karp algorithm and something isn't clear about the modulus algebra:

Let's suppose I have all base-10 numbers for simplicity's sake

$14159 = (31415 - 3 \cdot 10^4) \cdot 10 + 9$

now if I apply the modulus operation ($\bmod 997$) to each term I get:

$201 = [ (508 - 3 \cdot 30) \cdot 10 +9 ] \bmod 997$

but in the algorithm I'm studying there is this line:

$201 = [ (508 + 3 \cdot (997-30)) \cdot 10 +9] \bmod 997$

interestingly to me, the result is the same: $201$.

Why do they used the second version? Is there something I'm not considering and the $3 \cdot 997 \cdot 10$ term is useful to something?

Edit: I was wondering... does adding a large prime number (like 997) has some algorithmic implications?

1 Answers 1

1

Hint $\rm\ mod\ 997\!:\ -30\, \equiv\, 997-30.\:$ This is probably done to keep the remainders positive.

Note that $\rm\: 1000\equiv 3\:\Rightarrow\: 31415\, =\ 31\cdot 1000 + 415\,\equiv\, 31\cdot 3 + 415\,\equiv\, 508,$ etc.

  • 1
    @John Though it is often convenient to work with a *balanced* residue system, e.g. $\rm\:\pm\{0,1,2,3\}\ mod\ 7,\:$ many textbooks (and algorithms) work only with the least *positive* representatives (remainders). It's usually easy to infer which is being empoyed. For algorithms it is essential to know wich is employed, e.g. for testing equality (congruence), i.e. for reducing to *canonical* normal forms.2012-09-15