How Are Unlimited Precision Integers Accomplished?

[Michael Chermside]

I wrote:
 > Can someone elaborate with a simple summary of the data structure that
 > is used [for Longs]?

Tim writes:
 > See include/longintrepr.h

Well, I *did* look, and here's the relevent part of what I saw:

|  typedef unsigned short digit;
|  #define SHIFT    15
|  #define BASE     ((digit)1 << SHIFT)
|  /* Long integer representation.
|     The absolute value of a number is equal to
|         SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i)
|     Negative numbers are represented with ob_size < 0;
|     zero is represented by ob_size == 0.
|     In a normalized number, ob_digit[abs(ob_size)-1] (the most
|     significant
|     digit) is never zero.  Also, in all cases, for all valid i,
|         0 <= ob_digit[i] <= MASK.
|     The allocation function takes care of allocating extra memory
|     so that ob_digit[0] ... ob_digit[abs(ob_size)-1] are actually
|     available. */
|
|  struct _longobject {
|      PyObject_HEAD
|      int ob_size;
|      digit ob_digit[1];
|  };


"Aha!" I sez to myself, they aren't REALLY of unlimited precision, just 
REALLY big precision. They're stored as a number in base BASE (base 
2**15), with a maximum of MAXINT digits. So the largest possible Long
should (I sez to myself) be:

         2**( 15 * (2**MAXINT) ) - 1

Well... I'd like to see THAT! So I tries it out for myself by starting 
up Python and typing the following (actually, it took me a couple of 
tries to figure out how to do it without crashing things):

Python 2.2.1 (#34, Apr  9 2002, 19:34:33) [MSC 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
 >>> big = 1L << (2**31 - 1)
 >>> big <<= 15
 >>> big += 1
 >>> big <<= 45
 >>>

As you can see, it should have overflowed (I thought) in line 3. And it 
CERTAINLY shouldn't have been able to do line 4! It is, of course, 
possible that ob_size is silently overflowing, but I did some simple 
experiments designed to test that and they all seemed work.

So how ARE *really* big numbers stored?

-- Michael Chermside