Arbitrary-Precision Arithmetic with Examples in C

Big-number arithmetic (long arithmetic) is a set of software tools (data structures and algorithms) that make it possible to work with numbers far larger than standard data types allow.

Types of integer big-number arithmetic

Generally speaking, even within competitive-programming problems alone the range of tools is quite large, so let us classify the various types of big-number arithmetic.

Classical big-number arithmetic

The basic idea is that a number is stored as an array of its digits.

Digits can be taken from one numeral system or another; decimal (and its powers, such as ten thousand or a billion) or binary are typically used.

Operations on numbers in this form of big-number arithmetic are performed using the "schoolbook" algorithms for column addition, subtraction, multiplication, and division. However, fast multiplication algorithms are also applicable to them: the Fast Fourier Transform and the Karatsuba algorithm.

Only work with non-negative big numbers is described here. To support negative numbers, you need to introduce and maintain an additional "negativity" flag for the number, or else work in complement codes.

Data structure

We will store big numbers as a vector of numbers , where each element is a single digit of the number.

typedef vector<int> lnum;

To improve efficiency, we will work in a system with base one billion, i.e. each element of the vector contains not one but digits at once:

const int base = 1000*1000*1000;

Digits will be stored in the vector in such an order that the least significant digits come first (i.e. ones, tens, hundreds, and so on).

In addition, all operations will be implemented so that after any of them is performed there are no leading zeros (i.e. superfluous zeros at the start of the number), assuming, of course, that there were no leading zeros before each operation either. It should be noted that in the presented implementation, two representations are correctly supported for the number zero at once: an empty vector of digits, and a vector of digits containing a single element — zero.

Output

The simplest thing is outputting a big number.

First we simply output the very last element of the vector (or if the vector is empty), and then we output all the remaining elements of the vector, padding them with zeros to characters:

printf ("%d", a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i)
	printf ("%09d", a[i]);

(there is a subtle point here: don't forget to write the type cast , since otherwise the number will be unsigned, and if , then overflow will occur during subtraction)

Reading

We read a string into , and then convert it into a vector:

for (int i=(int)s.length(); i>0; i-=9)
	if (i < 9)
		a.push_back (atoi (s.substr (0, i).c_str()));
	else
		a.push_back (atoi (s.substr (i-9, 9).c_str()));

If we use an array of 's instead of , the code becomes even more compact:

for (int i=(int)strlen(s); i>0; i-=9) {
	s[i] = 0;
	a.push_back (atoi (i>=9 ? s+i-9 : s));
}

If the input number can already contain leading zeros, they can be removed after reading as follows:

while (a.size() > 1 && a.back() == 0)
	a.pop_back();

Addition

Adds the number to the number and stores the result in :

int carry = 0;
for (size_t i=0; i(a.size(),b.size()) || carry; ++i) {
	if (i == a.size())
		a.push_back (0);
	a[i] += carry + (i < b.size() ? b[i] : 0);
	carry = a[i] >= base;
	if (carry)  a[i] -= base;
}

Subtraction

Subtracts the number from the number () and stores the result in :

int carry = 0;
for (size_t i=0; i() || carry; ++i) {
	a[i] -= carry + (i < b.size() ? b[i] : 0);
	carry = a[i] < 0;
	if (carry)  a[i] += base;
}
while (a.size() > 1 && a.back() == 0)
	a.pop_back();

Here, after performing the subtraction, we remove the leading zeros in order to maintain the invariant that none are present.

Multiplying a big number by a short one

Multiplies the big number by the short number () and stores the result in :

int carry = 0;
for (size_t i=0; i() || carry; ++i) {
	if (i == a.size())
		a.push_back (0);
	long long cur = carry + a[i] * 1ll * b;
	a[i] = int (cur % base);
	carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
	a.pop_back();

Here, after performing the division, we remove the leading zeros in order to maintain the invariant that none are present.

(Note: a way of additional optimization. If speed is extremely important, you can try replacing two divisions with one: compute only the integer part of the division (in the code this is the variable ), and then compute the remainder of the division from it (using a single multiplication operation). As a rule, this technique speeds up the code, although not very significantly.)

Multiplying two long numbers

Multiplies by and stores the result in :

lnum c (a.size()+b.size());
for (size_t i=0; i(); ++i)
	for (int j=0, carry=0; j<(int)b.size() || carry; ++j) {
		long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
		c[i+j] = int (cur % base);
		carry = int (cur / base);
	}
while (c.size() > 1 && c.back() == 0)
	c.pop_back();

Dividing a long number by a short one

Divides the long number by the short number (), stores the quotient in , and the remainder in :

int carry = 0;
for (int i=(int)a.size()-1; i>=0; --i) {
	long long cur = a[i] + carry * 1ll * base;
	a[i] = int (cur / b);
	carry = int (cur % b);
}
while (a.size() > 1 && a.back() == 0)
	a.pop_back();

Long arithmetic in factorized form

The idea here is to store not the number itself, but its factorization, i.e., the powers of each prime included in it.

This method is also quite simple to implement, and it makes multiplication and division operations very easy to perform, but addition or subtraction cannot be performed. On the other hand, this method saves significantly more memory compared to the "classical" approach, and allows multiplication and division to be performed significantly (asymptotically) faster.

This method is often used when it is necessary to perform division modulo a composite number: in that case, it is enough to store the number as powers of the prime divisors of that modulus, plus one more number — the remainder modulo that same modulus.

Long arithmetic using a system of prime moduli (Chinese Remainder Theorem or Garner's scheme)

The essence of the method is that a certain system of moduli is chosen (usually small ones that fit into standard data types), and the number is stored as a vector of the remainders of its division by each of these moduli.

As the Chinese Remainder Theorem states, this is sufficient to uniquely store any number in the range from 0 to the product of these moduli minus one. There is also Garner's Algorithm, which allows this restoration from the modular form into the ordinary, "classical", form of the number.

Thus, this method allows memory to be saved compared with "classical" long arithmetic (although in some cases not as dramatically as the factorization method). Moreover, in modular form addition, subtraction, and multiplication can all be performed very quickly — all in asymptotically the same time, proportional to the number of moduli in the system.

However, all this comes at the cost of a rather laborious conversion of the number from this modular form back to the ordinary form, which, besides considerable time costs, also requires an implementation of "classical" long arithmetic with multiplication.

In addition, performing division of numbers in such a representation using a system of prime moduli is not possible.

Types of fractional long arithmetic

Operations on fractional numbers are encountered much more rarely in olympiad problems, and working with huge fractional numbers is significantly more difficult, so only a specific subset of fractional long arithmetic is found in olympiads.

Long arithmetic in irreducible fractions

The number is represented as an irreducible fraction , where and — are integers. Then all operations on fractional numbers can easily be reduced to operations on the numerators and denominators of these fractions.

Usually, long arithmetic also has to be used to store the numerator and denominator, but in that case its simplest form — "classical" long arithmetic — suffices, although sometimes a built-in 64-bit numeric type is enough.

Separating out the floating-point position into a separate type

Sometimes a problem requires performing calculations with very large or very small numbers, while avoiding overflow. The built-in -byte type , as is well known, allows exponent values in the range , which may sometimes not be enough.

The technique itself is actually very simple — an additional integer variable is introduced to hold the exponent, and after each operation the fractional number is "normalized", i.e., brought back into the interval , by increasing or decreasing the exponent.

When multiplying or dividing two such numbers, their exponents must be added or subtracted, respectively. When adding or subtracting, before performing the operation the numbers must be brought to the same exponent, for which one of them is multiplied by raised to the power of the difference of the exponents.

Finally, it is clear that it is not necessary to choose as the base of the exponent. Given the design of built-in floating-point types, it appears most advantageous to set the base equal to .