$n \pmod k$ circuit

Question

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!

Answer 1

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

Answer 2

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.

Answer 3

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