Simple polynomial division question

AARRRGH

Hello

I hope someone can help me with this.

Let's say I want to divide x^2 + x + 1 into x^2 + 1

Am I right in thinking the answer is 1 remainder x?

This is how I am getting my answer...

I convert my polynomials into binary -

x^2 + x + 1 = 111
x^2 + 1 = 101

Then I do long division -

        1
111 / 101
      111
      ----
      010

Which translates as 1 remainder x.

Am I correct?

If so, how would I handle x^4 + 1 into x^2 + 1?

Convert to binary -

10001 / 101

Am I right in thinking the answer is -

          0
10001 / 101
        000
        ----
        101

So the answer is 0 remainder x^2 + 1?

Thank you.

Michael Collins

If it's just bog-standarnd polynomial division you're after, it can be done directly without any binary conversions.

See http://en.wikipedia.org/wiki/Polynomial_long_division for example.

AARRRGH

Well, I'm coding it, and my polynomials are represented internally as binary, so I'm kind of used to thinking that way...

The problem isn't how I'm representing the data; rather it's I'm unsure what happens if the divisor is larger than the dividend.

Cheers.

Cokehead Mother

I did it the non-binary-shenanigans way and got 1 remainder -x.

101 - 111 = -10, not 10. So I think what you did was fine besides from that little mistake.

For the second one, 0 remainder x^2 + 1 is basically 0 + (x^2 + 1)/(x^4 + 1) which is what you had to begin with. I don't think you can really do much with that one.

But yeah your method seems fine.

AARRRGH

Thanks! Nice to hear I am doing it right.

I'm not worried if it should be x or -x (it's all the same in binary, e.g. x + 1 ^ x - 1 is the same as x + 1 ^ x + 1)

Cheers.

MathsManiac

dublindude wrote: »

Well, I'm coding it, and my polynomials are represented internally as binary, so I'm kind of used to thinking that way...

The problem isn't how I'm representing the data; rather it's I'm unsure what happens if the divisor is larger than the dividend.

Cheers.

What you've done is right. When you say "the divisor is larger than the dividend", you just need to be clear on what that means: the point is that you need to look at the order of the polynomial, (i.e. the highest power). Given the way you're coding it, the polynomial of the higher power is the bigger binary number, so "bigger" is ok! If you're dividing a poly of a lower power by a poly of a higher power, then the answer will be 0, remainder whatever. Otherwise the answer will be non-zero. (I'm assuming you're talking about polynomials over the rationals. If you insist on coefficients being integers only, then it's a different story)

Whichever way, the remainder is always of a lower power than the divisor (and is unique up to units). It's the "Division Algorithm".

AARRRGH

MathsManiac wrote: »

What you've done is right.

Yay!

MathsManiac wrote: »

When you say "the divisor is larger than the dividend", you just need to be clear on what that means: the point is that you need to look at the order of the polynomial, (i.e. the highest power).

Yep, that's exactly how I'm thinking about it.

x^8 is greater than x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

I'm treating x^8 and x^8 + 1 as pretty much the same size.

MathsManiac wrote: »

Given the way you're coding it, the polynomial of the higher power is the bigger binary number, so "bigger" is ok! If you're dividing a poly of a lower power by a poly of a higher power, then the answer will be 0, remainder whatever. Otherwise the answer will be non-zero. (I'm assuming you're talking about polynomials over the rationals. If you insist on coefficients being integers only, then it's a different story)

The way I'm doing it is if the divisor is larger than the dividend, I get 0 remainder the dividend. Sound ok?

My coefficients are modulo 2, so they'll always be 1 or 0.

Cheers!