3
$\begingroup$

I am trying to learn binary long division, and I am confused. An example in my book gives that $10011010000/1101 = 11111001$ plus a remainder of $101$, which doesn't make sense, since $1001$ is not divisible by $1101$, and so the first digit should be $0$. When I use an online calculator, it gives me a result of $01011110$, which makes more sense. Could anybody enlighten me, please?

To add some context, this is the polynomial long division involved in CRC computation. Maybe the numbers, which represent the coefficients of polynomials, aren't supposed to be converted to decimal? The number being divided had already been extended by the degree of the divisor.

$\endgroup$
  • 2
    $\begingroup$ To understand why the polynomial (not the number) being divided has been extended by the degree of the divisor, see the answer to this question, which also gives some details about the division process. $\endgroup$ – Dilip Sarwate Mar 18 '13 at 1:59
  • $\begingroup$ Its not ordinary arithmetic. Its XOR division, meaning there is now carry involved. $\endgroup$ – Robin Dec 11 '18 at 9:32
2
$\begingroup$

If it is polynomials, you can't transform to decimal. What you have is: $$ x^{10} + x^7 + x^6 + x^4 / x^3 + x^2 + 1 $$ The coefficients are in $\mathbb{Z}_2$ (they are 0 or 1, and $1 \cdot 1 = 1$, $1 + 1 = 0$). Do the polynomial long division.

Or work similar to what you would do when dividing integers, sliding the divisor against the dividend. Just that it is much simpler: Next bit is the first bit of what comes next, and in $\mathbb{Z}_2$ addition is substraction (and is the XOR operation for bitwise operations e.g. in C).

 10011010000/1101 = 111001
-1101
 -----
  1001
 -1101
  -----
   1000
  -1101
   -----
    1010
   -0000
    -----
     0100
    -0000
     -----
      1000
     -1101
      -----
       101

Thus the quotient is 111001 (i.e., $x^5 + x^4 + x^3 + 1$) with remainder 101 (i.e., $x^2 + 1$).

$\endgroup$
  • $\begingroup$ What do you do when you get to a situation with 0-1? There's no negative one $\endgroup$ – CodyBugstein Mar 2 '15 at 19:40
  • $\begingroup$ @Imray You don't do any carryover in this situation. That is basically literally bit-by-bit XOR. $\endgroup$ – xji May 5 '15 at 6:18
  • 4
    $\begingroup$ The result is incorrect. The quotient is 11111001 with remainder 101. If you were to multiply only leading terms from polynomials you would get x^5 * x^3 = x^8 which is not x^10 as it should be. This is an easy way to spot this mistake. $\endgroup$ – kr85 Jan 6 '16 at 22:59
6
$\begingroup$

the vonbrand answer is slightly off. This is the correct operations in GF(2) -

        11111001
    ------------
1101(10011010000
     1101
     ----
      1001
      1101
      ----
       1000
       1101
       ----
        1011
        1101
        ----
         1100
         1101
         ----
            1000
            1101
            ----
             101

In GF(2) X^10+X^7+X^6+X^4 MOD (X^3+X^2+1) = X^2+1

Therefor your text book's answer is correct.

$\endgroup$
  • $\begingroup$ What do you do when you get to a situation with 0-1? There's no negative one $\endgroup$ – CodyBugstein Mar 2 '15 at 19:39
  • $\begingroup$ Imray - there is no subtraction. Only addition modulo 2. $\endgroup$ – brett Mar 24 '15 at 17:01
1
$\begingroup$

here is an online python3 sample for printing the long division.

def bitstring(x):  return bin(x)[2:]
def printlongdiv(lhs, rhs):
    rem = lhs
    div = rhs
    origlen = len(bitstring(div))

    # first shift left until the leftmost bits line up.
    count = 1
    while (div | rem) > 2*div:
        div <<= 1
        count += 1

    # now keep dividing until we are back where we started.
    quot = 0
    while count>0:
        quot <<= 1
        count -= 1
        print("%14s" % bitstring(rem))
        divstr = bitstring(div)
        if (rem ^ div) < rem:
            quot |= 1
            rem ^= div

            print(1, " " * (11-len(divstr)), divstr[:origlen])
        else:
            print(0, " " * (11-len(divstr)), "0" * origlen)
        print(" " * (13-len(divstr)), "-" * origlen)
        div >>= 1
    print("%14s <<< remainder" % bitstring(rem))
    print(" -> %10s <<< quotient" % bitstring(quot))

printlongdiv(0x4d0, 13)
$\endgroup$
-2
$\begingroup$

$1232 = 94 * 13 + 10$

$10011010000 = 1011110 * 1101 + 1010$

The example is wrong and your online calculator is calculating correctly.

$\endgroup$
  • 4
    $\begingroup$ It is polynomials, not integers in binary. $\endgroup$ – vonbrand Mar 18 '13 at 1:36
  • 2
    $\begingroup$ The example is not wrong, and what is calculating (correctly) is not what the online calculator is calculating. $\endgroup$ – Dilip Sarwate Mar 18 '13 at 1:56
  • 1
    $\begingroup$ my answer is obsolete, because the question has been substantialy changed. $\endgroup$ – V-X Mar 18 '13 at 6:51

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.