Although now we know how to use a table of pre-calculated logarithms to compute
logarithms of other numbers in any log base, you may still feel reasonably
unsatisfied. After all we still don't know how to compute the logarithm for
truly any value, for example the values actually given in the table such as
log(2) or decimal values such as log(12.34). So how do we compute such values?
The answer lies with the constant known as Euler's Number, commonly written
as e and approximately equal to 2.718282. (Maybe this number looks familiar
from a previous problem...?)
This constant has very wide-reaching applications, but for now we are interested
in logarithms taken to the base of this number, known as Natural Logarithms
and often written as log_e(x) = ln(x). Thankfully, there exists a Taylor Series Expansion to approximate any natural
logarithm:
$$ \large \ln(1+x) = \sum_{n=1}^{T} \frac{(-1)^{(n+1)}x^{n}}{n} = x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4} \space + \space ... $$
Note that the above example only shows 4 terms, but as T approaches infinity,
then more and more terms are added and the approximation
yields closer and closer to the exact answer. However, it should be noted that
this equation is only accurate for the range -1 < x < 1, and that outside of
this range it becomes wildly inaccurate or even undefined. So how would we
calculate the natural logarithm of numbers outside of that range? Let us recall
one of the fundamental properties of logarithms:
$$ \large \log_b \left( \frac{n}{m} \right) = \log_b \left( n \right) - \log_b \left( m \right) $$
Using these two relationships, we could create a clever method for calculating
the natural logarithm of any number. Let's choose some arbitrary number u such
that 0 < u < 1. We could then rearrange our equation as:
$$ \large \ln \left( 1+x \right) = \ln \left( \frac{1+x}{1+u} \right) + \ln \left( 1+u \right) $$
Now if both -1 < u < 1 and -1 < (1 + x) / (1 + u) - 1 < 1, then we can compute our final answer
using the Taylor Series Expansions! Otherwise we may need to perform that operation
multiple times until we can appropriately compute all logarithms using the Taylor Series.
For example the next application of the method may look like this:
$$ \large \ln \left( 1+x \right) = \ln \left( \frac{1+x}{(1+u)^{2}} \right) + 2 \ln \left( 1+u \right) $$
For example, calculating ln(5) using u = 0.5 and T = 50:
$$ \large \ln \left( 5 \right) = \ln \left( \frac{5}{(1.5)^3} \right) + 3 \ln \left( 1.5 \right) \approx 1.609438 $$
Note that 5 / (1.5)^2 ~= 2.222 while 5 / (1.5)^3 ~= 1.481. Therefore no more applications of the method are necessary for an accurate computation.
Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow, each with three space-separated values in the format
N T u.
You are asked to compute ln(N) using the value u to separate the
logarithms, and using T terms in the Taylor Series to approximate each natural
logarithm.
Answer
Should consist of Q space-separated values, corresponding to the calculated
natural logarithm described in each testcase.
Error should be less than 1e-6.
Example
input data:
5
5 5 0.5
5 5 0.25
5 50 0.5
500 100 0.66
500 100 0.95
answer:
1.61639 1.616918 1.609438 6.214608 6.21435