[ruby-list:20389] Re: class Polynomial

児玉 です.

From: Toyofuku <[e-mail]>
Subject: [ruby-list:20385] Re: class Polynomial
Date: Tue, 25 Jan 2000 21:44:32 +0900
Message-ID: <[e-mail]>
> ちょっと ruby-mathっぽくなります。
> （あまりに mathっぽくなるようでしたら ruby-math
> に移ります）

そういう気もする. 一応, ruby-math も読んでます.

> > 売りは, 整数係数多項式の 因数分解 を実装した点です.
...
> ところでこのアルゴリズムを解説した本やWebサイト
> がありましたら教えていただけませんか。

(今日は手元に無いけど)
Knuth の本で "素朴なアルゴリズム" とか云われちゃっているやりかた？

(本当は, 僕の実現の由来は...)
位相幾何学の結び目理論での 
結び目の幾何的な対称性が
Alexander多項式という整数係数の式の
mod P(Pは素数)での因数分解に反映する
という結果をプログラム化したのが元です.

mod P での分解を整数に戻すと一般の因数分解を
でっちあげられるという場当り的な発想で
因数分解アルゴリズムに発展したんですね.

> polynomial.rb より
> | def factorize(p)
>   ...
> | degN=PolyN.degree
> | i=1;
> | while (i<=degN)&&(i<=PolyN.array[0].abs)
> 
>   (i<=degN) しているのはどういう意味なんでしょうか。

ここ以下では (x-a) の aが小さい部分での因子が無いと仮定している.
# (x-a) の因子を除いておく.
とりあえず |a|<=degN まで保証できれば十分.
でも, (i<=degN)は無くても可だなぁ.
係数が大きいと時間はかかるけど.
なにしろ, 素朴なアルゴリズムなんで,
次数は小さめでの適用を想定しているわけ.
# 次数が大きいと, おそ----い.
ここでは, 係数より degN で制限がかかる事を期待している.
-- 
K.Kodama([e-mail])