ネギ式

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

バグ:無平方分解失敗……なんとか対応する

いやあ、失敗失敗。

x^3+5x^2+7x+3

を無平方分解しようとして、まず微分すると

3x^2+10x+7

になる。これと元の多項式の最大公約数を求める……って整数係数では無理じゃないですか。有理数係数で考えれば出来るけど、有理数のクラスを作らないとならない。

どうも全部整数係数でうまくいくと思ったのが間違いだったようだ。

最初の多項式は(x+3)(x+1)^2 でそれを微分したものは(x+1)(3x+7)なので、最大公約数(x+1)があるんだけど。有理数のクラスを作らなくても、浮動小数点数で大丈夫かなぁ。最後はぴったり割り切れる必要があるんだけど。

ここさえ乗り切れば……って思うけど、そういうのが連続するんだよなぁ。

なんとか誤魔化す方法を考える。……。

考えた。結局互除法の中の余り付き割り算で使うのは余りだけなので、有理数係数で割り算をしているような気分になって、被除数(多項式)の最高次係数を除数(多項式)の最高次係数の最小公倍数になるように被除数全体を何倍かするというのを割り算の途中でやってしまうのだ。ひどい処理といえばひどい。これをやると余りの多項式も何倍かされてしまうが、そこで係数の最大公約数を括り出(して捨てれ)ばよいはずだ。

と思ったら、無平方分解で商が必要なところもあったので、余り付き割り算を二種類作ってしまった。

$ npm run test

> jsfactorization@1.0.0 test
> jest

 PASS  src/polynomial.test.js
 PASS  src/euclid.test.js
---------------|---------|----------|---------|---------|-------------------
File           | % Stmts | % Branch | % Funcs | % Lines | Uncovered Line #s
---------------|---------|----------|---------|---------|-------------------
All files      |     100 |    99.28 |     100 |     100 |
 euclid.js     |     100 |      100 |     100 |     100 |
 polynomial.js |     100 |    99.19 |     100 |     100 | 312
---------------|---------|----------|---------|---------|-------------------

Test Suites: 2 passed, 2 total
Tests:       12 passed, 12 total
Snapshots:   0 total
Time:        1.14 s
Ran all test suites.

jest はカバレッジが出るのがいい。100%だとなんとなく気分がいいから。%Linesが100%なのにUncovered Line があるのは、if 文の条件が OR なのに片方しか通ってないから。

 

ad2217.hatenablog.com