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 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.

share|improve this question

2 Answers 2

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.

share|improve this answer
    
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$.

From Wikipedia.

share|improve this answer

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.