Why does this algorithm work for calculating ln(x)?

[Arnoldjavs3]

Homework Statement

I found this algorithm online for computing ln(x). I use the babylonians method for computing square root if it is relevant.

fun naturalLog(desired: Double): Double {
    var naturalLog = desired // desired = x
    for(number in 0..9) {
        naturalLog = squareRootx(naturalLog) // squareroot 10 times
    }
    naturalLog -= 1
    naturalLog *= 1024
    return naturalLog
}

(This code is in Kotlin).

Homework Equations

The Attempt at a Solution

I just really don't understand. I've verified that it has accuracy of up to 2 decimal points.

When I compute $ln(9)$ I get $2.19958358$, so after the 2nd decimal point it loses accuracy. It might be relevant to my squareroot algorithm, but I doubt it. What is this 1024 number? Is there some coincidence between a KiB = 1024 bytes? Googling around for ln(x) algorithms doesn't help.

 

[Zerox5f3759df]

As best as I can figure it is roughly approximating the following limits.

$\lim_{n \to \infty} (x^{\frac{1}{n}} - 1) * n = \lim_{n \to \infty} \frac{x^{\frac{1}{n}} - 1}{\frac{1}{n}} = \lim_{n \to \infty} \frac{x^{\frac{1}{n}} * \ln{x} * \frac{-1}{n^2}}{\frac{-1}{n^2}} = \ln{x}$

It mis-matches the root taking with the multiplier, but otherwise seems pretty close. Hard to determine at first because use of 1024 as the multiplier is suggestive of clever computing tricks such as register shifts and whatnot, but none of that is in play here that I can see.

Quick edit: If you want to improve accuracy, approximate larger nth roots, and have the multiplier at the end be based on the n.

 

[I like Serena]

I concur.
Taking the square root 10 times means that we have n=2¹⁰=1024, which is where the multiplier comes from.
The KiB finds its origin in the fact that this number is so close to 1000, but that won't be related to the algorithm. We can pick a higher n after all.

 

[Zerox5f3759df]

Good catch on where 1024 is coming from. I thought I saw the loop going from 1-9, not 0-9.

 

[Ray Vickson]

As best as I can figure it is roughly approximating the following limits.

$\lim_{n \to \infty} (x^{\frac{1}{n}} - 1) * n = \lim_{n \to \infty} \frac{x^{\frac{1}{n}} - 1}{\frac{1}{n}} = \lim_{n \to \infty} \frac{x^{\frac{1}{n}} * \ln{x} * \frac{-1}{n^2}}{\frac{-1}{n^2}} = \ln{x}$

It mis-matches the root taking with the multiplier, but otherwise seems pretty close. Hard to determine at first because use of 1024 as the multiplier is suggestive of clever computing tricks such as register shifts and whatnot, but none of that is in play here that I can see.

Quick edit: If you want to improve accuracy, approximate larger nth roots, and have the multiplier at the end be based on the n.

In fact, for finite $n$ we have
$$n \left( x^{1/n} - 1 \right) = \ln(x) + \frac{1}{2n} \ln(x)^2 + \frac{1}{6 n^2} \ln(x)^3 + \cdots + \frac{1}{k! \, n^k} \ln(x)^{k+1} + \cdots $$

 

[I like Serena]

In fact, for finite $n$ we have
$$n \left( x^{1/n} - 1 \right) = \ln(x) + \frac{1}{2n} \ln(x)^2 + \frac{1}{6 n^2} \ln(x)^3 + \cdots + \frac{1}{k! \, n^k} \ln(x)^{k+1} + \cdots $$

More specifically, we can calculate the error:
$$n \left( x^{1/n} - 1 \right) = \ln(x) + \frac{\xi^{1/n}}{2n} \ln(x)^2$$
where $\xi$ is between 1 and x.
That is, if $x\ge 1$ then the error is at most $\frac{x^{1/n}}{2n} \ln(x)^2$.