# 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. – Andy aka Nov 30 '20 at 13:22
• I see, thank you. – alexandrosangeli Nov 30 '20 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. – user253751 Nov 30 '20 at 13:51
• For 4-bit numbers, use a 256 element x 4-bit LUT, and write a spreadsheet to generate its contents. – user_1818839 Nov 30 '20 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. – the busybee Dec 1 '20 at 12:18

## 1 Answer

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. – alexandrosangeli Dec 1 '20 at 12:37
• You may also find more information at Computer Science Stack Exchange, which seems to be more suited for this topic. – megasplash Dec 1 '20 at 14:10