ネギ式

適当に生きるおっさんのブログ

プログラミング:因数分解のプログラムを作ろうと少し思いつつある

なんか理論に自信がなくなってきたので、プログラムを作って確認するしかない気がしてきた。めんどくさい

適切なライブラリを使えば簡単なんだけど、そういうライブラリには既に因数分解のプログラムも入っているので、作る意味がない気もする。そして、プログラムを作ったら、それを公開するのが当然という文化圏で育ったので、公開したい。というか、この流れでプログラムを公開しないという訳にはいかないだろう。たとえ読者が数人しかいないブログだとしても。

そうなると、サーバーとか使いたくないので、webだけで動くようにjavascriptで作ることになる。でも俺はjavascriptは得意でもなければ好きでもないんだよなぁ。前回パズル作ったので少し慣れたけど。まあ、typescriptとかじゃなくて、ぐだぐだのjavascriptで作ろう。

だいたいおれの近ごろのプログラミング言語選定は、使用できる資源とか環境とかに合わせているので、自分の好きな言語とかは滅多に使えない。というか好きな言語でプログラムをするほどの余裕がないというか。

というのが言い訳である。つまり、得意な言語で作っている訳ではないので作るのが遅いしバグも出るよとあらかじめ宣言しているわけだ。

もう俺には得意なプログラミング言語なんてないし。

ちょっとずつ確認しながら作るので、この話は更にペースが落ちるよ。アニメも見なきゃならないし、北方水滸伝も読んでるし、酒を飲んだらプログラムは作れないし。

ちょっと余裕あるので、多項式のデータ型などについて。

問題:x^2+2x+1 と y^2+2y+1 という多項式は同じ多項式か違う多項式か?

p(x) = x^2+2x+1 と置くと、ただちにp(y) = y^2+2y+1  となって、xとyの文字が違うだけだということが分かりやすいかも知れない。分かりにくくなったかも知れない。ここでp(x^2)とかにすると、p(x^2) = x^4+2x^2+1 だが、これも文字の違いだけで同じ多項式だという気分がしてくるはずだ。p(x+1)とかでもいい。高校くらいの因数分解の時にはX=x^2とかX=x+1とか置いたりした。つまるところ、実際のプログラムで扱う時は、係数の並び(係数ベクトル)だけが重要でxかyかは重要ではない。なので多項式=係数ベクトルみたいな感じでプログラムを作る。今回の話には関係ないけど、2で割った余りの世界の多項式はビット列として扱える。

ただし、今回は多変数多項式因数分解まで視野に入れているので不定元(xとかyとか)の情報も保存しておかないとならない。多変数については以前に読んだ本もwikipediaでの説明もかなり省略されているのでうまくそこまで行けるかどうか不明なのだが。省略された説明の理屈は分かるのだが。

問題の答えとしては、「実質同じだが、多変数多項式を扱う場合などには異なることもある」という感じだろうか。

さて、p(x) = 2x^2+3x+1 と置くと、係数の順番を逆にしたx^2+3x+2はどう表わされるだろうか? 係数の順番を逆にしたものの因数分解は同じように係数の順番を逆にした因子に分解されるという経験法則はご存知だろう。

 

ad2217.hatenablog.com