Better way to compute floor of log(n,b) for integers n and b?

Question

I'm looking to compute floor(log(n,b)) where n and b are both integers. Directly implementing this function fails for even slightly large values of n and b

# direct implementation
def floor_log(n,b):
    return math.floor(math.log(n,b))

For example, floor_log(100**3, 100) evaluates to 2 instead of the correct value 3.

I was able to come up with a working function which repeatedly divides until nothing remains

# loop based implementation
def floor_log(n,b):
    val = 0
    n = n // b
    while n > 0:
        val += 1
        n = n // b
    return val

is there a faster or more elegant way of obtaining this solution? Perhaps using built-in functionality?

@Blender Preferably I'm looking for a solution that works for all positive 32 bit integers. If you have a solution with different bounds I would also be interested in that too. — jodag, Feb 10 '18 at 21:50
I'm not aware of such function in both Python built-in or numpy. I think if you really care about performance in this function, it would be better to implement your python version in C. — llllllllll, Feb 10 '18 at 21:53

score 1 · Accepted Answer · answered Oct 03 '21 at 00:42

It's been a while since I posted this question. I originally accepted trincot's answer but recently realized that it fails to consistently produce the correct result when n gets large. There are really two problems. First, while we can be sure that the result of math.floor(math.log(n, b)) is not going be off by more than one as long as n < 2**(2**53) (which is probably too large to store in your computer), it turns out that it can be off by either +1 or -1. Furthermore, an error of +1 does not necessarily imply that n is a power of b, which is assumed by trincot's answer. Accounting for these issues is relatively straightforward:

def floor_log(n, b):
    res = math.floor(math.log(n, b))
    return res + 1 if b**(res+1) <= n else res - 1 if b**res > n else res

Or equivalently:

def floor_log(n, b):
    res = math.floor(math.log(n, b))
    return res + (b**(res+1) <= n) - (b**res > n)

Testing edge cases near powers of b

for p in [15, 30, 100, 1000]:
    for b in range(3, 50):
        for i in range(-2, 3):
            r, e = floor_log(b**p + i, b), p - (i < 0)
            assert r == e, f'floor_log({b}**{p} + {i}, {b}) = {r} but should be {e}'

score 1 · Answer 2 · answered Oct 17 '22 at 19:45

Based on this answer, we can avoid the need to use a logarithm on n, only a logarithm on b is necessary, as well as provably reduce the number of cases that need to be checked for correction. It suffices to use the bit length as a good estimate first and then follow up with correction.

from math import log

def floor_log(n, b):
    i = int(log(2, b) * (n.bit_length() - 1)) + 1
    return i - (b ** i > n)

The same logic is used as in the linked answer. Since the same base is probably used repeatedly, this can be further optimized using a cache:

from functools import lru_cache, partial
from math import log

CACHE_SIZE = 10
log_of_2 = lru_cache(CACHE_SIZE)(partial(log, 2))

def floor_log(n, b):
    i = int(log_of_2(b) * (n.bit_length() - 1)) + 1
    return i - (b ** i > n)

Better way to compute floor of log(n,b) for integers n and b?

2 Answers2

Linked