Operatii cu numere mari (adunare, inmultire, factorial)

Numerele mari (Big Numbers) sunt numere care depasesc limitele tipurilor de date standard din limbajele de programare (de exemplu, in C++, tipul long long int poate stoca pana la aproximativ 9.22 * 10^18). In problemele de informatica, frecvent intalnim calcule cu numere care au sute sau mii de cifre, cum ar fi factorialul lui 1000 (1000! are peste 2500 de cifre). Pentru a manipula astfel de numere, se folosesc siruri de caractere (stringuri) sau vectori de cifre.

Operatia de baza este reprezentarea: fiecare cifra a numarului se stocheaza intr-un element al unui vector (de obicei in ordine inversa, pentru a usura efectuarea calculelor cu transport). Adunarea se face cifra cu cifra, de la dreapta la stanga, pastrand transportul. Inmultirea unui numar mare cu un numar mic se realizeaza prin inmultirea fiecarei cifre si gestionarea transportului, iar inmultirea a doua numere mari se face prin metoda manuala (inmultirea fiecarei cifre a primului cu fiecare cifra a celui de-al doilea, urmata de adunare cu deplasare).

Factorialul se calculeaza iterativ, inmultind numarul mare curent cu numerele naturale succesive, pana la N. Eficienta algoritmilor se masoara in complexitate: adunarea are O(n), inmultirea cu un numar mic O(n), iar inmultirea a doua numere mari O(n*m). Pentru factorial, complexitatea totala este O(N^2) in cazul naiv, dar se poate optimiza.

Este esential sa se acorde atentie gestionarii memoriei si inversarii ordinii cifrelor la afisare.

Exemple

• Exemplul 1: Adunarea a doua numere mari. Fie A = 12345678901234567890 si B = 98765432109876543210. Se reprezinta cifrele in ordine inversa: vectorul pentru A: [0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1] (cifra cea mai nesemnificativa prima). Se aduna cifra cu cifra: 0+0=0 (transport 0), 9+1=10 => 0 transport 1, etc. Rezultatul final este 111111111011111111100.
• Exemplul 2: Inmultirea unui numar mare cu un numar mic. Sa se calculeze 123456789 * 7. Se ia fiecare cifra din numarul mare (in ordine inversa): 9*7=63 => 3 transport 6; 8*7=56+6=62 => 2 transport 6; 7*7=49+6=55 => 5 transport 5; si asa mai departe. Rezultatul este 864197523.
• Exemplul 3: Calculul factorialului pentru N=10. Pornim cu rezultatul = 1. Inmultim succesiv: 1*1=1, 1*2=2, 2*3=6, 6*4=24, 24*5=120, 120*6=720, 720*7=5040, 5040*8=40320, 40320*9=362880, 362880*10=3628800. Toate inmultirile se fac folosind algoritmul de inmultire a unui numar mare (rezultatul) cu un numar mic (i).

Concepte cheie: Reprezentarea numerelor mari in vectori (cifra cu cifra, ordine inversa), Adunarea a doua numere mari cu gestionarea transportului, Inmultirea unui numar mare cu un numar mic si inmultirea a doua numere mari (metoda manuala), Calculul factorialului prin inmultiri repetate cu numere mici, Complexitatea algoritmilor de operatii cu numere mari