<docere>

Putem aştepta o creştere semnificativă de viteză, dacă am modela operaţiile folosind baza 10⁶ (nu zece).

Schiţă pentru un obiect "bignum"

Sunt necesare funcţii de transformare între un şir de cifre zecimale şi un tablou numeric T[], tablou în care fiecare element să corespundă unui anumit grup de maximum şase cifre zecimale consecutive din şir; este necesară o funcţie de înmulţire între numărul mare obţinut în T[] şi un număr natural obişnuit (factorul curent, în procesul calculării factorialului). Este un bun prilej de a implica o modalitate elementară de folosire în javascript a OOP.

"Manualul de întrebuinţare" a obiectului nostru (îi zicem "bignum") ar arăta cam aşa:

var Z = "112123123412345123456";  // un număr în forma zecimală obişnuită (21 de cifre)
var myBig = new bignum(Z);  // construieşte folosind Z, obiectul 'myBig' (conţinând T[] şi funcţiile indicate) 
alert(myBig.T);  // tabloul numeric corespunzător, [123456, 412345, 123123, 112]
// T[0]=123456 reprezintă numeric grupul ultimelor 6 cifre din Z ("cifra" unităţilor în baza 10^6)
// T[3] = 112 este cifra cea mai semnificativă (în baza 10^6) a numărului
alert(myBig.len);  // 4 cifre în baza 10^6 (vor fi necesare 4 operaţii "cifră cu cifră")
myBig.mul_int(90000);  // T[] înregistrează acum rezultatul înmulţirii sale cu factorul 90000:
alert(myBig.T);        // [40000, 61111, 107111, 91081, 10], adică sub forma zecimală obişnuită:
alert(myBig.to_str()); //   "10 091081 107111 061111 040000" (verificare: Z*9 şi adaugă 4 zerouri)

Să observăm că T[3] = 91081 corespunde unui grup de 5 cifre zecimale, deci trebuie prefixat cu un '0' nesemnificativ - fiindcă prin construcţie, orice T[i] (exceptând doar cifra cea mai semnificativă, ultima din T[]) provine dintr-un grup de 6 cifre zecimale şi ca urmare, pentru conversia inversă: pentru fiecare k = 1..5, dacă T[i] < 10^k atunci vor trebui adăugate (6 - k) zerouri nesemnificative.

Implementare

Maniera de modelare OOP pe care o prezentăm aici (similar manierei elementare de lucru în C++) se poate folosi în general, pentru obiecte independente de DOM (care nu pretind şi modelarea de interacţiuni cu obiecte şi evenimente specifice Web).

var CIFRA = 6;                  // O cifră T[i] "conţine" maxim CIFRA cifre zecimale
var BAZA = eval("1e" + CIFRA);  // Operaţiile "cifră cu cifră" pe T[] angajează BAZA = 10 ^ CIFRA

/* "declaraţia" obiectului 'bignum' (descrierea conţinutului) */

function bignum( Z ) {  // Z este un şir de cifre zecimale, în ordinea obişnuită,
                        // pe baza căruia va fi construit obiectul (var myBig = new bignum(Z);)
    // variabile "de lucru", temporare ("private" obiectului instanţiat)
    var len_Z = Z.length;      // Numărul de cifre zecimale din Z 
    var rest = len_Z % CIFRA;  // Numărul de cifre zecimale care rămân prin gruparea cifrelor lui Z
                               // câte CIFRA, de la dreapta (cifra unităţilor) spre stânga 
    var len = 0;        // Iniţializează numărul de elemente ale tabloului T[]

    // Setează datele "membre" ale obiectului, accesibile public prin operatorul de selecţie, "."
    this.T = new Array();  // Orice obiect păstrează un "pointer" la el însuşi, 'this'
    this.T[0] = 0;         // Pe rangul 0 - cifra unităţilor (ultimele CIFRA cifre din Z)
    // converteşte la "integer" câte CIFRA cifre din Z (de la dreapta spre stânga) şi înscrie în T[]:
    for( len = 0; CIFRA*(len + 1) <= len_Z; len++ ) { 
        this.T[len] = parseInt( Z.substring( len_Z - CIFRA*(len + 1), len_Z - CIFRA*len ), 10 );
    }
    if( rest ) {  // cifra "high" din T[], poate conţine mai puţin de CIFRA cifre zecimale din Z 
        this.T[len++] = parseInt( Z.substring( 0, rest ), 10 ); 
    }
    this.len = len;  // Setează ca dată "membru", numărul de valori înscrise în T[]

    // "metodele" de lucru asupra obiectului respectiv
    this.to_str = bignum_str;  // va returna forma zecimală obişnuită corespunzătoare tabloului numeric T[]
    this.mul_int = bignum_mul_int;  // înmulţeşte T[] propriu, cu numărul natural obişnuit primit ca parametru
    // alte metode... (pentru adunare/înmulţire/împărţire cu un alt 'bignum', incrementare, comparare, etc.)  
}

/* urmează "implementarea" metodelor declarate în 'bignum' */

function bignum_str() {
    var th = this.len - 1;
    var str = "" + this.T[th];  // Cifrele cele mai semnificative (ultima valoare din T[])
    while(--th >= 0) {          // Valorile din T[] începând de la penultima spre stânga,   
        var cifre = "" + this.T[th];  // trebuie transformate în şir de lungime CIFRA  
        while(cifre.length < CIFRA)   // prefixând eventual cu zerouri "nesemnificative"
            cifre = '0' + cifre;
        // cifre = " " + cifre;  // separă grupurile de CIFRA cifre zecimale
        str += cifre;   // Adaugă la 'str' grupul curent de CIFRA cifre zecimale
    }
    return str;
}

function bignum_mul_int( n ) { // Număr natural obişnuit, mai mic decât 2^53 / 10^CIFRA
    var i; var th = this.len;
    // Prima trecere: înmulţeşte numerele CIFRA din T[] cu n
    for( i = 0; i < th; i++ ) this.T[i] *= n;
    // A doua trecere: corectează rezultatele în raport cu BAZA (la prima trecere puteau rezulta 
    // în T[i] şi valori mai mari decât BAZA; le reduce modulo BAZA şi propagă transportul)
    for( i = 0; i < th - 1; i++ ) {
        if( this.T[i] >= BAZA ) {
            n = Math.floor( this.T[i] / BAZA );  // Refoloseşte variabila n creată la apel
            this.T[i] = this.T[i] % BAZA;
            this.T[i+1] +=  n;  // Propagă transportul spre dreapta (la rangul i+1)
        }    
    }
    while( this.T[ th - 1 ] >= BAZA ) {  // Reduce şi ultima cifră, extinzând eventual T[],
        this.T[ th ] = Math.floor( this.T[ th - 1 ]/BAZA );  // cu transportul generat.
        this.T[ th - 1 ] %= BAZA;
        this.len++;  // Corectează şi numărul de elemente CIFRA existente în T[]
        th++;        // reia "reducerea" şi pentru ultima cifră adăugată 
    }
    return this;  // returnează un "pointer" la obiect, util pentru formulările recursive şi
                  // pentru imbricări ca  alert( myBig.mul_int(n).to_str() ) 
}

Pentru bignum_mul_int(n) am folosit un algoritm de înmulţire "cu două treceri"; posibilitatea acestui algoritm decurge din faptul că orice valoare T[i] (număr mai mic decât 10⁶, conform cu definiţia 'bignum') ar deveni prin înmulţire cu numărul n o valoare care poate fi înregistrată şi ea în T[i] ("încape", fără trunchiere şi fără erori de rotunjire).

Mai precis, javascript îşi reprezintă numerele (întregi sau nu) în formatul IEEE_754—double precision floating point, pe 64 biţi; în cazul unui număr întreg, sunt reprezentate exact numai cele mai semnificative 15-16 cifre zecimale, anume pe 53 de biţi din cei 64 (iar restul biţilor reprezintă numărul de cifre care urmează în număr). Fiindcă 2⁵³ ≈ 9007*10¹², iar max(T[i]) = 10⁶ - 1, rezultă că factorul maxim n pentru care produsul cu T[i] nu depăşeşte "capacitatea" lui T[i] este (împărţind prima valoare menţionată prin cea de-a doua) 9.007.208.261 - un număr suficient de mare, ca să nu apară "depăşiri" în cazul problemei factorialelor (doar dacă ar vrea careva să calculeze factorialul unui număr care are 10 cifre, ceea ce ar fi o absurditate fără nici o şansă de acoperire).

Rezultă de aici că baza poate fi încă mărită, fără a apărea probleme de depăşire; dar dacă ea s-ar mări dincolo de 10¹², atunci raportul menţionat mai sus va deveni mai mic de 90.071, adică deja nu vom mai putea calcula (în felul descris mai sus, cu două treceri) factorialul lui 100.000 (ceea ce n-ar fi chiar absurd, de calculat…; dar probabil nu în javascript!).

n! folosind "bignum"

Acum putem folosi 'bignum' pentru a calcula factorialele, de exemplu prin următoarea funcţie:

function big_fact( n ) {
    var big = new bignum("1");
    for(var f = 2; f <= n; f++) 
        big.mul_int( f );
    return big.to_str();
}
// factorialul va fi redat prin funcţia print_big_fact() (v. fişierul "qmin.js")

De data aceasta, 1000! rezultă în mai puţin de o secundă, 2000! în 3-4 secunde, iar 5000! rezultă în 35 secunde - timpi cam de trei ori mai buni, decât în cazul bazei 10.

Este de discutat o deosebire privind desfăşurarea calculului, între cele două programe redate mai sus: primul (în baza 10) făcea calculul în cadrul unei singure funcţii (deci în cel mai economicos mod), pe când al doilea implica apelarea repetată a unei funcţii (e drept - nu orice funcţie, ci o "metodă" internă obiectului), consumând astfel timp nu numai pentru calculul necesar, dar şi pentru a îndeplini protocoalele de apel respective (transmite parametrii necesari serviciului apelat, salvează şi apoi recuperează punctul de revenire, etc.). Al doilea program, deşi dezavantajat faţă de primul prin faptul că a trebuit să apeleze repetat la funcţia 'mul_int', a dat totuşi timpi mai buni - ceea ce întăreşte (dacă mai trebuia) concluzia că modelarea calculelor folosind baza 10⁶ este mult mai eficientă decât modelarea obişnuită, în baza 10.

n! recursiv

Este interesant de confruntat cu o versiune recursivă (angajând un obiect 'bignum'):

function big_fact_rec(big, n) {  // 'big' referă un "bignum" iniţial
    if(n == 1) return big;
    return big_fact_rec(big.mul_int(n), n-1);  // Reapelează pentru 'big'-ul rezultat, 
}                                              // după înmulţire cu factorul curent

Diferenţa faţă de versiunea iterativă precedentă este de până la o zecime de secundă (cel puţin până pe la 1000!). Pentru un număr mai mare ca 1000 (în funcţie şi de browser) rezultă eroarea too much recursion sau "Out of Memory" (fiindcă javascript are stabilită limita de 1000 de apeluri recursive). Dacă am vrea să calculăm în această manieră şi 1500! de exemplu, atunci am putea modifica "condiţia de oprire" (n == 1) astfel:

var stop = 1;  // "coborârea" se face până la n == stop (cu 'stop' setat în prealabil) 
function big_fact_rec(big, n) {   // 'big' referă un "bignum" obţinut anterior
    if(n == stop) return big;     // "revenirile" încep când n coboară până la 'stop'
    return big_fact_rec(big.mul_int(n), n-1);  // se calculează "invers": n*(n-1)*...*stop.
}

De exemplu, obţinem întâi 500! şi apoi pe baza acestei valori găsim şi 1500! astfel:

var myBig = big_fact_rec(new bignum("1"), 500);  // obţine 500! în variabila myBig
stop = 500;  // schimbă condiţia de oprire (pentru a evita "too much recursion")
document.write( big_fact_rec( myBig, 1500 ).to_str() );  // în myBig se obţine 1500!

Altă aplicaţie: obţinem un produs de numere consecutive astfel:

stop = 500; 
document.write( big_fact_rec( new bignum("1"), 1000).to_str() ); // rezultă 500*501*...*1000