-1
The challenge is to write the shortest program/function which counts the number of distinct real roots of a given polynomial.
Expected input: a list of integers, L, which are the coefficeints of your polynomial. p(L). (e.g. L[i] is the coefficient of x^i)
Required output: the number distinct real roots, of the polynomial, p(L). You should count multiplicities only once.
Standard code golf rules apply.
Additionally, there will be a -100 byte bonus for answers which do not use built-ins that do all the work for you. (i.e. if your program lives up to the first constraint of this similar question)
Examples
input: [1], polynomial: 1, output: 0
input: [1,2], polynomial: 1+2x, output: 1
input: [1,0,1], polynomial: 1+x^2, output: 0
input: [2,3,1], polynomial: 2+3x+x^2 = (x+2)(x+1), output: 2
input: [1,-2,1], polynomial: 1-2x+x^2 = (x-1)^2, output: 1
Zachary Hunter
Posted 2020-02-21T20:13:22.923
Reputation: 437
No, that requires a significantly more precise output than what I'm asking for. – Zachary Hunter – 2020-02-21T20:22:28.270
1Are we not counting complex roots? – xnor – 2020-02-21T20:36:04.317
I meant to specify real roots, fixed. – Zachary Hunter – 2020-02-21T20:37:18.757
2I'm not an expert, but I believe in general it is not possible to know the number of roots a polynomial has without finding all of them. If you restrict the inputs to polynomials of degree less than 5, you might have an interesting and sufficiently different question. – FryAmTheEggman – 2020-02-21T21:16:38.797
yes, after thinking about it I came to the same thoughts. thanks for the input, maybe I’ll post the new variant in a bit – Zachary Hunter – 2020-02-21T21:20:54.803
1@FryAmTheEggman That is not true. For quintics and above, it isn't (usually) possible to express the roots as closed form solutions, but that doesn't mean counting the roots is not possible. There are a lot of theorems involving number of roots (by looking at polynomial automorphism groups, or by looking at derivatives) that make counting possible for pretty general polynomials without finding them. That being said, this challenge is definitely too hard for this site. – Don Thousand – 2020-02-22T03:15:53.727