Как работать с большими целыми числами, которые не вписываются ни в одну из структур данных языка

Question

Я пытаюсь решить предварительные задачи конкурса по программированию, и для двух задач мне нужно вычислить и вывести несколько очень больших целых чисел (например, 100 !, 2 ^ 100).

Мне также нужен быстрый способ для вычисления степеней этих больших целых чисел.

Можете ли вы посоветовать мне некоторые алгоритмы или структуры данных для этого? (Кстати, я прочитал раздел "Интерфейсы и реализации C" арифметики произвольной точности, но это не помогает для pow ())

РЕДАКТИРОВАТЬ: Я думаю, что возведение в степень методом возведения в квадрат и сдвигом битов будет работать на мощность, но мне также нужен быстрый способ для вычисления факториалов для этих целых. Спасибо.

EDIT2: для тех, кто заинтересован;

Найдите самую короткую длину строки битов, которая включает все строки битов с длиной N (извините за мой английский, я приведу пример). N <= 10000 </p>

Например, длина самой короткой битовой строки, которая включает все битовые строки длины 2 (00, 01, 10, 11), равна 5 (11001).

Мое решение для этой проблемы было 2 ^ n + n - 1. (поэтому я должен рассчитать степени 2, я думаю, что я буду использовать сдвиг битов)

Другая проблема заключается в том, что, учитывая 2 длины, выясните, как разными способами вы можете достичь длины N. Например, входное значение равно 10, 2, 3. Затем вы должны достичь 10 с помощью 2 и 3 (например, , 2 + 2 + 2 + 2 + 2, 2 + 2 + 3 + 3, 3 + 2 + 2 + 3, 3 + 3 + 2 + 2 ...). 1 <= N <2 ^ 63. Рассчитаем ответ в моде 1000000007. </p>

Мое решение было: 2x + 3y = N, поэтому x = (N - 3y) / 2. Для y от 0 до 2 * N / 3, если x является целым числом, тогда я должен вычислить обобщенную перестановку для этих X и Y, всего + = (x + y)! / (х! * у!).

Answer 1

Для pow с целыми числами, Возведение в степень в квадрате

Answer 2

Используйте GMP , чтобы справиться с этим. Он имеет встроенную факториальную поддержку и большие возможности и т. Д. Он имеет интерфейс C и C ++, среди прочего. Вам понадобится mpz_t как тип, который содержит очень большие целые числа.

Answer 3

Возможно, вы захотите взглянуть на реализации криптографических программ (особенно GnuPG приходит мне в голову в первую очередь).Причина в том, что криптографические функции также используют очень большие целые числа (так называемые MultiPrecision Integers - MPI).Эти MPI хранятся таким образом, что первые 2 байта сообщают, как размер целого и последние байты хранят значение.

GPG с открытым исходным кодом, просто посмотрите на него:)

Answer 4

Для вычисления степеней используйте дихотомический алгоритм, который использует двоичное представление показателя степени и уменьшает полученное число умножений. Структура данных - это просто массив целых чисел

Answer 5

Базовая математика может умножить любой двойной на двойной ...

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 6

Вы можете сохранить номер в следующем формате: количество цифр и массив цифр этого номера. Это распространенный способ борьбы с большими числами в соревнованиях по программированию.

Вот класс, который обеспечивает хранение чисел и умножение. Можно вводить и выводить цифры, которые тривиальны.

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 7

Для C что-то вроде это сработает, или выкатите свой собственный, используя массивы int или char, с точкой в ​​массиве, представляющей цифру. [1 | 0 | 1] или ['1'|'0'|'1'] для 101 и т. Д.