С умножением больших чисел

Question

Следующая программа на C умножает большие числа в виде строк.Это работает хорошо с положительными числами, но с большими числами используется слишком много памяти.Как я могу улучшить его, чтобы использовать меньше памяти?

Моя программа:

char *strrev(char *str) {
        char *p1, *p2;

        if(!str || !*str)
            return str;

        for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2) {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
        }
        return str;
    }

    char* addNumbers(char* c1, char* c2) {

        char *m1;
        char *m2;


        if (strlen(c1) >= strlen(c2)) {
            m1 = malloc(sizeof(c1));
            m2 = malloc(sizeof(c2));
            strcpy(m1, c1);
            strcpy(m2, c2);
        } else {
            m1 = malloc(sizeof(c2));
            m2 = malloc(sizeof(c1));
            strcpy(m1, c2);
            strcpy(m2, c1);
        }

        strrev(m1);
        strrev(m2);

        int lm1 = strlen(m1);
        int lm2 = strlen(m2);

        //char *w = malloc(1000000);
        char its;
        int jd = 0;
        for (int l = 0; l < lm1; l++) {
            int w1 = strToInt(m1[l]);
            int w2;
            if (l < strlen(m2)) {
                w2 = strToInt(m2[l]);
            } else {
                w2 = 0;
            }
            int w3 = w1 + w2 + jd;
            if (w3 > 9) {
                jd = 1;
                w3 = w3 % 10;
            } else {
                jd = 0;
            }
            its = w3 + 48;
            m1[l] = its;
        }
        if (jd > 0) {
            char its2[12];
            sprintf(its2, "%d", jd);
            strcat(m1, its2);
        }

        return strrev(m1);
    }

    int main(int argc, char* argv[]) {
        char *c1;
        char *c2;
        if (strlen(argv[1]) > strlen(argv[2])) {
            c1 = malloc(sizeof(argv[1]));
            c2 = malloc(sizeof(argv[2]));
            strcpy(c1, argv[1]);
            strcpy(c2, argv[2]);
        } else {
            c1 = malloc(sizeof(argv[2]));
            c2 = malloc(sizeof(argv[1]));
            strcpy(c1, argv[2]);
            strcpy(c2, argv[1]);
        }
        char counter[sizeof(c2)];
        sprintf(counter, "%d", 0);
        char one[2];
        sprintf(one, "%d", 1);
        char *w = malloc(100);
        while (strcmp(counter, c2) != 0) {
            strcpy(counter, addNumbers(counter, one));
            strcpy(w, addNumbers(w, c1));
        }
        printf("%s\n%s\n", c1, c2);
        free(c1);
        free(c2);
        printf("Result: %s,%ld\n\n", w,sizeof(w));
        free(w);
    }

Я знаю, что существуют лучшие алгоритмы, но я должен использовать функцию addNumbers().

Answer 1

Вы используете много памяти, выделяя ее, но не освобождая ее.Даже если вы освободите его, у вас будет много выделения, копирования и освобождения.

Вместо того, чтобы делать это, вам будет лучше выделить место для результата, а затем накапливать в том же самом результате, пока ваш продукт не будет завершен.

Поскольку ваши входные данные могут быть константными строками, вы должны стремиться к тому, чтобы только один malloc в вашей функции main () выделил место для результата, а остальное модифицирует это на месте.Если вам нужно изменить входные строки, вам понадобится еще пара выделений, но это все.Я не буду делать сложения в строках, но использую массив uint_8 и выполняю преобразование strToInt один раз для каждого входа в начале, а не много, много раз в цикле.

Answer 2

Как я могу улучшить его, чтобы сэкономить память?
Как написано, ваше сообщение включает несколько экземпляров вызовов на calloc(), каждый из которых создает кучную память, но ни одна из созданной памяти не освобождается, что приводит к утечке памяти.Как минимум, ответом на ваш вопрос будет просто сделать соответствующий звонок на free() для каждого звонка на malloc().

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

Ниже приведено упрощение функции addNumbers при сохранении ее первоначального прототипа.Как просили в комментариях, он использует ANSI C без дополнительных библиотек.Помимо прочего, он также имеет встроенную реверсивность строк (исключая функцию strrev()), использует только один экземпляр динамически выделяемой памяти и не пропускает ни одной.Раскомментируя функции scanf() и добавляя входные данные командной строки, его можно легко преобразовать в соответствии с вашими потребностями.

char* addNumbers(char* s1, char* s2) ;

int main(int argc, char *argv[])
{
    char s1[101] = {"150353265326"};
    char s2[101] = {"22055653351"};

    // Expect: 3316139500221184007426

    //scanf(" %s",s1);
    //scanf(" %s",s2);
    char * result = addNumbers(s1, s2); 


    printf("%s\n", result);

    free(result);

    return 0;
}


char* addNumbers(char* s1, char* s2) 
{
    int i=0, j=0, tmp;

    int l1 = strlen(s1);
    int l2 = strlen(s2);
    int a[100]={0},b[100]={0};
    int ans[200] = {0};
    char *result = calloc(l1+l2+1, 1);

    for(i = l1-1,j=0;i>=0;i--,j++)
    {
        a[j] = s1[i]-'0';
    }
    for(i = l2-1,j=0;i>=0;i--,j++)
    {
        b[j] = s2[i]-'0';
    }
    for(i = 0;i < l2;i++)
    {
        for(j = 0;j < l1;j++)
        {
            ans[i+j] += b[i]*a[j];
        }
    }
    for(i = 0;i < l1+l2;i++)
    {
        tmp = ans[i]/10;
        ans[i] = ans[i]%10;
        ans[i+1] = ans[i+1] + tmp;
    }
    for(i = l1+l2; i>= 0;i--)
    {
        if(ans[i] > 0)
            break;
    }

    for(j=i;j >= 0;j--)
    {
        result[i-j] = (char)('0' + ans[j]);
    }
    return result;
}

Протестировано с использованием входов командной строки:

Примечание. Эта адаптация дает кредит этойреализация.