# Any way to avoid catastrophic cancellation when computing the discriminant of a quadratic function?

Homework disclaimer...

We are using the following algorithm to solve the quadratic equation $$x^2+2px+q=0$$:

$$x_1=|p|+\sqrt{p^2-q}\mathtt{;}$$

$$\mathtt{if}\,p>0\,\mathtt{then}\,x_1=-x_1\mathtt{;}$$

$$x_2=q/x_1\mathtt{;}$$

Point out two places where running this algorithm can meet significant problems. How to mitigate these problems?

That's my guess: The first place is this: $$p^2-q$$, we're risking catastrophic cancellation here; and the second place is this: $$q/x_1$$, we're getting a NaN if $$x_1$$ is $$0$$.

The second one seems kind of easy: the only way for the absolutey larger root to be $$0$$ is when both roots are $$0$$, which entails so $$p=q=0$$; we can test for this case.

I don't know how to mitigate the first problem, though. I can't think of a way to solve a quadratic equation without computing its discriminant, and computing its discriminant does require subtraction. Which, of course, risks catastrophic cancellation.

Is there any way to avoid catastrophic cancellation when computing the discriminant of a quadratic function?

Hah. Regarding $$x_1=|p|+\sqrt{p^2-q}$$. Another student was arguing today that this cannot be an issue: According to him, catastrophic cancellation can only occur if $$p^2\approx q$$; but then $$\sqrt{p^2-q}\approx 0$$ and moreover $$|p|\gg\sqrt{p^2-q}$$; so the discriminant itself and any errors introduced by computing it loose significance when computing $$x_1$$. The Professor said he would have to think about it; I'll post an update here if/when he's done thinking.
However, there is one more problem I failed to notice. Namely, if $$p$$ is large, then $$p^2$$ may overflow; but then $$\sqrt{p^2-q}$$ will also overflow even if its accurate value would fit in the range of the number format; so $$x_1$$ will be spuriously set to $$\infty$$. To avoid this, the Professor said, $$p$$ needs to be rescaled if its large enough.
• The statement that $\sqrt{p^2-q}\approx0$ is sufficient to ensure that the formula is fine seems true in the real case, but is wrong when $p^2-q<0$, which should trigger your code to output two complex numbers. I think a counterexample is any quadratic with $p^2-q\approx0$ where your evaluation of $p^2-q$ produces the wrong sign. But you seem to assume only real roots. (Also: it is quite alright to answer your own questions on Stack Exchange, and your answer looks okay to me.) – Kirill Dec 15 '18 at 0:51