Catastrophic cancellation in logsum

I'm trying to implement the following function in double-precision floating point with low relative error:

$$\mathrm{logsum}(x,y) = \log(\exp(x) + \exp(y))$$

This is used extensively in statistical applications to add probabilities or probability densities that are represented in log space. Of course, either $\exp(x)$ or $\exp(y)$ could easily overflow or underflow, which would be bad because log space is used to avoid underflow in the first place. This is the typical solution:

$$\mathrm{logsum}(x,y) = x + \mathrm{log1p}(\exp(y - x))$$

Cancellation from $y-x$ does happen, but is mitigated by $\exp$. Worse by far is when $x$ and $\mathrm{log1p}(\exp(y - x))$ are close. Here's a relative error plot:

The plot is cut off at $10^{-14}$ to emphasize the shape of the curve $\mathrm{logsum}(x,y) = 0$, about which the cancellation occurs. I've seen error up to $10^{-11}$ and suspect that it gets much worse. (FWIW, the "ground truth" function is implemented using MPFR's arbitrary-precision floats with 128-bit precision.)

I've tried other reformulations, all with the same result. With $\log$ as the outer expression, the same error occurs by taking a log of something near 1. With $\mathrm{log1p}$ as the outer expression, cancellation happens in the inner expression.

Now, the absolute error is very small, so $\exp(\mathrm{logsum}(x,y))$ has very small relative error (within an epsilon). One might argue that, because a user of $\mathrm{logsum}$ is really interested in probabilities (not log probabilities), this terrible relative error isn't a problem. It's likely that it usually isn't, but I'm writing a library function, and I'd like its clients to be able to count on relative error not much worse than rounding error.

It seems I need a new approach. What might it be?

-
I don't understand your last paragraph. "within an epsilon" doesn't mean anything to me. Do you mean a Unit in the Last Place? As for users being interested in probabilities, a small log probability error will result in a large probability error, so this is not the case. –  Aron Ahmadia Oct 22 '12 at 18:37
Out of curiosity, have you tried taking the "best of" of your two methods and plotting the error of that? Then all you need is the right logic to detect which case you're in (hopefully being less costly or part of the required cost of the algorithm anyway), then switching to the appropriate method. –  Aron Ahmadia Oct 22 '12 at 18:43
@AronAhmadia: "Within an epsilon" means relative error less than a double-precision floating-point epsilon, which is about 2.22e-16. For normal (i.e. not subnormal) floats, it corresponds to about an ulp. Also, if $a$ is the absolute error of $x$, then the relative error of $\exp(x)$ is $\exp(a)-1$, which is nearly the identity function near zero. IOW, small absolute error for $x$ implies small relative error for $\exp(x)$. –  Neil Toronto Oct 22 '12 at 19:47
Addendum: When absolute error $a$ is near zero. When $a > 1$, for example, you're right: the relative explodes. –  Neil Toronto Oct 22 '12 at 20:02

The formula $$logsum(x,y)=\max(x,y)+log1p(\exp(-abs(x-y))$$ should be numerically stable. It generalizes to a numerically stable computation of $$\log \sum_i e^{x_i} = \xi+ \log\sum_i e^{x_i-\xi},~~~\xi=\max_i x_i$$
In case the logsum is very close to zero and you want high relative accuracy, you can probably use $$logsum(x,y)=\max(x,y)+lexp(x-y)$$ using an accurate (i.e., more than double precision) implementation of $$lexp(z):=log(1+e^{-|z|})$$ which is nearly linear for small $z$.
@NeilToronto: Please give an example with two explicit inputs $x$ and $y$, so that I can play with it. –  Arnold Neumaier Oct 22 '12 at 18:46