•Owlree
Strain
Karma: 16
Deconectat
Mesaje: 27
|
|
« Răspunde #1 : Februarie 19, 2015, 23:46:24 » |
|
Ca să facem o analiză, pentru a reprezenta un număr n în baza k ne trebuie cam logkn cifre. Dacă ne luăm două baze, să zicem a și b, numărul n în baza a are logan, iar în baza b are logbn = logan / logab. Deci schimbând de la baza a la baza b, numărul cifrelor diferă printr-un factor de logab. Deci trecând de la, să zicem, baza 10 la baza 10n numărul cifrelor diferă printr-un factor de log1010n = 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, 24 - 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.
|