ユークリッドの互除法の安定化について白柳研究室 5508015 上原花帆研究の背景 • 一般に数式処理のアルゴリズムでは、整数や分数をそのまま使用して計算すると係数膨張が起こり、計算が出来なくなることがある。 • そこで浮動小数点を用いて表現をすることになるが、これは真の値の近似にすぎないので誤差がつきまとう。 • そこで数値数式融合計算方式の一つである「安定化手法」に着目。安定/不安定なアルゴリズムとは (3𝑥 − 1) ÷ 1 𝑥－ 3 商：3 余：0 3𝑥 − 1 ÷ 𝑥 − 0.333 商：3 余：-0.001 YES 研究の目的 • アルゴリズムによっては、真の値を浮動小数点で近似したがゆえに、プログラムの出力が大きく違ってしまう“不安定なアルゴリズム”が存在する。 • それを“区間”と“ゼロ書き換え”を駆使した安定化手法を用いて不安定なアルゴリズムを安定なアルゴリズムに変換することを目的とする。安定化手法 • まず入力の多項式の係数をすべて精度桁n の区間係数に変換。例)1/3=0.3333… [0.332,0.334](精度桁3) • アルゴリズムの命令に従い、区間演算を行いながら進行。 • YESかNOかの判定のときは、その直前に各区間に対してゼロ書き換えを適用。 • 区間演算 [A,B],[C,D]をそれぞれ区間とする。・[A,B]+[C,D]=[A+C,B+D] ・[A,B]-[C,D]=[A-C,B-D] ・[A,B]×[C,D] =[min(A× C, A × D, B × C, B × D), max(A× C, A × D, B × C, B × D)] ・[A,B]÷[C,D] =[min(A ÷ C, A ÷ D, B ÷ C, B ÷ D), max(A ÷ C, A ÷ D, B ÷ C, B ÷ D)] • ゼロ書き換え区間がゼロを含めば、その区間をゼロに書き換えるルール。例)[-1,1] [0,5] [5,10] 0 0 [5,10](変化なし) ・すなわち安定化手法とは、ゼロ書き換えを取り入れた区間法を指す。ユークリッドの互除法入力:(f,g) a:=f b:=g とせよ。１、bが0ならばaを返せ。そうでなければ、２、r:=「aをbで割った余り」 a:=b b:=r として1に戻れ。入力;(F,G) (F,Gは区間係数多項式) A:=F B:=G とせよ。１、Bの各区間係数にゼロ書き換えを行い、もし全部がゼロになれば、Aを返せ。そうでなければ、２、R:=「AをBで割った余り」 A:=B B:=R として、1に戻れ。実験結果 > euclid1(9x-1, x-0.111); -0.000999999999 > euclid(kukan1(9x-1, 3), kukan1(x1/9, 3), 3); [1., 1.] x + [-0.112, -0.110] m := (9x-1)(2x+3); n := x-1/9 > euclid1(evalf(m, 3), evalf(expand(n), 3)); -0.003222000000 m := (9x-1)(2x+3); n := x-1/9 > euclid(kukan1(m, 3), kukan1(n, 3), 3); [1, 1] x + [-0.112, -0.110] 実験結果を通して得られたもの • 安定化していないユークリッドの互除法に近似値を入力すると全く見当違いな出力となったが、安定化をしたユークリッドの互除法に区間係数多項式を入力すると真の値に近い値を出力させることに成功。 1 など)に区間を用いる場合 9 • シンプルな分数( は精度桁が高くなくても正しい出力を返す。まとめ • 安定化手法を適用することで、近似も危険なものでなく、上手く取り入れられることがわかった。 • 安定化手法はある精度桁から安定すると言われている。今後の課題として、ユークリッドの互除法で複雑な区間係数多項式同士を計算し、どの精度桁から安定化するのかを調べる。 • 安定化手法をユークリッドの互除法以外のアルゴリズムにも応用していく。