東京大学 情報理工学系研究科 電子情報学専攻 2014年8月実施 専門 第3問

Author

adj-matrix

Description

Let and be polynomials of ( and are real. and ). We represent the leading terms of the polynomials and by and , and their degrees by and . The polynomial division, where is divided by a non-zero polynomial , is given by

Here quotient and remainder are polynomials of satisfying or . In this case, we represent and .

(1) Calculate and for and .

(2) Complete a pseudocode of the polynomial division algorithm by filling (a) with appropriate expressions. Note that the four arithmetic operations for monomial terms (expressions that contain only one term, e.g. or ) and addition/subtraction operations for polynomials can be used as they are.

Input: f, g
Output: q, r
q = 0, r = f
while (r ≠ 0 and deg(g) ≤ deg(r)) {
    q = q + LT(r)/LT(g)
    r = _____ (a) _____
}

(3) Prove that the algorithm introduced in (2) always terminates.

(4) The greatest common divisor (GCD) for polynomials and is a polynomial which satisfies the following conditions.

• divides and
• if a polynomial divides and , then also divides

satisfying these conditions is represented by . is unique up to multiplication by nonzero numbers. Given , by using the following relations and , can be calculated by the following procedure (without loss of generality, we assume ). Fill (b) and (c) with appropriate expressions.

Input: f, g
Output: h
h = f
s = g
while (s ≠ 0) {
    rem = remainder(h, s)
    h = ______ (b) ______
    s = ______ (c) ______
}

(5) Given arbitrary polynomials and (), calculate an upper bound of the number of times that a function remainder is called inside the while-loop during the calculation of . Also provide a reason for the obtained result.

Kai

(1)

and .

Since .

Therefore .

(2)

• (a): r - (LT(r) / LT(g)) * g

(3)

Let be the remainder at iteration . Since

Let , then

i.e.,

Since

Therefore

Since if the loop stops and will not change. Therefore the algorithm always terminates.

(4)

• (b): s
• (c): rem

(5)

According to (3),

In GCD, .

According to the analysis of (3), we know and .

To find the worst case, we need let .

In this case, the degree of follows the sequence: , where .

The total number of steps is the length of this sequence plus the final step: .