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?

  • $\begingroup$ What do you call quite large ? 32 bits or million bits ? $\endgroup$ – Yves Daoust Aug 26 '18 at 9:13
  • $\begingroup$ @YvesDaoust Many thousands of bits. Probably "mid-sized input" would be more fitting. $\endgroup$ – Ecir Hana Aug 26 '18 at 9:17
  • $\begingroup$ @Hurkyl Please see the edit. $\endgroup$ – Ecir Hana Aug 26 '18 at 9:37
  • $\begingroup$ Integer part of logarithm $\endgroup$ – phuclv Aug 26 '18 at 11:55
  • $\begingroup$ Nice insights in this answer: math.stackexchange.com/questions/1382070/… $\endgroup$ – N74 Aug 27 '18 at 20:10

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.

  • $\begingroup$ Interesting idea, thanks! But even if I could guarantee the upper bound of inputs (which I unfortunately cannot), how should I proceed calculating the table? I assume you meant to use some BigFloat library, compute an entry to sufficient precision and "floor" it. If so, couldn't it happen that because of a rounding error I would get off-by one value? $\endgroup$ – Ecir Hana Aug 26 '18 at 9:42
  • $\begingroup$ @EcirHana: Often, libraries will give bounds on the error, which you can check to be sure the error interval doesn't span an integer. $\endgroup$ – user14972 Aug 26 '18 at 9:49
  • $\begingroup$ @EcirHana: with a little care you can compute with sufficiently many guard digits of $e$ so that rounding yields the exact integer - use error calculus. By curiosity, why do you need such tremendous accuracy ? $\endgroup$ – Yves Daoust Aug 26 '18 at 9:51
  • $\begingroup$ @YvesDaoust Re "tremendous accuracy", I don't I just thought that kind of error would be not very rare. $\endgroup$ – Ecir Hana Aug 26 '18 at 10:30
  • $\begingroup$ @YvesDaoust I meant thousands of digits of input integer $x$. $\endgroup$ – Ecir Hana Aug 26 '18 at 11:54

$$ \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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.