Mnożenie dużych liczb

0

Witam.

Mam problem. Piszę program, którego zadaniem jest mnożenie dwóch dużych liczb podanych na wejściu. Wszystko działa dobrze do pewnych danych, dalej wyniki się sypią. Nie bardzo wiem gdzie zawiniłem. Będę wdzięczny za wskazówki.

Kompilacja:
cc -ansi -Wall main.c

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

int main()
{
    size_t  r1 = 1,         /* dlugosc pierwszej liczby */
            r2 = 1,         /* dlugosc drugiej liczby */
            r3 = 1;         /* dlugosc wyniku */

    short   *l1, *l2, *out, /* tablice przechowujace liczby i wynik */
            T,              /* ilosc zestawow */
            znak = 0;

    char c;                 /* wczytywany znak */

    unsigned i, k;          /* zmienne pomocnicze do sterowania petlami */

    scanf("%hi\n", &T);

    while(T--) {
    /* allokacja pamieci dla tablic l1 i l2 */
        l1 = (short *) malloc(r1);
        l2 = (short *) malloc(r2);

    /* wczytywanie liczb l1, l2 do tablic dynamicznych */
        do {
            c = getchar();

            l1[r1-1] = c-48;
            l1 = (short *) realloc(l1, (++r1) * sizeof(short));
        } while(c != ' ');

        do {
            c = getchar();

            l2[r2-1] = c-48;
            l2 = (short *) realloc(l2, (++r2) * sizeof(short));
        } while(c != '\n');

    /* pomnozenie l1 przez l2 */
        out = (short *) malloc(r3);

        for(i=0 ; i<r1-2 ; i++) {
            for(k=0 ; k<r2-2 ; k++) {
                out[i+k] += l1[i] * l2[k];

                if(i+k >= r3) {
                    out = (short *) realloc(out, (++r3) * sizeof(short *));
                }
            }
        }

    /* przepisywanie dziesiatek jezeli istnieja */
        for(i=r3-1 ; i>=1 ; i--) {
            switch(i) {
                case 0: printf("%hi", out[i]); break;
                default: out[i-1] += out[i] / 10; break;
            }
            out[i] %=10;
        }

    /* wyswietlenie wyniku */
        if(out[r3-1] != 0) {
            for(i=0 ; i<r3 ; i++) {
                printf("%hi", out[i]);
            }
        } else {
            putchar('0');
        }
        putchar('\n');

    /* zresetowanie wartosci zmiennych dla nastepnego zestawu */
        r1 = 1;
        r2 = 1;
        r3 = 1;
        znak = 0;
        free(l1);
        free(l2);
        free(out);
    }

    return 0;
}
0

używaj funkcji a nie wpychaj wszystko do main!
Czy nie lepiej alokować duża tablicę i użyć gets?
Gdzie masz zerowanie tablicy z wynikiem? Dodajesz tam wartość do nieokreślonej wartości!

0

To było pisane na szybko, wszystko pójdzie do osobnych plików main.c lib.c lib.h. Zeruje na końcu wszystkie tablice. Przeniesienie też jest, przyjrzyj się. Deklarowanie "dużej" tablicy to ostateczność....

0

Fakt przeniesienie jest, ale w dziwnym miejscu.
Zerowanie na końcu nie ma sensu, chodzi o to, że powinieneś zerować na początku tablicę out bo w tej chwili w tej tablicy masz śmieci i dodajesz do tych śmieci wynik mnożenia.

0

Mylisz się. Sprawdziłem, tablica jest wypełniona zerami. Poza tym dla małych wartości wejściowych (np 1234567890123 1234567890) wszystko gra i pokazuje prawidłowy wynik.

0

Może przeczytasz pierwsze 4 wierzy:
http://www.cplusplus.com/reference/clibrary/cstdlib/malloc/

0

Tablica out jest wypełniona zerami bez potrzeby jej czyszczenia (sprawdziłem ręcznie) a w pozostałych nie korzystam z komórek, którym nie przypisuje żadnej wartości. Program działa dla dużych danych wejściowych (np. po 15 cyfr w każdej liczbie) natomiast przestaje działać dla ogromnych danych (np. po 40 cyfr).... Proponuje po prostu skompilować kod i zobaczyć jakieś dane przykładowe, np:

5
10 100
44 12391
123456789012345 12345678643
1232131231231231231 23123123123123123
44444444444444444444444444444444444444444444444444444444444444444444444444444444 11111111111111112222222222222222222222222222222222222222222
0

Nie do tematu, ale masz
out = (short ) realloc(out, (++r3) sizeof(short ));
a powinno być
out = (short
) realloc(out, (++r3) * sizeof(short));

0

Tablica out nie będzie wypełniona zerami zawsze, owszem może tak się przypadkiem okazać.
Poczytaj na temat malloc i realloc.

0

najwyraźniej nudzi mi się:

#define DefaultSize 256

struct BigInt {
     int digitCount; // ile jest znaczących cyfr
     int maxDigitCount; // ile można zmieścić cyfr
     unsigned char digits[1]; // tu jest małe oszustwo, ale będzie działać
};

BigInt *BigIntAlloc(int digitCount = DefaultSize)
{
    BigInt * result = (BigInt *) malloc(sizeof(BigInt)+sizeof(unsigned char)*(digitCount-1));
    if (result) {
        result->digitCount = 0;
        result->maxDigitCount = digitCount;
        memset(result->digits, 0, sizeof(unsigned char)*digitCount);
    }
    return result;
}

BigInt *BigIntResize(BigInt *number, int newMaxDigits)
{
    assert(number);
    if (number->maxDigitCount == newMaxDigits)
        return number;
    if (number->digitCount>newMaxDigits) {
        number->digitCount = newMaxDigits;
    }
    number = (BigInt *)realloc(number, sizeof(BigInt)+sizeof(unsigned char)*(newMaxDigits-1));
    if (number->maxDigitCount<newMaxDigits) {
         memset(result->digits+number->maxDigitCount, 0, sizeof(unsigned char)*(newMaxDigits - number->maxDigitCount));
    }
    number->maxDigitCount = newMaxDigits;
    return number;
}

BigInt *BigIntMul(BigInt *a, BigInt *b)
{
     maxDigits = a->digitCount + b->digitCount;
     BigInt *result = BigIntAlloc(maxDigits);
     assert(result);

     result->digitCount = maxDigits;
     for(int i=a->digitCount-1; i>=0; --i) {
         int carry = 0;
         for(int j=b->digitCount-1; j>=0; --j) {
             carry = b->digits[j] * a->digits[i] + result->digits[1+i+j] + carry;
             result->digits[1+i+j] = carry%10;
             carry = carry/10;
         }
         assert(result->digits[i]==0 && carry<10);
         result->digits[i] = carry;
     }
     // BigIntRemoveLeadingZeros(result);
     return result;
}

void BigIntRemoveLeadingZeros(BigInt *number)
{
     ...
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0