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

trincot · Answer 1 · 2018-02-10T21:53:12.440

6

One way is to make your function self-correcting:

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

Or a bit more obscure:

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

edited Feb 10 '18 at 21:53

answered Feb 10 '18 at 21:52

trincot

263,463
30
215
251

Great! I didn't consider that. – jodag Feb 10 '18 at 21:53
1

This works for a couple of million randomly chosen values of *n* and *b*. Are there any guarantees that `math.log` will be off by at most one on any platform? – Blender Feb 10 '18 at 22:07
1

If the floating point result of the logarithm would have an error of more than 1 due to the limited precision of floats, it would have to be greater than 2^53. With a base of 2, this means the function was called with a first argument number using 2^53 bits, which I bet doesn't fit in your laptop's RAM. ;-) – trincot Feb 10 '18 at 22:42

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}'

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

2 Answers2

Linked