# VHDL interview question - detecting if a number can be divided by 5 without remainder

I saw a nice interview question for VHDL - build a system that receives a number and detects if it can be divided by 5 without remainder. I tried to solve that with a state machine (I suppose they don't want you to use mod or rem) and while I did have initial success (numbers like 5, 10, 15, and numbers such as 20, 40, 80 worked), other numbers like 130, 75 and so on failed for me.

I would show my state machine but it's a complete mess (it's not a code, it's a drawing), and like I said, not even working.

Basically what I tried to do is write down in binary numbers that are divisible by 5, and build a state machine that will work for them.

I would be glad if you could show me how to solve this problem, and how to think when facing something like this.

Thank you!

• You mean a (synthesisizable) hardware implementation, not just code to test if an integer literal is divisible by 5 (e.g. for testbench). – smci Dec 16 '17 at 8:48
• @smci I was actually asking for a schematic/drawing of a state machine, but a code of that state machine would not hurt. Dave Tweed answered the question perfectly though. – Eran Dec 16 '17 at 8:53
• then I'd retitle it *"VHDL interview question - cct to detect if..." – smci Dec 16 '17 at 8:59
• Answer over here by egreg math.stackexchange.com/a/2569882/213607 might give some inspiration for a more parallell approach. – mathreadler Dec 18 '17 at 13:24

Doing a remainder operation in serial fashion is actually quite easy. The key assumption is that the data comes in MSB-first if it's serial. You only need N states to compute a remainder modulo N. Start in the "0" state and if you end up in the "0" state after the last bit (it doesn't matter how many bits there are), the remainder is zero.

simulate this circuit – Schematic created using CircuitLab

Think about how you'd do long division if the only thing you needed to keep track of was the remainder:

process (clk)
begin
if rising_edge(clk) then
if reset = 1 then
state <= 0;
else
if (state & din) >= N then
state <= (state & din) - N;
else
state <= state & din;
end if;
end if;
end if;
end process;

• Wow, I see that it works but you could explain how you came up with the state machine? What was the starting point? I've never seen this done before am I just curious what the logic is with how to come up with it? – zoder Dec 15 '17 at 21:42
• The state diagram is just what you get from the VHDL code for the specific case of N=5. In other words, if the state represents the current remainder, the next state is what you get when you shift the state left one bit, add the input bit to it and then subtract 5 if necessary. – Dave Tweed Dec 15 '17 at 21:49
• This if beautiful, I would be truly impressed if someone comes up with this by themselves in an interview. And then I'd happily ask them to comment on how the synthesis results would differ compared to just using a rem operator to process a full vector every clock cycle. – Casperrw Dec 15 '17 at 22:21
• @zoder The states are the residues mod 5; the 0 arrow points to 2n mod 5, and the 1 arrow points to (2n + 1) mod 5. – hobbs Dec 16 '17 at 2:16
• Could you add the declarations of state, din, and N to your code? – mkrieger1 Dec 16 '17 at 13:03

You can also design a state machine if the data comes LSB-first:

The existence of such a deterministic finite automaton (DFA) directly follows from the other answer, which describes the DFA for MSB-first. Because languages accepted by DFAs are regular and regular languages are known to be closed under reversal (e.g. see here), there must be a DFA which accepts the following language:

$L = \{w\in \{0,1\}^* |\ \text{reverse}(w)_{10}\ \text{is divisible by }5\}$.

### Construction

1. Copy the MSB-first DFA from Dave Tweed's answer. I used the automaton tool JFLAP for that.

2. Apply the explicit transformation algorithm for DFA reversals, e.g. as described on CS.SE: Designing a DFA and the reverse of it.
You can see the (unminimized) result of this step in the old revision of this answer.

3. Minimize the resulting DFA. Unfortunately, this feature is a little buggy in the latest JFLAP version, so I resigned myself to minimizing it by hand.
Again, there are many algorithms and sources for them out there, I used the one described at “DFA Minimization” on tutorialspoint.com.

(Actually, if your eyes are trained good enough with looking at DFAs, you could directly see that $q_0$ and $q_1$ are equivalent states in the DFA as obtained in point 2. Mine aren't, thanks for noticing it go to supercat's comment!)

Indeed, the resulting automaton gives the right answers:

Appendix: For accessibility reasons, the DFA which accepts binary numbers which are divisible by 5 with LSB-first is $A_{rev5} = (Q, \Sigma, \delta, q_0, F)$ with $Q = \{q_0, q_1, q_2, q_3, q_4\}$, $\Sigma = \{0,1\}$, $F = \{q_0\}$ and $\delta$ as follows:

$\delta(q_0, 0) = q_0,\quad\delta(q_0, 1) = q_1\\ \delta(q_1, 0) = q_4,\quad\delta(q_1, 1) = q_3\\ \delta(q_2, 0) = q_1,\quad\delta(q_2, 1) = q_2\\ \delta(q_3, 0) = q_2,\quad\delta(q_3, 1) = q_4\\ \delta(q_4, 0) = q_3,\quad\delta(q_4, 1) = q_0$

• If you're having difficulty reversing the DFA, you can also just reverse the equation: Instead of new_state = state*2 + input, you could use (new_state - input)/2 = state, then swap state and new_state. The DFA for the new equation should solve the LSB-first problem. – Eyal Dec 17 '17 at 8:56
• Why are q3 & q4 labelled so & not vice versa? Swap the labels q3 & q4, and the the machine implements the algo "halve (mod 5) & add the input bit". – Rosie F Dec 17 '17 at 11:03
• @RosieF: The phrase "halve (mod 5)" could perhaps use some more explanation for those not familiar with discrete math. Division in this context entails adding whatever multiple of the base would be needed to make the number divide evenly, so 3/2 (mod 5) would be (3+5)/2, i.e. 4. – supercat Dec 17 '17 at 17:05

One way to come up with the (MSB first) state machine is as follows:

1. The number received so far is N. Assume you know the remainder M = N mod 5.

2. There is a new bit coming in and new value is now N' = N*2 + b.

3. New remainder is then M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

This is easy enough to tabulate by hand:

    M   b  |  M'
------------------
0   0  |  0
1   0  |  2
2   0  |  4
3   0  |  1
4   0  |  3
0   1  |  1
1   1  |  3
2   1  |  0
3   1  |  2
4   1  |  4


Which matches the state machine in Dave Tweed's answer.

One hopes the interview question was about how you would solve the problem, rather than the ins and outs of VHDL or Verilog. The language details are straightforward once you have an algorithm.

If the number is passed bit by bit with MSB first, then the value of the number modulo 5 can be computed by initialising the state $S=0$ and then accumulating the value with $S \leftarrow (2 S + d) \text{ mod } 5$. At the end the number is divisible by 5 iff $S$ is zero. Since $S,d$ are bounded, the update equation can be written as a simple state machine with states $S=0,\cdots, 4$.

If the number is passed bit by bit with LSB first, we need to do a little more work. Off the bat we can try initialising the state $S=0, k= 0$ and then accumulating the value with $S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow k+1$. The problem with this is that $k$ is potentially unbounded, however since $2^4 = 1 \text{ mod } 5$, we can simplify the above to $S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow (k+1) \text{ mod } 4$. Again, since $S,k,d$ are bounded, the update equation can be written as a simple state machine with states $(S,k)$ where $S=0,\cdots, 4$, $k=0,\cdots, 3$.

Depending on what the VHDL is being written for, you may want to take an approach that describes it as a direct, combinational calculation. Receiving a number can mean that the entire number will be in a register for one clock cycle.

You could, for example, note down the mod 5 of the value that each of the bits represent, add these together, and then repeat the process until you are left with something less than 5. Either implement this combinationally for all the reduction steps, or re-use the logic for some small number of cycles.

But if you use the VHDL rem operator, that may just be the right answer. Assuming the company has decent synthesis tools, that would give you a fairly efficient implementation - a bit more area than state-machine solutions perhaps, but full throughput and therefore probably good energy per calculation. It is the option that would cost the least time to implement and therefore probably the least money for the employer!

To be fair, it's probably not the answer they are looking for with such a question - but it is also an opportunity to show off any real design experience.

If the number is presented in chunks larger than one bit, it may be helpful to use some parallel computations to compute the residue mod 15, with a proviso that the computation may yield 15 is exactly if the residue is zero. A simple way to compute the mod-15 residue is to observe that for any value of N>=1, adding the leftmost 4N bits to the portion of a number beyond that will yield a value which is congruent to the original mod 15. This allows the problem do be subdivided in many different ways depending upon the resources available.

For example, if one starts with a 32-bit value, that can be treated as eight 4-bit values. Those may be added together pair-wise to yield four 5-bit values, which can in turn be combined into two 6-bit values or one 7-bit value. Adding the upper three bits of that 7-bit value to the lower 4-bits will yield a 5-bit value which is at most 21. One can thus determine whether the original value is a multiple of 5 by observing whether the final value is one of 0, 5, 10, 15, or 20.

• ... or you could use 4-bit adders throughout, and just make sure that each carry-out becomes a carry-in for an adder later in the circuit. After three layers of adding you have a single 4-bit result and four yet-unused carries. Add three of the carries together in parallel with the last 4-bit addition and add their sum into the result with the last carry as carry-in. This yields at most 19, so you don't need to match on 20 afterwards. – Henning Makholm Dec 17 '17 at 9:13
• @HenningMakholm: There are many ways of arranging adders to yield the desired result. Which approach is better in a given situation would likely depend upon project-specific routing or resource utilization issues. Another trick would be to use a carry-save adders, but exploit the fact that the top bit of the shifted output may be moved to the bottom. Thus, one layer could turn 8 inputs to 6, then 6 into 4, then 4 into 3 and 3 into 2. One output of each layer would simply be AND gates and the other one XOR gates, so propagation time to get down to a pair of 4-bit values for the... – supercat Dec 17 '17 at 17:20
• ...one and only carry chain would be that of four xor gates. As for whether it's better to get the output below 19, or whether it's better to check for 20 as a possible residue, that probably depends upon resource availability and utilization. Given a number which is no more than 30, adding the upper and lower nybbles would yield a value that is at most 15 (either 16+14->1+14, or 0+15->0+15), but adding explicit checks for some or all of (20, 25, 30) might be cheaper. – supercat Dec 17 '17 at 17:26

I can't remember my VHDL, but here's a sketch of the idea that first came mind:

The last digits (in base 10) of the first powers of two are 1, 2, 4, 8, 6, 2, ... and the cycle repeats. Hence, the remainders mod 5 of powers of two are 1, 2, 4, 3, ....

Using that, we could shift in bits from the LSB, and accumulate the remainders mod 5 corresponding to the position whenever a 1 bit is seen. Do the accumulation mod 5, too, and it's enough to check if the sum is zero at the end.

We can use the idea from the answer here, that in base 4 we can derive that a number is divisible by 5 only if the alternating digit sum is. We therefore

1. group the digits 2 by 2,
2. sum the odd and subtract the even 2 bit blocks.
3. If the result is in the two complement region of a few bits for example [-4,3] (easy to check assuming we use two complements) then we are finished and we can divide the original number by 5 only if the result of the summation is 0 which is a very simple logical expression to check (basically just a big nor on all the resulting bits, no?)
4. otherwise we iterate on the new (much shorter number).

Let us try on the number 166 = (10)(10)(01)(10): 2,2,1,2

2-2+1-2 = -1

which is <= 3 in absolute value and not 0 why we can conclude in just one iteration that 166 is not divided evenly by 5.

Could be that a small memory could be cheaper/better in terms of speed/nr of gates than iterating. One can of course precalculate the worst (largest possible result given the allowed inputs) and plan the design accordingly.

The MSB approach is definitely easier, but I managed to do the LSB state diagram without needing to generate the MSB solution... it just took me a couple of hours. It turns out to be equivalent to the one shown by @ComFreek, just annotated differently.

We're going to be tracking two numbers. First, we're going to track the running sum, modulo 5 ("SUM"). Second, we'll track the value of the next power of 2 to be shifted in, modulo 5 ("NEXT"). I'll represent each state with possible values for "SUM" at the top, and their corresponding "NEXT" values below them.

Note that a state that looks like:
3,2,4,1
1,4,3,2

is equivalent to:
1,3,4,2
2,1,3,4

Because both states represent that:
SUM = 1 and NEXT = 4 OR
SUM = 2 and NEXT = 3 OR
SUM = 3 and NEXT = 2 OR
SUM = 4 and NEXT = 1.

Okay, so now we need to develop extra states, as most interviewers aren't going to be impressed by a state diagram with only one state. We're done when every state has two transitions.

Whenever you transition to a new state, each number in "NEXT" is doubled, then modulo'd 5. For the "SUM" follow these rules:

• If you transitioned along a 0, the top row keeps its values.
• If you transitioned along a 1, each column is the old state's "SUM" + "NEXT" modulo 5.

So, let's start by filling out the transitions when the incoming bit is 1.

All right, now we fill out the zeroes. There's only one state added, so we'll go ahead and fill its transitions out as well.

And voila! We've got a state machine that accepts the LSB first, without having to generate the MSB solution.

All of the above seems so complicated! There is an easy math way to detect if a binary integer is divisible by five. To start out, do you remember how to do "casting out nines" in ordinary decimal arithmetic? The residue modulo 9 of a decimal integer is the same as the residue modulo 9 of the sum of its digits. This works because 9 is one less than the number base.

There is a similar process, "casting out elevens", where the signs of alternate digits are set negative. This works because eleven is one greater than the number base.

So if we want to "cast out fives", we might represent our integer in number base four. Then we start with the lowest pair of digits as an initial sum, and subtract it from the next pair of digits to get the next sum. After going through our candidate integer this way, the final sum will be zero or divisible by 5 if our original integer is divisible by 5.

Example 70: 01 00 01 10 --> 01 00 -1 --> 01 01 --> 00, divisible by 5 Example 49: 11 00 01 --> 11 -1 --> 1 00 --> 1, NOT divisible by 5

Note that you must carry an extra bits for the sign of the accumulated difference and for cases when there is carrying.

Another way to go, is to simply add the hex digits to get the residue modulo 15. Of course you need a final logic step to identify the three acceptable results of zero, five, and ten.

Example 70: 4 6 --> A, so 70 is divisible by 5 (but not by 15) Example 49: 3 1 --> 4, so 70 is NOT divisible by 5.

Note that you can use different number bases to construct lots of divisibility tests, though in computer logic the ones for powers of 2 +/- 1 are easiest to implement.

In decimal arithmetic, one of my favorites is my test for residue mod 7. Note that 100 is two greater than a multiple of 7, so group the digits into pairs (work in number base 100) and add the hundreds TWICE from the units. Here we work from left to right...

Example: 98 76 --> 2 72 --> 76, so 9876 is not divisible by 7. It is 6 mod 7. Example: 03 45 67 --> 51 67 --> 1 69 --> 71 so it is 1 mod 7.

Of course, in binary, just take the sum of the octal digits (groups of 3 bits).

Sorry, I wish I was a Verilog guru, but the arithmetic is all I can offer at this stage of life. See Ron Doerfler's "Dead Reckoning" for a lot of tricks like this.

• I wonder if our Canadian cousins might have some special algorithms. Since they outlawed the Canadian penny, all prices are rounded to the nearest \$0.05. – richard1941 Dec 22 '17 at 4:39

A VHDL interview question should result in some VHDL code.

I had occasion to find a ghdl llvm backend bug with an implementation of Dave Tweed's state transition table where ghdl's author distilled the implementation in a function to 17 lines:

type remains is (r0, r1, r2, r3, r4); -- remainder values

function mod5 (dividend: bit_vector) return boolean is
type remain_array is array (NBITS downto 0) of remains;
type branch is array (remains, bit) of remains;
constant br_table:  branch := ( r0 => ('0' => r0, '1' => r1),
r1 => ('0' => r2, '1' => r3),
r2 => ('0' => r4, '1' => r0),
r3 => ('0' => r1, '1' => r2),
r4 => ('0' => r3, '1' => r4)
);
variable  remaind:    remains := r0;
variable tbit:        bit_vector (NBITS - 1 downto 0) := dividend;
begin
for i in dividend'length - 1 downto 0 loop
remaind := br_table(remaind,tbit(i));
end loop;
return remaind = r0;
end function;


The associated test case is quite small allowing easier debugging and uses state names compatible with VHDL in the enumerated type remains:

(created with Dia)

The idea here is that the function (or even an example VHDL program of 27 lines) is short enough to write a VHDL answer during an interview. No need to worry about spoiling an interview question requiring demonstration of both knowledge and skill, an interviewee would be expected to defend an implementation when questioned.

(The llvm backend bug has been fixed in commit 1f5df6e earlier today.)

One of the things of note is the state transition table also tells us where a quotient bit would be a '1' shown by a transition to a state with a lower remainder value (or both transitions for r4) when subtracting 5 from the dividend. That can be encoded in a separate table (or a table of a record type which seems cumbersome). We do this historically in graphics hardware dealing with horizontal screen resolutions that multiples of 5 pixels.

Doing so gives us a div/mod5 producing a quotient and remainder:

library ieee;
use ieee.std_logic_1164.all;

entity divmod5 is
generic (
NBITS:  natural := 13
);
port (
clk:        in  std_logic;
dividend:   in  std_logic_vector (NBITS - 1 downto 0);
quotient:   out std_logic_vector (NBITS - 3 downto 0);
remainder:  out std_logic_vector (2 downto 0);
remzero:    out std_logic
);
end entity;

architecture foo of divmod5 is
type remains is (r0, r1, r2, r3, r4); -- remainder values
type remain_array is array (NBITS downto 0) of remains;
signal remaindr:    remain_array := (others => r0);
signal dividendreg: std_logic_vector (NBITS - 1 downto 0);
signal quot:        std_logic_vector (NBITS - 3 downto 0);
begin

parallel:
for i in NBITS - 1 downto 0 generate
type branch is array (remains, bit) of remains;
-- Dave Tweeds state transition table:
constant br_table:  branch := ( r0 => ('0' => r0, '1' => r1),
r1 => ('0' => r2, '1' => r3),
r2 => ('0' => r4, '1' => r0),
r3 => ('0' => r1, '1' => r2),
r4 => ('0' => r3, '1' => r4)
);

type qt is array (remains, bit) of std_ulogic;
-- Generate quotient bits from Dave Tweeds state machine using q_table.
-- A '1' when a remainder goes to a lower remainder or for both branches
-- of r4. A '0' for all other branches.

constant q_table:   qt :=     ( r0 => (others => '0'),
r1 => (others => '0'),
r2 => ('0' => '0', '1' => '1'),
r3 => (others => '1'),
r4 => (others => '1')
);
signal tbit:    bit;
begin
tbit <= to_bit(dividendreg(i));
remaindr(i) <= br_table(remaindr(i + 1),tbit);
do_quotient:
if i < quot'length generate
quot(i) <= q_table(remaindr(i + 1),tbit);
end generate;
end generate;

dividend_reg:
process (clk)
begin
if rising_edge(clk) then
dividendreg <= dividend;
end if;
end if;
end process;

quotient_reg:
process (clk)
begin
if rising_edge (clk) then
quotient <=  quot;
end if;
end process;

remainders:
process (clk)
begin
if rising_edge(clk) then
remzero <= '0';
case remaindr(0) is
when r0 =>
remainder <= "000";
remzero <= '1';
when r1 =>
remainder <= "001";
when r2 =>
remainder <= "010";
when r3 =>
remainder <= "011";
when r4 =>
remainder <= "100";
end case;
end if;
end process;

end architecture;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity divmod5_tb is
end entity;

architecture foo of divmod5_tb is
constant NBITS:    integer range 0 to 13 := 8;
signal clk:        std_logic := '0';
signal dividend:   std_logic_vector (NBITS - 1 downto 0);

signal quotient:   std_logic_vector (NBITS - 3 downto 0);
signal remainder:  std_logic_vector (2 downto 0);
signal remzero:    std_logic;
signal psample:    std_ulogic;
signal sample:     std_ulogic;
signal done:       boolean;
begin
DUT:
entity work.divmod5
generic map  (NBITS)
port map (
clk => clk,
dividend => dividend,
quotient => quotient,
remainder => remainder,
remzero => remzero
);
CLOCK:
process
begin
wait for 5 ns;
clk <= not clk;
if done'delayed(30 ns) then
wait;
end if;
end process;
STIMULI:
process
begin
for i in 0 to 2 ** NBITS - 1 loop
wait for 10 ns;
dividend <= std_logic_vector(to_unsigned(i,NBITS));
wait for 10 ns;
wait for 10 ns;
end loop;
wait for 15 ns;
done <= true;
wait;
end process;

SAMPLER:
process (clk)
begin
if rising_edge(clk) then
sample <= psample after 4 ns;
end if;
end process;

MONITOR:
process (sample)
variable i:     integer;
variable div5:  integer;
variable rem5:  integer;
begin
if rising_edge (sample) then
i := to_integer(unsigned(dividend));
div5 := i / 5;
assert div5 = unsigned(quotient)
report LF & HT &
"i = " & integer'image(i) &
" div 5 expected " & integer'image(div5) &
" got " & integer'image(to_integer(unsigned(quotient)))
SEVERITY ERROR;
rem5 := i mod 5;
assert rem5 = unsigned(remainder)
report LF & HT &
"i = " & integer'image(i) &
" rem 5 expected " & integer'image(rem5) &
" got " & integer'image(to_integer(unsigned(remainder)))
SEVERITY ERROR;
end if;
end process;

end architecture;


Implemented here with a generate statement, an inner generate statement producing quotient bits. The remaindr array provides a state transition trace:

All without an arithmetic operation.

It's also possible to implement in a procedure without all the registers taking advantage of parameters with mode out. That'd approach a minimum number of lines for an interview.

A clocked sequential implementation would require a bit counter and flow control (a JK flip flop and a couple of gates).

There's a time/complexity trade off depending on dividend size you'd also likely be required to defend in an interview.