# How do circuits calculate the remainder of an n-bit number when divided by another n-bit number?

I am looking for a way to calculate the remainder of an n-bit number when divided by another n-bit number.

For example, 1000 mod 0011 = 10.

How is this done on a computer?

• If you want the remainder to be accurate to 3 bits then pre-shift-left the numerator by 3 bits and regard the lower 3 bits of the result as the remainder. Commented Nov 30, 2020 at 13:22
• I see, thank you. Commented Nov 30, 2020 at 13:32
• When you do a division, it calculates the quotient and the remainder. So a remainder circuit is the same as a division circuit - you just use the other output. Commented Nov 30, 2020 at 13:51
• For 4-bit numbers, use a 256 element x 4-bit LUT, and write a spreadsheet to generate its contents.
– user16324
Commented Nov 30, 2020 at 14:51
• A division circuit is not necessarily complicated. If you design a sequential one, along the algorithm shown in megasplash's answer, it is quite simple. Commented Dec 1, 2020 at 12:18

A processor in a computer calculates such things by using a binary arithmetic. In particular, the remainder is one of the results of a binary division.

The simplest (i.e. non-optimized) way to perform a binary division is to iterate through the binary subtraction (using binary adder) and shift operations until a desired accuracy of the quotient. This binary division resembles a "school" way of division (long division).

CPU knows, what is a number of digits in an integer part of a quotient. So when you set the accuracy to be 0 digits in the fractional part, you will get the result of the mod operation in the remainder. (This is generally speaking, as if you were to design a processor. Usually you don't set such things manually as it is already hardwired in an ALU of a processor.)

Example Lets divide $$\8_{10}\$$ by $$\3_{10}\$$. Numerator $$\8_{10}=1000_2\$$ has four significant binary digits, denominator $$\3_{10}=11_2\$$ has two significant binary digits. The quotient will have $$\4 - 2 + 1 = 3\$$ significant binary digits in an integer part.

Iteration 1. You start from the left-most binary position and compare (by subtraction) the first two digits of the numerator and the denominator. We get ($$\10_2=2_{10} < 11_2=3_{10}\$$), which results in a "0" bit in the quotient. The remainder remains equal to the numerator value.

Iteration 2. Then you shift to the right and perform the same comparison. Now $$\100_2=4_{10} > 11_2=3_{10}\$$, which results in a "1" bit in the quotient. You subtract: $$\100_2 - 11_2 = 1_2\$$, which gives you the remainder equal to $$\10_2\$$.

Iteration 3. For the last iteration you make the same comparison, which gives you a "0" bit in the quotient and doesn't change the remainder.

Notes: 1. As the last value of the remainder is not zero, you could continue the division. Following results will form a fractional part of the quotient.

1. This simple explanation should suffice to answer your question. However, the actual implementation of the divider may differ in a lot of ways, since it has to deal with negative numbers, two's complements, floating points, demands of performance and/or chip space and many other thing.

2. This is a good reference on the topic: Appendix J: Computer Arithmetic by David Goldberg in Hennessy, Patterson: Computer Architecture: A Quantitative Approach, 5th Ed.

• Seems like explaining how the remainder is obtained from a division operation is not as simple as explaining how other operations work like counting or addition so thanks for the explanation and the reference source. Commented Dec 1, 2020 at 12:37
• You may also find more information at Computer Science Stack Exchange, which seems to be more suited for this topic. Commented Dec 1, 2020 at 14:10