# Time complexity of a modulo operation

I am trying to prove that if $p$ is a decimal number having $m$ digits, then $p \bmod q$ can be performed in time $O(m)$ (at least theoretically), if $q$ is a prime number. How do I go about this?

A related question is asked here, but it is w.r.t to MATLAB, but mine is a general one.

The relevant text, that I am referring: chapter 32 -String Matching, PP:991, "Introduction to Algorithms" 3rd edition Cormen et al.

-

I will assume that $q$ is not part of your input, but rather a constant. Then, Algorithm D in 4.3.1 of Knuth's book "The Art of Computer Programming" (Volume 2) performs any long division in $O(m)$ steps.

-
This is not very helpful to anyone who doesn't have the book at hand (including quite possibly the OP): any chance you could explain here what "Algorithm D" is? –  ShreevatsaR Aug 17 '13 at 3:16
@ShreevatsaR: No offense, but that would be quite time-consuming. In addition, it feels rather pointless (to me personally) when there is a reference that does explain it. I would suggest a library. –  Jesko Hüttenhain Aug 17 '13 at 9:45
Sure. Just observing that this answer isn't very useful in that case. :-) (After all, most questions can be answered by "go to a library".) –  ShreevatsaR Aug 17 '13 at 10:25
@ShreevatsaR: You're right. Absolutely 100% right. I frankly don't expect any upvotes. But since the question was unanswered and doesn't seem to get that much attention, I thought a literature reference is better than nothing =D. –  Jesko Hüttenhain Aug 17 '13 at 11:27
Oh I didn't notice this was an unanswered question from long ago. :) I agree with you. This was bumped up today, for some reason, perhaps because it had no answers with upvotes... I've voted this up to fix. :-) Let me see if I can also post a short answer. –  ShreevatsaR Aug 17 '13 at 12:13

Assuming (as Jesko does) that $q$ is a constant and not part of the input, the usual long-division algorithm you learn at school will do quite nicely. The algorithm is the following:

1. Compute multiples $q$, $2q$, $3q$, $4q$, $\dots$, $10q$. This takes constant time, as it's independent of $q$.

2. Say $q$ has $k$ digits. Start with the first $k$ digits of $p$. Call this string $s$.

3. Compare it against each of the $10$ multiples of $q$; whichever $cq$ is the largest one smaller than $s$, write down $c$ as a digit of answer, subtract $cq$ from $s$, and "bring down" the next digit of $p$. That is, set $s$ to be $(s - cq)$ concatenated with the next digit of $p$.

4. If $s < q$, then it's your answer, stop. Else, go back to step $3$ and repeat.

Here's an image from Wikipedia, for the example of $q = 37$.

-