maximum integer length?

Discussion in 'Python' started by nate, Jun 18, 2006.

  1. nate

    nate Guest

    Hey everyone,

    I am trying to figure out what is the largest integer I can. Lets say
    for 400 megabytes of memory at my disposal.

    I have tried a few things
    c = 2**1000000
    d = 2**2000000
    print c**d

    Obviously I didn't have enough memory for that, but I was able to c**3.
    (I think anyways, it is still trying to display the result)

    So I am just wondering how long an integer can be with 400 megabytes of
    memory.

    I guess this is a question of logic?
    each integer takes up a byte right? If I have 400 megabytes that would
    mean I could have a long integer with up to 419,430,400,000 integers?

    Really I am not sure on this one and that is why I am asking. Because it
    is just bugging me I am not sure how it works...

    I know this probably seems trivial and just a stupid question, but I
    find this type of stuff interesting...
     
    nate, Jun 18, 2006
    #1
    1. Advertising

  2. nate enlightened us with:
    > Obviously I didn't have enough memory for that, but I was able to c**3.
    > (I think anyways, it is still trying to display the result)
    >
    > So I am just wondering how long an integer can be with 400 megabytes of
    > memory.


    I guess the best way would be a binary search for the proper value of
    the integer. You already have an upper (c**d) and a lower (c**3) bound
    for your search.

    > each integer takes up a byte right?


    That depends on the size of the integer, doesn't it?

    > If I have 400 megabytes that would mean I could have a long integer
    > with up to 419,430,400,000 integers?


    Que? An integer is just a whole number without fraction. What are you
    talking about?

    Sybren
    --
    The problem with the world is stupidity. Not saying there should be a
    capital punishment for stupidity, but why don't we just take the
    safety labels off of everything and let the problem solve itself?
    Frank Zappa
     
    Sybren Stuvel, Jun 18, 2006
    #2
    1. Advertising

  3. nate

    Guest

    nate wrote:
    > So I am just wondering how long an integer can be with 400 megabytes of
    > memory.
    >
    > I guess this is a question of logic?
    > each integer takes up a byte right? If I have 400 megabytes that would
    > mean I could have a long integer with up to 419,430,400,000 integers?
    >

    Python longs are stored using 15 bits out of every 16 bits (2 bytes).
    So every 2 bytes will contain approximately 4.5154 decimal digits.
    Ignoring memory usage and overhead, the number of digits in the largest
    possible long integer that can fit in 400 megabytes is

    >>> import math
    >>> 200 * 1024 * 1024 * 15 * math.log10(2)

    946958486.2000643

    Since memory space is required for temporary storage of intermediate
    results, you won't actually be able to create a number that large if
    you only have 400 megabytes.

    casevh
     
    , Jun 18, 2006
    #3
  4. On 2006-06-18, Sybren Stuvel <> wrote:
    > nate enlightened us with:
    >> Obviously I didn't have enough memory for that, but I was able to c**3.
    >> (I think anyways, it is still trying to display the result)
    >>
    >> So I am just wondering how long an integer can be with 400 megabytes of
    >> memory.

    >
    > I guess the best way would be a binary search for the proper value of
    > the integer. You already have an upper (c**d) and a lower (c**3) bound
    > for your search.
    >
    >> each integer takes up a byte right?

    >
    > That depends on the size of the integer, doesn't it?
    >
    >> If I have 400 megabytes that would mean I could have a long integer
    >> with up to 419,430,400,000 integers?

    >
    > Que? An integer is just a whole number without fraction. What are you
    > talking about?


    He's talking about decimal digits. Each decimal digit takes up
    3.322 bits. A byte can hold about 2.4 digits. 400MB should be
    able to hold an integer with about 1,010,000,000 decimal
    digits.

    --
    Grant Edwards
     
    Grant Edwards, Jun 18, 2006
    #4
  5. nate

    Guest

    nate wrote:
    > Hey everyone,
    >
    > I am trying to figure out what is the largest integer I can. Lets say
    > for 400 megabytes of memory at my disposal.
    >
    > I have tried a few things
    > c = 2**1000000
    > d = 2**2000000
    > print c**d
    >
    > Obviously I didn't have enough memory for that, but I was able to c**3.
    > (I think anyways, it is still trying to display the result)


    Don't print, takes too long. Do e=c**3.

    >
    > So I am just wondering how long an integer can be with 400 megabytes of
    > memory.
    >
    > I guess this is a question of logic?
    > each integer takes up a byte right? If I have 400 megabytes that would
    > mean I could have a long integer with up to 419,430,400,000 integers?
    >
    > Really I am not sure on this one and that is why I am asking. Because it
    > is just bugging me I am not sure how it works...
    >
    > I know this probably seems trivial and just a stupid question, but I
    > find this type of stuff interesting...


    Using gmpy (and I don't know if it stores large ints different
    from Python ints) and only 192M on my laptop, I can get
    to billion bit numbers, but not much larger. Switching to
    Python ints ran out of memory trying gen 11. It also ran out
    of memory trying to calculate gen 10, which gmpy was able
    to do successfully, so maybe gmpy is better for such things:

    Closed form: Type12MH(k,i)
    Find ith, kth Generation Type [1,2] Mersenne Hailstone
    using the closed form equation

    2**(6*((i-1)*9**(k-1)+(9**(k-1)-1)/2+1)-1)-1

    2**5-1 generation: 1
    2**29-1 generation: 2
    2**245-1 generation: 3
    2**2189-1 generation: 4
    2**19685-1 generation: 5
    2**177149-1 generation: 6
    2**1594325-1 generation: 7
    2**14348909-1 generation: 8
    2**129140165-1 generation: 9
    2**1162261469-1 generation:10

    Traceback (most recent call last):
    File "C:\python24\user\user_home\gmpy ver 1.01\MHtest.py", line 41,
    in -toplevel-
    a = Type12MH(k,1)
    File "C:\python24\lib\collatz_functions.py", line 595, in Type12MH
    return TWO**(SIX*a - ONE) - ONE
    ValueError: mpz.pow outrageous exponent


    >>>
    >>> i=1
    >>> k=11
    >>> a = 2**(6*((i-1)*9**(k-1)+(9**(k-1)-1)/2+1)-1)-1


    Traceback (most recent call last):
    File "<pyshell#3>", line 1, in -toplevel-
    a = 2**(6*((i-1)*9**(k-1)+(9**(k-1)-1)/2+1)-1)-1
    MemoryError
     
    , Jun 18, 2006
    #5
  6. On 2006-06-18, Grant Edwards <> wrote:

    >> Que? An integer is just a whole number without fraction. What are you
    >> talking about?

    >
    > He's talking about decimal digits. Each decimal digit takes up
    > 3.322 bits. A byte can hold about 2.4 digits. 400MB should be
    > able to hold an integer with about 1,010,000,000 decimal
    > digits.


    Oops. The real answer is 15/16 of that. I didn't realize that
    the integer representation only uses 15 of 16 bits.

    --
    Grant Edwards
     
    Grant Edwards, Jun 18, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jacky Kwok
    Replies:
    2
    Views:
    3,642
    Mark1969
    Jun 24, 2005
  2. =?Utf-8?B?Y21heQ==?=
    Replies:
    8
    Views:
    32,302
    SilentSojourner
    Apr 2, 2012
  3. Chris Hayes
    Replies:
    8
    Views:
    9,511
    DDaanV
    Oct 21, 2010
  4. Chris Hayes
    Replies:
    0
    Views:
    690
    Chris Hayes
    Jul 27, 2005
  5. phanhuyich
    Replies:
    4
    Views:
    324
Loading...

Share This Page