# $n \pmod k$ circuit

I wondered if, for a fixed integer $$k ≥ 3$$, how can I construct a circuit for each $$n \in \mathbb{N}$$, that takes as input an n-bit integer $$x$$ and outputs whether 3 divides $$k$$?

Considering an n-bit integer as input: e.g. $$\ldots10101110$$, where $$a_0$$ is the rightmost bit and $$a_N$$ the leftmost bit, $$\bmod 3$$ has a cycle of $$2$$:

$$(a_0 \times 2^0 + a_1 \times 2^1 + a_2 \times 2^2 + a_3 \times 2^3 + \ldots) \bmod 3\\ = a_0 \times 1 + a_1 \times (-1) + a_3 \times 1 + a4 \times (-1) \ldots$$

so it has a cycle of two, considering the remainder being either 1 or (-1).

How can I use this knowledge to construct a boolean circuit that checks for an n-bit integer as input the divisibility by 3?

Additionally: Once solved for $$k = 3$$, how can I generalize this to any fixed k? The idea behind this is to create a circuit whose sizes should be polynomial in n.

Important: Please give hints only so I can figure it out myself!

• Isn't it the coefficient alternating between ±1? The remainder should be 0 every once in a while. Aug 16 at 9:07
• if you are familiar with finite state automaton, you can try to design an automata that reads the binary encoding from the most significant bit to the least and ends in a state that corresponds to $n \mod k$. Now, you can "unfold" the automaton to make a circuit for each size $n$.
– holf
Nov 30 at 10:20

Sadly, my knowledge of circuits is quite limited, so I will try to answer the question algorithmically. If You go through your bits from most to least significant, You could reconstruct Your number as follows:

number = 0

foreach bit in [a[n-1], a[n-2], ..., a[n]] do
number = 2*number + bit
end foreach

return number


This can be done by a simple shift followed by an increment per iteration. But, of course, the number might be huge and we are only interested in the remainder. So instead we can can use modular arithmetic to only build the remainder:

remainder = 0

foreach bit in [a[n-1], a[n-2], ..., a[n]] do
remainder = (2*number + bit) mod k
end foreach

return remainder


Since 2*remainder + bit <= 2*(k-1) + 1 we can replace the modulo operator by a comparison, conditonally followed by a subtraction:

remainder = 0

foreach bit in [a[n-1], a[n-2], ..., a[n]] do

remainder = 2*number + bit

if remainder >= k then
remainder = remainder - k
end if

end foreach

return remainder


And there You have it. For each bit in $$a$$ you would need:

• 1 Shift
• 1 Increment (e.g. via chain of "flip-flops")
• 1 Comparison
• 1 Conditional Subtraction (e.g. via Ripple-Carry-Adder using two's complement of $$k$$)

That should take around $$\mathcal{O}\left(\left\lceil\log_2\left(2k-1\right)\right\rceil\right)$$ logic gates per bit in $$a$$.

In practice there are of course much more efficient solutions than that. For division algorithms, I can recommend the book Modern Computer Arithmetic. Everything You learn there should be applicable to circuits as well, but You will have to think much more parallel in circuit design, I presume.

For reference, here is a Scala implementation of the algorithm:

def mod( n: BigInt, k: Int ): Int =

require(n >= 0)
require(k >  1)

var rem = 0L

var i = n.bitLength
while i > 0 do
i -= 1
rem *= 2
if n.testBit(i) then rem += 1
if rem >= k     then rem -= k
end while

assert(rem >= 0)
assert(rem <  k)
return rem.toInt

end mod

• Amazing, thanks for the detailed explanation! I spun up some code for it and noticed that this approach indeed works for k=3. Do you know how to do the same for k = 11 for example? This approach doesn't work for all fixed k's. Aug 15 at 15:16
• It should work for every $k >= 2$ if I am not mistaken... Aug 15 at 15:30
• Indeed. Something was off in my previous code. I updated it and posted it here too. Thanks again for your help, I marked it as the solution. Aug 16 at 2:37

Here is some JS code that performs the n mod k operations. To visualize I generate all 8-bit representations and let them run through the function to output a truth table, outputting True if divisible by k and False otherwise. For higher bit-inputs one can adapt the code.

function mod(n, k) {
if (n < 0 || k <= 1) {
throw new Error("Invalid input: n must be non-negative and k must be greater than 1");
}

let rem = 0n; // Use BigInt for arbitrary precision arithmetic

let i = n.toString(2).length; // Bit length of n
while (i > 0) {
i -= 1;
rem *= 2n;
if (n & (1n << BigInt(i))) rem += 1n;
if (rem >= BigInt(k)) rem -= BigInt(k);
}

if (rem < 0n || rem >= BigInt(k)) {
throw new Error("Assertion failed: Invalid remainder value");
}

return Number(rem);
}

// Generate all 8-bit combinations
const allCombinations = Array.from({ length: 256 }, (_, i) => BigInt(i));

// Set the value of k
const kValue = 13;

// Iterate over the combinations and check divisibility by k
const divisibilityResults = allCombinations.map(combination => mod(combination, kValue) === 0);

console.log(divisibilityResults);


Thanks to @DirkT for the ideas.

Given a 3 bit number, we can find a 2 bit number with the same remainder modulo 3. That means we map 0 to 7 to 0, 1, 2, 0 or 3, 1, 2, 0 or 3, and 1. So we take the number xyz and create a circuit C that outputs y’, z’ as follows: If x=0 then y’ = y, z’ = z. If x = 1 then with 4 modulo 3 = 1 we map 1yz to 01 if y = z and to 1y if y ≠ z.

For n >= 3 bits, we use this to transform the first 3 bits to two bits and are left with n-1 bits. Then we feed these two bits and the fourth bit into an identical circuit, get n-2 bits, and so on until we are left with just two bits. At that point xy is divisible by 3 if and only if x=y.

If you want to build super fast hardware then the problem is that you have a chain of n of these circuits in sequence, taking O(n) steps. You can reduce this to O(log n). Use this method for n <= 4. For n <= 8 transform the upper and lower 4 bits into 2 bits each in parallel, then take the resulting 4 bits and handle them as before. For n = 16, split x into 2 x 8 bits, for n = 32 use 2 x 16 bit, for n = 64 use 2 x 32 bits and so on. This takes O(log n) sequential steps.

How many circuits C do we need? n = 4 -> 2 circuits C. n = 8 -> 2x2, plus 2, = 6 circuits. n = 16 -> 2x6, plus 2, = 14 circuits, n = 32 -> 30 circuits, n = 64 -> 62 circuits C. That’s what we need anyway, so the fast circuit for large n doesn’t actually need more hardware.

How to build such a circuit: First build a circuit A which outputs (x = y) for inputs x and y. This is (y AND z) OR (NOT y AND NOT z). Now "01 for y=z, or 1y for y!=z" is done by a circuit which outputs (A AND 0) OR (NOT A AND 1) = NOT A, and another that outputs (A AND 1) OR (NOT A AND y) = A or y, call the circuit with these two outputs B and B'. And finally you have (NOT x AND y) OR (x AND b), and (NOT x AND z) OR (x AND b').

• Thanks for the explanation. This is a neat way of how to reduce the size of the circuit. However, I tried to build a circuit from your idea and had issues realizing this. I simply don't know how I can translate the "if x=0, then output = yz, if x=1, then output is either 01 for y=z, or 1y for y!=z". How do I realize this approach? Aug 16 at 7:11