Precise math.log(x, 2) in Python

Question

In python, I need to get the rounded down logarithm of positive integers for base 2, including big numbers.

However, since floating point math is used, I might get bad results, for example:

>>> import math
>>> int(math.log(281474976710655, 2))
48

However:

>>> 2 ** 48
281474976710656

So the correct result, rounded down, should be 47.

How can I get the correct value?

PM 2Ring · Accepted Answer · 2016-12-13 13:02:44Z

4

In Python 3, integers have a .bit_length method, so you should use that to get your rounded down base 2 logarithm.

Here's a short demo:

m = 2 ** 1000
for n in (281474976710655, m-1, m, m+1):
    a = n.bit_length() - 1
    b = 2 ** a
    print(a, b <= n < 2 * b)

output

47 True
999 True
1000 True
1000 True

answered Dec 13, 2016 at 13:02

PM 2Ring

55.6k6 gold badges96 silver badges201 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Community · Accepted Answer · 2017-05-23 12:30:32Z

2

In python 3 ints even have an efficient .bit_length() method!

>>> (281474976710655).bit_length()
48
>>> (281474976710656).bit_length()
49

In python 2, instead of using floating point math, count the number of bits:

def log2(n):
    assert n >= 1
    return len(bin(n)) - 3  # bin() returns a string starting with '0b'

(Edited following this comment)

edited May 23, 2017 at 12:30

CommunityBot

11 silver badge

answered Dec 13, 2016 at 12:50

Udi

30.8k9 gold badges105 silver badges134 bronze badges

1 Comment

PM 2Ring Over a year ago

That's fine for Python 2, but in Python 3 .bit_length is much more efficient than converting the number to a binary string. BTW, in Python 2.6+ format(n, 'b') is more convenient for this than bin, since you don't get that pesky '0b'.

Collectives™ on Stack Overflow

Precise math.log(x, 2) in Python

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related