5
$\begingroup$

I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation.

I currently have an assignment to work on:

An algorithm reads in the binary digits of a positive integer $N$ and determines whether $N$ is a multiple of 3. Show that the algorithm takes time at least of order $n$, where $n$ is the number of binary digits of $N$.

Basically, I have thought up of an algorithm which I'm pretty sure is correct: (I don't know what's the best/correct way to write an algorithm but here's my attempt)

  1. Start with a binary number $x=a_na_{n-1}\dots a_1a_0$.

  2. Then compute $x'=\sum^{i=n}_{i=0} (\frac{3}{2}+\frac{1}{2}(-1)^{i+1})a_i$.

  3. Then $x'=0 \mod3 \iff 3|x$

This works because $2^{2k}=1\mod3$ and $2^{2k+1}=2\mod3$

I can guess that my algorithm takes time at least of order $n$ because I need order $n$ steps to compute $x'$.

However, I have my doubts:

  1. How do I know my algorithm is the optimal algorithm?

  2. Am I 'cheating' by saying $x'=0 \mod3 \iff 3|x$?

  3. Am I even answering the question correctly by providing such an algorithm or is there some other sort of analysis to show lower bounds for algorithm time?

$\endgroup$
3
  • $\begingroup$ Note that you should usually restrict yourself to one question per port, but I think yours are reasonably scoped and can be dealt with in one answer. $\endgroup$
    – Raphael
    May 5, 2014 at 23:26
  • 1
    $\begingroup$ related Algorithms computing if a number is a multiple of 3 $\endgroup$ May 5, 2014 at 23:40
  • 1
    $\begingroup$ You can also think of it in this way: for binary numbers, each binary digit can influence the divisibility by 3. As such you have to "do something" with each digit, so at least N "somethings" for N digits. $\endgroup$
    – PlasmaHH
    May 6, 2014 at 9:44

5 Answers 5

9
$\begingroup$

If an algorithm that takes less than $O(n)$ time, this means that the algorithm won't be able to look at all the digits of the number. Thus you can prove a lower bound of $O(n)$ by showing that you have to look at all (or almost all) digits of the number in order to decide divisibility.

To show the latter property, assume you had an algorithm that decides divisibility by 3 by looking at $n-2$ or fewer of the digits. This gives you 2 digits that you can set freely, since the algorithm has to give the same answer for any choice of these digits (it doesn't look at them) and it has to be always correct. However you can show that no matter where these digits are and what the value of the remaining digits is, you always have a choice for the digits that gives a number divisible by 3 and another choice that doesn't. Thus, the assumed algorithm can not exist. (I'll leave it to you to show the existance of such choices.)

$\endgroup$
4
  • $\begingroup$ Why not $n-1$ though? $\endgroup$
    – Haikal Yeo
    May 6, 2014 at 9:59
  • 1
    $\begingroup$ There are situations, where you can flip a (specific) single bit without affecting divisibility by 3. E.g. for "10?" you can set the last bit (?) to either 0 or 1 and get a number not divisible by 3 both times. $\endgroup$
    – FrankW
    May 6, 2014 at 10:13
  • 1
    $\begingroup$ Yes, an algorithm that looked at $\frac n2$ digits would still be $O(n)$ (if it didn't do too much other stuff). But why should I prove a lower bound of $\frac n2$, if I can prove one of $n-2$? $\endgroup$
    – FrankW
    May 6, 2014 at 10:23
  • $\begingroup$ The same argument works in many cases: If you can prove that you cannot determine the correct result by looking at n-1 of n input items, then a lower bound for running time is O (n). And all you have to prove for this is that if I could change one item after you give the answer, I could turn your answer into a wrong one. Any other lower bounds are usually very, very difficult to prove. $\endgroup$
    – gnasher729
    Dec 16, 2016 at 21:48
6
$\begingroup$

Answering your questions one by one:

  1. From what you know, you don't; you'd have to show that no algorithm can be better, that is it attains a (tight) lower bound.

  2. I don't know what you mean by "cheating". If it's valid, it's okay, unless you are not allowed to use the modulo operation.

    However, is it valid? What do you compute in step 2?

  3. No, not at all! Providing an algorithm with a certain runtime only proves an upper bound on the complexity of the solved problem. Lower bounds are tougher; there is no genereal method that I know of.

Some notes and hints that might get you on the right track:

  • You give very abstract pseudo code; it's level is often okay when communicating ideas of algorithms, but can get you in trouble when analysing runtime. There are many examples for more detailed ("lower level") pseudo code around, e.g. here.
  • Remember elementary school. Is there a simple property by which you can tell if a number is divisible by three?
  • Which cost model do you assume? The algorithm you give does take linear time in the uniform cost model, but not in the logarithmic model.
  • Towards a lower bound, assume a (deterministic) algorithm that solves the problem could do so without looking at all digits of the input number. What can you conclude?
$\endgroup$
4
$\begingroup$

Let's answer your questions one by one:

  1. You have a misunderstanding here. There is no clear notion of "the optimal algorithm", for two reasons. First, it depends on the exact computational model. Second, usually it is too much to expect to obtain the absolute optimal algorithm. Therefore we usually only worry about optimality up to multiplicative constants (big O), or if we want to be more careful, optimality up to lower order factors. In the first case, given an algorithm with running time $O(f(n))$, we would like a matching lower bound of $\Omega(f(n))$. In the second case, given an algorithm with running time $f(n)$, we would like a lower bound of $f(n) - o(f(n))$.

  2. You are totally cheating. You could just as well compute $x \pmod{3}$ at the outset. It is true that $x'$ is much smaller than $x$, but still it needn't be constant size. Moreover, even your addition in the second step of your algorithm is problematic since the summand gets bigger and bigger.

  3. Lower bounds are not shown by giving algorithms. (Unless in a very fancy way, like in Ryan Williams' recent work).

The standard way to compute the residue modulo 3 is as follows:

  1. Initialize $a$ to $0$.

  2. For $i$ from $0$ to $n$, compute $a \gets (a + x_i) \pmod{3}$. (You can implement this instruction using a table if you wish.)

This takes $O(n)$ time in any reasonable computation model (even a Turing machine, if you're very careful). There is also an equivalent way of stating this algorithm using finite automata, which amounts to the very same algorithm.

Lower bounds in general are very difficult, but here all we need to do is prove a linear lower bound, thus showing that the algorithm is optimal up to multiplicative constants. The trick is showing that the algorithm needs to read all the input bits. The reason is that $2^i \not\equiv 0 \pmod{3}$ for all $i$. I'll let you fill in the details. (The analysis become simpler if you allow leading zeroes).

$\endgroup$
2
  • $\begingroup$ I apologise for my misuse of the the phrase 'the optimal algorithm'. I was referring to the possibility that there may exist a faster (than linear) algorithm. I also agree that it is cheating and hence felt like I wasn't doing something right. But why does the second step of the algorithm become problematic? Isn't that just dependent on the $n$ terms and hence has running time $O(f(n))$? $\endgroup$
    – Haikal Yeo
    May 6, 2014 at 8:26
  • $\begingroup$ @HaikalYeo It depends on the machine model, but assuming that the machine model doesn't allow $O(1)$ operations on unbounded operands (otherwise you can compute the entire modulo in $O(1)$), then computing the sum takes more than linear time since one of the operands, the running sum, keeps growing and is super-constant. $\endgroup$ May 6, 2014 at 12:52
2
$\begingroup$

It is rather easy to construct a DFA that recognizes the language of binary strings divisible by 3. States are the residue classes modulo 3, your transition function is $\delta (q, d) = (2 \cdot q + d) \bmod 3$, initial and final state is 0.

The exact same construction works for other bases and divisors.

In any case, no algorithm can take less than $O(n)$, where $n$ is the length of the string; this is optimal.

$\endgroup$
4
  • $\begingroup$ How does one know that $O(n)$ is optimal for this problem? Is this a well-known result, or something that is obvious? $\endgroup$ May 6, 2014 at 1:17
  • $\begingroup$ @Guildenstern, the result depends on all bits (unlike, say, checking if it is divisible by 256). $\endgroup$
    – vonbrand
    May 6, 2014 at 1:26
  • $\begingroup$ @vonbrand: Specify that your program accepts input in base 3, with the tape positioned at the ones digit. Bingo--O(1). $\endgroup$
    – supercat
    May 6, 2014 at 2:01
  • 1
    $\begingroup$ @supercat, here the input is binary. $\endgroup$
    – vonbrand
    May 6, 2014 at 2:16
1
$\begingroup$

Actually you gave the answer yourself: since $2^{2k}=1\mod3$ and $2^{2k+1}=2\mod3$, one must consider all $n$ binary digits to check if the number is a multiple of $3$, there is no way around. Hence any algorithm is at least $O(n)$. This is the answer to the question, there is no need to provide an algorithm which is $O(n)$.

$\endgroup$
2
  • $\begingroup$ But this is dependent on the algorithm that I'm using right? How do I know that there is no faster (than linear) algorithm out there that doesn't use this property? $\endgroup$
    – Haikal Yeo
    May 6, 2014 at 8:23
  • $\begingroup$ This is not dependent on the algorithm you choose. Since every binary digit is either = 1 or = 2 mod 3, every single digit must be considered, as it can change the value of x mod 3. $\endgroup$ May 6, 2014 at 10:57

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.