25
$\begingroup$

To frame the question, in computer science often we want to calculate the product of several probabilities:

P(A,B,C) = P(A) * P(B) * P(C)

The simplest approach is simply to multiply these numbers, and that is what I was going to do. However, my boss said it's better to add the log of the probabilities:

log(P(A,B,C)) = log(P(A)) + log(P(B)) + log(P(C))

This gives the log probability, but we can get the probability afterwards if necessary:

P(A,B,C) = e^log(P(A,B,C))

Log addition is considered better for two reasons:

  1. It prevents "underflow" whereby the product of probabilities is so small that it gets rounded to zero. This can often be a risk since probabilities are often very small.
  2. It is faster because many computer architectures can perform addition more quickly than multiplication.

My question is about the second point. This is how I have seen it described, but it doesn't take into account the added cost of getting the log! We should be comparing "cost of log + cost of addition" to "cost of multiplication". Is it still smaller after taking that into account?

Also, the Wikipedia page (Log probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?

Finally, the justification that "computers perform addition faster than multiplication" is kind of vague. Is that specific to the x86 instruction set, or is it some more fundamental trait of processor architectures?

Improve this question
$\endgroup$
3
  • 20
    $\begingroup$ The first benefit (avoiding underflow) is often much more important than the performance gain, so even if it wasn't faster we'd still use log probabilities. $\endgroup$
    – D.W. ♦
    Commented Jun 23, 2017 at 18:32
  • $\begingroup$ To expand on what @D.W. said, there's a similar "log-sum-exp trick" used specifically to address underflow, without any regards to performance whatsoever. In fact, this was the first time I'd seen someone regard taking logarithms as a performance-improvement technique! $\endgroup$
    – user541686
    Commented Jun 24, 2017 at 8:27
  • $\begingroup$ Just to expand on the advantages of log probabilities even though those are only indirectly related to your question: when using gradient descent, the derivative of sum of logs is much cheaper than the derivative of a product (which corresponds on an exponential number of terms). Also, when optimizing probabilities, you need to stay within [0,1] and unconstrained optimization algorithms like gradient descent cannot guarantee that, but if you are optimizing the logs than any value from -inf to +inf is a valid log probability. $\endgroup$
    – user118967
    Commented Aug 7, 2020 at 18:37

2 Answers 2

Reset to default
17
$\begingroup$

Also, the Wikipedia page (https://en.wikipedia.org/wiki/Log_probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?

If you just want to compute $P(A_1)\ldots P(A_n)$ once, then you are right. You will have to compute $n$ logarithms and $n-1$ additions, whereas the naive method requires $n-1$ multiplications.

However, it is very common that you want to answer queries of the form:

Compute $\prod_{i \in I} P(A_i)$ for some subset $I$ of $\{1, \ldots n\}$.

In that case, you can preprocess your data to compute all $\log P(A_i)$ only once, and answer each query by doing $|I|$ additions.

Finally, the justification that "computers perform addition faster than multiplication" is kind of vague. Is that specific to the x86 instruction set, or is it some more fundamental trait of processor architectures?

This is a broader question. In general it is (probably?) harder to compute multiplication than addition. Computing $a+b$ is linear in the size of $a$ and $b$ (using the trivial algorithm), whereas we currently don't know how to compute $a\times b$ with the same time complexity (check the best algorithms here).

Of course there is no definitive answer: for instance if you deal with integers only and you multiply by powers of $2$, then you should rather compare shift with add operations.

Nevertheless this is a reasonable statement on all common computer architectures: multiplication on floating-point numbers will be slower than addition.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Don't you also need to account for the time complexity needed to compute the logarithms for all the probabilities $P(A_i)$? $\endgroup$
    – David C
    Commented Jun 24, 2017 at 0:48
  • $\begingroup$ What about the final exp()? Isn't that slow? $\endgroup$
    – user541686
    Commented Jun 24, 2017 at 1:22
  • $\begingroup$ @DavidC: I didn't try to compute the overall time complexity. I just replied to the question "is multiplication faster than addition". But in general computing logarithm of floating-point numbers on a software scale may take $\Theta(M(n)\log n)$ where $M(n)$ is the complexity of a multiplication algorithm. So it would give a $\Theta(nM(n)\log n+n\sum_{q\in Q}|I_q|)$ complexity (where $Q$ is the set of queries). $\endgroup$
    – md5
    Commented Jun 24, 2017 at 8:12
  • 2
    $\begingroup$ @Mehrdad: It is as difficult as computing a logarithm. However I'm not sure you'll ever need to do that. For instance if you only compare probabilities you'd rather not compute the final $\exp$. The multiplication of $n$ numbers in $(0,1)$ may quickly become very small, so for the same reason we try to avoid underflow by using log probabilities, we should stay in the logarithmic form at the end (e.g. by computing $\log$ in base $10$, so that it's even more "human-readable"). $\endgroup$
    – md5
    Commented Jun 24, 2017 at 8:17
  • 1
    $\begingroup$ Is addition still faster than multiplication if you use IEEE floats - which you certainly will in this case? Modern cpus are pretty good at multiplying numbers whereas float addition has a couple steps that can't be executed simultaneously - align mantissas (shift left based on the result of subtraction), then actually add them, then normalize (which may trigger both underflow and overflow, yay). In circuit it's quite a lot of die, in microcode each step costs a cycle or few. $\endgroup$
    – John Dvorak
    Commented Jun 24, 2017 at 11:57
4
$\begingroup$

By "incurred once" it probably means that if you have $N$ probabilities $p_1,...p_N$ then you switch to log space only once by taking logs of each $p_i$, perform probability multiplications in the log space by adding them (which is less time consuming), and then switch back to your initial space using exponentiation.

If the number of operation is only slightly greater than $N$ then I think there is no meaning of switching to the log space (from the performance point of view). However, if the number of operations is too many , then I think it is worth switching to the log space. For example, say you have 50 variables, and your computation involves 1000 multiplications. Then I think you should work in log space.

Finally, addition is faster than multiplication not because of machine architecture. Addition is inherently faster than multiplication. In terms of complexity, it takes $O(n)$ (linear) time to perform addition of two $n$-bit integers, while multiplication takes $O(n^2)$ (quadratic) time.

By the way, this idea is similar to the Montgomery modular multiplication, where multiplications are performed in the Montgomery form which is quite faster than usual multiplication and then reduction.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ -1 Multiplication does not take quadratic time... $\endgroup$
    – user541686
    Commented Jun 24, 2017 at 1:23
  • 1
    $\begingroup$ @Mehrdad, i hope you learnt school multiplication of two numbers. That algoritnm is still widely used on computer chips please look here What you mean is software level algorithms which are still worse than linear time. Are these multiplication algorithms widely used as on multiplication circuit? $\endgroup$
    – fade2black
    Commented Jun 24, 2017 at 2:58
  • $\begingroup$ en.wikipedia.org/wiki/Carry-save_adder#The_basic_concept $\endgroup$
    – user541686
    Commented Jun 24, 2017 at 2:59
  • 1
    $\begingroup$ The spirit of the answer is still correct though, right? If none of the multiplication algorithms are going to match the linear time of addition? $\endgroup$
    – Stephen
    Commented Jun 24, 2017 at 14:57
  • 1
    $\begingroup$ @Stephen, in fact the question was not about what the exact best complexity of multiplication algorithm is. I could provide additional information on this subject if commenters required. I think that a long discussion on that would be off-topic here. ))) $\endgroup$
    – fade2black
    Commented Jun 24, 2017 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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