Operații cu numere mari în C++ - Toate funcțiile explicate

Există situații în care vrem să memorăm în limbajele de programare precum C++ numere întregi foarte mari (cu sute de cifre, de exemplu), iar în aceste situații, tipuri de date int și long long nu sunt destul de încăpătoare pentru a memora astfel de valori (de pildă, long long reține până la 19 cifre).

Din această nevoie a apărut conceptul de numere mari, adică o modalitate de a reține valori uriașe și de a efectua operații aritmetice cu acestea (precum adunarea, scăderea, înmulțirea, împărțirea, etc.). Vom numi în continuare scalar/număr mic un număr obișnuit, de tip int sau long long.

Operațiile aritmetice sunt ca cele din clasele primare, așadar se pot memora ușor logic, însă le vom și explica în această lecție. Fiecare operație va fi o funcție, pentru a le putea apela unde vrem în program cu ușurință.

Ce este un număr mare și cum se memorează

Un număr mare este defapt un vector de cifre ce reține un număr natural. Mai precis, dacă a[] este un număr mare, salvăm pe poziția a[0] lungimea sa (numărul de cifre ale sale), iar pe pozițiile 1, 2, 3, …, a[0] memorăm cifrele sale în ordine inversă.

Spre exemplu, dacă am vrea să memorăm numărul 302561, vectorul ar arăta în felul următor:

Se respectă structura menționată mai devreme: avem a[0] = 6 cifre, cifra unităților este 1, cifra zecilor este 6, cifra sutelor este 5 și așa mai departe.

De ce se memorează cifrele în ordine inversă pentru numerele mari?

Motivul pentru care se memorează cifrele în ordine inversă este că se gestionează mult mai ușor în acest fel. Este mult mai ușor să știm mereu că pe poziția 1 reținem cifra unităților, pe poziția 2 reținem cifra zecilor și așa mai departe — altfel, cifrele acestea ar depinde de lungimea numărului, ceea ce este mai complicat.

Declararea numerelor mari

Pentru a declara un număr mare, creăm pur și simplu un vector, unde lungimea depinde de numărul de cifre. Crearea unui număr mare de lungime 1000 este:

int numarMare[1003];

Unii preferă să creeze propria structură de date cu numere mari. Așadar, o alternativă este:

typedef int numarMare[1003];
…
numarMare a; //a este acum un vector număr mare cu 1000 de cifre

Inițializarea numerelor mari

Un număr mare poate fi inițializat în două moduri.

Inițializare cu un număr mic

Dacă avem un număr mic într-un int și vrem să îl punem într-un număr mare, avem următoarea funcție:

void atribuire_nrmic(int a[], int b) {
    //a <- b
    a[0] = 0;
    do {
        int cif = b % 10;
        b = b / 10;
        a[0]++;
        a[a[0]] = cif;
    } while(b != 0);
}

Practic, resetăm lungimea numărului mare a cu 0, iar cât timp b are cifre (folosind proprietățile cifrelor unui număr), punem ultima cifră a lui b pe poziția ultimei cifre a lui a, cifra zecilor și așa mai departe.

Inițializare cu un număr mare

Dacă avem un număr mare b și vrem să îl duplicăm într-un alt număr a, avem următoarea funcție, care pur și simplu copiază tot vectorul dintr-unul în altul:

void atribuire_nrmare(int a[], int b[]) {
    //a <- b
    a[0] = b[0];
    for(int i = 1; i <= a[0]; i++) {
        a[i] = b[i];
    }
}

Afișarea numerelor mari

Funcția de afișare a numerelor mari este foarte simplă: afișăm cifrele din vector, însă în ordine inversă, de la prima cifră către ultima:

void afisare_nrmare(int a[]) {
    for(int i = a[0]; i >= 1; i--) {
        cout << a[i];
    }
}

Compararea numerelor mari

Compararea a două numere mari este simplă, exact ca cea învățată în clasele mici:

• dacă un număr are mai multe cifre decât celălalt, atunci este mai mare;
• dacă au același număr de cifre, se compară cifrele începând cu cele mai semnificative, până la ultima cifră; dacă toate sunt egale, atunci cele două numere sunt egale, altfel deducem care este mai mare.

Funcția de comparare a două numere mari returnează 0 dacă numerele sunt egale, 1 dacă primul număr este mai mare și -1 dacă al doilea număr este mai mare. Trebuie la început să ne asigurăm că vectorii memorează corect numărul de cifre (mai precis, că nu avem cifre de 0 la început, de pildă la numărul 00123 = 123, lucru ce se poate întâmpla în timpul programului):

int comparare_nrmare(int a[], int b[]) {
    //a == b -> 0  |  a > b -> 1  |  a < b -> -1
    while(a[0] > 1 && a[a[0]] == 0) //avem cel puțin o cifră, iar prima cifră este 0
        a[0]--;
    while(b[0] > 1 && b[b[0]] == 0)
        b[0]--;

    if(a[0] > b[0]) return 1;
    else if(a[0] < b[0]) return -1;

    int lungime = a[0];
    for(int i = lungime; i >= 1; i--) {
        if(a[i] > b[i]) return 1;
        else if(a[i] < b[i]) return -1;
    }

    return 0; //numerele sunt egale
}

Adunarea numerelor mari

Funcția de adunare așteaptă două numere a și b (cu număr variabil de cifre) și salvează, la final, în a, suma dintre a și b. Suma este ca cea din clasele primare: luăm cifrele de la coadă la cap și adunăm cifrele pe rând. Dacă cifra curentă este 10 sau mai mult, atunci trebuie adunat 1 la următoarea cifră, iar pe poziția curentă luăm ultima cifră a sumei cifrelor. Pentru a evita posibilele erori, pentru numărul cu mai puține cifre, completăm cifrele de după cu 0. Iată funcția:

void adunare_nrmare(int a[], int b[]) {
    //a <- a + b
    int lungime;
    if(a[0] > b[0]) lungime = a[0];
    else lungime = b[0];

    for(int i = a[0] + 1; i <= lungime; i++)
        a[i] = 0;
    for(int i = b[0] + 1; i <= lungime; i++)
        b[i] = 0;

    a[0] = lungime;
    int t = 0;
    for(int i = 1; i <= a[0]; i++) {
        a[i] = a[i] + b[i] + t;
        t = a[i] / 10;
        a[i] = a[i] % 10;
    }
    //este posibil să rămânem cu cifre în plus de adăugat (exemplu 999 + 1 = 1000, nu 000)
    if(t != 0) {
        a[0]++;
        a[a[0]] = t;
    }
}

Scăderea numerelor mari

Similar, scăderea se face cifră cu cifră începând cu ultima. În acest caz, presupunem din start că b ≤ a, pentru că lucrăm cu numere naturale (putem verifica cu funcția comparare_nrmare). Din nou, avem un transport t, care asigură scăderi peste ordin (de pildă 1000 - 1 = 999):

void scadere_nrmare(int a[], int b[]) {
    //a <- a - b

    for(int i = b[0] + 1; i <= a[0]; i++)
        b[i] = 0;

    int t = 0;
    for(int i = 1; i <= a[0]; i++) {
        a[i] = a[i] - b[i] - t;
        if(a[i] < 0) {
            t = 1;
            a[i] += 10;
        } else {
            t = 0;
        }
    }

    while(a[0] > 1 && a[a[0]] == 0) //dacă mai avem cifre de 0 la coadă, de exemplu 1000 - 1 = 0999 = 999
        a[0]--;
}

Înmulțirea unui număr mare cu un număr mic

Înmulțirea cu un număr mic se face la fel, ca în clasele mici. Când numărul mic are o singură cifră, rezultatul este simplu, iar un lucru interesant este că funcția merge și când numărul mic are mai mult de o cifră (funcționează la fel). Trebuie doar să ținem cont că transportul poate avea mai mult de o cifră, așadar, la final, în loc să verificăm cu un if dacă transportul este gol sau nu, verificăm cu un while, extragând mereu ultima cifră.

void inmultire_nrmic(int a[], int b) {
    // a <- a * b
    int t = 0;
    for(int i = 1; i <= a[0]; i++) {
        a[i] = a[i] * b + t;
        t = a[i] / 10;
        a[i] = a[i] % 10;
    }

    while(t != 0) {
        a[0]++;
        a[a[0]] = t % 10;
        t /= 10;
    }
}

Înmulțirea a două numere mari

Înmulțirea a două numere mari a și b se face, la fel, ca în clasele mici. Algoritmul în acest caz este mai dificil de înțeles, deci să vedem cum funcționează:

• luăm numerele inițiale și le așezăm unul sub celălalt, ca în clasele mici:

      4   1   2  ×
          7   4

• înmulțim fiecare cifră din a cu fiecare cifră din b, însă așezăm rezultatele deplasate, ca mai jos:

      4   1   2  ×
          7   4 
----------------
     16   4   8
 28   7  14

• calculăm sumele de pe fiecare coloană:

      4   1   2  ×
          7   4 
----------------
     16   4   8
 28   7  14    
----------------
 28  23  18   8

• ca la sumă, corectăm rezultatul, mutând cifrele peste 9 cu o poziție spre stânga:

         4   1   2  ×
             7   4 
-------------------
        16   4   8
    28   7  14    
-------------------
    28  23  18   8
-------------------
 3   0   4   8   8

Vedem că numărul de cifre ale rezultatului este în jur de a[0] + b[0] - 1 (depinzând de transport). Pentru ușurință, memorăm rezultatul într-un al treilea număr mare, c.

void inmultire_nrmare(int a[], int b[], int c[]) {
    //c <- a * b
    c[0] = a[0] + b[0] - 1;
    for(int i = 1; i <= a[0] + b[0]; i++) //golim vectorul c
        c[i] = 0;

    for(int i = 1; i <= a[0]; i++) {
        for(int j = 1; j <= b[0]; j++) {
            c[i + j - 1] += a[i] * b[j];
        }
    }

    int t = 0;
    for(int i = 1; i <= c[0]; i++) {
        c[i] = c[i] + t;
        t = c[i] / 10;
        c[i] = c[i] % 10;
    }

    if(t != 0) {
        c[0]++;
        c[c[0]] = t;
    }
}

Împărțirea unui număr mare la un număr mic

Operația de împărțire este similară ca algoritmul de pe hârtie (învățat în casele mici). Luăm cifrele începând cu prima, găsim restul curent și calculăm rezultatul. Funcția întoarce restul și salvează în numărul mare câtul împărțirii întregi:

int impartire_nrmic(int a[], int b) {
    //a <- a / b  |  se returnează restul
    int r = 0;
    for(int i = a[0]; i >= 1; i--) {
        r = r * 10 + a[i];
        a[i] = r / b;
        r = r % b;
    }

    while(a[0] > 1 && a[a[0]] == 0) {
        a[0]--;
    }

    return r;
}

Alte observații

Alte operații care se pot implementa

Bazat pe operațiile menționate mai sus, se pot implementa alte operații mai complexe (ridicarea la putere, ridicarea la putere în timp logaritmic, împărțitrea a două numere mari, înmulțiri și împărțiri mai eficiente cu 10 și multe altele).

Cu toate acestea, numerele mari nu se folosesc foarte des, iar în situațiile în care se folosesc, numerele rezultat de obicei se construiesc doar cu operațiile menționate mai devreme.

Folosirea altor baze de numerație

Toate operațiile pe care le-am menționat mai sus folosesc operații în baza 10, bază pe care o folosim în viața de zi cu zi. Cu toate acestea, nu este o necesitate să folosim această bază, dacă folosim operații cu alt număr în loc de 10. De pildă, folosind o bază precum baza 100, 1000, …, putem să facem operațiile mai rapid, însă în detrimentul simplității. Trebuie avut grijă ca baza pe care o folosim în acest caz și operațiile folosite să nu depășească tipul de date int, deoarece numerele mari sunt vectori de numere int.

Exerciții propuse

Completează următoarele secvențe de cod:

a[???]--;

int s = 0;
for(int i = ???; i <= a[0]; i++) {
    s += a[???];
}
cout << s;

Alte resurse și bibliografie

• InfoArena: Lucrul cu numere mari
• Informatica pas cu pas: Numere mari
• PbInfo: Aritmetica numerelor mari