post's blog

By post, history, 11 days ago, In English

Hi, I'm solving D. Ilya and Escalator.

I have written (I guess) the correct solution for it, but I'm getting a wrong answer, because I print some weird value because of a lot of operations with doubles (you can see it in the code). That is, I believe I never exceed the maximum of double, but calculate something like $$$0.65^{2000}$$$, whose only a few digits I need.

code

Is there any workaround for this given that I need only six digits precision?

Thanks.

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +18 Vote: I do not like it

When you have only multiplication and division, you can avoid the precision problem by using logarithm arithmetic instead of the normal one. So if you have 2 numbers $$$a, b$$$, you can rewrite them as $$$a = e^{a'}$$$ and $$$b = e^{b'}$$$ (that is, $$$a' = \log(a)$$$, $$$b' = \log(b)$$$. And now you can just use $$$a'$$$ and $$$b'$$$ instead:

  • $$$a \times b = e^{a'} \times e^{b'} = e^{a' + b'} \Rightarrow a' + b'$$$.
  • $$$a / b = e^{a' - b'} \Rightarrow a' - b'$$$.

After the the computation, you can receive the original answer by using the function exp().

»
11 days ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I don't know if this is applicable to your problem, but sometimes you can use the fact that $$$ln(x \cdot y) = ln(x) + ln(y)$$$. So you can transform multiplication operations into additions and then you'd get the actual answer by doing $$$e^{lnAnswer}$$$.

Edit: I was too slow.