C言語で学ぶ大学の数学

C言語で学ぶ大学の数学 「Laurent多項式の扱い」

この記事ではLaurent多項式をC言語で扱う方法を説明します。

１．Laurent多項式とは

そもそもLaurent（ローラン）多項式とは、次数がマイナスの項を許した多項式のことです。例えば

a(x) = x^(-3) - x^(-1) + 2 + x

b(x) = x^(-1)

c(x) = 2*x + x^3

d(x) = 0

などです。c(x) は次数が正の項しか持ちませんが、これもLaurent多項式に含めます。d(x) も「全ての次数の項の係数が０の多項式」としてLaurent多項式に含めます。

２．計算機で扱う場合のLaurent多項式の次数

通常の多項式をC言語で扱うときは、まず次数をdeg_aに格納し、それをもとに配列変数 a[deg_a +1]を用意しました。

Laurent多項式の場合も、まずは次数を変数に格納します。

ただしLaurent多項式は次数が負の項を持つものを扱うので、最低次数も格納する必要があります。

そのことに注意して最高次数と最低次数を格納します。

それには二つの方法があります。

方法A：最高次数は０以上、最低次数は０以下と約束する。そして最低次数は符号を除去する。

方法B：最高次数と最低次数の値の範囲を制限しない。

どういうことかは、上の例で説明します。

まずは方法Aで a(x), b(x), c(x), d(x)の次数を決定します。

deg(a(x))は最高次数、ldeg(a(x))は最低次数を表すとします。

deg(a(x)) = 1　,　ldeg(a(x)) = 3

deg(b(x)) = 0　,　ldeg(b(x)) = 1

deg(c(x)) = 3　,　ldeg(c(x)) = 0

deg(d(x)) = 0　,　ldeg(d(x)) = 0

次に方法Bで次数を決定します。こちらの場合は符号をそのままで考えます。

deg(a(x)) = 1　,　ldeg(a(x)) = -3

deg(b(x)) = -1　,　ldeg(b(x)) = -1

deg(c(x)) = 3　,　ldeg(c(x)) = 1

deg(d(x)) = 0　,　ldeg(d(x)) = 0

両者が異なるのは、b(x)のように次数が負の項しか持たない場合や、c(x)のように次数が正の項しか持たない場合です。

なお方法Bでは d(x)=0 の次数を最高次数、最低次数ともに０としていますが、これは便宜上そうしただけです。

二つの方法の違いによって配列変数への代入の仕方や計算の方法が若干異なります。

それぞれに利点があり、方法Aだと計算が理解しやすく、方法Bだとメモリの節約や計算時間の短縮になります。

３．配列変数にLaurent多項式の係数を格納する

まずは多項式 a(x) = x^(-3) - x^(-1) + 2 + x を、方法AでC言語で扱う方法を考えます。

まず初めに、方法Aで最高次数と最低次数を格納します。ただし上で説明したように、最低次数は符号を外します。

int deg_a = 1;

int ldeg_a = 3;

deg_a が最高次数、ldeg_a が最低次数です。l は lowestのことです。

次数を格納したので、次は配列変数に係数を格納します。

しかし、通常の多項式のように配列変数a[]を使って定義しようと思っても、a[-3]やa[-1]という変数は無いので「項の次数」がマイナスのものをそのまま考えることはできません。

そこで一旦、Laurent多項式を「正規化(？)」します。

やり方は簡単です。全ての項の係数が０以上になるよう、単項式をかけるだけです。

具体的には、a(x)の最低次数をちょうど０に引き上げます。つまりx^3を掛けます。そうすると

x^3*(a(x)) = 1 - x^2 + 2x^3 + x^4

となり、通常の多項式が得られます。こうすれば

float a[5];

a[0] = 1;

a[1] = 0;

a[2] = -1;

a[3] = 2;

a[4] = 1;

と配列変数に代入できます。

一般には、最高次数Nと最低次数N0（N0 ≧０）のLaurent多項式a(x)に対し、「x^(N0) をかける」ことで多項式を正規化します。

正規化した多項式の次数は N + N0 なので、

int deg_a = N;

int ldeg_a = N0;

float a[deg_a + ldeg_a +1];

と配列変数を用意します。

同じく方法Aで c(x) = 2*x + x^3 を格納すると、

int deg_c = 3;

int ldeg_c = 0;

float c[deg_c + ldeg_c +1];

c[0] = 0;

c[1] = 2;

c[2] = 0;

c[3] = 1;

となります。このように、通常の多項式を方法Aで Laurent多項式として代入する場合は、ldeg_c = 0 という情報以外は通常の多項式を定義する場合と同じになります。

注意することは、b(x) = x^(-1) のように最高次数が０かつ定数項が０の場合です。このときは

int deg_b = 0;

int ldeg_b = 1;

float b[deg_b + ldeg_b +1];

b[0] = 1;

b[1] = 0;

のように０を代入するのを忘れないようにします。

では次に、方法Bで多項式 a(x) = x^(-3) - x^(-1) + 2 + x を扱う方法を考えます。

まず次数について、方法Bでは最高次数、最低次数ともに符号込みでそのまま代入します。

int deg_a = 1;

int ldeg_a = -3;

次に係数を格納します。方法 Bでは多項式に「x^(-ldeg_a) をかける」ことで正規化します。すると

x^3*(a(x)) = 1 - x^2 + 2x^3 + x^4

となります。これを

float a[5];

a[0] = 1;

a[1] = 0;

a[2] = -1;

a[3] = 2;

a[4] = 1;

と配列変数に格納します。

方法Bでは、配列変数を必要最小限の個数だけ用意します。

一般に、正規化した多項式の次数は（最高次数）－（最低次数）になります。なので

float a[deg_a - ldeg_a +1];

と宣言することになります。

例えば方法B で c(x) = 2*x + x^3 を格納することを考えます。c(x) に「x^(-ldeg_c) をかける」と

x^(-1)*c(x) = 2 + x^2

となり、

int deg_c = 3;

int ldeg_c = 1;

float c[3 - 1 +1];

c[0] = 2;

c[1] = 0;

c[2] = 1;

となります。方法 Aと異なり、最低次数が０より大きい場合も正規化しているので、通常の多項式として定義する場合と異なる扱いになります。

（通常の多項式しか扱わない場合でも、Laurent多項式を方法 B で扱うやり方を採用したほうが便利なこともあります。たとえば

f(x) = x^1000

という多項式を扱う際、通常の多項式を定義するやり方だと

float f[1001];

for(i=0; i<1000; i++){

　f[i] = 0;

}

f[1000] = 1;

のようにする必要があります。このやり方では千個もの変数が無駄に用意されてしまいます。

一方で方法 Bだと

int deg_f = 1000;

int ldeg_f = 1000;

float f[1];

f[0] = 1;

となり、無駄がありません。）

次の記事ではLaurent多項式の加法を計算する方法を紹介します。