B - 一変数方程式 Editorial by kzrnm
数学的な話
- \(a\ne0\) のときは二次方程式
- \(D = b^2 -4ac < 0\) のときは実数解なし
- \(D = 0\) のときは重解
- \(D > 0\) のときは2つの実数解
- \(a = 0, b \ne 0\) のときは一次方程式
- \(a=b, c\ne0\) のときは解なし
- \(a=b=c=0\) のときは無数の解
コンピュータ的な話
\(4ac\) は \(64\) ビット整数がオーバーフローする危険があります。
long ac = a * c;
if (ac > 0)
{
long D = b * b;
D -= ac;
if (D < 0) return 0;
D -= ac;
if (D < 0) return 0;
D -= ac;
if (D < 0) return 0;
D -= ac;
if (D < 0) return 0;
}
とすればオーバーフローを回避できます。
上記のコードをパスしたならばb * b - 4 * a * c
がオーバーフローしないのは確かめられるので if(b * b - 4 * a * c == 0)
の判定と Sqrt(b * b - 4.0 * a * c)
と根号の計算をして問題ないです。
桁落ち
二次方程式の解の公式の計算で解が\(0\) に近い場合は浮動小数点演算の桁落ちが発生してしまい精度が足りなくなる場合があります。
たとえば、\(x^2 -2147483647 x -1=0\) では \(\alpha=\frac{2147483647 - \sqrt{2147483647 ^2 +4}}{2}\) が解の一つですが、単純に計算すると \(0.0\) になってしまいます。
もう一つの解 \(\beta=\frac{2147483647 + \sqrt{2147483647 ^2 +4}}{2}\) を用いて、解と係数の関係から\(\alpha=\frac{c}{a\beta}\) と計算すると精度を保てます。
より一般的には、「解の公式で解を求めたあとに、絶対値の大きい方の解を用いて絶対値の小さい方の解を導出する」とすれば確実です。
数値計算で求めようとすると
二次関数の頂点を導出して左右それぞれでニュートン法を行う方法なども考えられます。
しかし、二次関数\(f(x) = ax^2+bx+c\) の頂点が\(0\)に非常に近い場合には倍精度浮動小数点型ではとても足りない精度が必要になります。
たとえば、\(2147123458x^2+2147123457x+ 536780864=0\) を\(10^{-9}\) の精度で解くのは厳しいです。
posted:
last update: