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

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!).

Goblet

What are maximum arguments (100 or more?) and how much time should it take to calculate the answers? – Neckcloth

The problem is different but I have to calculate 2^10000 and 100! to solve. Time limit is 1 second and memory limit is 256mb. I can translate the problem if you're interested. There may be another solution but it's written in the problem text that answer is larger than 64bit. – Goblet

possible duplicate of Unsigned Long Long Won't Go Beyond The 93th Fibonacci Number? – Clearcut

Constraints are quite small. So, you can do the exponation by squaring as explained below and find the factorial just consequently multiplying by 1, 2, ..., 100. If you store numbers digit-wise, then everything you need is multiplication of your long number by int and multiplication of two numbers. You can see the code in my answer. – Neckcloth

Answer 1

For pow with integers, exponentiation by squaring

Cacciatore

For 2^100, left-shift with carry is a smarter choice. Printing the result is the hard part... – Sturdy

Base two is certainly a special case! – Cacciatore

@larsmans can you give me examples or links about calculating powers in base-2 and left-shift method? – Goblet

Left-shift by 1 means multiply by two. Left-shift by n means multiply by 2^n. 2^100 is just a uint64_t with bit 36 set followed by a uint64_t that is 0. – Sturdy

@larsmans, thanks, I have no idea about uint64_t but I think shifting or exponentiation by squaring method will work.. – Goblet

storing data in uint64_t is a bad idea because you will not be able to control any overflows and operate such numbers. – Neckcloth

Answer 2

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

Ulcerate

thanks, I think libraries like GPG is too advanced for me but I'll give it a chance. – Goblet

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.

Siloxane

Answer 4

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

Wein

It's a programming contest so I have to write my solution(I can't use gmplib). What do you mean by dihotomic algorithm? I looked to wikipedia and I found Dichotomic search. – Goblet

in the next answer Doug Currie gave link en.wikipedia.org/wiki/Exponentiation_by_squaring and proper name of this algorithm – Wein

Answer 5

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.

Phenetidine

Answer 6

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

Neckcloth

+1, but you do realise that "number of digits and array of digits of this number." is not just for programming contests... that's how GMP stores numbers too. – Kimon

Of course, it is a widespread method. But if I'm not mistaken, GMP stores numbers in a base that is a power of 2. So, memory usage and speed are improved but input and output in the decimal format become compicated. Here, instead the base of 10 is used which makes the output very simple. – Neckcloth

Answer 7

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)

Prettypretty