Numere mari: înmulțirea a două numere mari

După ce am învățat cum înmulțim un număr mare cu unul mic (lecția 118), e timpul să generalizăm: înmulțirea a două numere mari, ambele reprezentate ca vectori de cifre.

E operația cea mai puternică din setul de operații pe numere mari - apare în calcule de factorial, puteri, exponențiere rapidă pentru numere mari etc.

Ideea

Ca la școala primară - înmulțim fiecare cifră a lui a cu fiecare cifră a lui b și adunăm rezultatele pe poziția potrivită.

    1 2 3
×     4 5
─────────
    6 1 5    ← 123 × 5 = 615
+ 4 9 2 0    ← 123 × 40 = 4920 (shift 1 la stânga)
─────────
  5 5 3 5    ← rezultatul final: 123 × 45 = 5535

Formula cheie

Dacă a[i] e cifra pe poziția i a lui a și b[j] e cifra pe poziția j a lui b, atunci produsul a[i] * b[j] contribuie la cifra de pe poziția i + j - 1 a rezultatului (pentru indexare de la 1).

c[i + j - 1] += a[i] * b[j]

După toate adunările, propagăm transportul prin întregul vector c.

Algoritmul

1. Inițializăm c[] cu 0
2. Pentru fiecare i de la 1 la lenA:
     Pentru fiecare j de la 1 la lenB:
         c[i + j - 1] += a[i] * b[j]
3. Propagăm transportul prin c:
     Pentru k de la 1 la lenA + lenB:
         transport = c[k] / 10
         c[k] = c[k] % 10
         c[k + 1] += transport
4. Stabilim lungimea (eliminăm zerourile de la coadă)

Pas cu pas: 123 × 45 = 5535

Reprezentare:

• a = 123 → a[1]=3, a[2]=2, a[3]=1, lenA = 3
• b = 45 → b[1]=5, b[2]=4, lenB = 2

Etapa 1: produse fără transport

După etapa 1: c = [_, 15, 22, 13, 4]

Etapa 2: propagăm transportul

După etapa 2: c = [_, 5, 3, 5, 5]

Rezultat

c[4]=5, c[3]=5, c[2]=3, c[1]=5 → afișat de la dreapta la stânga → 5535 ✓

Cod

const int NMAX = 2005;
int a[NMAX], b[NMAX], c[NMAX * 2];

void inmultire(int a[], int b[], int c[]) {
    // Initializam c cu 0
    for (int i = 0; i < NMAX * 2; i++) {
        c[i] = 0;
    }

    // Etapa 1: produsele pe pozitiile i+j-1
    for (int i = 1; i <= a[0]; i++) {
        for (int j = 1; j <= b[0]; j++) {
            c[i + j - 1] = c[i + j - 1] + a[i] * b[j];
        }
    }

    // Etapa 2: propagam transportul
    int len = a[0] + b[0];
    for (int k = 1; k <= len; k++) {
        c[k + 1] = c[k + 1] + c[k] / 10;
        c[k] = c[k] % 10;
    }

    // Eliminam zerourile de la coada
    while (len > 1 && c[len] == 0) {
        len--;
    }
    c[0] = len;
}

Complexitate: O(lenA · lenB) - pătratic în lungime.

Pentru a și b de câte 1000 cifre, algoritmul face 10^6 operații - rapid.

Cod complet

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int NMAX = 2005;
int a[NMAX], b[NMAX], c[NMAX * 2];
char s[NMAX];

void citire(int v[]) {
    fin >> s;
    int len = strlen(s);
    v[0] = len;
    for (int i = 1; i <= len; i++) {
        v[i] = s[len - i] - '0';
    }
}

void afisare(int v[]) {
    for (int i = v[0]; i >= 1; i--) {
        fout << v[i];
    }
    fout << "\n";
}

void inmultire(int a[], int b[], int c[]) {
    for (int i = 0; i < NMAX * 2; i++) c[i] = 0;

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

    int len = a[0] + b[0];
    for (int k = 1; k <= len; k++) {
        c[k + 1] = c[k + 1] + c[k] / 10;
        c[k] = c[k] % 10;
    }

    while (len > 1 && c[len] == 0) len--;
    c[0] = len;
}

int main() {
    citire(a);
    citire(b);
    inmultire(a, b, c);
    afisare(c);
    return 0;
}

date.in:

123
45

date.out:

5535

De ce c[i + j - 1]?

Poziția i în a reprezintă cifra de rang 10^(i-1). Produsul a[i] · b[j] are rangul 10^(i-1) · 10^(j-1) = 10^(i+j-2), deci contribuie la poziția i + j - 1 a rezultatului (indexare de la 1).

Dacă ai folosi indexare de la 0, formula ar fi c[i + j].

Lungimea rezultatului

Produsul a două numere cu lenA respectiv lenB cifre are cel mult lenA + lenB cifre (și cel puțin lenA + lenB - 1).

• 99 · 99 = 9801 → 4 cifre (2 + 2)
• 10 · 10 = 100 → 3 cifre (2 + 2 - 1)
• 1 · 1 = 1 → 1 cifră (1 + 1 - 1)

De aceea alocăm c cu dimensiune NMAX * 2.

Aliasing: inmultire(a, a, c) funcționează?

Da - citim cifrele din a și b înainte să scriem în c, iar c e inițializat cu 0. Chiar dacă a == b (vrem a²), totul merge corect pentru că vectorii rămân neschimbați în etapa 1.

Atenție: inmultire(a, b, a) (rezultat suprascris peste a) nu e sigur - am citi din a după ce am modificat a[k]. Folosește un vector temporar.

Aplicație: factorial mare

Calculează n! pentru n până la 1000.

1000! are ~2568 cifre - nu încape în niciun tip nativ. Folosim numere mari.

int fact[NMAX], temp[NMAX];

int main() {
    int n;
    fin >> n;

    fact[0] = 1;
    fact[1] = 1; // fact = 1

    int mic[NMAX] = {0};
    mic[0] = 1;
    mic[1] = 0; // mic = numar mic convertit in vector

    for (int i = 2; i <= n; i++) {
        // Convertim i in vector (max 4 cifre pentru n <= 1000)
        int x = i, len = 0;
        while (x > 0) { mic[++len] = x % 10; x /= 10; }
        mic[0] = len;

        inmultire(fact, mic, temp);

        // Copiem temp in fact
        for (int k = 0; k <= temp[0]; k++) fact[k] = temp[k];
    }

    afisare(fact);
    return 0;
}

Pentru n = 20:

2432902008176640000

Pentru n = 1000 - un număr de 2568 cifre calculat instant.

Aplicație: puterea unui număr

Calculează a^n pentru a mic și n până la 1000.

// rez = 1
rez[0] = 1; rez[1] = 1;

// mic = a
mic[0] = ...; // cifrele lui a

for (int i = 1; i <= n; i++) {
    inmultire(rez, mic, temp);
    // Copiem temp in rez
    for (int k = 0; k <= temp[0]; k++) rez[k] = temp[k];
}

Pentru 2^1000 - un număr de 302 cifre calculat în timp liniar.

Algoritm mai rapid: Karatsuba

Pentru numere foarte mari (peste 10.000 cifre), există algoritmul Karatsuba care rulează în O(n^1.585) în loc de O(n²). E bazat pe divide et impera și un truc algebric ingenious.

Pentru olimpiade de liceu, algoritmul naiv O(n²) e aproape mereu suficient.

Greșeli frecvente

1. Dimensiune insuficientă pentru c

int c[NMAX]; // GRESIT - rezultatul poate avea pana la 2·NMAX cifre
int c[NMAX * 2]; // CORECT

2. Uitarea inițializării cu 0

// Fara "for (int i = 0; i < NMAX * 2; i++) c[i] = 0;"
// c contine gunoi din apelul precedent → rezultat gresit

Vectorii globali sunt inițializați cu 0 de compilator, dar dacă apelezi inmultire de mai multe ori, trebuie să-l resetezi.

3. Indexare greșită

c[i + j] += a[i] * b[j]; // GRESIT pentru indexare de la 1
c[i + j - 1] += a[i] * b[j]; // CORECT pentru indexare de la 1

4. Overflow la c[i+j-1] += a[i] * b[j]

a[i] * b[j] e maxim 9 * 9 = 81. Dacă lenA = lenB = 10000, c[k] se incrementează cu 81 de ~10000 ori → c[k] ≤ 810000, încape în int.

Pentru lenA și lenB foarte mari (peste 100.000 cifre), folosește long long pentru c.

5. Uitarea propagării transportului

// Etapa 1: produsele
for (...) c[i+j-1] += a[i] * b[j];

// Uitat etapa 2! Rezultat gresit.

După etapa 1, c[k] poate avea valori ≥ 10 - trebuie obligatoriu să propagi transportul.

6. Nu ștergi zerourile de la coadă

// 100 * 0 = 000 in loc de 0 daca nu stergem
while (len > 1 && c[len] == 0) len--;

Dacă unul dintre numere e 0 sau rezultatul are zerouri la capăt, trebuie să elimini cifrele inutile.

Ce să reții

• Înmulțirea a două numere mari: fiecare cifră din a cu fiecare cifră din b, adunate pe poziția i + j - 1.
• Două etape: produsele (fără transport) + propagarea transportului.
• Rezultatul are cel mult lenA + lenB cifre - alocă c cu dimensiune NMAX * 2.
• Complexitate: O(lenA · lenB) - pătratic în lungime.
• Aplicații: factorial mare, puteri mari, exponențiere rapidă pentru numere mari.
• Pentru viteză suplimentară: baza 10000 (grupuri de 4 cifre) sau algoritmul Karatsuba (O(n^1.585)).
• Elimină zerourile de la coadă la final.