How to work on big integers that don't fit int

Question

I'm trying to solve a programming contest's preliminary problems and for 2 of the problems I have to calculate and print some very big integers(like 100!, 2^100).

I also need a fast way to calculate powers of this big integers.

Can you advice me some algorithms or data structures for this?(btw, I read C Interfaces and Implementations 'arbitrary precision arithmetic' section but it doesn't help for pow())

EDIT: I think exponentiation by squaring method and bit-shifting will work for power but I also need a fast way to calculate factorials for this ints. Thanks.

EDIT2: For those who are interested;

Find the shortest bit string length that includes all bit strings with length N (sorry for my english, I'll give an example). N <= 10000

For example, the shortest bit string length that includes all of bit strings of length 2(00, 01, 10, 11) is 5(11001).

My solution for this problem was 2^n + n - 1. (so I should calculate powers of 2, I think I'll use bit-shifting)

Other problem is, given the 2 lengths, find how in how many different ways you can reach the length N. For example, the input is 10, 2, 3. Then you should reach 10 with 2 and 3(for example, 2+2+2+2+2, 2+2+3+3, 3+2+2+3, 3+3+2+2...). 1 <= N < 2^63. We will calculate the anwser in mod 1000000007.

My solution was, 2x + 3y = N, so x = (N - 3y) / 2 . For y from 0 to 2*N / 3, if x is an integer, then I should calculate generalized permutation for this X and Y, total += (x+y)! / (x!*y!).

Answer 1

For pow with integers, exponentiation by squaring

Answer 2

Basic mathematics can do multiplication of any double with double...

def biginteger(num1, num2):
result = []
lnum1 = len(num1)
lnum2 = len(num2)

k = x = remainder = 0
while len(result) < lnum1:
    result.append(0)
for i in range(lnum1, 0, -1):
    multiplier = int(num1[i - 1])
    for j in range(lnum2, 0, -1):
        temp = (int(num2[j - 1]) * multiplier) + remainder + int(result[k])
        result[k] = str(temp % 10)
        remainder = temp / 10
        k += 1
    result.append(str(remainder))
    if remainder != 0:
        remainder = 0
    x += 1
    k = x

return ''.join([result[i - 1] for i in range(len(result), 0, -1)])

num1 = '37234234234234'
num2 = '43234234234232'
print biginteger(num1, num2)

Answer 3

Use GMP to handle these. It has built in factorial support and large powers etc. It has a C and a C++ interface, among other things. You'll need mpz_t as a type that holds very large integers.

Answer 4

You can store number in the folowing format: number of digits and array of digits of this number. It is a common way to deal with big numbers in programming contests.

Here is a class than provides storing of numbers and multiplication. Input and output of numbers can be added which are trivial.

class huge {
public:
    int size;
    int data[1000];

    friend void mul(const huge &a, int k, huge &c) {
        c.size = a.size;
        int r = 0;
        for (int i = 0; i < a.size; i++) {
            r += a.data[i] * k;
            c.data[i] = r % 10;
            r = r / 10;
        }
        if (r > 0) {
            c.size++;
            c.data[c.size - 1] = r;
        }
        while (c.size > 1 && c.data[c.size - 1] == 0)
            c.size--;
    }

    friend void mul(const huge &a, const huge &b, huge &c) {
        c.size = a.size + b.size;
        memset(c.data, 0, c.size * sizeof(c.data[0]));
        for (int i = 0; i < a.size; i++) {
            int r = 0;
            for (int j = 0; j < b.size; j++) {
                r += a.data[i] * b.data[j] + c.data[i + j];
                c.data[i + j] = r % 10;
                r /= 10;
            }
            if (r > 0)
                c.data[i + b.size] = r;
        }
        while (c.size > 1 && c.data[c.size - 1] == 0)
            c.size--;
    }
};

Answer 5

You might want to take a look in implementations of cryptographic programs (especially GnuPG comes into my mind first). The reason is that cryptographic functions also make use of very large integers (so called MultiPrecision Integers - MPIs). These MPIs are stored in such a way that the very first 2 bytes tell how the size of the integer and the latter bytes store the value.

GPG is open-source, just have a look at it :)

Answer 6

To calculate powers use dihotomic algorithm which uses binary representation of exponent and reduces resulting number of multiplications. Data structure is just an array of integers