Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
I think you're right, what bothers me is that I spent something like 2 hours trying to figure out what was the purpose... all this could be avoided if the author of the paper I'm reading had explained it in the first place –  John Smith Sep 15 '12 at 17:19
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. –  Bill Dubuque Sep 15 '12 at 17:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.