Integer part of natural logarithm

Question

Please, does anyone know of a algorithm to compute the integer part $n$ of natural logarithm of an integer $x$?

$$n = \lfloor \ln(x) \rfloor$$

Preferably using integer arithmetic only (akin to integer square root method), without relying on floating-point $\log(x)$ function, as the argument could be quite large (typically many thousands of bits; maybe less than millions, definitely more than 64).

PS: I also would like to compute the integer part of square of the natural logarithm, i.e.:

$$n = \lfloor \ln^2(x) \rfloor$$

Would it be possible to adapt the above algorithm to compute this as well?

Answer 1

I guess that the most efficient is to tabulate all the integer powers of $e$ and use a dichotomic search.

For $64$ bits integers, $44$ tables entries will suffice and the answer is found in $6$ steps.

For a million bits, $693148$ entries and $20$ comparisons only. But this is impractical because the entries are large and the table won't fit in memory.

---

If you cannot afford the storage space, then you can do with keeping the powers of $e$ that are powers of $2$, i.e. $e,e^2,e^4,e^8,\cdots$ and compute the intermediate powers as you go, during the dichotomic search.

I think that you will have to keep extra fractional parts (fixed-point arithmetic) to make sure that the products yield exact integer parts.

Answer 2

$$ \ln(2^n a + b) = n \ln(2) + \ln(a) + \ln\left(1 + \frac{b}{2^n a} \right) $$

Assuming $b < 2^n a$, you have

$$ n \ln(2) + \ln(a) \leq \ln(2^n a + b) < n \ln(2) + \ln(a) + \frac{b}{2^n a} $$

Unless you are in an unlucky situation where $n \ln(2) + \ln(a)$ is extremely close to an integer, this lets you determine the integer part using an existing low-precision implementation of $\ln$.

If you are in the unlucky situation, and you really can't tolerate the result being off by 1, I imagine the only way you can reasonably get the result is to involve doing higher precision floating point calculation, whether you write it yourself or use an existing library.

If you have to implement yourself, a nice source is Modern Computer Arithmetic.