How to work on big integers that don't fit into any of language's data structures

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 calcu开发者_JAVA百科late generalized permutation for this X and Y, total += (x+y)! / (x!*y!).

For pow with integers, exponentiation by squaring

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 :)

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.

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

For C something like this would work, or roll your own using int or char arrays, with a spot in the array representing a digit. [1 | 0 | 1] or ['1'|'0'|'1'] for 101, etc.

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--;
    }
};

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)