I was reading an article called Computing the Cube Root, in which they approximate a cube root using one quartic polynomial divided by another, in the form
$$y=\frac{ax^4+bx^3+cx^2+dx+e}{fx^4+gx^3+hx^2+ix+j}$$
Is there a reason for representing their approximation in such a form? Is it possible to get a similar level of accuracy using a polynomial in general form?
Also, how would you go about deriving the smallest maximum error of such a formula? (Sorry, I probably seem like a complete idiot.)
The reason is that rational approximation normally is much more efficient than polynomial approximation. Here are some examples for your problem: The task is to approximate $f: x \rightarrow x^{\frac{1}{3}}$ on the interval $[\frac{1}{8},1]$. I don't know the source for the given rational function above, but here are the result from Maple V's minimax function (using the default weight function 1), writing $P_n(x), Q_m(x)$ for the numerator and denominator polynomials:
P_4(x)/Q_4(x): max. error 0.2067773134985e-7
P_4(x)/Q_3(x): max. error 0.1687562176023e-6
P_5(x)/Q_3(x): max. error 0.2773562640305e-7
P_4(x)/Q_0(x): max. error 0.4725267889820e-3
To get a comparable accurate polynomial approximation you have to use a polynomial of degree 16 or 17:
P_17(x)/Q_0(x): max. error 0.1567070356649e-7
P_16(x)/Q_0(x): max. error 0.3537910592697e-7
Actually, rational approximations are usually much less efficient than polynomial approximations, since in modern computer arithmetic division is many times slower than multiplication and addition, so the single division needed for a rational approximation takes about as long as 5 to 10 extra terms for a polynomial approximation. Divisions are inherently slower, and tend to stall pipelines.
However, rational approximations do tend to take fewer terms. I haven't studied the reasons in detail, but heuristically this is because the error for a polynomial approximation blows up in a hard to control way depending on he number of terms, perhaps quadratically or worse. In rational approximations, the error only blows up depending on the number of terms in the polynomials in the numerator and denominator separately. This is the infinite-precision error. Rounding errors are usually dominated by the one for the final operation, and thus don't blow up.
The example of $x^{\frac{1}{3}}$ on the interval $[\frac{1}{8},1]$ is close to a worst case for a reasonable polynomial approximation. Often, the rational approximation only takes 1 fewer term for a given accuracy, but here it takes about twice as many terms. The interval is just too wide for a polynomial approximation to work well. The width of an interval that is too wide to work well is very dependent on the function. For example, $[0,\frac{\pi}{4}]$ is barely manageable for $sin(x)$ but is too wide for $tan(x)$; $[0,-1]$] is barely manageable for $cosh(x)$ but $[0,\frac{1}{4}]$ is barely manageable for $tanh(x)$. Algebraic functions tend to be harder to approximate than transcendental ones.
I go to great lengths to rewrite algorithms to avoid using rational approximations. The basic technique is to use only short intervals over which polynomial approximations work well. For $x^\frac{1}{3}$ on $[0,1]$, I use 64 subintervals of length $\frac{1}{64}$. The function is barely simple enough to allow efficient accurate interpolation after reduction to the primary interval $[0,\frac{1}{64}]$ (in general, this method would need 64 different polynomials or lose more efficiency or accuracy than it gains because the interpolation would be unmanageable). A degree 3 polynomial suffices for float precision on the primary interval. Float precision is relatively easy. I use it to warm up for higher precisions.
