Remainder of a 16-bit number divided by 3


I have to design a combinational logic circuit which accepts a 16-bit number as input and then calculates the remainder of the number divided by 3 as its output.

I originally had no idea how to proceed and if there is any convenient algorithm for finding the remainder.

Based on the link provided by @RJR I learned that the following recursive algorithm might be a possibility:

x mod 3 = ((x >> 2) + (x & 3)) mod 3

Can this be implemented with combinatorial logic? What sort of approach would be taken to break down the problem into functional blocks which can then be reduced to gates?

Is there a better solution?

If I separate the bits 2 by 2 and add them, and do the same with the result, then the remaining number would be between 00 to 11. For 00 and 11 the remainder is 0, for 01 the remainder is 1 and for 10 the remainder is 2. How can I add 8 2-bit numbers and get a (let's say) 6-bit answer? The answer to this can solve my problem.

Best Answer

I did it :) I made a device that calculates the remainder of a 4-bit number divided by 3 (using truth table and Karnaugh maps) and then connected 4 of them for the 16-bit input, then two more for the resulting 8 bits, and 1 more for the final 4 bits and it is working perfectly! Anyways thank you so much for your help.