the need for 64 bits

[Mensanator]

I routinely use large numbers in my Collatz Conjecture work.

Really large. As in a quarter million bits. You wouldn't think
that the processor would make all that much difference. But
using the number is a doddle. The real trick is getting there.

There is a limitation that few encounter. In an exponential, the
exponent is limited to 32 bits, else you get an "outrageous
exponent" error. But I assume that was due to integer size,
that if you have 64 bit integers, the limit of the exponent
ought to also be 64 bits.

With my new MacBook replacing my old Windows laptop,
I can try this.

Using this function (which grows really large, really quick)...

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

Type12MH(k,i)
k: generation
i: member of generation
returns Hailstone (a)
"""
ONE = gmpy.mpz(1)
TWO = gmpy.mpz(2)
SIX = gmpy.mpz(6)
NIN = gmpy.mpz(9)
if (k<1) or (i<1): return 0
i = gmpy.mpz(i)
k = gmpy.mpz(k)
# a = (i-1)*9**(k-1) + (9**(k-1) - 1)//2 + 1
# return 2**(6*a - 1) - 1
a = (i-ONE)*NIN**(k-ONE) + (NIN**(k-ONE) - ONE)//TWO + ONE
return TWO**(SIX*a - ONE) - ONE


i: 1 bits: 5 decimals: 2
i: 2 bits: 29 decimals: 9
i: 3 bits: 245 decimals: 74
i: 4 bits: 2,189 decimals: 659
i: 5 bits: 19,685 decimals: 5,926
i: 6 bits: 177,149 decimals: 53,328
i: 7 bits: 1,594,325 decimals: 479,940
i: 8 bits: 14,348,909 decimals: 4,319,453
i: 9 bits: 129,140,165 decimals: 38,875,064
i: 10 bits: 1,162,261,469 decimals: 349,875,565

… my Windows/32-bit machine can't get past generation 10 without
getting "outrageous exponent".

But with a 64-bit processor, that limitation no longer stops me.

i: 11 bits: 10,460,353,205 decimals: 3,148,880,080
i: 12 bits: 94,143,178,829 decimals: 28,339,920,715

Wow! 94 billion bits! 28 billion decimal digits!

Of course, once one wall falls, you get to go up against the next
one.
For generation 13, I get:

gmp: overflow in mpz type
Abort trap

Hmm, not sure what "overflow" means in this context, but I suspect
it ran out of memory, I probably should have gotten the MacBook Pro
with 8 GB of ram. But then, maybe it wouldn't help.

Regardless, my window of research has gotten slightly larger.

 

[Mark Dickinson]

But with a 64-bit processor, that limitation no longer stops me.

i: 11   bits: 10,460,353,205   decimals:  3,148,880,080
i: 12   bits: 94,143,178,829   decimals: 28,339,920,715

Wow! 94 billion bits! 28 billion decimal digits!

Of course, once one wall falls, you get to go up against the next
one.
For generation 13, I get:

gmp: overflow in mpz type
Abort trap

Hmm, not sure what "overflow" means in this context, but I suspect
it ran out of memory, I probably should have gotten the MacBook Pro
with 8 GB of ram. But then, maybe it wouldn't help.

I don't think this was due to running out of memory: it looks like
gmp uses the 'int' C type to count the number of limbs in an mpz,
which would make the maximum number of bits 2**31 * 64, or around 137
billion, on a typical 64-bit machine. Maybe there's a configure
option to change this?

For Python longs, the number of limbs is stored as a signed size_t
type, so on a 64-bit machine memory really is the only limitation.

 

[casevh]

I don't think this was due to running out of memory:  it looks like
gmp uses the 'int' C type to count the number of limbs in an mpz,
which would make the maximum number of bits 2**31 * 64, or around 137
billion, on a typical 64-bit machine.  Maybe there's a configure
option to change this?

For Python longs, the number of limbs is stored as a signed size_t
type, so on a 64-bit machine memory really is the only limitation.

Based on comments on the GMP website, the maximum number of bits on a
64-bit platform is limited to 2**37 or 41 billion decimal digits. A
number this size requires 16GB of RAM. A future version of GMP (5.x)
is supposed to remove that limit and also work well with disk-based
storage.

casevh

 

[Mensanator]

Based on comments on the GMP website, the maximum number of bits on a
64-bit platform is limited to 2**37 or 41 billion decimal digits.

I guess that eliminates ever finding generation 13.

And I haven't checked the 12th generation number yet.
I can calculate it, but I don't if I can actually run it
through the Collatz process. Being a Mersenne Number, the
excursion (maximum value reached in the sequence) will be
about 1.585 times as many bits as the starting number.
If that fails with genertaion 12, then finding generation
13 is moot.

A number this size requires 16GB of RAM.

Ah, the 8 GB Mac wouldn't have helped. Glad I didn't spend the extra
$1000.

A future version of GMP (5.x)
is supposed to remove that limit and also work well with disk-based
storage.

Something to look forward to.

Thanks, guys.

 

[Steven D'Aprano]

I routinely use large numbers in my Collatz Conjecture work.

Really large. As in a quarter million bits.

That's not large. *THIS* is a large number:

http://en.wikipedia.org/wiki/Graham's_number

Unless you need special notation merely to describe how to generate the
number, it's not a large number.

 

[Mensanator]

That's not large.

Perhaps not in the absolute sense. But it's large compared to
32-bit or 64-bit integers. Probably most people's applications
don't come anywhere near the limit of what can be represented
in long integers. Numbers near such a limit are "large" for
practical purposes.

*THIS* is a large number:

http://en.wikipedia.org/wiki/Graham's_number

Right. And if I were ice fishing on the retention pond near
my house and someone came up and said "You know, blue whales
can achieve a length of up to 108 ft.", he would leave in a
basket.

Unless you need special notation merely to describe how to generate the
number, it's not a large number.

I'm only interested in numbers I can represent in memory and
run through the Collatz process. Interesting as they are, these
truly "large" numbers are of no use to me.

 

[Steven D'Aprano]

And if I were ice fishing on the retention pond near my house and
someone came up and said "You know, blue whales can achieve a length of
up to 108 ft.", he would leave in a basket.

Come and see the violence inherent in the system! Help, help! I'm being
repressed!


Bringing it back to Python'ly yrs,

 

[Mensanator]

Come and see the violence inherent in the system! Help, help! I'm being
repressed!

Bringing it back to Python'ly yrs,

 

[Roy Smith]

That's not large. *THIS* is a large number:

http://en.wikipedia.org/wiki/Graham's_number

Unless you need special notation merely to describe how to generate the
number, it's not a large number.

And then, after 'e was done nailing my head to the floor, he said,
"Consider an n-dimensional hypercube". It was at that point that I knew he
was talking about a really big number.

 

[Mensanator]

And then, after 'e was done nailing my head to the floor, he said,
"Consider an n-dimensional hypercube".  It was at that point that I knew he
was talking about a really big number.

I remember it more like:

And then, after 'e was done nailing my head to the floor, he said,
"Consider an n-dimensional hypercube, Eric". It was at that point
that I knew he
was talking about a really big number, so I said "My names not Eric."

 

[Aahz]

Ah, the 8 GB Mac wouldn't have helped. Glad I didn't spend the extra
$1000.

It's almost always cheaper to buy your Mac and then upgrade the RAM
separately.

 

[Cameron Simpson]

| In article <[email protected]>,
| >Ah, the 8 GB Mac wouldn't have helped. Glad I didn't spend the extra
| >$1000.
|
| It's almost always cheaper to buy your Mac and then upgrade the RAM
| separately.

Unless it's a Macbook Air. Then you're stuck with 2GB max:-(
At least I didn't pay for it It's a nice machine in many respects.
--
Cameron Simpson <[email protected]> DoD#743
http://www.cskk.ezoshosting.com/cs/

I am a Bear of Very Little Brain and long words Bother Me.
- Winnie-the-Pooh

 

[Aahz]

| In article <[email protected]>,
| >Ah, the 8 GB Mac wouldn't have helped. Glad I didn't spend the extra
| >$1000.
|
| It's almost always cheaper to buy your Mac and then upgrade the RAM
| separately.

Unless it's a Macbook Air. Then you're stuck with 2GB max:-(

No VM for you! I'm already unhappy with VM performance on my 4GB
machine; I can't wait for the weekend to install 8GB instead.