Optimal Algorithm for checking if a number is a multiple of three

Question

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?

Answer 1

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

Answer 2

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?

Answer 3

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

Answer 4

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.

Answer 5

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