Can Modulo be Distributed?

Question

It can in Math, but I came across this when I was looking into Rabin-Carp string searching algorithm. The hash function they used (source: wikipedia: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm#Hash_function_used) was this:

[(104 × 256 ) % 101  + 105] % 101  =  65

How is this better than deleting the inner mod operator so you only have one on the outside? As so:

[104 × 256  + 105] % 101

As far as I can tell it should give the same result, and mods are generally expensive operations, so wouldn't it be better to have one?

The only thing I can think of is concerns about overflow, but if that were the case, the multiplication would be similarly split up, like so:

(104 % 101 × 256 % 101 ) % 101  + 105] % 101  =  65

user_436560 · Answer

When you implement a formula, in general you try to have the very same outlook. Let's suppose that the formula looks like this:

[(x × y ) % z + t] % w

In our case z and w have the very same value, but they could be different. If you simplify the formula to match your case, then in the future, if the differences between z and w start to creep in, then you will have trouble finding out what was meant by the code. Yet, if z and w are entangled and it is guaranteed that they will be entangled in the future as well, then you might consider this simplification. Yet, you also need to be careful while doing so, because if x and y are fairly large, then you might have some number overflow issues in some cases when adding t to it. Also, if t is very large, you might have number overflow problems.

As about your question,

[a % b + c] % b

is equivalent to

[a + c] % b

mathematically. But in the actual code there might be some nuances that justify the seemingly superfluousness of the code.

Can Modulo be Distributed?

1 Answers