There are now two articles on the web which present extensive surveys of
approximations of the perimeter of an ellipse. One article is Gerard
Michon's at <http://www.numericana.com/answer/ellipse.htm>; the other,
which appeared quite recently, is Stanislav Sykora's at
<http://www.ebyte.it/library/docs/math05a/EllipsePerimeterApprox05.html>.
Near the end of the latter, Sykora says "Those who wish to pursue this
topic further should look for an efficient formula using only the four
algebraic operations (if possible, avoiding even square-root) with a
maximum error below 10 ppm. If would be also nice if such a formula were
exact for both the circle (y=1) and the degenerate flat ellipse (y=0)."
Here I provide two approximations which meet those criteria.

With a and b denoting the lengths of the semiaxes of the ellipse, both
approximations have the form [for viewing in a fixed-width font]

                             2             (  a b  ) 2
                    p (a + b)  + q a b + r ( ----- )
             a b                           ( a + b )
4(a + b) -  ----- * ----------------------------------
            a + b            2             (  a b  ) 2
                      (a + b)  + s a b + t ( ----- )
                                           ( a + b )

or [written linearly]

4(a+b) - ab/(a+b) * (p(a+b)^2 + qab + r(ab/(a+b))^2)/((a+b)^2 + sab + t(ab/(a+b))^2)

where p, q, r, s and t are parameters to be determined.

Of course, there are many other ways this form could be expressed, some of
which might be preferable for aesthetic or computational reasons. [For
example, the form can easily be put in terms of the three Pythagorean
means: Replace each occurrence of ab/(a+b) by H/2, where H is the harmonic
mean of a and b. Then similarly, replace each occurrence of (a+b) and ab by
2A and G^2, where A and G are the arithmetic and geometric means, resp.]

If eccentricity is 1 (so that the ellipse is degenerate, a=0 or b=0), the
form gives the perimeter precisely. At the other extreme, when eccentricity
is 0 (so that the ellipse is a circle, a=b), if we require that the form
also give the perimeter precisely, it is simple to solve for one parameter
in terms of the others. For example, solving for r gives

r = 4 [ (4 - pi)(4s + t + 16) - (4p + q) ]

which we shall use henceforth. Our approximations will therefore be
extreme-perfect (i.e., give the perimeter precisely at both extremes of
eccentricity). Values of the other parameters (p, q, s and t) then remain
to be determined according to other criteria.

Historically, in approximating the ellipse perimeter, attention has most
often been given to making the approximation as accurate as possible for
near-circular ellipses. Here, however, we wish |relative error| to be small
over _all_ eccentricities. As such, an obvious way to determine values of
the four other parameters is to minimize worst |rel. error|. Doing this
numerically, we find

p = 3.982901, q = 66.71674, s = 18.31287 and t = 23.39728

(and accordingly r = 56.2007)

and that our form of approximation then has |rel. error| < 5.2 * 10^-6.
This approximation meets all of Sykora's criteria. [However, despite the
presence of a square root, I still prefer my second approximation
in "Two New Approximations, in a Certain Form, for the Perimeter of an
Ellipse" (sci.math, 2004 May 23)
at <http://groups.google.com/group/sci.math/msg/618a2c0f319dd8e4>
since it is neater and slightly more accurate.]

Looking at the value of p given above, one might ask "Should that not be
exactly 4 perhaps?" Answer: No, not if we really wish to minimize
worst |rel. error| for an extreme-perfect approximation in the form being
considered. However, if we do choose p = 4 exactly, the approximation then
becomes more accurate for near-degenerate ellipses and, with the values of
the three remaining parameters adjusted appropriately, worst |rel. error|
is still less than 10^-5. Specifically, with

p = 4, q = 129.79130, s = 34.53115 and t = 63.29008

(and accordingly r = 163.3562),

our form of approximation then has |rel. error| < 9.4 * 10^-6. Readers may
be surprised that such a small change in the value of p induced such large
changes in the other parameter values, but I think this merely shows that
this form of approximation is quite sensitive to the values of the
parameters. This matter is related to the following

Disclaimer: My numerically approximated parameter values may differ
  somewhat from the optimal ones! (In other words, their last few digits
  may well be spurious.)

Nonetheless, for the two sets of parameter values given, the error bounds
stated above are correct. And "refinement" of the parameter values should
not yield any significant reduction in the error bounds.