state machines - 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!

Answer

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;