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.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Is this homework? $\endgroup$– Emil JeřábekApr 5, 2015 at 17:16
-
$\begingroup$ @EmilJeřábek, no. As far as I know, it is not a homework. Motivation comes from computing logarithm of the result of monotone SLPs. $\endgroup$– Gorav JindalApr 5, 2015 at 17:50
-
3$\begingroup$ 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$. $\endgroup$– Emil JeřábekApr 5, 2015 at 18:12
-
1$\begingroup$ 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. $\endgroup$– Emil JeřábekApr 5, 2015 at 18:18
-
1$\begingroup$ I don't see any actual question in the opening post. $\;$ $\endgroup$– user6973Apr 5, 2015 at 20:33
Add a comment
|