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

Groups > comp.lang.python > #76191 > unrolled thread

Log base 2 of large integers

Back to article view | Back to comp.lang.python

Contents

  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

#76191 — Log base 2 of large integers

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?

Thanks in advance.

M. K. Shen

[toc] | [next] | [standalone]

#76194

On Wed, Aug 13, 2014 at 8:05 AM, Mok-Kong Shen
<mok-kong.shen@t-online.de> 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?

A bit of googling turned up this page:

http://gnumbers.blogspot.com/2011/10/logarithm-of-large-number-it-is-not.html

Might be worth studying for ideas.

Skip

[toc] | [prev] | [next] | [standalone]

#76198

Am 13.08.2014 15:16, schrieb Skip Montanaro:

> http://gnumbers.blogspot.com/2011/10/logarithm-of-large-number-it-is-not.html
>
> Might be worth studying for ideas.

Thanks. I think the idea may help.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#76195

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:

def log2(n):
    """Return the floor of log2(n)."""
    if n <= 0: raise ValueError
    i = -1
    while n:
        n //= 2
        i += 1
    return i

log2(511)
=> returns 8
log2(512)
=> returns 9
log2(513)
=> returns 9


Does that help?



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#76197

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:
>
> def log2(n):
>      """Return the floor of log2(n)."""
>      if n <= 0: raise ValueError
>      i = -1
>      while n:
>          n //= 2
>          i += 1
>      return i
>
> log2(511)
> => returns 8
> log2(512)
> => returns 9
> log2(513)
> => returns 9
>
>
> 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

[toc] | [prev] | [next] | [standalone]

#76201

Mok-Kong Shen <mok-kong.shen@t-online.de>:

>>> 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.

   >>> math.log(7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777, 2)
   18270.24195180111

How big an integer are we talking about?


Marko

[toc] | [prev] | [next] | [standalone]

#76202

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

[toc] | [prev] | [next] | [standalone]

#76205

Steven D'Aprano wrote:

> 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:
> 
> def log2(n):
>     """Return the floor of log2(n)."""
>     if n <= 0: raise ValueError
>     i = -1
>     while n:
>         n //= 2
>         i += 1
>     return i
> 
> log2(511)
> => returns 8
> log2(512)
> => returns 9
> log2(513)
> => returns 9

For base 2 there is also the bit_length() method:

>>> 511 .bit_length()
9
>>> 512 .bit_length() 
10
>>> 513 .bit_length()  
10

[toc] | [prev] | [next] | [standalone]

#76200

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?

What version of Python are you using? Python 2.7 can handle "fairly large" 
integers:

>>> float(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to float
>>> math.log(x, 2)
50462500.07504181

Or maybe our idea of "fairly large" differ; so how large is fairly large?

[toc] | [prev] | [next] | [standalone]

#76211

On Wed, 13 Aug 2014 15:58:02 +0200, Peter Otten <__peter__@web.de> wrote:
> 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.
[snip]
> Or maybe our idea of "fairly large" differ; so how large is fairly large?

MK Shen used to hang out on the sci.crypt newsgroup, so we're
probably talking "cryptographically large" rather than "engineeringly
large".

-- 
To email me, substitute nowhere->spamcop, invalid->net.

[toc] | [prev] | [next] | [standalone]

#76212

Peter Pearson <ppearson@nowhere.invalid>:

> MK Shen used to hang out on the sci.crypt newsgroup, so we're probably
> talking "cryptographically large" rather than "engineeringly large".

I'm thinking we're talking about philosophically large. Those kinds of
numbers are unwieldy from all angles, including cryptography.


Marko

[toc] | [prev] | [next] | [standalone]

#76214

On Thu, Aug 14, 2014 at 2:12 AM, Peter Pearson <ppearson@nowhere.invalid> wrote:
> MK Shen used to hang out on the sci.crypt newsgroup, so we're
> probably talking "cryptographically large" rather than "engineeringly
> large".

So "fairly large" means somewhere between googolplex an Graham's
Number, and after that they'd be called "very large"?

ChrisA

[toc] | [prev] | [next] | [standalone]

#76222

On Wed, Aug 13, 2014 at 10:18 AM, Chris Angelico <rosuav@gmail.com> wrote:
> On Thu, Aug 14, 2014 at 2:12 AM, Peter Pearson <ppearson@nowhere.invalid> wrote:
>> MK Shen used to hang out on the sci.crypt newsgroup, so we're
>> probably talking "cryptographically large" rather than "engineeringly
>> large".
>
> So "fairly large" means somewhere between googolplex an Graham's
> Number, and after that they'd be called "very large"?

I estimate that representing a googolplex as a 64-bit Python 3 int
would require around 4.429 * 10**75 yottabytes of memory. So probably
not that large.

[toc] | [prev] | [next] | [standalone]

#76204

Mok-Kong Shen <mok-kong.shen@t-online.de> Wrote in message:
> 
> 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?
> 
> Thanks in advance.
> 
> M. K. Shen
> 

Easiest way to get the integer part is to convert to binary
 string,  and take the length of that string.
Call that m.

Then construct a string consisting of a 1 followed by m zeroes.
 
Convert that to a long,  and divide your original number by it.
 Now take the log base 2 of the quotient. Add that to m and you
 have your answer, plus or minus 1.

-- 
DaveA

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web