Tuesday, April 26, 2016

Log scale computations

Sometimes there is the need to multiply a lot of small positive numbers. This leads to underflow. Log scale is used to overcome (aka postpone) it:

  • log(a * b) = log(a) + log(b)

scala> val x = Double.MinPositiveValue
x: Double = 4.9E-324
scala> val xx = x * x
xx: Double = 0.0 // underflow
scala> val logx = math.log(x)
logx: Double = -744.4400719213812
scala> val logxx = logx + logx
logxx: Double = -1488.8801438427624

It enables to do log product of about E305 minimum Doubles and E307 of 0.1's:
scala> val logProdMin = Double.MinValue / logx
logProdMin: Double = 2.414825857268154E305
scala> val logProd01 = Double.MinValue / math.log(0.1)
logProd01: Double = 7.807282086260621E307

Interestingly, there is not a big difference in capacity for log product of 0.1 and 4.9E-324. The capacity looks good unless you are doing some sort of iterative computations, so that each step you need to multiply the products from the previous step. Apparently, after about a thousand of steps one will reach overflow:
scala> val iterProd = math.log(logProd01) / math.log(2)
iterProd: Double = 1022.7967455273003

That number is smaller for single precision: ~126.8.

Sometime there is the need to perform normalization of small numbers, i.e. division of each element by their sum. This is typical when your small numbers are in vector (a1, a2):
(a1, a2) = (a1 + a2) * (a1 / ( a1 + a2), a2 / (a1 + a2))
Now we could apply log, but what is log of sum?

  • log(a + b) = log[exp(log(a)) + exp(log(b))]=log[exp[(log(a))*(1 + exp(log(b) - log(a))]]=log(a) + log[1+exp(log(b) - log(a))]
  • similarly, log(a - b) = log(a) + log[1 - exp(log(b) - log(a))]

Note that we assumed that a > b, otherwise the difference will be (a - b). For a vector of bigger length:

  • log(a1 + ... + aN) = log(max(a)) + log[1 + exp(log(a1 +... aN - max(a)))]

Implementation of log(x) is not a very good approximation of log(1 + x), so there is a separate function for that purpose math.log1p.

However, there is exponent in the formula. If log(b) - log(a) is less than a log(Double.MinPositiveValue) then exponent is zero, log1p is zero and log(a+b)=log(a).

Relevant link: http://colorfulengineering.org/logmath-notes.pdf

No comments:

Post a Comment