Say I want to solve the following equation for k
\(
\( 1 \; - \; \frac{1}{D} \)^k \; = \; p
\)
for values of p near 0.5.
The exact solution is
\(
k \; = \; \frac{\ln{ \( p \)}}{\ln{ \(1 \; - \; \frac{1}{D} \)}}
\)
But if D is large, then calculating the ln() in the denominator is problematic.
So I can think of two approximations that should be valid when D is very large (as in something like 2^256).
The first is the approximation that
\(
\ln{ \( 1 \; + \; x \) } \; \approx \; x
\)
Applying this to the denominator of the solution, we get
\(
k \; = \; -D \ln{ \( p \)} \; = \; D \ln{ \( \frac{1}{p}\) }
\)
Another approximation is that
\(
\( 1 \; + \; x\)^k \; \approx \; 1 \; + \; kx
\)
Applying this to the original expression, we get
\(
k \; = \; D \( 1 - p \)
\)
If we set p = 0.5, then the first approximation yields
\(
k \; = \; D \ln{\( 2 \)} \; = \; 0.693 D
\)
While the second yields
\(
k \; = \; 0.5 D
\)
For several reasons, I have more confidence in the first approximation. But I would expect both approximations to converge as 1/D goes to zero (meaning that the ratio of the two approximations approaches unity), yet clearly they don't.
Any insights would be appreciated.
\(
\( 1 \; - \; \frac{1}{D} \)^k \; = \; p
\)
for values of p near 0.5.
The exact solution is
\(
k \; = \; \frac{\ln{ \( p \)}}{\ln{ \(1 \; - \; \frac{1}{D} \)}}
\)
But if D is large, then calculating the ln() in the denominator is problematic.
So I can think of two approximations that should be valid when D is very large (as in something like 2^256).
The first is the approximation that
\(
\ln{ \( 1 \; + \; x \) } \; \approx \; x
\)
Applying this to the denominator of the solution, we get
\(
k \; = \; -D \ln{ \( p \)} \; = \; D \ln{ \( \frac{1}{p}\) }
\)
Another approximation is that
\(
\( 1 \; + \; x\)^k \; \approx \; 1 \; + \; kx
\)
Applying this to the original expression, we get
\(
k \; = \; D \( 1 - p \)
\)
If we set p = 0.5, then the first approximation yields
\(
k \; = \; D \ln{\( 2 \)} \; = \; 0.693 D
\)
While the second yields
\(
k \; = \; 0.5 D
\)
For several reasons, I have more confidence in the first approximation. But I would expect both approximations to converge as 1/D goes to zero (meaning that the ratio of the two approximations approaches unity), yet clearly they don't.
Any insights would be appreciated.