1

Compute $\log(A_1 B_1 + \cdots+ A_n B_n)$, given $\log(A_1),\dots,\log(A_n)$. The catch is one can't simply do $\log(\exp(\log(A_1))B_1 + \cdots+ \exp(\log(A_n))B_n)$. Why? Because $A_1$, ... $A_n$ are very small. Small enough that $\exp(\log(A_i))$ gets rounded to zero in most computers (and thus results in $R=\log(0)=-\infty$).

Is there any way to compute $\log(A_1 B_1 + \cdots + A_n B_n)$ given those constraints? Numerical approximations are fine, but would need to be fast (and stable) enough.

EDIT: The $B_k$ are given and not as small as the $A_k$. Consider the following (very rough) orders of magnitude: $log A_k \approx -100$ and $log B_k \approx -15$.

jjagmath
  • 18,214
Polygons
  • 33
  • 2
    What are $B_k$? Are they given? How do they compare in magnitude to $A_k$? – Alan Abraham Aug 12 '21 at 20:43
  • If $log(A)$ very small why not use $ log(x)=x-1$ or if not accurate enough take the next Taylor – trula Aug 12 '21 at 20:48
  • If the $A_i$ are very small, then their logs are large numerically, so the sum would be large numerically. – marty cohen Aug 12 '21 at 20:52
  • $x=e^{-100}$ makes $x-1$ very bad, @trula Even with two terms. Very small means $\log(1+y)$ where $y$ is close to the radius of convergence for the power series. – Thomas Andrews Aug 12 '21 at 20:53
  • By the way, the usual IEEE double (64-bit floating point) format handles $e^{-100}$ to full precision without breaking a sweat. – Troposphere Aug 12 '21 at 20:55
  • @Troposphere Unfortunately, I am limited to 32 bit floats – Polygons Aug 12 '21 at 20:56
  • Okay, then $e^{-100}$ would indeed underflow. – Troposphere Aug 12 '21 at 20:58
  • From the page on how to ask a good question: Your question should be clear without the title. After the title has drawn someone's attention to the question by giving a good description, its purpose is done. The title is not the first sentence of your question, so make sure that the question body does not rely on specific information in the title. – jjagmath Aug 12 '21 at 21:01

1 Answers1

5

You could compute $$ \log(A_1B_1+\cdots+A_nB_n) = \log\bigl (e^{\log(A_1)+C}B_1 +\cdots + e^{\log(A_n)+C}B_n\bigr) - C $$ where $C$ is some appropriate constant offset to avoid the underflow.

If the $B_k$s are all roughly of the same magnitude, you could take $C=-\max(\log A_1,\ldots,\log A_n)$.

Troposphere
  • 7,158
  • If the $B_k$ are not roughly the same order of magnitude, what should C be? – Polygons Aug 12 '21 at 21:06
  • @Polygons: You only need very rough sameness. The risk is that a single very small $B_n$ could cancel out the largest $A_n$ such that all the terms of the sum still underflow even after you normalize that $A_n$ to be $1$. A more careful choice would be $$ C = - \max(\log A_1 + \log B_1,\ldots,\log A_n + \log B_n)$$ at the cost of needing to compute the log of each $B_k$. For example, if the $B_k$s are known to be within a factor of, say, $2^{16}$ of each other, I wouldn't bother. – Troposphere Aug 12 '21 at 21:11
  • 1
    I see, thank you! May I ask how does one come up with such trick? Is this a common approach to this type of problem? – Polygons Aug 12 '21 at 21:27
  • @Polygons: Hmm, I'm afraid my powers of introspection fail to come up with anything except "it seemed like the obvious thing to do". If the magnitudes of the $A_kB_k$ products happen to differ wildly, only the largest of them will matter for the sum, so we want to select the scaling constant such that the exponent of the largest $A_kB_k$ ends up somewhere in the comfortable middle of the representable range. – Troposphere Aug 12 '21 at 22:04