C言語で学ぶ大学の数学

C言語で学ぶ大学の数学 準備編「多項式の乗法」

この記事はC言語で以下のような計算をすることを目標とします。

・１変数多項式の乗法

・２変数多項式の乗法

１．１変数多項式の乗法

まずは基本となる１変数多項式の乗法から説明します。

N 次多項式 a(x)と M 次多項式 b(x)が与えられたとき、c(x)= a(x)b(x) を求めます。

c(x) の次数は高々 N+M です。まずはそのことを踏まえて多項式の次数を格納します。

int deg_a = N;

int deg_b = M;

int deg_c = deg_a + deg_b;

（高々の説明：係数が整数や有理数、実数など「整域」である場合は、多項式 0 の次数を－∞と定義すればc(x)の次数はa(x)とb(x)の次数の和に等しくなります。

しかし剰余環 Z/6Zなど、整域でない環を係数とする多項式の場合は次数の和がc(x)の次数になるとは限りません。例えばZ/6Z係数の多項式 a(x) = 2x+1, b(x) = 3x について a(x)b(x) = 3x となり次数が2より小さくなっています。）

次に係数を格納する配列変数を用意します。

float a[deg_a +1], b[deg_b +1], c[deg_c +1];

なお加法と異なり deg_c はdeg_a, deg_b の値で場合分けが生じないので、あえてdeg_cを定義せず

float a[deg_a +1], b[deg_b +1], c[deg_a +deg_b +1];

としても同じです。

変数を用意したら、a(x)とb(x)の係数を格納しておきます。

それが終わってから乗法を計算します。計算方法は案１と案２があります。n, i, j をint型の変数とします。

案１

for(n=0; n<=deg_c; n++){

　c[n] = 0;

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

　for(j=0; j<=deg_b; j++){

　　if(i+j==n)　c[n] += a[i]*b[j];

　}

　}

}

案２

for(n=0; n<=deg_c; n++){

　c[n] = 0;

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

　　if(n-i>=0 && n-i<=deg_b)　c[n] += a[i]*b[n-i];

　}

}

案１は素朴にa(x)の i 次の係数とb(x)の j 次の係数を取り出してきて、次数の合計がnに等しければ係数に加える、というものです。

案２は「i+j=n」と「j=n-i」が数学的に同値なので、変数 j を使わずに表現したものです。ただしjのとる範囲が0<=jかつj<=deg_bであるので、ifの中身にそれを反映させています。

変数が少ないぶん案２のほうが計算時間は少なく済むと思いますが、好みの問題もあるのでどちらでもいいです。

２．２変数多項式の乗法

では、今度は２変数多項式の計算をしてみます。

まずは多項式の係数を格納するための変数を定義します。まずは次数からです。

int deg_ax, deg_ay, deg_bx, deg_by;

これらに次数を代入してから、多項式の係数にあたる変数を定義します。今回はc(x,y)の次数をあえて格納しないことにします。

float a[deg_ax +1][deg_ay +1];

float b[deg_bx +1][deg_by +1];

float c[deg_ax +deg_bx +1][deg_ay +deg_by +1];

変数を用意したら、a(x,y) と b(x,y) の係数を代入しておきます。

それが終わったら、乗法を計算します。int型の変数 m, n, i, j, k, l を用意しておきます。１変数のときと同じように計算方法は案１と案２があります。

案１

for(m=0; m<=deg_ax +deg_bx; m++){

for(n=0; n<=deg_ay +deg_by; n++){

　c[m][n] = 0;

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

　for(j=0; j<=deg_bx; j++){

　　for(k=0; k<=deg_ay; k++){

　　for(l=0; l<=deg_by; l++){

　　　if(i+j==m && k+l==n)　c[m][n] += a[i][k]*b[j][l];

　　}

　　}

　}

　}

}

}

案２

for(m=0; m<=deg_ax +deg_bx; m++){

for(n=0; n<=deg_ay +deg_by; n++){

　c[m][n] = 0;

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

　　for(k=0; k<=deg_ay; k++){

　　　if(m-i>=0 && m-i<=deg_bx && n-k>=0 && n-k<=deg_by)

　　　　c[m][n] += a[i][k]*b[m-i][n-k];

　　}

　}

}

}

１変数のときのように、a(x,y)の x^i*y^k の係数とb(x,y)の x^j*y^l の係数を取り出してきて、x と y の次数の和がそれぞれ m, n であるときに足すものが案１です。

またb(x,y) の係数に相当する変数 j, l を j = m-i, l= n-k により除去したものが案２です。

同様にして、３変数以上の場合にも多項式の乗法が計算できます。

変数が増えていくと計算時間も長くなっていくため、案２で計算することをお勧めします。