いけがみです.

今,次の本を手元に置いて読んでいます.

Algorithms for Computer Algebra,
Keith O. Geddes, Stephen R. Czapor, George Labahn.,
Kluwer Academic Publisher, ISBN 0-7923-9259-0

この本は多項式の実装についてページをいくらか割いていて,
リンクトリストで実装する方法と,巾と係数の表を実装する方法が載ってました.
Ruby で実装するのにどちらが向いているかわかりませんが,
後者を試してみました.
巾(Arrayで実装)を key とし,係数(任意のObjectで実装)をvalueとする
多項式の実装はうまく動きそうです.
# 1 変数の多項式では四則演算+整数巾はうまく動きました.
この場合 "x"という文字シンボルを別クラスで扱えるので,

> できれば, 以下も受け付けるように書きたい.
> g = 3*x**2 + x  + 1;

も受け付けます.

# Array を key とするのはやめましょう,と Ruby 本に書いてますが,
# hashを多項式の巾の multi-degree とすると妥当な表現のような気がします.

あと,Ahoらの超有名なアルゴリズム本も目を通したんですが,
1変数多項式の実装に配列を内部表現として用いるのは,
実装が簡単になり,小さな多項式の四則演算が高速に行える半面,
副作用として多変数への拡張が複雑になるのと,
x^1000+1 のような「疎」な多項式に対する記憶量が増えるようです.

1変数多項式環の実装を多変数多項式環と別にするメリットは,
他にもなにかあるでしょうか?
たとえば,体上の1変数多項式環はユークリッド整域で,
2変数以上の多項式環が持ってない良い性質を有していますが,
実装が違うことによるメリットは何でしょうか.
--
池上 大介
Daisuke IKEGAMI <daisu-ik / is.aist-nara.ac.jp>
奈良先端科学技術大学院大学 情報科学研究科
情報処理学専攻 情報基礎学講座 関研究室