12
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ There is a bug in the above: The termination condition should not be $s < q$, but running out of digits of $p$. $\endgroup$ Commented Mar 27, 2016 at 20:16
3
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ 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? $\endgroup$ Commented Aug 17, 2013 at 3:16
  • $\begingroup$ @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. $\endgroup$ Commented Aug 17, 2013 at 9:45
  • 3
    $\begingroup$ 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".) $\endgroup$ Commented Aug 17, 2013 at 10:25
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Aug 17, 2013 at 11:27
  • $\begingroup$ 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. $\endgroup$ Commented Aug 17, 2013 at 12:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .