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$ Is this homework? $\endgroup$ Apr 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$ Apr 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$ Apr 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$ Apr 5, 2015 at 18:18
  • 1
    $\begingroup$ I don't see any actual question in the opening post. $\;$ $\endgroup$
    – user6973
    Apr 5, 2015 at 20:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.