プログラミング雑感  新JavaScript入門  JavaScript,Neo-Generation  掲示板  表紙
15. 多項式クラス(8)  17. 多項式クラス(10) 
プログラミング雑感
Written 12/11/02
16. 多項式クラス(9)
いちおうどんな多項式でもオーバーフローさえしなければ 有限時間内に因数分解するプログラムを作りました。 バグがあったら自分が直してください。
■ソース
ソースは次の５つです。 
    fact_test1.cpp
    polynomial_z_001.h
    polynomial3.h
    p_numbers.h
    fraction.h
fact_test1.cpp に main があります。 
    typedef vector<Polynomial_Z>  Factorized;
    
    void main(void) {
        Polynomial  p("x*x*x+y*y*y+z*z*z-3*x*y*z");
        Polynomial_Z    pz(p);
        cout << pz.factorize() << endl;
        Polynomial  p2("x*x+y*y-x*y-x");
        Polynomial  p3("x*x+y*y+x*y-y");
        Polynomial_Z    pz2(p2 * p3);
        cout << pz2.factorize() << endl;
        Polynomial  p4("1-x*x*x*x*x*x*x*x*x*x*x");
        Polynomial_Z    pz3(p4);
        cout << pz3.factorize() << endl;
    }
文字列から Polynomial クラスのオブジェクト作り、 そこから Polynomial_Z クラスのオブジェクトを作り、 それを因数分解すると、Polynomial を要素とする vector が返るので、 それを表示します。 上では３つの多項式を因数分解をしていますが、 別の多項式を因数分解する場合は、このファイルを改造してください。
Polynomial_Z は因数分解をするための整係数多項式クラスです （Zは整数を意味します）。 それが、 polynomial_z_001.h で定義されています。 これが今回のプログラムの事実上の本体です。 今からこれを簡単に紹介していきます。
■項を並べる
例として次の多項式を考えましょう。 
    x3 + y3 + z3 - 3xyz
まず、扱いやすくするために各項を順に並べます。
並び方は前のページにあったようになのですが、 詳しく言うと、次の条件で並べます。 
    1. 次数が小さいほうが前
    2. 次数が同じならx1の次数が大きいほうが前
    3. 2も同じならx2の次数が大きいほうが前
        ...
今考えている例では x1 を x、x2 を y などと解釈します。
x y z で生成される3次までの項を全て並べると次のようになります。 
    1 x y z x2 xy xz y2 yz z2 x3 x2y x2z xy2 xyz xz2 y3 y2z yz2 z3
この順列を生成するために各項を、 各変数の指数を各桁とした4進数で表します。 そして、使われていない分の指数をその頭につけ加えます （要するに各桁をたし合わせると3になるようにします）。 そうすると上の順列は次のように表されます。 
    3000 2100 2010 2001 1200 1110 1101 1020 1011 1002
    0300 0210 0201 0120 0111 0102 0030 0021 0012 0003
以上は4進数表記です。
これをよく観察すると、 この値はその右隣の値との差が次のように求められることが分かります。 
    2番目に下の桁から見て最初に0でない桁が現れる前まで取る
    ex) 2100 -> 0   2001 -> 00   0111 -> 
    頭に3から元の1番下の桁を引いたものを加える
    ex) 2100 -> 30  2001 -> 200  0111 -> 1
    元の1番下の桁を足す
    ex) 2100 -> 30  2001 -> 201  0111 -> 2
x は2100だから、その次はそれから30を引いて2010で、これは y、などとなり、 各項を順に並べることができます。
■パラメータを選ぶ
前のページにも書きましたが、 この多項式関数の値 f1, ... , f10 が0にならないように、 x0, x1, x2, y0, y1, y2, z0, z1, z2 を選ばなければなりません。
まず、 
    x0 = y0 = z0 = 0
とします。これで、f0 が0にならなければいいのですが、 0なら (x0, y0, z0) を変えます。 このとき、あまり大きな数にならないように工夫しています。 すなわち、 
    (x0, y0, z0) = (1, 0, 0)
                 = (0, 1, 0)
                 = (0, 0, 1)
                 = (-1, 0, 0)
この並びは、基本的には上の項の並べ方と同じですが、 
    0 -> 0  1 -> 1  2 -> -1  3 -> 2  4 -> -2 ...
と読み替えます。
次に、x1, y1, z1 が出てくる fi で0にならないようにする、
ということを繰り返します。
なんだか効率が悪そうですが、もっとずっと遅い部分があるので問題ありません。
■スピードについて
このプログラムはとても遅いです。
上の例は何とか返ってきますが、 3変数の場合は因子の一方が2次までの多項式にならないと苦しいようです。
また、1変数の場合でも、 次数が高いと割り算の部分でオーバーフローになってしまいます。
プログラムがボケなところもあるのですが、 根本的に考え方が悪いようです。 今回はいちおう解けるということを示しただけで、 次回からは、別の考え方でプログラムを作っていこうと思います。
first, prev, next, exit