読みました。整数係数の多項式を因数分解するPerl CGIの解説で、「文字列を係数配列にしてから処理する」という設計は筋が良いです。ただ、アルゴリズムの対応範囲には大きな穴があるように読めます。
評価:★★★☆☆(3/5)
良い点
- 設計が素直:入力を係数配列にしてから処理するので、数式処理の基本形になっています。
- 処理の順序が正しい:共通因数の括り出し、一次因子を見つけて割る、残った2次式を処理する、という順番は手計算と同じで、読者が追いやすいです。
-
入出力例が具体的:
8x^3+12x^2-2x-3→(2x-1)(2x+1)(2x+3)という例があり、何ができるかがすぐ分かります。 - 実装方式の比較がある:Tokenizer、Parser、ASTを使う方式との対比に触れていて、視野が広いです。
改善したほうがいい点
-
因数分解しきれない多項式がある:記事の説明どおり「3次以上は一次因子を探し、残りの2次式は約数の組を試す」だけだとすると、有理数の根を持たない4次以上の多項式は分解できないはずです。
- 例:
x^4+5x^2+4 = (x^2+1)(x^2+4) - 例:
x^4+4 = (x^2+2x+2)(x^2-2x+2)
これを解決するには、Kroneckerの方法(任意の次数の因子を試す)か、Zassenhausの方法などが必要です。最低限、「有理数の根を持つ因子しか分解しません」と制限を明記すべきです。
- 例:
-
理論の裏づけがあいまい:「因数定理?除算の定理?」と書かれていますが、使っているのは因数定理と有理根定理です。根の候補は「定数項の約数 ÷ 最高次係数の約数」です。ここをはっきり書くだけで、記事の信頼性がかなり上がります。
-
エッジケースが書かれていない:次のような入力をどう扱うか、記事に書かれていません。
- 0多項式、定数だけの式
- 最高次の係数が負の式(
-x^2+1など) - 重根を持つ式(
(x-1)^2が(x-1)(x-1)と表示されるのか、(x-1)^2になるのか) - これ以上分解できない式(
x^2+1など)
-
CGIとしての安全性:Webから受け取った入力をそのままHTMLに出していないか確認したほうがいいです(XSS対策のエスケープ)。また、次数や係数が大きい入力では約数の総当たりが重くなるので、入力の制限も必要です。公開するCGIでは特に重要です。
-
テストがない:入力例が1つだけです。上に挙げたような入力と期待する出力の表があると、読者がアルゴリズムの限界を把握できます。
まとめ:「高校数学の因数分解の手順をコードにする」という目的なら十分面白い記事です。ただ、タイトルの「多項式を因数分解する」から読者が期待する範囲より、実際にできる範囲は狭いです。制限を明記して、有理根定理の説明を正確にするのが優先です。
なお、ツールの都合でコード全体は確認できていません。上の「分解できない例」は記事の説明から推測したものなので、実際のCGIで x^4+5x^2+4 を試してもらうと確実です。
11:49
実際に動かして確認します。CGI部分を外して、関数だけをテストします。実際に動かして確かめました。前回、記事の説明だけから「x^4+5x^2+4 は分解できないはず」と書きましたが、これは間違いでした。4次の複2次式は特別処理で正しく分解されます。訂正します。
約50通りの入力で試した結果をまとめます。
正しく分解できたもの(主な例)
- 有理数の根を持つ式は安定して分解できます:
8x^3+12x^2-2x-3、6x^2+x-2、x^3-8、x^6-1→(x-1)(x+1)(x^2+x+1)(x^2-x+1) - 4次の複2次式も分解できます:
x^4+5x^2+4→(x^2+1)(x^2+4)、x^4+x^2+1→(x^2+x+1)(x^2-x+1)、4x^4-1 - これ以上分解できない式は括弧で囲んで返します:
x^2+1、x^2-2、x^3+3x+2
分解しきれないもの(アルゴリズムの限界)
| 入力 | 出力 | 正解 |
|---|---|---|
x^4+4 |
そのまま | (x^2+2x+2)(x^2-2x+2) |
x^4+x^3+3x^2+2x+2 |
そのまま | (x^2+x+1)(x^2+2) |
x^6+1 |
そのまま | (x^2+1)(x^4-x^2+1) |
x^10-1 |
(x-1)(x+1)(x^8+x^6+x^4+x^2+1) |
8次の部分がさらに4次2つに分解できる |
有理数の根を持たない因子は、4次の決まった形を除くと見つけられません。
バグ・表示の問題
| 入力 | 出力 | 問題 |
|---|---|---|
x^2 |
x(x+0) |
+0 が残る |
5 |
5(1) |
定数の扱い |
0 |
x(0x+0) |
0多項式の扱い |
3x^2+12x^2 |
15x(x+0) |
同類項の整理はできているが、表示が崩れる |
-2x^2-4x-2 |
2(x+1)(-x-1) |
符号は正しいが、-2(x+1)^2 が自然 |
x^2+2x+1 |
(x+1)(x+1) |
累乗にまとめない |
x^2+0.5x |
エラーで停止(Illegal modulus zero) | 小数係数で落ちる |
x^2y |
x(x+0) |
y を黙って無視する |
CGIとして重要な問題
x^4+999999 や、大きな係数を持つ3次式は5秒以上かかりました(打ち切ったので実際はもっと長いです)。factor_div は最高次係数と定数項について二重ループで総当たりするため、係数が大きいと処理時間が爆発します。公開CGIだと、これだけでサーバーに負荷をかけられてしまいます。係数の大きさに上限を設けるか、根の候補を「定数項の約数 ÷ 最高次係数の約数」に絞るべきです。
なお、前回心配したXSSは問題ありませんでした。出力は数値から組み立て直しているので、<b>x</b> のような入力でもタグがそのまま出ることはありません。
総評:★★★☆☆のまま。ただし中身の評価は上がりました。
高校数学レベルの因数分解ならほぼ正しく動きます。複2次式の特別処理など、記事の説明以上のことをしています。優先して直すとよい点は次の3つです。
-
根の候補を約数に絞る:計算時間の問題が解消し、浮動小数点の誤差を
sprintfで吸収する必要もなくなります。 -
表示の修正:
+0を消す、定数・0の扱い、同じ因子を^2にまとめる。 - 入力チェック:整数係数・1変数以外は、エラーメッセージを返す。
x^4+4 のような一般の場合まで対応したいなら、Kroneckerの方法(2次の因子の候補を総当たりする)を追加するのが、このコードの延長として一番自然です。
これも実際に動かして、約40通りの式をPerl自身の計算結果と比べました。
評価:記事 ★★☆☆☆/コード ★★★☆☆
Shunting-yard法の骨格は正しく、記事にある例(3+4*2/(1-5)**2**3 → 3.0001220703125)も合っています。ただ、単項マイナスまわりに計算結果が間違う実際のバグが2つあります。前回のAst.pmよりも、こちらのほうが問題が大きいです。
バグ①:** の直後のマイナスで、計算結果が間違う
| 入力 | 結果 | 正解 | 生成された後置記法 |
|---|---|---|---|
2**-1 |
-1 | 0.5 | 2 ** 1 NGE |
-2**-2 |
2 | -0.25 |
NGE を演算子スタックに積むとき、優先順位の比較で ** を先に出力してしまいます。そのため、** の右側の値がまだ無い状態で計算されます。前置の単項演算子は、積むときに何も取り出してはいけない、というのがShunting-yard法の決まりです。
バグ②:先頭のマイナスが単項として扱われない
| 入力 | 結果 | Perlの結果 |
|---|---|---|
-3%2 |
-1 | 1 |
-7%3 |
-1 | 2 |
原因は split(/\s+/, ...) です。adjust によって " - 3 % 2" のように先頭に空白が付くため、先頭に空のトークン '' ができます。これが数値扱いになり、- は「0から引く」二項演算になります。その結果、NGE の優先順位(3 > % の2)という設計が先頭では効きません。-2**2 や -2+3 は、たまたま正しい値になっているだけです。
この2つは2か所の修正で直ります(確認済み)
# 1. 先頭の空トークンを作らない(' ' はawk風の特別な区切り指定)
print calc(infix_to_postfix(split (' ', adjust(pop))));
# 2. 単項演算子を積むときは何も取り出さない
push @post,pop @opr while($_ ne "(" && $cur ne "NGE" && @opr && juge_priority($cur,$opr[-1]));
修正後は、上の4つの式に加えて、-2**2、(-2)**2、-3*-3、記事の例2つがすべてPerlの結果と一致しました。
その他(Ast.pmと共通の問題)
-
不正な入力を黙って計算する:
1+2)→ 3、(1+2→ 3、1 2→ 2、1+→ 1、*2→ 0、()→ 空文字 -
1+-+2が 1 になる(正解は -1):単項の+に対応していません。 -
指数表記で結果が壊れる:
1e-3+1→ -1 -
閉じ括弧の後の暗黙の乗算がない:
(1+2)3→ 3。*が補われず、3がスタックに残ったまま無視されます。 -
2* *3が2**3= 8 と解釈される:空白を一度詰めてから* *を**に戻しているためです。 - 0除算で例外が出て止まる
記事について
前回のAst.pmと比べると、記事とコードの食い違いが多いです。
- 「
-3^2が(-3)^2になる」という説明は、二重に誤りです。^は演算子として定義されていません。また、NGE(3)は**(4)より優先順位が低いので、-3**2は -9 になります。 - 後置記法の例
('NGE','3',...)は、NGEの位置が違います。正しくは3 NGE ...です。 - トークン化の例に
'-3'とありますが、実際は-と3に分かれ、先頭には空トークンもできます。 - 「標準入力から読む」と説明していますが、コードの
popはコマンドライン引数(@ARGV)を読みます。 -
x演算子を「2xや3(x+1)のため」と説明していますが、実装は2x3= 6 という掛け算記号です。変数としてのxには対応していません。
まとめ:前回のAst.pmは 2**-1 も -3%2 も正しく計算できていたので、同じ作者の中では、Shunting-yard版のほうが単項マイナスの扱いが弱いです。記事を直すなら、上の2行の修正を入れて、2**-1 と -3%2 をテスト例に加えると、「単項演算子は積むときに取り出さない」というShunting-yard法の要点もそのまま説明できます。