Imbunatatire operatii cu numere mari

[•mateidanut]

Buna ziua! La operatiile cu numere mari fiecare element al vectorului retine doar o cifra, deci ramane multa memorie neutilizata. Mi s-a spus ca daca as face a(i)=(a(i)+b(i))%1000000 pentru a retine mai multe cifre as economisi din memorie si ar scadea si timpul de executie. Merita sa ma complic cu asa un artificiu? Multumesc.

[•Owlree]

Ca să facem o analiză, pentru a reprezenta un număr n în baza k ne trebuie cam log_kn cifre. Dacă ne luăm două baze, să zicem a și b, numărul n în baza a are log_an, iar în baza b are log_bn = log_an / log_ab. Deci schimbând de la baza a la baza b, numărul cifrelor diferă printr-un factor de log_ab. Deci trecând de la, să zicem, baza 10 la baza 10ⁿ numărul cifrelor diferă printr-un factor de log₁₀10ⁿ = n.

Să presupunem că fiecare întreg are dimensiunea de 4 octeți fiecare. Un număr de la 0 la 9, pe care-l putem identifica cu o cifră a numărului mare, ocupă maxim jumătate de octet (4 biți, 2⁴ - 1 = 15). Mai rămân 3 octeți și jumătate pe care îi pierdem.

Lucrând într-o bază mai mare te vei folosi mai mult și de instrucțiunile de operații de bază (mă refer aici la adunare, scădere, înmulțire, împărțire) ale procesorului și mai puțin de instrucțiunile artificiale pentru aceste oprații din programul tău.

Acum dacă ținem cont că baza maximă pe care o putem folosi ar fi cam 9 dacă folosim 4 octeți pe întreg sau 18 dacă folosim 8 octeți, ne putem întreba dacă un factor de maxim 18 merită să facem acest artificiu.

Desigur că merită să lucrezi într-o bază cât de mare ți se permite pentru că odată ce te-ai prins cum să implementezi, o să observi că nu e prea diferit de atunci când folosești baza 10 (schimbi pe acolo niște zero-uri și ai grijă la afișare). Practic depunem foarte puțin efort pentru un avantaj destul de semnificativ uneori.

Ca un exemplu concret la ce am zis mai sus - unele probleme chiar de pe infoarena nu pot fi rezolvate de 100p lucrând cu numere mari în bază 10, dar intră foarte bine în timp cu același algoritm, folosit însă cu o bază ceva mai mare.