割り算アルゴリズム その１

割り算アルゴリズム　その１

• 単項式を消していく事で、割り算を実現
• 多項式の割り算は、単項式を少しずつ消していく
• （順序が重要）

---

---

はじめに？

「割り算アルゴリズム」で一記事にしようとしていましたが、長くなってしまったので分割しました。この記事では、割り算アルゴリズムの簡単な例を扱っていきます。後述の目標である多項式の割り算は次の記事に書きます。

---

理論

準備（前提知識）

• 単項式、多項式
• 係数
• 順序

目標（理論）

最終的には、多項式と多項式で割り算をすることが目標です。 まずは、簡単な問題から考えます。

簡単な例（理論）

簡単な問題として、単項式の割り算を考えます。 具体的には、, とし、 を考えます。

ここで扱う割り算アルゴリズムは、いわゆる/による割り算ではなく、足し算（引き算）、掛け算で計算していきます。

割り算とは何か？次の式を考えます。

• は、割られる式です。具体例ではF1に相当します。
• は、商です。
• は、割る式です。具体例ではF2に相当します。
• は、余りです。

この式に乗っ取って計算をしてみます。

答えとしては、 すなわち、答え 余り となります。

ここで、式を変形してみます。

このように考えると、 を消す操作（引き算）になります。 つまり、割り算を引き算で実行できることがわかります。 この式が、割り算アルゴリズムの基本的な考え方になります。

ではどうするか

ここまでの話から、割り算は引き算で実行できそうなことがわかりました。 では、アルゴリズムとしてどうするべきかを考えます。

引くには、

を実行すればよく、F1を消す操作がしたいというわけです。

F1を引くには、のときは、 まず、 と考えます。 これは言い換えると、F1とF2 の次数を合わせていると考えます。

そして、 でした。 これは言い換えると、F1とF2 の係数を合わせていると考えます。

つまり、引いて消す操作をするには、次数と係数を合わせてやる必要があります。

---

プログラム

今回はプログラムというより電卓です。足し算引き算して、理論の内容が実装できているように見えればOKという感じです。

まずは、単項式での割り算を計算しています。

単項式の割り算

// 割り算アルゴリズム

print("コード見ながらの実行を推奨します。")$
print("もしくは、対話モードで実行を推奨します。")$

// example1
F1 = 3*x^2$
F2 = x$

/*
 3x^2 - yx = 0
 [...yは適当な値、変数（つまりyは単項式）]
 これを、割り切りたい！

 y = 3x
 なら割り切れる
*/

R1 = F1 - 3*x*F2;
// R1 = 0

end$