I have a cubic function: $$ax^3+bx^2+cx+d$$ What would be the fastest algorithm to find the first positive root (if there is one)? Ideally the algorithm wouldn't have operations that are too expensive for a computer like square root(although that seems inevitable), cos, etc.
Any suggestion, link to resource is appreciated. Thanks in advance.
The Jenkins-Traub algorithm for polynomials with real coefficients, is a sound, well tested black box polynomial root finder, that finds the roots of smallest modulus first:
https://dl.acm.org/doi/10.1145/355637.355643
The reference implementation, 493.f, is in FORTRAN and is not easy to read, as it was written to preserve precision and accuracy while being fast.
There is one error in 493.f, on line 209, the initial value for V going into the second stage fixed shift iterations is written as
when it should be
This error matters for finding roots of very small modulus first, so it's worth correcting for your case.
If you do decide to pick through 493.f, along with the main algorithm, you'll find Horner's rule for polynomial evaluation, Newton-Rhapson iteration for quick estimate of roots for root bounds, Cauchy's bound for the roots of a polynomial, a method to compute the quadratic formula while preserving as much precision and accuracy as possible, and a plethora of numerical techniques related to preserving precision and computing machine error. Quite a lot of thought went into the implementation.
But if precision doesn't matter to you, then Jenkins-Traub may be overkill.