Velocity Reviews > maximum integer length?

# maximum integer length?

nate
Guest
Posts: n/a

 06-18-2006
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...

Sybren Stuvel
Guest
Posts: n/a

 06-18-2006
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

> 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

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

casevh@comcast.net
Guest
Posts: n/a

 06-18-2006

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

Grant Edwards
Guest
Posts: n/a

 06-18-2006
On 2006-06-18, Sybren Stuvel <(E-Mail Removed)> 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
>
>> 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

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
http://www.velocityreviews.com/forums/(E-Mail Removed)

mensanator@aol.com
Guest
Posts: n/a

 06-18-2006
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

Grant Edwards
Guest
Posts: n/a

 06-18-2006
On 2006-06-18, Grant Edwards <(E-Mail Removed)> wrote:

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

>
> 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
(E-Mail Removed)