1
$\begingroup$

In the Time Complexity section of this Wikipedia article, it states

In the algorithm as written above, there are two expensive operations during each iteration: the multiplication s × s, and the mod M operation. The mod M operation can be made particularly efficient on standard binary computers by observing that $k ≡ ( k \mod 2^n ) + ⌊ k / 2^n ⌋ ( \mod 2^n − 1 ) $

This says that the least significant n bits of k plus the remaining bits of k are equivalent to k modulo $2^n−1$. This equivalence can be used repeatedly until at most n bits remain. In this way, the remainder after dividing k by the Mersenne number $2^n−1$ is computed without using division.

I am having difficulty understanding what this is saying. Is it presenting a method for calculating the residue that is faster than long division? What is $k$? Is there two different types of "mod" where the first is a binary operator and the second means instead of being equivalent the equation is congruent? I find it hard to understand how one formula can have two "mods".

What do bits have anything to do with this?

$\endgroup$
1
  • $\begingroup$ remember that $M$ is a Mersenne number in this context... $\endgroup$ Feb 25 '20 at 13:16
2
$\begingroup$

This algorithm computes $k \mod M$ where $k$ is any integer (the input) and $M$ is a Mersenne number, ie there is an integer $n$ such that $M = 2^n - 1$.

The bits are just the digits of $k$ expressed in basis $2$. The example in the Wikipedia article you quote illustrates this very well.

Say $M = 2^n -1$. Remember that any int $k$ is stored by the computer as its binary expression $k_2$, and the computer performs all arithmetic computations in basis 2. Hence :

  1. computing $k \mod 2^n$ is very easy : just take the last $n$ digits of $k_2$.

  2. finding $\lfloor \frac{k}{2^n}\rfloor$ is also very quick : just remove the last $n$ digits of $k_2$.

  3. let $x$ be a number whose binary expression $x_2$ has $\leqslant n$ digits, then computing $x \mod (2^n - 1)$ is a piece of cake :

$$ x \mod (2^n - 1) = \left\{ \begin{array}{ll} 0 & \textrm{if } x_2 = \underbrace{1 \dots 1}_{n \textrm{ times}} \\ x & \textrm{otherwise} \end{array}\right.$$

$\endgroup$
7
  • $\begingroup$ So the whole point is this algorithm gives a faster way to compute $k \mod{M}$ faster than using long division to find the remainder? $\endgroup$
    – northerner
    Feb 26 '20 at 9:14
  • $\begingroup$ Yes that is the point, effectiveness. $2^n -1$ becomes large very quick, so dividing by $2^n -1$ is costly. $\endgroup$ Feb 26 '20 at 9:24
  • $\begingroup$ In terms of the notation, what does it mean when mod is in between two operands versus at the end in brackets? For example is $(k \mod{2^n})$ a binary operator that takes remainder of k divided by $2^n$ where as the $(mod {2^n-1})$ at the end means the left side of the equation is congruent to that? $\endgroup$
    – northerner
    Feb 26 '20 at 23:36
  • $\begingroup$ @northerner Yes, you are correct. $\endgroup$ Mar 2 '20 at 7:40
  • $\begingroup$ The Wikipedia article states "It will produce $2^n−1$ for a multiple of the modulus rather than the correct value of 0". In your point 3. is this accounted for, or does this an additional special case? Thanks in advanced. $\endgroup$
    – northerner
    Mar 20 '20 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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