How Are Unlimited Precision Integers Accomplished?

[Jeff Epler]

On Fri, May 24, 2002 at 03:00:32PM -0400, Michael Chermside wrote:
> A.M. Kuchling writes:
> >To really break things, I think this should really be something like:
> >
> >>>>exp = 2**31L - 1
> >>>>exp
> >2147483647L
> >>>>exp = exp * 15
> >>>>exp
> >32212254705L
> >>>>1 << exp
> >Traceback (most recent call last):
> >  File "<stdin>", line 1, in ?
> >OverflowError: long int too large to convert to int
> 
> Yes, but that's just because << is defined to take only an int on the 
> right-hand-side, not a number. It's not a limit to the size of a Long.
> 
> >Also note that Python can't print the value of your 'big' variable; it
> >gets a MemoryError.
> 
> Yes, I noticed that. But I can still do arithmatic with it.
> 
> Now it's no big deal if Longs are actually limited to some absurdly big 
> value rather than being of truely unlimited size so long as you are 
> running on a machine with infinite memory. But what I don't get is why 
> they AREN'T limited (or appear not to be) given the way they are coded.

You computed a number with (2**31 - 1) + 15 bits, not (2**31 -
1) * 15 bits.  Your second shift was incorrect.  Try computing
math.log(big)/math.log(2) to find the actual number of bits in your
'big' result.

I think that this loop would compute the first long that cannot be
represented:
    i = 1L
    exp = 2**31L - 1
    for j in range(15):
	i <<= exp

Once you tie the size of the machine's memory (eg 32 bit address space)
with the size of its 'long' (eg 32 bits) you realize that a Python long
with (2**31-1) bits would occupy (2**32-2) bytes, and, well, you won't
have much room left for the python interpreter.  I don't recall from your
original snippet whether the type used to store the length was an int or
a long, but in any case a tweak to use "long" would let Python Longs take
up the whole address space on any LP64 machine (64-bit longs and pointers)

Jeff