Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #76202

Re: Log base 2 of large integers

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Log base 2 of large integers Mok-Kong Shen <mok-kong.shen@t-online.de> - 2014-08-13 15:05 +0200
  Re: Log base 2 of large integers Skip Montanaro <skip@pobox.com> - 2014-08-13 08:16 -0500
    Re: Log base 2 of large integers Mok-Kong Shen <mok-kong.shen@t-online.de> - 2014-08-13 15:50 +0200
  Re: Log base 2 of large integers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-08-13 23:32 +1000
    Re: Log base 2 of large integers Mok-Kong Shen <mok-kong.shen@t-online.de> - 2014-08-13 15:46 +0200
      Re: Log base 2 of large integers Marko Rauhamaa <marko@pacujo.net> - 2014-08-13 17:00 +0300
      Re: Log base 2 of large integers Andrew Jaffe <a.h.jaffe@gmail.com> - 2014-08-13 15:06 +0100
    Re: Log base 2 of large integers Peter Otten <__peter__@web.de> - 2014-08-13 16:17 +0200
  Re: Log base 2 of large integers Peter Otten <__peter__@web.de> - 2014-08-13 15:58 +0200
    Re: Log base 2 of large integers Peter Pearson <ppearson@nowhere.invalid> - 2014-08-13 16:12 +0000
      Re: Log base 2 of large integers Marko Rauhamaa <marko@pacujo.net> - 2014-08-13 19:15 +0300
      Re: Log base 2 of large integers Chris Angelico <rosuav@gmail.com> - 2014-08-14 02:18 +1000
      Re: Log base 2 of large integers Ian Kelly <ian.g.kelly@gmail.com> - 2014-08-13 12:13 -0600
  Re:Log base 2 of large integers Dave Angel <davea@davea.name> - 2014-08-13 10:10 -0400

csiph-web