Kata

Being honest, I have no clue how that code works because i am unfimilar with all those libraries, SORRY!

Let me know if it works now

I will look into it, can you please send me an example from the test cases with your and my solutions

I added an extra restriction in the description, please tell me if this helps

Consider the fixed test case 539x^28-342x^27-324x^26+852x^25-457x^24+575x^23-35x^22+992x^21+156x^20-794x^19+577x^18-417x^17+308x^16+541x^15+316x^14+761x^13+710x^12-241x^11-469x^10+134x^9-830x^8-547x^7-810x^6+341x^5-446x^4-132x^3+110x^2+762x+524 with starting point x=63. I find a solution -0.60756 in 152 iterations. Your algorithm finds no solution. I iterate for a maximum of 512 iterations, and stop when |x_{n+1} - x{n}| < 1e-6 and |f(x_{n+1})| < 1e-6.

Conversely, for 205x^26-611x^25+349x^24-28x^23-464x^22-755x^21+792x^20+168x^19-680x^18-593x^17+13x^16-62x^15-1000x^14+87x^13-240x^12-409x^11-284x^10-439x^9+83x^8+457x^7-936x^6+544x^5-541x^4-83x^3+479x^2-997x+205 with starting point x=14 I find no solution. Your algorithm finds solution x=2.5251. By changing to the convergence condition suggested in your new description, i.e., |x_{n+1} - x{n}| < 1e-6 and |f(x_{n+1})| < 1e-2, I get the same solution.

In fact, after using your new condition, my implementation finds strictly more solutions than yours. The remaining problem is why it does this. I tried lowering the number of iterations and this helps a bit, but sometimes it then misses solutions found by your algorithm. For example, your solution to 632x^48-598x^47+498x^46+51x^45-674x^44-518x^43-686x^42+694x^41+525x^40+992x^39-27x^38-371x^37-429x^36+64x^35-662x^34+475x^33+203x^32+350x^31-807x^30-910x^29-65x^28-973x^27-781x^26-168x^25-808x^24+899x^23+36x^22-667x^21+533x^20-814x^19+999x^18+167x^17-84x^16+866x^15-507x^14-398x^13-214x^12+413x^11-237x^10-33x^9+68x^8-352x^7-269x^6+131x^5-577x^4+879x^3-83x^2-783x+537 starting from x=82 is found only after 208 iterations, so I cannot reduce the number of iterations too drastically either.

In sum, I suggest modifying the description to specify the terminal conditions very clearly. How close does the final f(x) have to be to zero? How close do f(x_{n+1}) and f(x_{n}) have to converge? What's the maximum n considered, i.e., how long should we iterate?

I added more specificity to the convergence conditions in the description, I think your original solution should work now :)

OK, now I got much more successes in the tests, and with a few dozen clicks of "Attempt" it worked out.

Looking at your solution, I now see what you're exactly looking for. Your terminal conditions could be described as "On each iteration, round x_{n+1} to 13 digits, and stop if x_{n+1} == x_{n}, or after 512 iterations. The final solution candidate is accepted if the absolute value of f is <= 0.01."

These rules are fine by me as long as it's described in the description. However, especially the rounding to 13 digits is very non-standard for numerical mathematics, although I can see how it enables using x_{n+1} == x_{n} as the terminal condition. A more standard solution would be to not round the x_{n+1}s, but simply compare the absolute value of the difference, i.e., |x_{n+1} - x_{n}|, to some threshold. This could be described as "Stop the iteration when |x_{n+1} == x_{n}| <= 1e-6, or after 512 iterations. The final solution candidate is accepted if the absolute value of f is <= 0.01."

(Less importantly, if a solution is not found in 512 iterations, your terminal conditions still return a solution as long as f is <= 0.01, even though the x_{n+1}s have not shown convergence. An alternative is to return None whenever the maximum 512 iterations are exceeded. But I think this is just a matter of taste, and I'm fine with your choice.)

I have similar tests that return None instead of "nothing"

I wasn't aware that numpy had functions that could mae it so easy

Battery included ...

Disabling things in Python is generally a bad idea, because its really hard to do properly. But on the otherhand, the difficulty difference between languages will be huge if this kata gets translated, if numpy is allowed to remain.

sos i'll change that

Not trivial to build the random test cases for this kata.
I suggest you to randomly choose a random number of (complex and/or real) roots and build the polynomial from that.

[-1.83796, -1.12368, 0.3901, 1.05329] should equal [0.3901, 1.05329, -1.83796, -1.12368]

From what I could see, it expects the sorted positives then the sorted negatives.
But it needs to be defined.

EDIT:
[-1.62737, -1.12454, -0.7806] should equal [-0.7806, -1.12454, -1.62737] Nevermind, I don't know how it's sorted. :/

It's sorted in the order his solution found them in ;)

I don't even know how you would find them, I just used the pythonic solution of finding a module doing it for me. x)