整数と多項式の演算

計算代数
奈良女子大学理学部情報科学科
平成 26 年 4 月 24 日
加古富志雄
i
目次
第 4 章整数と多項式の演算
1
整数の演算
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
高速乗算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
4.2.1
4.2.2
4.2.3
Karatsuba の方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 分割による方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(離散) フーリエ変換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
3
4.2.4
4.2.5
高速フーリエ変換 (FFT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FFT による高速乗算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
7
4.2.6 除算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.7 ニュートン法による除算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
多項式の演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
8
9
加減算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
9
9
4.1
4.2
4.3
4.3.1
4.3.2
4.3.3
4.4
除算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
整係数多項式の除算と擬除算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4.1
4.5
乗算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
整係数多項式の除算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4.2 整係数多項式の擬除算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1
第 4 章整数と多項式の演算
4.1
整数の演算
整数 n は、基数 (Base) を b とすると、
n = n0 + n1 b + n2 b2 + · · · + nk bk
(4.1)
ただし、0 ≤ bk < b、と表される。例えば、10 進数で 642343 は基数を 10 として、
642343 = 3 + 4 × 10 + 3 × 102 + 2 × 103 + 4 × 104 + 6 × 105
となる。
n = n0 + n1 b + n2 b 2 + · · · + nk b k
m = m0 + m1 b + m2 b + · · · + mk b
2
(4.2)
k
(4.3)
の二つの数の加算は
n + m = (n0 + m0 ) + (n1 + m1 )b + . . . + (nk + mk )bk
(4.4)
となる。また、乗算は次の式で与えられる。
n×m =
2k
∑
lj bj
(4.5)
ni mj−i
(4.6)
j=0
lj
=
j
∑
i=0
実際の処理としては、上記の式で得られた結果を標準形 (lj が 0 ≤ lj < b を満たすようにする) に直す必要が
ある。これは、
l0
= q0 b + r0
lj + q0
= qj b + rj ,
(4.7)
j = 1, 2, . . . , 2k,
(4.8)
として、
n × m = r0 + r1 b + r2 b2 + . . . + r2k b2k + q2k b2k+1
(4.9)
で表される。基底 b としては、計算機で実行する場合には、2 の冪乗を選ぶことで計算としては 2k 回の加算程
度の計算手間で出来る。
k 桁の数同士の加算では、k 回の項毎の加算で計算が出来る。これに対して、k 桁同士の乗算では
1 + 2 + . . . + (k − 1) + k + (k − 1) + . . . + 2 + 1 = (k − 1)2
回の項毎の乗算が必要であり、計算の手間としては k の 2 乗に比例した計算時間がかかる。
第4章
2
4.2
整数と多項式の演算
高速乗算法
古典的な方法では多倍長整数の乗算には桁数の 2 乗に比例した計算時間がかかる。これをより高速に計算す
る方法として Karatsuba の方法と高速フーリエ変換を利用した方法がある。
4.2.1
Karatsuba の方法
n = n0 + n1 b
(4.10)
m = m0 + m1 b
(4.11)
n × m = n0 × m0 + (n0 × m1 + n1 × m0 )b + n1 × m1 b2
(4.12)
の二つの数の積を考える。
で 4 回の積が必要である。ここで、n0 × m1 + n1 × m0 の計算を
n0 × m1 + n1 × m0 = (n0 + n1 ) × (m0 + m1 ) − n0 × m0 − n1 × m1
と書き直すと、n × m の計算には n0 × m0 , n1 × m1 , (n0 + n1 ) × (m0 + m1 ) の 3 回の積で計算できる。
n 桁の計算にかかる時間 Tn は
Tn = 3Tn/2
の関係式で与えられる。これから、
Tn = T積 nlog 3
ただし、T積は、一桁の掛算に要する時間である。また、加算に要する時間は無視している。
k 桁の数同士の計算では、Karatsuba の方法を繰り返し使うことにより
k log2 3 ≈ k 1.585
に比例する計算量で計算が行なえる。
4.2.2
3 分割による方法
Karatsuba の方法に習って、三つに分割して積を計算する方法を考える。
n = n0 + n1 b + n2 b 2
(4.13)
m = m0 + m1 b + m2 b2
(4.14)
に対して、
n × m = n0 m0 + (n1 m0 + n0 m1 )b + (n2 m0 + n1 m1 + n0 m2 )b2 + (n2 m1 + n1 m2 )b3 + n2 m2 b4
では９回の積が必要である。これに対して、
s0
= n0 × m0
s1
= (n2 + n1 + n0 ) × (m2 + m1 + m0 )
s2
= (4n2 + 2n1 + n0 ) × (4m2 + 2m1 + m0 )
s3
= (n2 − n1 + n0 ) × (m2 − m1 + m0 )
s4
= n2 × m2
4.2. 高速乗算法
3
とすると、
n0 m0
= s0
−3s0 + 6s1 − s2 − 2s3 + 12s4
=
6
−2s0 + s1 + s3 − 2s4
=
2
3s0 − 3s1 + s2 − s3 − 12s4
=
6
= s4
n1 m0 + n0 m1
n2 m0 + n1 m1 + n0 m2
n2 m1 + n1 m2
n2 m2
となって、５回の積で計算できる。
この場合の計算時間は
Tn = T積 nlog3 5
ただし、T積は、一桁の掛算に要する時間である。
k 桁の数同士の計算では、この方法を繰り返し使うことにより
k log3 5 ≈ k 1.465
に比例する計算量で計算が行なえる。
一般に、l 個の和に分割して、積を求めると 2l − 1 回の積（それに、和）で計算できる。この時の計算量は、
k logl (2l−1) = k log(2l−1)/logl
となる。
4.2.3
(離散) フーリエ変換
n 個の数列
{f0 , f1 , f2 , . . . , fn−1 }
に対して
a
ˆk =
n−1
∑
fj cos(
2kjπ
)
n
fj sin(
2kjπ
)
n
j=0
ˆbk =
n−1
∑
j=0
で決まる数列 ˆ(ak , ˆbk を f の離散フーリエ変換という。あるいは、
fˆk
= a
ˆk + i ˆbk
n−1
∑
=
fj wkj
j=0
とおいて、{fˆ0 , fˆ1 , . . . , fˆn−1 } を f の離散フーリエ変換という。
ここで、w は n 乗すると 1 となるような数である。w = e
i sin( 2kπ
n )
となり、wn = 1 である。
2πi
n
2π
2kπ
k
= cos( 2π
n ) + i sin( n ) ととると、w = cos( n ) +
第4章
4
n−1
∑
fˆj w−jl
=
j=0
n−1
∑ n−1
∑
整数と多項式の演算
fk wjk w−jl
(4.15)
j=0 k=0
=
n−1
∑
fk
n−1
∑
wj(k−l)
(4.16)
j=0
k=0
= nfl
(4.17)
より、
fk =
n−1
1 ∑ ˆ −kj
fj w
n j=0
となる。これは離散逆フーリエ変換の式である。ここで、
∑n−1
j=0
wj(k−l) = nδk,l は k 6= l のとき 0 になり、k = l
の時 n となることを使った。(δi,j は i = j の時 1 となり、それ以外では 0 であるような関数である。)
フーリエ変換およびその逆変換をその定義式から直接計算した場合、ω k , k = 1, 2, . . . , n − 1 が計算されてい
るとして、O(n2 ) の計算時間が必要である。
4.2.4
高速フーリエ変換 (FFT)
今、n が 2 の冪乗であるとする。n = 2m 。フーリエ変換の式を書くと、
fˆ0
= f0 + f1 + f2 + . . . + fn−2 + fn−1
fˆ1
= f0 + f1 ω 1 + f2 ω 2 + . . . + fn−2 ω n−2 + fn−1 ω n−1
fˆ2 = f0 + f1 ω 2 + f2 ω 4 + . . . + fn−2 ω 2n−4 + fn−1 ω 2n−2
..
.
fˆn2
n
= f0 + f1 ω 2 + f2 ω n + . . . + fn−2 ω
n(n−2)
2
n
fˆn2 +1 = f0 + f1 ω 2 +1 + f2 ω n+2 + . . . + fn−2 ω
..
.
+ fn−1 ω
(n+2)(n−2)
2
n(n−1)
2
+ fn−1 ω
(n+2)(n−1)
2
fˆn−2
= f0 + f1 ω n−2 + f2 ω 2(n−2) + . . . + fn−2 ω (n−2)(n−2) + fn−1 ω (n−2)(n−1)
fˆn−1
= f0 + f1 ω n−1 + f2 ω 2(n−1) + . . . + fn−2 ω (n−1)(n−2) + fn−1 ω (n−1)(n−1)
これを書き直すと、次のようになる。
fˆ0
= f0 + f2 + . . . + fn−2 + f1 + f3 + . . . + fn−1
fˆ1 = f0 + f2 ω 2 + . . . + fn−2 ω n−2 + ω(f1 + f3 ω 2 + . . . + fn−1 ω n−2 )
..
.
fˆn2
= f0 + f2 ω n + . . . + fn−2 ω
n(n−2)
2
fˆn2 +1 = f0 + f2 ω n+2 + . . . + fn−2 ω
..
.
n
+ ω 2 (f1 + f3 ω n + . . . + fn−1 ω
(n+2)(n−2)
2
+ω
n
2 +1
n(n−2)
2
)
(f1 + f3 ω n+2 + . . . + fn−1 ω
(n+2)(n−2)
2
)
4.2. 高速乗算法
5
あるいは行列の形で書き直すと、

















fˆ0
fˆ1
..
.
fˆn2 −1
fˆn2
fˆn2 +1
..
.
fˆn−1


1
1
..
.













 1


 = 

 1





 1

 .

 .

 .
1
ω2
..
.
...
...
..
.
ω n−2
...
ωn
...
ω n+2
..
.
...
..
.
ω
..
.
..
.
...
ω (n−1)(n−2)
ω (n−1)
1 ω 2(n−1)
1
1
ω
..
.
ω n−2
..
.
ω
(n−2)(n−2)
2
ω
(n−2)
2
ω
n(n−2)
2
1
ω3
..
.
ω
n
ω2
(n+2)(n−2)
2
ω
3(n−2)
2
...
3n
2
...
ω
(n+2)
2
ω
...
...
..
.
3(n+2)
2

1
ω n−1
..
.
ω
(n−2)(n−1)
2
ω
n(n−1)
2
(n+2)(n−1)
2
ω
..
.
...
..
.
ω 3(n−1)
...
ω (n−1)(n−1)
..
.
f0
f2
..
.






 f
  n−2

  f1

 f

3
 .
 .
 .
fn−1

















となる。この式を二つに分割して、ω n = 1 すなわち、ω n/2 = −1 であることを使うと、

fˆ0
fˆ1
..
.











 = 




fˆn/2−1

1
1
..
.
1
ω2
..
.
1
ω n−2


= 





+ 


ω 3(n−2)/2
1
1
..
.
1
ω2
..
.
...
...
..
.
1
ω n−2
...





fˆn/2
fˆn/2+1
..
.
ˆ
fn−1






 = 





1
1
..
.
ω n/2
 (n+2)/2
 ω
+ 
..


.



= 


ω n−1
1
1
..
.
1
ω2
..
.
1 ω n−2

1
. . . ω (n−2)(n−1)/2

1
f0

n−2
ω
  f2
 .
..
 .
 .
.
...
ω 3(n+2)/2
..
.
ω 3(n−1)
fn−1





1
1
..
.
1
ω2
..
.
1 ω n−2






ω n−2
..
.
...
ω (n−2)(n−2)/2
1
ω n−2
..
.
...
ω (n−2)(n−2)/2
1

f0
f2
..
.





fn−2

n(n−1)/2
ω (n−1)(n−1)

f0

  f2
 .
 .
 .
...
...
..
.

...
...
..
.
...
ω
. . . ω (n+2)(n−1)/2
..
..
.
.
...





fn−2
ω (n−1)(n−2)
ω 3n/2


f1
f3
..
.





ω n−1
..
.
...
ω n(n−2)/2
(n+2)(n−2)/2
... ω
..
..
.
.
1 ω 2(n−1)





fn−2
...
...
..
.
ω (n−2)(n−2)/2

0 ...
0


ω ...
0


... ...
...

(n−2)/2
0 ... ω
ωn
ω n+2
..
.

f0
f2
..
.





. . . ω (n−2)(n−2)/2
ω (n−2)/2
0

ω n−2
..
.
1
ω3
..
.
1
0
...

1
1
ω
..
.


+ 



...
...
..
.
fn−2











f1
f3
..
.
fn−1











f1
f3
..
.
fn−1



 (4.18)


第4章
6

1

 0
− 
 ...

0
0
ω
...
...

0
0
... ...
...
0 . . . ω n−1





1
1
1
ω2
..
..
.
.
n−2
1 ω
...
...
..
.
...
1
ω n−2
..
.
ω (n−2)(n−2)/2
整数と多項式の演算






f1
f3
..
.



 (4.19)


fn−1
したがって、



= 


F

Ω =





1
1
...

1
1
ω2
..
..
.
.
n−2
1 ω
...
ω n−2
..
..
.
.
(n−2)(n−2)/2
... ω

1
0 ...
0

0
ω ...
0 

... ... ...
... 

0
0 . . . ω n−1





(4.20)
(4.21)
とすると、












fˆ0
fˆ1
..
.
fˆn/2−1
fˆn/2
fˆn/2+1
..
.
ˆ
fn−1


f0
f2
..
.




 = F





fn−2

f0
f2
..
.




 = F










 + ΩF 










 − ΩF 




fn−2
f1
f3
..
.
fn−1
f1
f3
..
.






(4.22)






(4.23)
fn−1
ここで、F( f0
f2 . . . fn−2 )T および F( f1 f3 . . . fn−1 )T はそれぞれ {f0 , f2 , . . . , fn−2 } および
{f1 , f3 , . . . , fn−1 } のフーリエ変換である。
したがって, n 個のデータからなる列 {f0 , f1 , f2 , . . . , fn−1 } のフーリエ変換は、それぞれ n/2 個のデータから
なる列 {f0 , f2 , . . . , fn−2 } および {f1 , f3 , . . . , fn−1 } のフーリエ変換から n/2 回の乗算と n 回の加算（あるいは
減算）で計算できる。
従って、サイズ n のフーリエ変換を計算するのに必要な時間 Tn は
Tn =
n
T + 2Tn/2
2 積
で与えられる。n = 2m から、
Tn = m ×
n
n log n
=
2
2
逆変換も同じ計算時間で計算可能である。
n は 2 の冪乗の場合について説明したが、それ以外の場合についても同様に行なえる。例えば、n = 3m の場
合、サイズ n のフーリエ変換を計算するのに必要な時間 Tn は
Tn =
n
T + 3Tn/3
3 積
で与えられる。n = 3m から、
Tn = m ×
n
n log3 n
=
.
3
3
4.2. 高速乗算法
4.2.5
7
FFT による高速乗算
f
= f0 + f1 b + f2 b2 + · · · + fn/2−1 bn/2−1
(4.24)
g
= g0 + g1 b + g2 b2 + · · · + gn/2−1 bn/2−1
(4.25)
の二つの数の乗算を考える。
h=f ×g
= f0 g0 + (f1 g0 + f0 g1 )b
+ (f2 g0 + f1 g1 + f0 g2 )b2
..
.
+ (fk g0 + fk−1 g1 + . . . + f1 gk−1 + f0 gk )bk
..
.
+ (fn/2−1 gn/2−2 + fn/2−2 gn/2−1 )bn−3
+ fn/2−1 gn/2−1 bn−2
いま、fn+k = fk , gn+k = gk および fk = gk = 0, k ≥ n/2 とすると、
h =
n−2
∑
hi b i
(4.26)
i=0
hi
=
n−1
∑
∑
fi+k g−k =
fj gk
(4.27)
j+k=i
k=0
と表すことができる。
ˆ i は、
fi と gi のフーリエ変換をそれぞれ fˆi と gˆi とすると、hi のフーリエ変換 h
ˆ i = fˆi gˆi
h
となる。
fˆi gˆi =
n−1
∑
fj ω ij
j=0
n−1
∑
fˆi gˆi ω −il
i=0
gk ω kj
k=0
n−1
∑ n−1
∑
=
n−1
∑
fj ω ij
i=0 j=0
n−1
∑
=
j=0
= n
fj
∑
n−1
∑
gk ω ki ω −il
k=0
n−1
∑
gk
k=0
fj gk
n−1
∑
ω (j+k−l)i
i=0
(4.28)
j+k=l
ˆ i = fˆi gˆi で h のフーリエ係数を決めると
従って、 h
∑
fj gk はその逆フーリエ係数で求めることが出来る。
ˆ i を計算するのに O(n) の時
フーリエ変換およびその逆変換を計算するのに O(n log n) の時間が必要であり、h
j+k=l
間が必要であるから、このアルゴリズムで積を計算するには
O(n log n)
の計算時間が必要である。
第4章
8
4.2.6
整数と多項式の演算
除算
f
= f0 + f1 b + f2 b2 + · · · + fn bn
g
= g0 + g1 b + g2 b2 + · · · + gm bm
として、
f =g×q+r
を計算する。ただし、n ≥ m とする。n < m であれば、q = 0, r = f が f /g の答えとなる。
商と余りをそれぞれ、
q
= f0 + f1 b + q2 b2 + · · · + qn−m+1 bn−m
r
= r0 + r1 b + r2 b2 + · · · + rm−1 bm−1
として、手計算で行っている除算の手順をもとに、qi , ri を求めてみる。
まず、qn−m は、fn を gm で割った商から
q 0 = fn /gm
として、qn−m の値を見積もって、
f 0 = f − q 0 × bn−m × g
を計算する。もしくは、fn < gm の場合には、
q 0 = (fn × b + fn−1 )/gm
を qn−m−1 の値として見積もる。
f 0 < 0 であれば、商として立てた q 0 が大きすぎたので q 0 ← q 0 − 1 として、再度 f 0 を f 0 ← f 0 + g × bn−m と
して計算する。このようにして、qn−m を求める。後は、f 0 を改めて、f と考えて、f 0 /g を計算することで商が
計算できる。余りは、r = f − q × r で求まる。この計算方法での計算時間は、商を立てる計算を n − m + 1 回実行する必要がありそれぞれの計算に必要な
時間は、各々n − i 桁と 1 桁の積を一回と、最悪
b
2
回の商の見積もりの修正を行う必要があることから、 2b 回の
m 桁同士の引き算を行う必要がある。O((n − m + 1)(n + mb
2 )) に比例する時間を要する。
商の見積もりの修正回数を減らすには、あらかじめ除数と被除数に適当な数 (2 の冪乗) をかけて、gm が
b
2
を満たすように正規化しておけば、最悪２回の修正で終わる。この場合、計算時間は、O((n − m + 1)(n + 2m))
となる。
b > gm ≥
4.2.7
ニュートン法による除算
高速に商を求めるには、ニュートン法を用いれば良い。
f /g の計算の結果は n − m + 1 あるいは n − m 桁なので、計算は n − m + 1 桁まで行えば十分である。まず、
1/g の計算を
1
−g
x
の方程式に対するニュートン法で計算する。適当な初期値 x0 から初めて、
f (x) =
xk+1
= xk − f (xk )/f 0 (xk )
1
−g
= xk + xk 1
x2k
= xk (2 − gxk )
(4.29)
4.3. 多項式の演算
9
で xk を求める。xk − 1/g の値は、
xk+1 −
1
1
≈ c(xk − )2
g
g
従って、log(n − m + 1) に比例する回数繰り返すことで (n − m + 1) 桁の 1/g を計算することができる。この
ようにして求めた 1/g と f の積を計算することで f /g の計算が行える。各々の乗算で FFT を使った算法を使用
することにより
O(n log2 n)
の計算時間で、除算が計算できる。
余りは、
r = f − qg
から求める。
4.3
多項式の演算
f (x)
g(x)
= fm xm + fm−1 xm−1 + · · · + f0 ,
n
= gn x + gn−1 x
n−1
+ · · · + g0 ,
fm 6= 0,
gn 6= 0
(4.30)
(4.31)
の四則演算については、整数の場合と同様な方法で計算が実行できる。違いは、正規化の部分で、整数計算の場
合には最後に各項の正規化の手続きを行なう必要があったが、多項式演算の場合には不要である。
4.3.1
加減算
f (x) ± g(x) =
n
∑
(fi ± gi )xi
i=0
4.3.2
乗算
f (x) × g(x)
=
n ∑
m
∑
(fi × gj )xi+j
i=0 j=0
=
n+m
∑


i=0
4.3.3
∑

min(i,m)
fk × gi−k  xi
(4.32)
k=max(0,i−k)
除算
f (x) ÷ g(x)
= q(x) · · ·
m−n
∑
q(x) =
q i xi
r(x)
(4.33)
(4.34)
i=0
r(x) =
n−1
∑
i=0
r i xi
(4.35)
第4章
10
整数と多項式の演算
ここで、
qm−n = fm /gn
これから、f 0 (x) = f (x) − qm−n xm−n g(x) と置くと、f 0 (x) は、m − 1 次の多項式になるので、f 0 (x) の m − n
0
次の係数を fm−1
とすると
0
qm−n−1 = fm−1
/gn
と計算できる。以下同様にして、qi を求めることができる。
4.4
整係数多項式の除算と擬除算
4.4.1
整係数多項式の除算
整数を係数とする二つの多項式
f (x)
= fm xm + fm−1 xm−1 + · · · + f0 ,
g(x)
= gn xn + gn−1 xn−1 + · · · + g0 ,
fm 6= 0,
(4.36)
gn 6= 0
(4.37)
について、多項式 f を g で割った商 q と剰余 r を求める。
f (x) を g(x) で割った商と余りを順次計算していくと、
f (1) (x)
= f (x) −
fm
g(x)
gn
(1)
(1)
(1)
(1)
= fm−1 xm−1 + fm−2 xm−2 + . . . + f1 x1 + f0
(4.38)
(1)
f (2) (x)
= f (1) (x) −
fm−1
g(x)
gn
(2)
(2)
(2)
= fm−2 xm−2 + . . . + f1 x1 + f0
..
.
f (m−n+1) (x)
(m−n+1) n−1
= fn−1
(1)
x
(l+1)
(m−n+1)
+ . . . + f1
(l)
となる。ただし、fm−i = fm−i − gn−i fgm
、fm−i = fm−i − gn−i
n
(4.39)
(m−n+1)
x + f0
(4.40)
(l)
fm−l
gn
である。
したがって、商と剰余をそれぞれ
q(x) =
r(x) =
qm−n xm−n + · · · + q0 ,
rn−1 x
n−1
+ · · · + r0
(4.41)
(4.42)
とあらわすと、
qm−n
qm−n−1
=
=
fm
gn
(4.43)
fm−1 − gn−1 fgm
n
gn
=
fm−1 gn − gn−1 fm
{gn }2
(4.44)
..
.
となる。
また、余り r(x) も一般的には、1/{gn }m−n+1 を分母に持つ有理数となる。
このように、整係数多項式に対して除算を行なった結果は一般には有理係数多項式となる。この原因は g(x)
の最高次の係数 gn ( これを g(x) の主係数という) が 1 でないためで、fm が gn で割り切れないことによる。
4.4. 整係数多項式の除算と擬除算
11
整係数多項式の擬除算
4.4.2
整係数多項式の除算で有理数係数の多項式が現れることは、計算を難しくする。例えば、有理数同士の演算
には、整数の演算の数倍の計算時間を必要とする。また、結果の有理数を簡約するために GCD の計算が必要で
ある。
ここで現れる有理数は、その分母が {gn }m−n+1 でその冪乗は、f (x) の次数と g(x) の次数の差に 1 を加えた
数になっている。
あらかじめ、f (x) に gnm−n+1 を掛けておくことによって結果として現れる商と余りを整数係数として求めるこ
とができる。このようにして行なった除算を擬除算 (pseudo division) といい、商と余りをそれぞれ擬商 (pseudo
quotient) と擬剰余 (pseudo remainder) という。
整数を係数とする二つの多項式
f (x)
= fm xm + fm−1 xm−1 + · · · + f0 ,
g(x)
= gn xn + gn−1 xn−1 + · · · + g0 ,
fm 6= 0,
gn 6= 0
(4.45)
(4.46)
について、多項式 f を g で割った擬商 q と擬剰余 r の計算は
fˆ(1) (x)
= gn f (x) − fm g(x)
(1)
(1)
(1)
(1)
= fˆm−1 xm−1 + fˆm−2 xm−2 + . . . + fˆ1 x1 + fˆ0
(4.47)
(1)
= gn fˆ(1) (x) − fˆm−1 g(x)
fˆ(2) (x)
fˆ(m−n+1) (x)
(2)
(2)
(2)
= fˆm−2 xm−2 + . . . + fˆ1 x1 + fˆ0
..
.
(4.48)
(m−n+1) n−1
(m−n+1)
(m−n+1)
= fˆn−1
x
+ . . . + fˆ1
x + fˆ0
(4.49)
(1)
(l+1)
(l)
(l)
となる。ただし、fˆm−i = gn fm−i − gn−i fm 、fˆm−i = gn fm−i − fˆm−1 gn−i である。
したがって、擬商と擬剰余は
q(x) =
(1)
(2)
(m−n−1)
fm (gn x)m−n + fˆm−1 (gn x)m−n−1 + fˆm−2 (gn x)m−n−2 . . . + fˆn+1
(gn x) + fˆn(m−n) , (4.50)
r(x) =
fˆ(m−n+1) (x)
(4.51)
で与えられる。
例えば、
f
= x8 + x6 − 3x4 + 4x3 − 5x2 + 4x − 3
g
= 3x6 − 2x4 − 5x2 + 7x − 13
から、擬商と擬剰余を計算すると
q
= 9x2 + 15
r
= −6x4 + 45x3 + 57x2 + 3x + 114
となる。なお、(正しい) 商と剰余はそれぞれ
1 2 5
x +
3
9
2 4 5 3 19 2 1
38
r¯ = − x + x + x + x +
9
3
9
9
9
q¯ =
である。
この例では、擬商と商とは q = 33 q¯ = 27¯
q の関係になっている。
第4章
12
4.5
整数と多項式の演算
問題
問題 4.1.
(1) n 桁の正整数と m 桁の正整数の和は max(n, m) 桁以上 max(n, m) + 1 桁以下であることを示せ。
(2) n 桁の正整数と m 桁の正整数の積は n + m − 1 桁以上 n + m 桁以下であることを示せ。
問題 4.2.
(1) Karatsuba の方法を使って、57 × 38 の計算を行なえ。
(2) ３分割の方法を使って、257 × 183 の計算を行なえ。
問題 4.3.
f (x)
= x3 − 2x
g(x)
= 3x2 − 2
とする。
(1) f (x) ÷ g(x) の剰余および商を求めよ。
(2) f (x) の g(x) による擬商および擬剰余を求めよ。

Download Report