0

Please, does anyone know how to compute the integer part of natural logarithm of an integer?

Preferably using integer arithmetic only (akin to integer square root method), without relying on floating-point log (i.e. not Math.floor(Math.log(x)).

To explain why this question is not duplicate of the linked question: this deals with natural logarithm and possibly unbounded inputs, the other is for base 2 or 10 and simulates floating-point by 32-bit fixed-precision arithmetic. The other question also does not explain how many fixed bits it requires to correctly compute integer part of natural log of unbounded input.

Ecir Hana
  • 10,864
  • 13
  • 67
  • 117
  • What's your input range? – user3386109 Aug 26 '18 at 08:16
  • @RoryDaulton You mean as a floating-point number? If so, no, I would prefer not to. – Ecir Hana Aug 26 '18 at 09:13
  • @user3386109 Many thousands of bits, basically BigInteger range. – Ecir Hana Aug 26 '18 at 09:16
  • 1
    I think a method similar to [integer log 10](https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10) can be used. But please don't cross post questions [Integer part of natural logarithm](https://math.stackexchange.com/q/2894807/90333) – phuclv Aug 26 '18 at 12:03
  • 3
    This is an unusual thing to do. Why are you trying to do it? There may be another way to achieve your goal. – Eric Postpischil Aug 26 '18 at 12:29
  • @EricPostpischil Integer part of natural logarithm comes up at few primality testing algorithm so I got curious whether there is something similar as there is for integer square roots. – Ecir Hana Aug 26 '18 at 12:57
  • 1
    A simple crude estimate is the bit length of the integer, which is available in most big int implementations, e.g. for Java it is [BigInteger.bitLength()](https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#bitLength--) – President James K. Polk Aug 26 '18 at 13:19
  • 4
    The most reasonable way to get a log base e with integer math is to get a log base 2 and multiply. – Matt Timmermans Aug 26 '18 at 14:10
  • Possible duplicate of [Building a logarithm function in C without using float type](https://stackoverflow.com/questions/42107700/building-a-logarithm-function-in-c-without-using-float-type) – Spektre Aug 27 '18 at 07:03
  • you can use fixed point on integers... and exploit that `ln(x) = log2(x)/log2(e)` ... See the [duplicate QA](https://stackoverflow.com/questions/42107700/building-a-logarithm-function-in-c-without-using-float-type) I linked on How to compute that on integers only – Spektre Aug 27 '18 at 07:04
  • @Spektre I don't believe it is duplicate, the main difference is the unbounded input. – Ecir Hana Aug 27 '18 at 07:32
  • @EcirHana What do you mean by unbound input (bigints perhaps)? the duplicate computes exactly what you are asking about. The number of fractional bits depends on precision you want as you need just integer part 8 should be more than enough. the conversion between `log2` and `ln` base is in my comment above... simple integer division by constant – Spektre Aug 27 '18 at 07:42
  • I think that for `bigints` you could use the inputs bit-width for the fraction bits of the `log2(e)=1.4426950408889634073599246810019` so after division your integer accuracy is not lost . the result after division is ~1.5 less than the input so you can use `8+(70%)` of the input bitwidth as the fraction bits count – Spektre Aug 27 '18 at 08:01
  • @EcirHana: Out of curiosity, _which_ primality testing algorithms does this turn up in? (I've seen a lot of primality testing algorithms, but I don't recall ever seeing the need for floor of the natural log for them.) Do you actually need a precise value, or just an approximation, or perhaps some kind of lower or upper bound? It would be much easier to give a guaranteed and tight bound (either lower or upper) than an exact value for the floor of the natural log. – Mark Dickinson Aug 27 '18 at 10:11
  • Ah, if you're assuming the truth of GRH, the Miller-Rabin test has a bound of the form `floor(2*ln(n)^2)`. Is that the sort of thing you were thinking of? In that case, a guaranteed upper bound would be plenty good enough. – Mark Dickinson Aug 27 '18 at 10:19
  • @MarkDickinson Yes GRH, deterministic Miller's test, the one which Miller-Rabin stood from. And I understand I could add one to `Math.floor(Math.log(x))` just to be sure, I was just curios whether there is a nice way of calculating it directly with integers, as it is the case with integer square root. – Ecir Hana Aug 27 '18 at 14:26

1 Answers1

0

I hope that multiplication is allowed.

So you can apply exponential search (a kind of binary search) approach to find such power n that 

 e^n <= x < e^(n+1)
MBo
  • 77,366
  • 5
  • 53
  • 86
  • 1
    Then of course, how do I compute `e^x` using integers and what is a good initial guess for `x`? – Ecir Hana Aug 26 '18 at 08:42
  • It is impossible to compute e^x using integers only (while you don't need `Exp` function, just multiplication), Good initial guess is position of the left 1 bit in binary representation of value (binary logarithm). But what is reason for this task? – MBo Aug 26 '18 at 14:37
  • I thought by above you meant some kind of binary search for `n`. Then one would need to be able to compute `e^n`. But maybe I misunderstood..? – Ecir Hana Aug 26 '18 at 14:57
  • You are right. Binary search for n (to find `Floor(ln(x))`) – MBo Aug 26 '18 at 15:04
  • 1
    @EcirHana there are only 44 different powers of e that fits in a `uint64_t` so you can just put them into a lookup table – phuclv Aug 18 '20 at 15:54