6 ms·

> The underlying problem is that multiplication is much harder to perform with hardware than addition, especially with 1980s-era technology. The solution is tha

> The underlying problem is that multiplication is much harder to perform with hardware than addition, especially with 1980s-era technology. The solution is that the chip uses base-2 logarithms in many places because adding logarithms is equivalent to multiplying the values. Maybe it would have been obvious to me if I had taken calculus, but this blew my mind.

secondcoming 5y ago
Logarithms are taught before calculus where I grew up.
aaaaaaaaaaab 5y ago
Calculus? Really? Logarithms are basic highschool math in my country…
- presspot 5y ago
  We don't learn mahr here
- NullPrefix 5y ago
  Such a shame that grammar wasn't a basic thing back there.
  - jacquesm 5y ago
    Or tact.
- mwfunk 5y ago
  Fun fact: in the UK they call it marhs!
- dang 5y ago
  Please don't put other users down, regardless of how math is taught in your country. We want curious conversation in which people treat each other well, even if they know less than you do. We do not want point-scoring and putdowns. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html Edit: you've unfortunately been posting unsubstantive comments and breaking the site guidelines with this account elsewhere, too. Can you please stop that so we don't have to ban you again?
jacquesm 5y ago
Look at how multiplication is done with a sliderule. https://www.sliderules.org/react/aristo_0901_junior.html https://www.sliderules.org/react/aristo_0901_junior.html
shoo 5y ago
A similar trick is used for a different reason in statistical and probabilistic calculations -- for numerical stability rather than performance. Suppose you have n probabilities p_1, ..., p_n. Each p_i is a real number in the interval [0, 1] . Often you want to multiply probabilities to compute prod_i p_i . Probabilities p_i can be tiny floating point values (very close to zero) and if n, the number of factors, is large, then the product will evaluate to zero due to underflow. Software that processes probabilities often instead stores log-probabilities. Then the product prod_i p_i can be evaluated as sum_i log(p_i) , which is more numerically stable. Where this gets a bit trickier is if you instead want to compute the sum of probabilities, rather than their product -- e.g. to renormalise probabilities so they all sum to 1. If you have encoded the probabilities as log-probabilities, you now need to take the log-exp-sum [1][2], which will cause numeric overflow if done naively, and is also relatively expensive to compute, as it requires n exponentials and 1 log to combine n log-probs. log-exp-sum can be evaluated in a stable way by first doing a pass over the data to compute the max log-prob, then doing a second pass to take the exponential of each log-prob offsetted by the max log-prob, so each of the terms being exponentiated is at most 0. There's also a streaming version of log-exp-sum that permits a single pass over the data [3] -- a max is calculated on the fly and each time a new max is identified, the running sum is multiplied by a correction factor. I'm a bit suspicious that the branches in the streaming log-exp-sum might cause a performance impact when executing, although each exp calculation is so expensive that perhaps it doesn't make that much of a difference. [1] https://en.wikipedia.org/wiki/LogSumExp https://en.wikipedia.org/wiki/LogSumExp [2] https://blog.smola.org/post/987977550/log-probabilities-semirings-and-floating-point https://blog.smola.org/post/987977550/log-probabilities-semi... [3] http://www.nowozin.net/sebastian/blog/streaming-log-sum-exp-computation.html http://www.nowozin.net/sebastian/blog/streaming-log-sum-exp-...
- nwallin 5y ago
  > I'm a bit suspicious that the branches in the streaming log-exp-sum might cause a performance impact when executing, Since you're just checking whether the current sample is larger than the largest sample seen so far, you're very likely to find a "large" sample early that rarely gets updated. From then on, this branch will virtually always be false, and the branch predictor will make this fast. Unless the distribution is increasing (but not monotonically increasing) over time in an unpredictable way; in that case, the branch predictor will fail often and will be slow. The branch predictor (and cache, for that matter) is a sort of Schrodinger's cat that makes programs both slow and fast at the same time, but you never know which until you benchmark it.
jeffwass 5y ago
It’s not too difficult to see. Eg : 2^3 x 2^5 = 2^8 Explicitly writing the powers as multiplications : 2x2x2 x 2x2x2x2x2 = 2x2x2x2x2x2x2x2 So multiplying powers of the same base is just adding the exponents. Logarithms are the inverse of exponentiation. Log2(N) counts how many factors of 2 are needed to multiply together to get N. So Log2(2^x) = x As per above example : Log2(2^3 x 2^5) = 3 + 5

secondcoming 5y ago

Logarithms are taught before calculus where I grew up.

aaaaaaaaaaab 5y ago

Calculus? Really? Logarithms are basic highschool math in my country…

presspot 5y ago
We don't learn mahr here
NullPrefix 5y ago
Such a shame that grammar wasn't a basic thing back there.
- jacquesm 5y ago
  Or tact.
mwfunk 5y ago
Fun fact: in the UK they call it marhs!
dang 5y ago
Please don't put other users down, regardless of how math is taught in your country. We want curious conversation in which people treat each other well, even if they know less than you do. We do not want point-scoring and putdowns. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html Edit: you've unfortunately been posting unsubstantive comments and breaking the site guidelines with this account elsewhere, too. Can you please stop that so we don't have to ban you again?

jacquesm 5y ago

Look at how multiplication is done with a sliderule. https://www.sliderules.org/react/aristo_0901_junior.html https://www.sliderules.org/react/aristo_0901_junior.html

shoo 5y ago

A similar trick is used for a different reason in statistical and probabilistic calculations -- for numerical stability rather than performance. Suppose you have n probabilities p_1, ..., p_n. Each p_i is a real number in the interval [0, 1] . Often you want to multiply probabilities to compute prod_i p_i . Probabilities p_i can be tiny floating point values (very close to zero) and if n, the number of factors, is large, then the product will evaluate to zero due to underflow. Software that processes probabilities often instead stores log-probabilities. Then the product prod_i p_i can be evaluated as sum_i log(p_i) , which is more numerically stable. Where this gets a bit trickier is if you instead want to compute the sum of probabilities, rather than their product -- e.g. to renormalise probabilities so they all sum to 1. If you have encoded the probabilities as log-probabilities, you now need to take the log-exp-sum [1][2], which will cause numeric overflow if done naively, and is also relatively expensive to compute, as it requires n exponentials and 1 log to combine n log-probs. log-exp-sum can be evaluated in a stable way by first doing a pass over the data to compute the max log-prob, then doing a second pass to take the exponential of each log-prob offsetted by the max log-prob, so each of the terms being exponentiated is at most 0. There's also a streaming version of log-exp-sum that permits a single pass over the data [3] -- a max is calculated on the fly and each time a new max is identified, the running sum is multiplied by a correction factor. I'm a bit suspicious that the branches in the streaming log-exp-sum might cause a performance impact when executing, although each exp calculation is so expensive that perhaps it doesn't make that much of a difference. [1] https://en.wikipedia.org/wiki/LogSumExp https://en.wikipedia.org/wiki/LogSumExp [2] https://blog.smola.org/post/987977550/log-probabilities-semirings-and-floating-point https://blog.smola.org/post/987977550/log-probabilities-semi... [3] http://www.nowozin.net/sebastian/blog/streaming-log-sum-exp-computation.html http://www.nowozin.net/sebastian/blog/streaming-log-sum-exp-...

nwallin 5y ago
> I'm a bit suspicious that the branches in the streaming log-exp-sum might cause a performance impact when executing, Since you're just checking whether the current sample is larger than the largest sample seen so far, you're very likely to find a "large" sample early that rarely gets updated. From then on, this branch will virtually always be false, and the branch predictor will make this fast. Unless the distribution is increasing (but not monotonically increasing) over time in an unpredictable way; in that case, the branch predictor will fail often and will be slow. The branch predictor (and cache, for that matter) is a sort of Schrodinger's cat that makes programs both slow and fast at the same time, but you never know which until you benchmark it.

jeffwass 5y ago

It’s not too difficult to see. Eg : 2^3 x 2^5 = 2^8 Explicitly writing the powers as multiplications : 2x2x2 x 2x2x2x2x2 = 2x2x2x2x2x2x2x2 So multiplying powers of the same base is just adding the exponents. Logarithms are the inverse of exponentiation. Log2(N) counts how many factors of 2 are needed to multiply together to get N. So Log2(2^x) = x As per above example : Log2(2^3 x 2^5) = 3 + 5