<p>As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input such that $(\log(a)-\alpha)\leq \frac{1}{2^k}$ and $(\log(b)-\beta)\leq \frac{1}{2^k}$. We need to compute $(k-c)$-bit approximation of $\log(a+b)$, i.e, we want to compute $\gamma$(as binary string) such that  $(\log(a+b)-\gamma)\leq \frac{1}{2^{k-c}}$. Here $c$ is some constant integer, you can choose it to be anything as long as running time complexity bound is satisfied. Required time complexity is $\mathrm{poly}(|\alpha|, |\beta|, k)$, here time complexity is defined as number of bit operations.  $|\alpha|, |\beta|$ denote the bit length of $\alpha$ and $\beta$ respectively.</p>

CC BY-SA 3.0
2015-04-05T17:16:34.640Z
Is this homework?
Emil Jeřábek
CC BY-SA 3.0
2015-04-05T17:50:43.740Z
@EmilJeřábek, no. As far as I know, it is not a homework. Motivation comes from computing logarithm of the result of monotone SLPs.
Gorav Jindal
CC BY-SA 3.0
2015-04-05T18:12:27.507Z
Two straightforward solutions: (1) Exponentiate to get an approximation of $a,b$ in exponent-mantissa representation with $k$ bits of mantissa accuracy, add them, approximate the log. (2) WLOG $a\ge b$. Approximate $b/a=\exp(\log b-\log a)$ to $k$ bits, use it to approximate $\log (1+b/a)$, and add the result to $\log a$.
Emil Jeřábek
CC BY-SA 3.0
2015-04-05T18:18:09.247Z
Actually, if you want to approximate the result of an integer SLP, you can save yourself a lot of trouble by doing *all* the computation in the exponent-mantissa representation. You can compute the logarithm at the end.
Emil Jeřábek
<na.numerical-analysis><computing-over-reals><approximation>
Computing log of sum of positive integers
Gorav Jindal
# Computing log of sum of positive integers

(Asked by: username_0 on 2015-04-05)

As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input such that $(\log(a)-\alpha)\leq \frac{1}{2^k}$ and $(\log(b)-\beta)\leq \frac{1}{2^k}$. We need to compute $(k-c)$-bit approximation of $\log(a+b)$, i.e, we want to compute $\gamma$(as binary string) such that $(\log(a+b)-\gamma)\leq \frac{1}{2^{k-c}}$. Here $c$ is some constant integer, you can choose it to be anything as long as running time complexity bound is satisfied. Required time complexity is $\mathrm{poly}(|\alpha|, |\beta|, k)$, here time complexity is defined as number of bit operations. $|\alpha|, |\beta|$ denote the bit length of $\alpha$ and $\beta$ respectively.

**Tags:** na.numerical-analysis, computing-over-reals, approximation
> **Comments:**
> **username_1**: Is this homework?  
> **username_0**: @EmilJeřábek, no. As far as I know, it is not a homework. Motivation comes from computing logarithm of the result of monotone SLPs.  
> **username_1**: Two straightforward solutions: (1) Exponentiate to get an approximation of $a,b$ in exponent-mantissa representation with $k$ bits of mantissa accuracy, add them, approximate the log. (2) WLOG $a\ge b$. Approximate $b/a=\exp(\log b-\log a)$ to $k$ bits, use it to approximate $\log (1+b/a)$, and add the result to $\log a$.  
> **username_1**: Actually, if you want to approximate the result of an integer SLP, you can save yourself a lot of trouble by doing *all* the computation in the exponent-mantissa representation. You can compute the logarithm at the end.  

---

## 0 answers

