I have a type CReal = (precision: Int) -> (approximation: BigInt). I have a Polynomial[CReal] as well. I want to get the roots out of this polynomial as a List[Complex[CReal]].
With $z_i$ as the ith guess, $n$ as the degree of the polynomial, and $f$ as the polynomial, using this guessing method (or a similar guessing method like Muller or NR):
$$ z_{i+1} = z_i - \frac{nf(z_i)}{f'(z_i) \pm \sqrt{(n - 1)((n - 1)f'(z_i)^2-nf(z_I)f''(z_i))}} $$
has two problems:
- The smaller problem: A single iteration takes a long time. A lot of time is spent inside of the square root, and even more time is spent on comparing the two results of the plus-minus to determine which denominator to use.
- The bigger problem: The output doesn't exactly represent the semantics of
CReal. The output is still just a guess, irrespective of theprecisionit is given. It should be able to represent the root exactly to a precision.
My searching unveiled ARCAVOID: it sounds like it is designed to be used on CReal (or something easily constructable from CReal). However, I've been unable to locate a reference implementation, and I'm not even sure if ARCAVOID is the best option.
What's a performant way to compute the complex roots of a polynomial to a known precision?