структура данных для добавления очень больших чисел?

Question

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

Answer 1

Вам понадобится библиотека C, которая реализует арифметику произвольной точности. Есть из чего выбирать. Один из популярных вариантов - GNU Multi-Precision Library .

Answer 2

Я недавно использовал MPFR - вычисления с плавающей точкой с множественной точностью GNU с правильной библиотекой округления. По своей структуре API похож на MAPM, который довольно просто использовать в моем опыте.

Однако, если вы используете только целые числа, вы, вероятно, получите лучшую производительность из библиотеки с множественной точностью, которая имеет отдельные целочисленные типы (например, MAPM), поскольку MPFR выделен для числа с плавающей запятой.

Answer 3

Если вы хотите добавить только целые числа, что может быть в вашем вопросе, то вы можете просто использовать строки и реализовать сложение из одной цифры с помощью двумерной таблицы поиска. Если ваши требования более сложны, то, как другие предложили, вам нужна какая-то библиотека для обработки больших чисел. Используете ли вы одну из существующих библиотек или катите свою собственную, решать только вам.

Answer 4

Помимо использования таких библиотек, как MAPM и MPIR , вы можете попробовать удерживать их в двойном формате (если точность не требуется) или сворачивать собственную реализацию на основе массивов.

Google up на C bignum для альтернатив.

Это, вероятно, хорошее место для начала .

Answer 5

Для добавления бигнума для бедного человека вы можете использовать строки C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *bigadd(const char *a, const char *b) {
    size_t alen = strlen(a);
    size_t blen = strlen(b);
    size_t clen = (alen > blen) ? alen : blen;
    char *c = malloc(clen + 2);
    if (c != NULL) {
        size_t i = clen;
        int carry = 0;
        c[i] = '\0';
        while (i > 0) {
            char digit = (alen ? a[--alen] - '0' : 0) +
                (blen ? b[--blen] - '0' : 0) + carry;
            c[--i] = digit - 10 * (carry = digit > '9');
        }
        if (carry) {
            memmove(c + 1, c, clen + 1);
            c[0] = '1';
        }
    }
    return c;
}

int main(int argc, char *argv[]) {
    const char *a = argc > 1 ? argv[1] : "123456890123456890123456890";
    const char *b = argc > 2 ? argv[2] : "2035864230956204598237409822324";
    char *c = bigadd(a, b);
    printf("%s + %s = %s\n", a, b, c);
    free(c);
    return 0;
}

Answer 6

Я буду использовать STACKS . Числа могут быть сохранены в стеке, если сначала поместить цифру с наивысшим значением, чтобы цифра в одном месте была на вершине стека. Вставьте два стека и добавьте цифры из стеков с переносом, который изначально равен нулю. Вставьте результат в третий стек цифра за цифрой. Повторяйте, пока оба стека не опустеют.