3

Haskell で線形フィードバック シフト レジスタをモデル化しようとしています。これらは有限体上の多項式によってモデル化できるので、numeric-prelude を使用して、通常の prelude よりも数学的代数構造に近い型クラスを取得しています。

私は抽象代数の専門家ではないので、IntegralDomain型クラスについて少し混乱しています。問題は、抽象代数に関する私の本 (Charles C. Pinter による抽象代数の本) と型クラスが互いに競合しているように見えることです。

この本によると、整数領域上の多項式の環は、それ自体が整数領域です。また、体上の多項式の環は整域にすぎませんが、除算アルゴリズムが持つ特別な (特別であるという事実が言及されています) 性質を持っています。

つまり、F[x] が体上の多項式である場合、F[x] 内の a と F[x] 内の b!=0 に対して、F[x] 内に b*q+ を満たす q,r が存在します。 r=a であり、r の次数は b の次数よりも小さい。

この性質が体上の多項式に特有であるという事実は、私にとって、それがどの整数領域にも当てはまらないことを意味します。

一方、数値プレリュードの型クラスによると、フィールド上の多項式 (つまり、zeroTestable) も IntegraldDomain です。しかし、ドキュメントによると、integralDomains にはいくつかの法則があり、そのうちの 1 つが次のとおりです。

(a `div` b) * b + (a `mod` b) === a

http://hackage.haskell.org/packages/archive/numeric-prelude/0.4.0.1/doc/html/Algebra-IntegralDomain.html#t:C

これは私には除算アルゴリズムのように見えますが、除算アルゴリズムは、整数領域上の多項式を含む、任意の整数領域で真です。私の本は矛盾しています。また、整数ドメイン上の polynomail には、numeric-prelude の IntegralDomain のインスタンスがないことも注目に値します (少なくとも、すべての型クラスが単に C と呼ばれるという事実はわかりません。ドキュメントを作成するのが少し難しくなります)。読んだ）。では、数値プレリュードの IntegralDomain は、除算アルゴリズムが保持する追加のプロパティを持つ整数ドメインである可能性があります。

では、numeric-prelude の IntegralDomain は本当に整数ドメインなのでしょうか?

ゴム製のアヒルのデバッグ ポスト スクリプト: この質問を書いているときに、考えられる説明の一部についてアイデアを得ました。「rの次数がbの次数よりも小さい」という要件ですか。全体の違いはどれですか？その要件は、数値プレリュードの IntegralDomain にはありません。繰り返しになりますが、他の法律のいくつかは、この事実を暗示している可能性があります...

4

1 に答える 1

3

この本によると、整数領域上の多項式はそれ自体が整数領域です。

それは正しく表現されていません。整域上の多項式環も整域です。

次数 0 のすべての多項式が単位であるため、体上の 1 つの不定の多項式の環は、除算アルゴリズムによって証明されるように、主要なイデアル ドメインですらあります。

一般的な整域 R では、ゼロ以外の非単位があり、aが 1 の場合、次のように書くことはできません。

X = q*a + r

の次数は(0)の次数rよりも小さい。a

r「 の程度が の程度よりも小さい」という要件ですかb。全体の違いはどれですか？

正確に。この要件により、除算アルゴリズムが終了することが保証されます。一般的な積分領域では、任意の固定環要素を法とする剰余の「標準的な」選択を行うことができますが、標準的な剰余は意味のある方法で「小さく」する必要はないため、除算アルゴリズムを使用する試みを終了する必要はありません。

繰り返しになりますが、他の法律のいくつかは、この事実を暗示している可能性があります

Algebra.IntegralDomainそれを暗示する法律はありません。

法律

(a+k*b) `mod` b === a `mod` b

は、実際のインスタンスを多少制限する可能性がある完全に一般的な統合ドメインに対して実装するのは難しいと思いますが、PID のようなものZ[X]またはR[X,Y]PID ではないものに対してはインスタンスが可能です。

于 2013-07-23T14:08:06.420 に答える