Log base 2 of large integers
Andrew Jaffe
a.h.jaffe at gmail.com
Wed Aug 13 10:06:48 EDT 2014
On 13/08/2014 14:46, Mok-Kong Shen wrote:
> Am 13.08.2014 15:32, schrieb Steven D'Aprano:
>> Mok-Kong Shen wrote:
>>
>>>
>>> I like to compute log base 2 of a fairly large integer n but
>>> with math.log(n,2) I got:
>>>
>>> OverflowError: long int too large to convert to float.
>>>
>>> Is there any feasible work-around for that?
>>
>> If you want the integer log2, that is, the floor of log2, the simplest
>> way
>> is calculate it like this:
>>
>> <<< removed... see below >>>
>>
>> Does that help?
>
> That is too inaccurate (e.g. for 513 above) for me, I would like
> to get accuracy around 0.01 and that for very large n.
>
> M. K. Shen
Well, we can use Steven d'A's idea as a starting point:
import math
def log2_floor(n):
"""Return the floor of log2(n)."""
if n <= 0: raise ValueError
i = -1
while n:
n //= 2
i += 1
return i
def log2(n):
""" return log_2(n) by splitting the problem into the integer and
fractional parts"""
l2f = log2_floor(n)
if n == 2**l2f:
return l2f
else:
return l2f + math.log(n*2**-l2f, 2)
Andrew
More information about the Python-list
mailing list