maximum integer length?

[nate]

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

[casevh]

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

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

[Grant Edwards]

On 2006-06-18, Sybren Stuvel <sy*******@YOUR thirdtower.com. imagination> 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
gr****@visi.com

[mensanator]

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\us er\user_home\gm py ver 1.01\MHtest.py" , line 41,
in -toplevel-
a = Type12MH(k,1)
File "C:\python24\li b\collatz_funct ions.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

[Grant Edwards]

On 2006-06-18, Grant Edwards <gr****@visi.co m> 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
gr****@visi.com