Notice
Recent Posts
«   2019/09   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Tags more
Archives
Today
2
Total
289,256
관리 메뉴

## 다항식 전개하기(Polynomial Expansion) 본문

Season 1/Problem solving

### 다항식 전개하기(Polynomial Expansion)

codeonwort 2014.08.23 12:58

$$z ← z^2 + c$$

I want its expanded form after several iterations. Let's say it's 3 times.

\begin{aligned} z_1 = z_0^2 + c \\ z_2 = z_1^2 + c = (z_0^2 + c)^2 + c \\ z_3 = z_2^2 + c = ((z_0^2 + c)^2 + c)^2 + c \end{aligned}

There are so many brackets and multiplications. I don't want to expand it by hand, so let's make a program to do it.

First consideration is how to represent the expression in the code. Simple SOP(Sum Of Product) came to mind. We are dealing with polynomials, so let's regard a polynomial as sum of monomials.

$$p = a_0x^0 + a_1x^1 + a_2x^2 + ...$$

Here, each monomial is composed of a coefficient, a letter(strictly, an unknown), and an exponent.

Object declaration of them is straightforward then(In this article, I will use javascript for demonstration):

function Monomial(coeff, letter, exponent) {

this.coeff = coeff

this.letter = letter

this.exponent = exponent

}

function Polynomial(monomials) {

this.monomials = monomials || []

}

We need methods for addition and multiplication. Let's consider addition of two monomials.

$$ax^2 + bx^2 = (a+b)x^2 \\ ax^2 + bx^4 = ax^2 + bx^4$$

There are two cases:
1. Both letters and exponents same, result in single monomial.
2. Otherwise, we just make a polynomial containing those two.

It's easy to write a code for it.

if(this.letter == x.letter && this.exponent == x.exponent){
return new Monomial(this.coefficient + x.coefficient, this.letter, this.exponent)
}
return new Polynomial([this, x])
}

Now consider multiplication of two monomials:

$$ax^2 \times bx^3 = abx^{2+3} = abx^5 \\ ax \times by^2 = abxy^2$$

Wait. we have a problem. Currently a monomial stores only one letter. It cannot hold $abxy^2$ which contains two letters(accordingly, two exponents). A monomial has to store an 'array of letters' and an 'array of exponents.'

function Monomial(coeff, letters, exponents) {

this.coeff = coeff

this.letters = letters // Array of String

this.exponents = exponents // Array of Number

}

function Polynomial(monomials) {

this.monomials = monomials || []

}

$$axy^2 + bx^2y = axy^2 + bx^2y \\ axy + bxy = (a+b)xy$$

Now, the condition that the result to be a monomial is, all letters and exponents are same.

Monomial.prototype.mergeable = function(x) {

var L = this.letters.join("") == x.letters.join("")

var D = this.exponents.join("") == x.exponents.join("")

return L && D

}

if(this.mergeable(x)){

return new Monomial(this.coeff+x.coeff, this.letters, this.exponents)

}

return new Polynomial([this, x])

}

What, comparison using join()? unnecessary creation of strings and no consideration of letter ordering. It will crashes for $2(zz)^3(z)^5 + 3(z)^7(zz)^2$ or $xy^2 + 2y^2x$. Oh, I just want the expansion of $z ← z^2 + c$. Screw them.

Return to multiplication, when you multiply two monomials, if letters are same, add their exponents. If not, just combine them.

\begin{aligned} ax^2y^3z \\ \times bx^4 ~~~~ z^7 \\abx^{2+4}y^3z^{1+7} \end{aligned}

Monomial.prototype.multiply = function(x) {

var letterMap = {}

var letters = [], degrees = []

for(var i=0; i<this.letters.length; i++){

if(letterMap[this.letters[i]] == null){

letterMap[this.letters[i]] = this.degrees[i]

}else{

letterMap[this.letters[i]] += this.degrees[i]

}

}

for(i=0; i<x.letters.length; i++){

if(letterMap[x.letters[i]] == null){

letterMap[x.letters[i]] = x.degrees[i]

}else{

letterMap[x.letters[i]] += x.degrees[i]

}

}

for(var letter in letterMap){

letters.push(letter)

degrees.push(letterMap[letter])

}

return new Monomial(this.coeff*x.coeff, letters, degrees)

}

It's a bit long and inefficient. But I'll go to next step. I'm just prototyping and when it needs good performance, I can revise only the inside of the method. In other words, it's an unpropagated, controllable inefficiency.

We finished addition and multiplication of two monomials. Remaining work is boring and obvious extension from mono to poly. Need to add a monomial M and a polynomial P? Find a monomial N in P that is mergeable with M. If N exists, merge M into N. otherwise, append M to P's monomial list.

Adding two polynomials P and Q is simple as previous. apply above step with Q's every monomials for P.

Multiplication of P and Q: multiply all monomial pairs of P and Q, and sum up them. it's PxQ.

for(var i=0; i<this.monomials.length; i++){

if(this.monomials[i].mergeable(x)){

break

}

}

if(i == this.monomials.length){

this.monomials.push(x)

}

return this

}

for(var i=0; i<X.monomials.length; i++){

}

}

Polynomial.prototype.multiply = function(X) {

var P = new Polynomial()

for(var i=0; i<this.monomials.length; i++){

for(var j=0; j<X.monomials.length; j++){

}

}

return P

}

Finally, If you want to see a real example, it's here:  http://jsfiddle.net/codeonwort/ynz8nqzx/

Tag
,
공유하기 링크