#J, 222
247 - recursion + numerical
NB. multiple lines for visibility
f=:[:-(]$:~[:}.[-%&{.*],#&0@l)`[@.(0>l=:-&#)
r=:1={.
s=:[:=/+/@(2=&*/\])@(,.]*_1^i.@#)@({.@>@(([;];f;j;f f j=.]f f)([:}:(i._5)*])))@|.
u=:0,0([(]*_1^r@k)>:@]^:(1 1-:k=:[:*(0 p.~[)*(p.(,-)))^:_)~]
h=:{.@((n@],]{~[:r[:*p.*(p.n=:{.+-:@-~/))^:_ u)`('n'"_)@.s@|.
Methods
- Using Sturm's theorem to find number of roots.
f
is polynomial division (recursive)
s
is Sturm's theorem output: 0
for no real roots, 1
otherwise. It evaluates Sturm's polynomials ([;];f;j;f f j=.]f f)
and checks their behaviour at +/- infinity.
- Using bisection method to avoid divisions by zero, local maxima etc.
u
scans from 0 to +/- infinity to find an appropriate interval
((n@],]{~[:r[:*p.*(p.n=:{.+-:@-~/))^:_ u)
evaluates the polynomial at the edges and midpoint then halfs the interval accordingly
Verification of results
Using J's buildin polynomial root finder as realRoots
:
ti,>([;h;realRoots) each samples
┌──────────────┬────────┬─────────────────┐
│a b c d e │output │all real roots │
├──────────────┼────────┼─────────────────┤
│_1 2 3 4 5 │_1.11029│3.37192 _1.11029 │
├──────────────┼────────┼─────────────────┤
│_1 2 3 4 _5 │0.728727│3.18248 0.728727 │
├──────────────┼────────┼─────────────────┤
│1 2 3 4 5 │n │ │
├──────────────┼────────┼─────────────────┤
│1 1 2 _1 _1 │0.728262│0.728262 _0.52236│
├──────────────┼────────┼─────────────────┤
│1 2 3 4 0 │0 │_1.65063 0 │
├──────────────┼────────┼─────────────────┤
│1 2 0 0 1 │_1 │_1.83929 _1 │
├──────────────┼────────┼─────────────────┤
│_1 _1 _1 _1 _1│n │ │
└──────────────┴────────┴─────────────────┘
BTW, a simple implementation of Newton's method would be:
f=:3 :'((-(y&p.%y&p.D.1))^:_)0'@|.