Challenge: I want to know about the real roots of polynomials. As a pure mathematician, I care about the existence of such roots, rather than their numeric values.
The challenge is to write the shortest program that takes a polynomial, of degree at most 4, and simply returns how many distinct real roots said polynomial has. Polynomials with degree 4 or less have the unique property that there exist closed forms (such as the quadratic formula), which give all their roots. You can google these forms or find some useful related information in the appendix.
Input: the coefficients of a polynomial. For simplicity, we shall only care about polynomials with integer coefficients.
You may input this as a list, get the coefficients one at a time, or use any other reasonable method. You may, for example, require polynomials of degree d to inputted as lists of length d+1.
You should specify how you convert a polynomial of degree at most 4 into a valid input.
Output: the number of distinct real roots of said polynomial. (meaning roots with multiplicity are only counted once)
You must output one of the integers 0,1,2,3,4 for valid polynomials, and trailing spaces are completely fine. (the special case of the polynomial, \$P(x) = 0\$, is discussed in the scoring section)
Examples: in these examples, we represent a polynomial, \$P\$, as a list L, where L[i] contains the coefficient of \$x^i\$ in \$P\$. (with index starting at 0)
\$P(x) = 1\$, input: [1], output: 0
\$P(x) = 1+2x\$, input: [1,2], output: 1
\$P(x) = 1+x^2\$, input: [1,0,1], output: 0
\$P(x) = 1+x+x^2+x^3 = (x+1)(1+x^2)\$, input: [1,1,1,1], output: 1
\$P(x) = 2+3x+x^2 = (x+2)(x+1)\$, input: [2,3,1], output: 2
\$P(x) = 1-2x+x^2 = (x-1)^2\$, input: [1,-2,1], output: 1
Scoring:
-5 bytes if the polynomial, \$P(x) = 0\$, outputs a representation of infinity, such as: the infinity float in python, the Unicode symbol ∞, or a string that can be mathematically interpreted to evaluate to infinity, like "1/0". (otherwise, you don't need to handle this case)
Otherwise, shortest code wins. (however I am personally quite interested in seeing answers which don't rely on built-in root finders)
Appendix: Closed Forms
Starting with the basics:
Degree 0: \$P(x) = a\$, roots: none, (or all reals, if a = 0)
Degree 1: \$P(x) = ax+b\$, roots: \$x=-b/a\$
Degree 2: \$P(x) = ax^2+bx+c\$, roots: \$x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}\$
Then, we have the harder ones. For these, it becomes quite verbose to state the closed forms. I've paraphrased some ways you can deduce the number of roots by considering discriminants, you may also seek to find the closed forms of the roots.
Degree 3: From Wikipedia. \$ P(x) = ax^3+bx^2+cx+d\$. We define the discriminant as \$\Delta = 18abcd -4b^3d+b^2d^2-4ac^3-27a^3d^2\$.
If \$\Delta > 0\$ then there are 3 distinct roots, if \$\Delta = 0\$, then there are two distinct real roots, otherwise then \$ \Delta < 0\$ and there is only one real root.
Degree 4: From Wikipedia.\$ P(x) = ax^4+bx^3+cx^2+dx+e\$. We define the discriminant as $$\begin{align} \Delta\ =\ &256 a^3 e^3 - 192 a^2 b d e^2 - 128 a^2 c^2 e^2 + 144 a^2 c d^2 e - 27 a^2 d^4 \\ &+ 144 a b^2 c e^2 - 6 a b^2 d^2 e - 80 a b c^2 d e + 18 a b c d^3 + 16 a c^4 e \\ &- 4 a c^3 d^2 - 27 b^4 e^2 + 18 b^3 c d e - 4 b^3 d^3 - 4 b^2 c^3 e + b^2 c^2 d^2 \end{align}$$
If \$\Delta > 0\$ then there are two distinct real roots. Otherwise things get more complicated.
Defining \$P = 8ac - 3b^2\$, \$D = 64 a^3 e - 16 a^2 c^2 + 16 a b^2 c - 16 a^2 bd - 3 b^4\$, then if \$ \Delta < 0 \$ and \$ P < 0\$ and \$ D < 0 \$ then there are 4 distinct real roots. Otherwise, if \$ \Delta < 0\$, there are 2 distinct real roots.
Finally, if \$\Delta = 0\$, we define \$\Delta_0=c^2-3bd+12ae\$ and \$R= b^3+8da^2-4abc\$.
If \$D =0\$, then:
- \$ P < 0\$ implies two distinct real roots
- \$ P > 0\$ implies zero distinct real roots
- \$P = 0\$ implies four distinct real roots
Else, if \$\Delta_0 = 0\$, then there are two distinct real roots.
Else, if \$P<0\$ and \$D <0\$ there are three distinct real roots.
Else, there are one real root.
