2
$\begingroup$

IF I convert the dividend and divisor into decimal, perform the division and convert the remainder and quotient back in to binary will I get correct answer? I'm doing this:

  • $630 ÷ 13$
  • Quotient=$48= (110000)_2$
  • Remainder=$6= (110)_2$

But if I use this online calculator here, I get

  • Quotient=$(1111110)_2$
  • Remainder=$0$

So my question is what is the correct way to perform binary division, the exclusive-or operator one or by simply subtracting the numbers?

$\endgroup$
3
$\begingroup$

The answer is that "it depends".

If your binary numbers are integers, then the first result is correct: $$ 630=48\cdot13+6, $$ so the integer part of the quotient is, indeed, 48 and the remainder is six.

The link that you gave specifically states that it is doing polynomial division. What that means is that it interprets the individual bits as coefficients of powers of $x$ in such a way that the least signficant bit are the lower degree terms. This polynomial is an element of the ring $\mathbb{F}_2[x]$. In this case it interprets $$ 630=1001110110_2=x^9+x^6+x^5+x^4+x^2+x $$ and $$ 13=1101_2=x^3+x^2+1. $$ This time it happens that the polynomial division has zero remainder, and the output is that the quotient is $111110_2=x^6+x^5+x^4+x^3+x^2+x$. Let's check: $$ \begin{align} (x^3+x^2+1)(x^6+x^5+x^4+x^3+x^2+x)&=x^3(x^6+x^5+x^4+x^3+x^2+x)+\\ &+x^2(x^6+x^5+x^4+x^3+x^2+x)+\\ &+1(x^6+x^5+x^4+x^3+x^2+x)\\ &=x^9+x^8+x^7+x^6+x^5+x^4+\\ &+x^8+x^7+x^6+x^5+x^4+x^3+\\ &+x^6+x^5+x^4+x^3+x^2+x\\ &=x^9+2x^8+2x^7+3x^6+3x^5+3x^4+2x^3+x^2+x\\ &=x^9+x^6+x^5+x^4+x^2+x, \end{align} $$ because the arithmetic of the coefficients of the polynomials is done modulo two.

The latter type of division is very important to mast for example when CRC-checks are tagged to data blocks.

So the answer depends on how your sequence of bits should be interpreted.

$\endgroup$
  • $\begingroup$ The polynomial option would give the same results. Clever .;) (+1) $\endgroup$ – Inceptio Apr 24 '13 at 18:44
1
$\begingroup$

The calculator you posted does not do operations in the usual sense, it does it in $GF(2)$, i.e. modulo 2, in each coordinate $1+1=0$, for example.

Arithmetic should give the same answer when done in base 10 and base 2.

$\endgroup$
0
$\begingroup$

Absolutely you should get the correct result. Note that both the first and second subtraction they subtract $1001_2-1101_2=100_2$ They must be working in the field of two elements, not in $\Bbb N$

$\endgroup$

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.