# Computing log of sum of positive integers

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.

• Is this homework? – Emil Jeřábek Apr 5 '15 at 17:16
• @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 Apr 5 '15 at 17:50
• 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 Apr 5 '15 at 18:12
• 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 Apr 5 '15 at 18:18
• I don't see any actual question in the opening post. $\;$ – user6973 Apr 5 '15 at 20:33