Saturday, 23 September 2017

elementary number theory - Simple modulus algebra - rabin karp weird implementation



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=(314153104)10+9



now if I apply the modulus operation (mod) 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?


Answer



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.


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...