<docere>

Numărul de operaţii depinde (esenţial) de sistemul de numeraţie în care sunt modelate operaţiile.

Un număr cu 100 de cifre zecimale ocupă 100 de "locaţii"; fiecare locaţie înregistrează o cifră zecimală. Orice operaţie care angajează acest număr (de exemplu, adunarea lui cu un alt număr de 100 de cifre) trebuie să efectueze 100 de operaţii elementare "cifră-cu-cifră". Dar să presupunem că în "locaţie" încap 2 cifre zecimale: (00)..(99); atunci numărul nostru de 100 de cifre zecimale, poate fi înregistrat folosind 50 de locaţii, iar operaţiile care l-ar implica ar necesita 50 de "operaţii elementare" între conţinuturile locaţiilor (desigur, folosind table de operare cu "cifre" 00-99, în loc de cele obişnuite cu cifre 0-9).

Memoria calculatorului este constituită din "locaţii" care au dimensiunea standard de 8 biţi; pe un bit se poate înregistra fie valoarea 0, fie valoarea 1; pe doi biţi se pot înregistra cele 2² perechi de biţi (00), (01), (10) sau (11) - adică, reprezentând în baza uzuală, valorile 0, 1, 2, 3; ş.a.m.d. Într-o locaţie de memorie de 8 biţi se pot înregistra valori 0..255 (numite octeţi, sau bytes, sau cifre în baza 2⁸ = 256; resturile modulo 256, adică elementele inelului Z₂₅₆).

Cam toate operaţiile interne se bazează pe faptul că "unitatea de măsură" este locaţia de 8 biţi; nu se accesează şi nu se transferă biţi individuali, ci întreaga locaţie; nu se operează bit-cu-bit, ci "locaţie-cu-locaţie". O instrucţiune precum ADD AX, BX consumă acelaşi timp pentru execuţia ei atât în cazul când regiştrii AX şi BX conţin respectiv valoarea 1 (pentru e efectua adunarea 1+1), cât şi în cazul în care AX=234 şi BX=159.

Cel mai mare număr natural care are Z cifre zecimale este 10^Z - 1; cel mai mare număr natural care are T cifre în baza 256 este 256^T - 1; ca să vorbim de aceleaşi numere naturale şi într-o bază şi în cealaltă, trebuie să avem 10^Z = 256^T; aplicând logaritmii zecimali, rezultă: Z = T * lg(256) ≈ T * 2.40824.

Adică, reprezentarea în baza 256 necesită de minimum 2.4 ori mai puţine "locaţii" decât cea în baza 10, iar operarea bazată pe reprezentarea în baza 256 necesită de 2.4 ori mai puţine operaţii "cifră cu cifră" decât cea bazată pe reprezentarea zecimală obişnuită.

De exemplu, un număr cu 100 de cifre zecimale va fi reprezentat în baza 256 pe maximum [100 / 2.4] + 1 = 42 de octeţi, putând fi modelat în C prin char N[42], cu N[i] = 0..255 (în loc de char N[100] cu N[i] = 0..9).

Un raţionament similar se poate face şi faţă de reprezentarea în baza 2¹⁶ = 256² (exerciţiu).

Estimarea diferenţei

Să presupunem că în calculul unui n! (n > 451), am ajuns la 450! şi urmează înmulţirea acestei valori cu 451, ceea ce implică următoarea operaţie individuală: se înmulţeşte 451 cu cifra curentă şi se adună transportul de la precedenta înmulţire; această operaţie individuală trebuie începută de la cifra unităţilor şi trebuie repetată de atâtea ori câte cifre are "deînmulţitul" - deci de 1001 ori în cazul reprezentării în baza 10, respectiv de vreo [1001 / 2.4] = 417 ori în cazul reprezentării în baza 256. Diferenţa dintre numărul de operaţii individuale necesare în cele două baze ar fi de 10001 - 417 = 584 de operaţii individuale. Mai departe, prin înmulţirea de mai sus am obţinut 451! şi urmează să înmulţim această valoare cu următorul factor 452; numărul de operaţii individuale necesare este în jur de 1003 în baza 10 şi de vreo 1003/2.4 = 418 în baza 256; înseamnă că iarăşi avem o economie de operaţii individuale şi aceasta trebuie cumulată cu cea precedentă ş.a.m.d., pentru a determina ce economie totală de operaţii are loc dacă lucrăm în baza 256. Putem abstractiza acest calcul astfel:

 total_operaţii_10 = 0;
 for (k = 2; k <= n; k++) total_operaţii_10 += nr_cifre_10 (k!);
 economie_operaţii_256 = total_operaţii_10 — (total_operaţii_10 / 2.4) = 0.583 * total_operaţii_10

function total_op_10( n ) {
    var toz = 0;           // total operaţii în baza 10
    var ln10 = Math.LN10;  // să accesăm constanta o singură dată! (v. 'factorial_info()')
    for(var factor = 2; factor < n; factor++) {   
        var lgf = 0;  // nr. cifre = nr. operaţii (în baza 10) = [lg(factor!)] + 1 &asymp; Math.ceil(factor!)
        for(var k = 2; k <= factor; k++) 
            lgf += Math.log(k) / ln10;
        toz += Math.ceil(lgf); // contorizează operaţiile la înmulţirea cu 'factor' curent
    }
    return toz;  
}
function get_diff( nr ) {  // nr = numărul al cărui factorial se investighează
    var toz = total_op_10( nr );
    alert("Total operaţii zecimale = "+toz+"\nîn baza 256 vor fi cam cu "+Math.floor(0.583*toz)+" mai puţine");
}

Avem această mică verificare: pentru 450! obţinem 203084 operaţii zecimale, iar pentru 451! obţinem 204085 - şi vedem că diferenţa este 1001, adică exact lungimea zecimală a factorialului de 450 (când 450! se înmulţeşte cu 451, pentru a găsi în final 451! - se mai fac exact aceste 1001 operaţii elementare); verificarea "ţine" şi pe alte cazuri, de exemplu pentru 1000! - dar timpul de execuţie creşte sensibil.

Desigur, în calculul prezentat intervin erori de rotunjire — poate (cumulat) chiar de ordinul a câteva sute de operaţii (acestea au fost numărate); dar şi-aşa, devine clar că modelarea operaţiilor cu numere mari, în baza 256 este categoric mai eficientă decât în baza 10.