4
$\begingroup$

Every once in a while, I come across the term numerical stability, which I don't really understand. In particular, I have seen a description of the practice of "adding logs rather than multiplying numbers" as "numerically stable." I would like to know why this is considered numerically stable.

By "adding logs rather than multiplying numbers" I mean that if you have several numbers, for example 0.01, 0.001, 0.0001, and you want to get their product, you can instead add the logs of each term. In this case assuming log base 10, the result would be -2 -3 -4 = -9. This doesn't give you the same output as multiplying, but it's a good way to get something like the product so that you don't experience numerical underflow.

My question is that I'm a bit confused because the definitions of numerical stability I've found on the Internet don't seem to apply to this case. The definitions of "numerical stability" I've found are that it occurs when a "malformed input" doesn't affect the performance of an algorithm, see for example here. In this case I don't really see how we would consider the numbers 0.01 etc "malformed," they are what they are. It would be more accurate to say that the algorithm (of multiplying them) is bad in this context since the computer can't handle it, so we choose a better algorithm. So why do people say this is "numerically stable"?

$\endgroup$
  • 1
    $\begingroup$ Investigate how non-integers are represented in most computers (IEEE floats), the limitations of that format, and relevant error-estimating techniques. $\endgroup$ – Raphael May 6 '18 at 7:14
  • 1
    $\begingroup$ I suspect you meant "the definition" (not "definitions"). I've never seen a definition that uses "malformed" or anything like it. That MathWorld "definition" is nonsensical precisely because "malformed" is a bizarre word to use. Presumably, "malformed" was just meant to mean "is (slightly) inaccurate", but even this isn't correct. Numerical stability is relevant even if the input is exactly represented. $\endgroup$ – Derek Elkins May 7 '18 at 14:29
6
$\begingroup$

A "numerically stable" method calculates a result in a way that will not produce excessive rounding errors.

Given a small number x, let's say x = 0.00079, it is possible to calculate log (1 + x) with much higher precision than 1 + x. (Of course calculating log (1 + x) avoids adding 1 + x). In both cases the relative error will be small and about equal size, but since the logarithm is very small, it's absolute error is much smaller.

So if you want to calculate the product of values $1 + x_i$ for many small i, then you use a clever method to calculate $log (1 + x_i)$, add those values, and calculate the exponential. With probabilities, it is possible that you have say 1,000,000 events each with small probability $p_i$, and the probability that none of the events happens is the product of $1 - p_i$, and calculating that probability is more precisely done by adding logarithms (you would also keep the rounding errors down by always adding the two smallest values).

In other situations, using logarithms can be less precise. For multiplication, the relative error is independent of the size of the numbers. But if you add logarithms, and say their sum is around 100, then each addition loses precision because 7 bits of the mantissa are used to store the 100. The precision of your result will be much less. So it's quite the opposite of numerically stable.

Start with x = 1, y = 0. Then for i = 1 to 100, multiply x by i, and add log i to y. Then for i = 1 to 100, divide x by i, and subtract log i from y. Except for rounding errors, you should end up with x = 1 and y = 0. Check how much the difference is.

PS. How do we calculate log (1 + x) without calculating 1 + x? There is the power series around 1, $ln (x) = (x-1) / 1 - (x-1)^2 / 2 + (x-1)^3 / 3 ...$. If we substitute 1 + x, then $ln(1 + x) = x / 1 - x^2 / 2 + x^3 / 3 ...$, which is obviously calculated without ever calculating 1 + x.

That's an important lesson: Given a problem that suggests an obvious sequence of steps to solve it, you will very often find a better and less obvious solution. To calculate log (1+x), the obvious sequence of steps is to calculate y = 1+x, z = log (y), but there is a much better solution that completely avoids the first step.

$\endgroup$
  • $\begingroup$ In your last paragraph I think you mean "divide x by i" right? $\endgroup$ – Stephen May 6 '18 at 16:57
  • $\begingroup$ I like your definition of "numerically stable" in your first paragraph, and I think I see overall what you're getting at. $\endgroup$ – Stephen May 6 '18 at 17:04
  • $\begingroup$ But your second paragraph doesn't make much sense to me: "it is possible to calculate log (1 + x) with much higher precision than 1 + x" but we can calculate 1 + x perfectly, it is just 1.00079, whereas log(1.00079) can only be imperfectly represented since its mantissa never ends. "Of course calculating log (1 + x) avoids adding 1 + x" but of course we have to calculate 1 + x before we can take the log of that. $\endgroup$ – Stephen May 6 '18 at 17:04
  • $\begingroup$ "In both cases the relative error will be small and about equal size, but since the logarithm is very small, it's absolute error is much smaller." again I don't see any error in just 1.00079, it's an exact number. Only the logarithm has an error. But I'm not very familiar with the discussion of numerical errors, so I'm probably missing something fundamental. $\endgroup$ – Stephen May 6 '18 at 17:06
  • $\begingroup$ @Stephen: 0.00079 is a bit above 1/2048. Adding 1, the exponent increases by 11, eleven mantissa bits will be lost, so if you had a typical 53 bit mantissa, only 42 bits of the 0.00079 are left in the result 1 + x. The error has just increased by a factor 2048. Using binary floating point, 1.00079 is absolutely not an exact number. $\endgroup$ – gnasher729 May 6 '18 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.