Timeline for Counting Distinct Real Roots of Low-Degree Polynomials
Current License: CC BY-SA 4.0
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2020 at 4:12 | comment | added | xnor | I'm wondering if a golfy approach here would be to evaluate the polynomial at a huge number of equally spaced points, and count the intervals where it crosses zero or nearly touches it. This would require a mesh size small enough to separate any two roots, and an epsilon where anything approaching that close to an axis must actually be multiple root touching it. I suspect something suitably small in the polynomial degree and coefficients will suffice, but don't now how to prove it. | |
| Feb 26, 2020 at 23:31 | comment | added | Milo Brandt | For the record, "count the number of roots in an interval" is a task that does not require being able to write down the roots; Sturm's theorem is a bit technical to explain, but it is a simple algorithm to count the number of roots of a polynomial over an interval (or over the whole real line) (and this is used in the answers) | |
| Feb 26, 2020 at 18:36 | comment | added | Grimmy | @Anush en.m.wikipedia.org/wiki/Rational_root_theorem | |
| Feb 26, 2020 at 17:27 | history | edited | Mr. Xcoder | CC BY-SA 4.0 |
edited body
|
| Feb 26, 2020 at 17:05 | comment | added | user9207 | @Neil How is trivial? | |
| Feb 26, 2020 at 16:36 | history | became hot network question | |||
| Feb 26, 2020 at 15:18 | answer | added | agtoever | timeline score: 2 | |
| Feb 26, 2020 at 15:12 | comment | added | agtoever | @ZacharyHunter: if you are specifically interested in non-built-in solutions, maybe next time consider another challange than #codegolf, which more or less encourages us to use built-ins... | |
| Feb 26, 2020 at 15:10 | comment | added | agtoever |
I suggest you add an example with mixed (real and complex) roots, such as [1, 0, 3, 1], which has 1 real root and 2 complex roots.
|
|
| Feb 26, 2020 at 14:19 | answer | added | Grimmy | timeline score: 6 | |
| Feb 26, 2020 at 13:29 | answer | added | RGS | timeline score: 0 | |
| Feb 26, 2020 at 12:25 | answer | added | Arnauld | timeline score: 9 | |
| Feb 26, 2020 at 10:52 | comment | added | Neil | @Anush On the other hand, finding rational roots of a polygon of integer coefficients is trivial for arbitrary degree. | |
| Feb 26, 2020 at 10:38 | answer | added | Kirill L. | timeline score: 0 | |
| Feb 26, 2020 at 10:15 | answer | added | Expired Data | timeline score: 3 | |
| Feb 26, 2020 at 10:09 | history | edited | Kevin Cruijssen |
edited tags
|
|
| Feb 26, 2020 at 10:01 | comment | added | Zach Hunter | @Anush, I'm also interested in programs that don't use built-in functions. To the best of my knowledge, this is only feasible with the restriction of degree, unless you use much deeper and complicated math formulas, or you repeat the premise of codegolf.stackexchange.com/questions/11694/…. | |
| Feb 26, 2020 at 9:55 | history | edited | Jonathan Allan |
edited tags
|
|
| Feb 26, 2020 at 9:50 | answer | added | alephalpha | timeline score: 2 | |
| Feb 26, 2020 at 9:45 | history | edited | Zach Hunter | CC BY-SA 4.0 |
got rid of kolomogorov complexity sentence
|
| Feb 26, 2020 at 9:43 | history | edited | Jonathan Allan |
edited tags
|
|
| Feb 26, 2020 at 9:31 | answer | added | Jonathan Allan | timeline score: 2 | |
| Feb 26, 2020 at 9:30 | comment | added | user9207 | OK but we could still ask them to find the number of roots right? They just can't do it via the radical root. | |
| Feb 26, 2020 at 9:27 | history | edited | Zach Hunter | CC BY-SA 4.0 |
said ascii, meant unicode
|
| Feb 26, 2020 at 9:25 | comment | added | Zach Hunter | @Grimmy, yeah, I'll fix that. | |
| Feb 26, 2020 at 9:23 | comment | added | Zach Hunter | @Anush The polynomial \$x^5-x+1\$ is an example of a polynomial with a root which cannot be expressed with radicals. (instead, we need hypergeometric functions) Since the roots no longer have a nice expression, we can't get an easy closed form, making considering higher degrees much less simple. | |
| Feb 26, 2020 at 9:11 | comment | added | user9207 | Is it not possible for polys of degree 5? | |
| Feb 26, 2020 at 9:00 | history | tweeted | twitter.com/StackCodeGolf/status/1232591293852856320 | ||
| Feb 26, 2020 at 8:31 | history | asked | Zach Hunter | CC BY-SA 4.0 |