Implementing Basic Arithmetic for Large Integers: Introduction: Representation

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Representation

We ﬁrst need a way to represent a large integer in the computer. We can learn from the well-known Positional Numeral System, of which the commonly used Decimal Numeral System is an example. Each large integer can be represented as a sequence of digits where each digit itself should ﬁt within a hardware provided integer. We will choose a base B for our numeral system, and each digit can have value in range 0 to B − 1.

In our implementation, we will assume 64-bit computer system, where types “int” and “long” in C language use 32-bits and 64-bits respectively; but this may vary across platforms. Each digit will be stored as a 32-bit hardware integer, allowing us to choose base B as large as 2³². The sequence of digits will be stored as an array of 32-bit integers, which are available as type “unsigned int” in C. The following structure represents a large integer:

#define B (0x100000000)  /* 2^32 */
#define WIDTH (200)

typedef unsigned int uint;
typedef unsigned long ulong;

typedef struct bigint
{
  uint digits[WIDTH];
  int  msd;           /* index of the MSD in the "digits" array */
} bigint;

For simplicity, we have chosen to use a ﬁxed-width array, but this can be improved for memory-eﬃciency. The least-signiﬁcant-digit (LSD) and most-signiﬁcant-digit (MSD) are digits[WIDTH − 1] and digits[msd] respectively. The value of a bigint is given by:

WIDTH −1 ∑ WIDTH −1−i digits[i]⋅B i=msd

Throughout our implementation, we enforce the condition that digit digits[msd] is not 0. That is, there will be no redundant 0s at the beginning of the digits sequence. We will refer this condition as “no leading zeros”. The only exception is the bigint for representing integer 0 itself; which has msd = WIDTH − 1 and digits[msd] = 0.

[Prev] [Up] [Next]