0
\$\begingroup\$

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?

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

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.

Binary long division

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.