Floor of Natural Logarithm

I looked up the true value of log(4311231547115195) on Wolframalpha:

35.999999999999999947320523193696952441144620104788563247797375573...

Now that's cutting it close! way closer than the built-in floating point numbers in python can support.

You have two problems: you need to be able to exponentiation or log floating point values with much higher precision, and you also need a way to know how much precision is enough or too much.

The decimal module can solve the first problem. Assuming 50 digits of precision will be good enough to get the job done, you don't really need to solve the second problem dynamically.

Here is something that should get the job done. You might want to just remove the conditions I threw in, but it's up to you:

import math
from decimal import Decimal, getcontext
getcontext().prec = 50
def truefloorlog(n:int) -> int:
    # if number is sufficiently far from integer values, floor will be
    # unaffected:
    overmargin = math.ceil(math.log(n)) - math.log(n)
    undermargin = math.log(n) - math.floor(math.log(n))
    if overmargin > 0.0005 and undermargin > 0.0005:
        return math.floor(math.log(n))
    else:
        return math.floor(Decimal(n).ln())
def truefloorlogsquared(n:int) -> int:
    logval = Decimal(n).ln()
    return math.floor(logval**2)
if name == "main":
    for i in [1,10,100,4311231547115195]:
        print(f"truefloorlog({i}) = {truefloorlog(i)}")
        print(f"truefloorlogsquared({i}) = {truefloorlogsquared(i)}")

truefloorlog(100) = 4 
truefloorlogsquared(100) = 21 
truefloorlog(4311231547115195) = 35 
truefloorlog_squared(4311231547115195) = 1295

When you use: ⌊ln(n)⌋ to mean the floor function, that implies you could use math.floor.

The answers to this question might help.

int gives the same as floor for positive values. In any case, it's not very good as using floats gives inaccurate results.

from decimal import Decimal, getcontext
def floorln(n):
    # We assume n is a positive integer.
    # The goal is to compute floor(ln(n)) exactly,
    # even when n is extremely large.
    # Set the precision of Decimal arithmetic.
    # We use n.bitlength() because ln(n) is roughly proportional
    # to the number of bits in n.
    # This guarantees enough precision for correct comparisons.
    getcontext().prec = n.bitlength()
    # Convert n to Decimal so we can compare it
    # with Decimal exponentials accurately.
    ndec = Decimal(n)
    # Binary search lower bound for k.
    # ln(n) is always >= 0 when n >= 1.
    low = 0
    # Estimate a safe upper bound for floor(ln(n)).
    #
    # We know:
    #   ln(n) = ln(2^(bitlength-1)) approximately
    #         ≈ (bitlength)  ln(2)
    #
    # So n.bit_length()  ln(2) is a safe overestimate.
    # We add +2 to be extra safe against rounding issues.
    high = int(n.bit_length() * Decimal(2).ln()) + 2
    # Perform binary search in range [low, high)
    # We are searching for the largest integer k such that:
    #   exp(k)  n.
    # Therefore low - 1 is the largest value
    # such that exp(k) 

Plug in 11892590228282008819681954096389267309259354644229. It outputs 113 when it should output 112. That number is very large, but I did say "arbitrarily large integer".

...Can't you just build a table of eⁿ for integers 0 through your arbitrarily large data size?

e⁰ = 1

e¹ = 2.7...

e² = 7.3...

Then you can just walk through the array and check if n is greater than the next index.

It took a bit of staring, but I'm 90% sure this was written by an LLM. What really tipped me off was the usage of that many comments in a Stack Overflow answer (really, it should just be text separate from the code) that just explain each line of code individually, the use of ≈ and not ≤ and ≥ (the use of ≈ alone isn't that big of a clue since if you configure things correctly, it becomes easy to type), the comment We assume n is a positive integer. The goal is to compute floor(ln(n)) exactly, even when n is extremely large., and the terrible algorithm itself.

I can't build a table of infinitely many elements. Even if I could, how would I make sure that I get the integer part of the exp(n) correct every time? Evaluate a series expansion using exact fractions for a million terms?

This is the second consecutive question to get an LLM generated answer. Weird.

Julia will do it at that resolution right out of the box using BigFloat.

julia> log(2) 0.6931471805599453

julia> log(BigFloat(11892590228282008819681954096389267309259354644229)) 112.9999999999999999999999999999999999999999999999999419962029156289951984924604

You can increase the bits used to represent a BigFloat if you need even more precision subject to running out of memory or performance whichever happens first.

BTW you never compute log using the Taylor series - convergence is glacially slow. Rational approximations are the way forward. Simplest of them being log(1+x) = x*(6+x)/(6+4x)

I'm not using Julia, but this isn't even a good Julia solution since how am I supposed to figure out when I need more precision?

julia> log(BigFloat(74152073030341784283386937576609008174070650931717428340301864914189853561344))
177.0

Sure, I can increase precision (I can do that in python too), but then I'll end up with the same issue.

Isn't that just a Padé approximant of ln(1+x)?

Even for subsequence n=2^k for k=1,2,3,.. you effectively need to calculate ⌊(2^k)*ln(2)⌋ which is first k binary digits of ln(2). I know no "simple" algorithm for determine sequence of digits in ln(2) representation. That means no simple algorithm exists for your initial task.