<p><a href="http://en.wikipedia.org/wiki/AC0#cite_note-6">Addition and subtraction of binary numbers are in $\mathsf{AC^0}$</a>. </p>

<p>For any constant number $c$, 
$x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$): 
$$x \bmod c = x - 
(\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}}) $$</p>

<p>It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$ 
which is not a power of $2$. 
Thus $\lfloor x/c \rfloor$ is hard for $\mathsf{AC^0}$ for any $c$ 
which is not a power of $2$.</p>

<p>As noted by Emil in the comments there is an easy reduction for odd prime $c$ 
from $\mathit{MOD}_c$ (that is, $\sum_ix_i\bmod c$ with $x_i\in\{0,1\}$) to 
$x\bmod c$ with binary input: 
we use only input bits which are multiples of $p-1$ and use <a href="http://en.wikipedia.org/wiki/Fermat%27s_little_theorem">FLT</a> ($2^{(p-1)i} \bmod p = 1$).  </p>

CC BY-SA 3.0
2014-12-02T23:33:48.167Z
The same argument applies to any $c$ which is not a power of 2.
Emil Jeřábek
CC BY-SA 3.0
2014-12-02T23:42:37.273Z
That $x\bmod c$ is not AC^0 for other $c$ is easy to show: for instance, we can assume $c=p$ is an odd prime, and then you can reduce MOD_p to it by using every $(p-1)$th bit. Or you can apply the Barrington-Thérien classification: it's a regular language, and its syntactic monoid is a nontrivial group.
Emil Jeřábek
CC BY-SA 3.0
2014-12-02T23:52:49.993Z
@Emil Jerabek: Thanks, this was exactly the help i needed :)
daniello
CC BY-SA 3.0
2014-12-02T22:46:15.827Z
2014-12-03T15:28:54.057Z
2014-12-03T15:28:54.057Z
daniello
<p>Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer.
This is just a shift if $c$ is a power of two, but what about other numbers?
Can we do it with a constant depth circuit for every $c$?
What about $c=3$?</p>

<p>ps. I know that computing $x\bmod c$ is hard, but this seems unrelated.</p>

<cc.complexity-theory><circuit-complexity><ac0>
For what c is division by c in AC0?
domotorp
# For what c is division by c in AC0?

(Asked by: username_0 on 2014-12-02)

Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer.
This is just a shift if $c$ is a power of two, but what about other numbers?
Can we do it with a constant depth circuit for every $c$?
What about $c=3$?

ps. I know that computing $x\bmod c$ is hard, but this seems unrelated.

**Tags:** cc.complexity-theory, circuit-complexity, ac0

---

## 1 answers

### Answer by username_1 on 2014-12-02. Score: 16 | Accepted answer

[Addition and subtraction of binary numbers are in $\mathsf{AC^0}$](http://en.wikipedia.org/wiki/AC0#cite_note-6).

For any constant number $c$,
$x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$):
$$x \bmod c = x -
(\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}}) $$

It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$
which is not a power of $2$.
Thus $\lfloor x/c \rfloor$ is hard for $\mathsf{AC^0}$ for any $c$
which is not a power of $2$.

As noted by Emil in the comments there is an easy reduction for odd prime $c$
from $\mathit{MOD}\_c$ (that is, $\sum\_ix\_i\bmod c$ with $x\_i\in\{0,1\}$) to
$x\bmod c$ with binary input:
we use only input bits which are multiples of $p-1$ and use [FLT](http://en.wikipedia.org/wiki/Fermat%27s_little_theorem) ($2^{(p-1)i} \bmod p = 1$).

> **Comments:**
> **username_2**: The same argument applies to any $c$ which is not a power of 2.  
> **username_2**: That $x\bmod c$ is not AC^0 for other $c$ is easy to show: for instance, we can assume $c=p$ is an odd prime, and then you can reduce MOD_p to it by using every $(p-1)$th bit. Or you can apply the Barrington-Thérien classification: it's a regular language, and its syntactic monoid is a nontrivial group.  
> **username_1**: @Emil Jerabek: Thanks, this was exactly the help i needed :)  

---

