0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

AIの記事評価(後で見直すメモ)

0
Posted at

読みました。整数係数の多項式を因数分解するPerl CGIの解説で、「文字列を係数配列にしてから処理する」という設計は筋が良いです。ただ、アルゴリズムの対応範囲には大きな穴があるように読めます。

評価:★★★☆☆(3/5)

良い点

  • 設計が素直:入力を係数配列にしてから処理するので、数式処理の基本形になっています。
  • 処理の順序が正しい:共通因数の括り出し、一次因子を見つけて割る、残った2次式を処理する、という順番は手計算と同じで、読者が追いやすいです。
  • 入出力例が具体的:8x^3+12x^2-2x-3 → (2x-1)(2x+1)(2x+3) という例があり、何ができるかがすぐ分かります。
  • 実装方式の比較がある:Tokenizer、Parser、ASTを使う方式との対比に触れていて、視野が広いです。

改善したほうがいい点

  1. 因数分解しきれない多項式がある:記事の説明どおり「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の方法などが必要です。最低限、「有理数の根を持つ因子しか分解しません」と制限を明記すべきです。

  2. 理論の裏づけがあいまい:「因数定理?除算の定理?」と書かれていますが、使っているのは因数定理と有理根定理です。根の候補は「定数項の約数 ÷ 最高次係数の約数」です。ここをはっきり書くだけで、記事の信頼性がかなり上がります。

  3. エッジケースが書かれていない:次のような入力をどう扱うか、記事に書かれていません。

    • 0多項式、定数だけの式
    • 最高次の係数が負の式(-x^2+1 など)
    • 重根を持つ式((x-1)^2 が (x-1)(x-1) と表示されるのか、(x-1)^2 になるのか)
    • これ以上分解できない式(x^2+1 など)
  4. CGIとしての安全性:Webから受け取った入力をそのままHTMLに出していないか確認したほうがいいです(XSS対策のエスケープ)。また、次数や係数が大きい入力では約数の総当たりが重くなるので、入力の制限も必要です。公開するCGIでは特に重要です。

  5. テストがない:入力例が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つです。

  1. 根の候補を約数に絞る:計算時間の問題が解消し、浮動小数点の誤差を sprintf で吸収する必要もなくなります。
  2. 表示の修正:+0 を消す、定数・0の扱い、同じ因子を ^2 にまとめる。
  3. 入力チェック:整数係数・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法の要点もそのまま説明できます。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?