momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Experimente cu factoriale in javaScript

factorial | javaScript
2008 dec

În manualele de liceu, factorialul apare la "analiză combinatorică" (numărul de permutări, de combinări, etc.) şi la "analiză matematică" (definiţia numărului e - suma inverselor factorialelor, aproximativ 2.7182; apoi, în formula lui Taylor). Factorialul este folosit şi pentru un prim exemplu de funcţie recursivă şi uneori este formulat vreun exerciţiu "să se calculeze 100!".

Factorialele sunt "numere mari"; eficienţa calculului depinde în primul rând de baza de numeraţie implicată; modelarea în baza 10 nu este de loc, cea mai potrivită alegere.

Browserul oferă posibilităţi standard pentru realizarea unei interfeţe unitare, prin care să putem explora şi expune împreună problemele care se pun (legate de bazele de numeraţie care s-ar putea implica, de numărul de cifre, de numărul de operaţii). Desigur, viteza unui program javaScript va fi mult mai mică decât aceea a programului omolog în C; totuşi, sunt de făcut nişte experimente şi nişte comparări…

N.B. Pe parcurs vom indica şi diverse valori temporale (1000! rezultă în mai puţin de o secundă, 5000! rezultă în 35 secunde - etc.); precizăm că acestea au rezultat folosind browserul Firefox-2.0 (la nivelul începutului anului 2008) - dar deja versiunea 3.0 este cam de două-trei ori mai rapidă (5000! folosind "bignum" rezultă acum în 11 secunde).

Metodă de informare asupra cifrelor

n! = 1×2×3×...×n iar logaritmul produsului este egal cu suma logaritmilor factorilor.

De exemplu, lg(10!) = lg(2) + ... + lg(10) ≈ 6.559763; rezultă că 10! are 7 cifre şi căutând în tabelul de logaritmi zecimali mantisa 0.559763, găsim primele cifre, anume 10! = 3628...

// numărul de cifre zecimale şi primele câteva cifre exacte ale factorialului
function factorial_info(n) {
    var lgf = 0;     // suma logaritmilor zecimali ai factorilor 2, 3, ..., n
    var est = Math.pow(10, 7);  // estimează numărul de cifre iniţiale exacte (7)
    var thend = "...";          // urmează alte cifre după cele estimate exact
    for(var k=2; k<=n; k++) {
        lgf += Math.log(k) / Math.LN10;  // log în baza 10, lg(k) = LN(k) / LN(10)
    }
    var len = parseInt(lgf);    // caracteristica logaritmului în baza 10 a lui n!
    if(len < 15) { est = Math.pow(10, len); thend = ""; } // "len" cifre exacte (≤ 14)
    var mantisa = parseFloat(lgf) - len; // mantisa logaritmului lui n!
    len++;                               // numărul de cifre ale lui n!
    var cifre = parseInt(Math.pow(10,mantisa)*est);   // primele "est" cifre ale lui n!
    alert(n + "! are " + len + " cifre zecimale\n" + n + "! = " + cifre + thend);
}

informaţii privind factorialul numărului: (factorial_info())

Întrebări

Există n încât n! să aibă 1000 cifre zecimale? (nu)
(tastaţi în formularul de mai sus 449 şi click 'alert'; înlocuiţi apoi cu 450)

Există n încât n! să aibă n cifre zecimale? (da: 22, 23 şi 24)
(tastaţi în formularul de mai sus 22 şi click 'alert')

Folosind un alt formular (vezi mai departe), se va putea răspunde şi la această întrebare:
Există n încât n! să aibă n cifre hexazecimale? (da: 38, 39 şi 40)

Câte cifre zecimale are 22009 şi care sunt primele câteva cifre?
(calculaţi 2009 * lg(2) şi folosiţi un tabel de logaritmi zecimali)

Numărul de operaţii necesare

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 înregistrând 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 22 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 28 = 256; în fond - resturile modulo 256, adică elementele inelului Z256).

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 a 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 10Z - 1; cel mai mare număr care are T cifre în baza 256 este 256T - 1; ca să vorbim de aceleaşi numere naturale în ambele baze, trebuie să avem 10Z = 256T; 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 216 = 2562 (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 (baza 10) = [lg(factor!)] + 1 ≈ 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");
}

pentru factorialului numărului: get_diff()
(compară total operaţii individuale în bazele 256 şi 10)

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); 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 — în total, poate chiar de ordinul a câteva sute de operaţii (operaţiile 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 (ceea ce nu are de ce să şocheze: baza nativă de operare a calculatorului nu este baza 10, ci 2k, cu k = 8 / 16 / 32).

Modelarea calculului în baza 10

Următoarea funcţie modelează calculul factorialului în baza 10.

function factorial( n ) {
    var cf = new Array();  // tabloul cifrelor factorialului numărului n
    cf[0] = 1;             // iniţializează cu factorialul lui 1 (1! = 1)
    for( var f = 2; f <= n; f++) {  // factorul cu care trebuie înmulţit cf[] anterior găsit
        var t = 0;  // transportul curent; se propagă de la operaţia (f*cifră) precedentă
        for(var i = 0, s = cf.length; i < s; i++) {  // începând cu cifra unităţilor (indice 0),
            var p = cf[i] * f + t;  // o înmulţeşte cu factorul curent f, adună transportul,
            cf[i] = p % 10;         // înscrie pe poziţia cf[i] cifra unităţilor produsului şi
            t = Math.floor(p / 10);  // elimină această cifră din produs, indicând noul transport.
        }
        while(t) {  // dacă terminând înmulţirea cu f, există un transport final (nenul),
            cf[s++] = t % 10;  // atunci adaugă în cf[] şi cifrele respectivului transport.
            t = Math.floor(p / 10); 
        }
    }
    return cf.reverse().join('');  // inversează tabloul cifrelor şi-l returnează ca şir de cifre
}

factorialul numărului: (factorial())

Presupunând că s-a determinat (f-1)! în cf[], pentru a determina mai departe şi pe f! urmează să se facă cel puţin atâtea operaţii individuale câte cifre are cf[], fiecare constând în înmulţirea factorului f cu cifra curentă din cf[], cumularea transportului de la precedenta înmulţire la produsul găsit şi apoi separarea acestui produs în două părţi: cifra unităţilor (adică restul împărţirii produsului prin baza 10 de lucru) reprezintă tocmai cifra care trebuie înscrisă în cf[] pe rangul curent, iar partea rămasă după eliminarea cifrei unităţilor din produs (câtul împărţirii produsului prin baza de lucru) reprezintă transportul final, către următoarea operaţie individuală.

Timpul de calcul depinde şi de calculator şi de browser şi de diverse configurări ale browserului; pot fi 3 secunde pentru 1000!, 14 secunde pentru 2000! şi 95 secunde pentru 5000! (în unele cazuri fiind necesar click pe 'Continue' în fereastra "Warning - Unresponsive script" alertată de browser).

Modelarea calculului în baza 106

Putem aştepta o creştere semnificativă de viteză, dacă am modela operaţiile folosind baza 106 (în care "cifrele" elementare sunt valorile 0..999999).

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";  // număr în forma zecimală (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 T[] = [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 
                   // (deci vor fi necesare 4 operaţii "cifră cu cifră")
myBig.mul_int(90000);  // T[] = T[] * 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] < 10k 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[] 
                                // vor angaja BAZA = 10 ^ CIFRA

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

function bignum( Z ) {  // şir de cifre zecimale, în ordinea obişnuită,
                        // pentru a construi un obiect: new bignum(Z);
    // variabile "de lucru" ("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 
        // grupând cifrele lui Z câte CIFRA, de la dreapta spre stânga 
    var len = 0;  // numărul de elemente ale tabloului T[]

    // Setează datele "membre" ale obiectului (vizat prin 'this'), 
    // accesibile public prin operatorul de selecţie, "."
    this.T = new Array();  
    this.T[0] = 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" a obiectului 'this', 
                     // 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
                                    // primit ca parametru
    // alte metode... (adunare/înmulţire cu un alt 'bignum', etc.)  
}

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

function bignum_str() {  // returnează forma zecimală obişnuită
    var th = this.len - 1;
    var str = "" + this.T[th];
    // Valorile din T[] începând de la penultima spre stânga,
    // trebuie transformate în şir de lungime CIFRA, 
    // prefixând eventual cu zerouri (sau spaţii) "nesemnificative" 
    while(--th >= 0) {  
        var cifre = "" + this.T[th];  
        while(cifre.length < CIFRA)   
            cifre = '0' + cifre;  // cifre = " " + cifre;
        str += cifre;  // alipeşte grupul de CIFRA cifre zecimale
    }
    return str;
}

function bignum_mul_int( n ) { // n < 2^53 / BAZA
    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 şi valori mai mari decât BAZA; 
    //  le reducem modulo BAZA şi propagăm transportul)
    for( i = 0; i < th - 1; i++ ) {
        if( this.T[i] >= BAZA ) {
            n = Math.floor( this.T[i] / BAZA );  
               // (refolosim variabila n creată la apel)
            this.T[i] = this.T[i] % BAZA;
            this.T[i+1] +=  n;  // Propagă transportul, spre dreapta
        }    
    }
    while( this.T[ th - 1 ] >= BAZA ) {  // Reduce şi ultima cifră, 
                     // extinzând eventual T[], cu transportul generat
        this.T[ th ] = Math.floor( this.T[ th - 1 ]/BAZA );  // .
        this.T[ th - 1 ] %= BAZA;
        this.len++;  // Corectează numărul de elemente CIFRA din 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() ) 
}
Testarea implementării:

pentru Z: var myBig = new bignum(Z);
factorul n:
alert(myBig.T); alert(myBig.mul_int(n)); alert(myBig.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 106, 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_754double 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ă 253 ≈ 9007*1012, iar max(T[i]) = 106 - 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 1012, 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 print_big_fact() (v. fişierul "qmin.js")

Factorialul numărului: (print_big_fact())

De data aceasta, 1000! rezultă în mai puţin de o secundă, 2000! în 3-4 secunde, iar 5000! rezultă în 35 secunde (15 secunde în Firefox 3.6) - 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 106 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, 
}   

Factorialul numărului (< 1000): (print_big_fact_r())

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ă browserul 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âre" până la n == stop (cu 'stop' setat în prealabil)
function big_fact_rec(big, n) {   // 'big' referă un "bignum" anterior
    if(n == stop) return big;     // "revenirile" încep când n a coborât la 'stop'
    return big_fact_rec(big.mul_int(n), n-1);  // 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 myBig
stop = 500;  // schimbă condiţia de oprire (evită "too much recursion")
document.write( big_fact_rec( myBig, 1500 ).to_str() );  // în myBig avem 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() ); // 500*501*...*1000

Modelarea calculului în baza 216

Calculul factorialului necesită numeroase operaţii de împărţire la BAZA de lucru, iar operaţia de împărţire consumă de cel puţin 20 de ori mai mult timp decât majoritatea celorlalte operaţii. Să observăm însă că dacă avem de împărţit la 10k, noi — care folosim în mod nativ baza 10 — nu facem efectiv împărţirea, ci doar deplasăm cifrele spre dreapta cu k poziţii.

Pentru calculator, baza nativă de operare este 2k, k = 8/16/32; modelând operaţiile de exemplu în baza 216, putem evita împărţirile la BAZA (= 65536) - înlocuindu-le cu operaţii "pe biţi" (AND, deplasări de biţi), incomparabil mai rapide decât împărţirea efectivă.

function factorial_hex( n ) {
    var cf = new Array();  // tabloul binar al cifrelor factorialului
    cf[0] = 1;
    for( var f = 2; f <= n; f++) {
        var t = 0;
        for(var i = 0, s = cf.length; i < s; i++) {
            var p = t + cf[i] * f;
            cf[i] =  p & 0xFFFF;  // = p % 65536;
            t = p >> 16;    // = Math.floor(p / 65536);
        }
        while(t) {
            cf[s++] =  t & 0xFFFF; 
            t >>= 16;  
        }
    }
    // Fiecărei cifre de 16 biţi din cf[] îi corespund 4 cifre hexazecimale,
    // exceptând eventual, cifra de 16 biţi cea mai semnificativă din cf[]
    var hfac = cf[cf.length - 1].toString(16);  // fără "zero padding" pe cifra "high"
    for(var i = cf.length - 2; i >= 0; i--) {
        var w = cf[i].toString(16);
        while(w.length < 4) 
            w = '0' + w;  // prefixează cu '0' ("zero padding")
        hfac += w;  // alipeşte cele 4 cifre, şirului cifrelor hexazecimale 
    }
    return hfac.toUpperCase();
}

Această funcţie este folosită în aplicaţia care urmează şi se va putea constata că viteza este mult mai mare decât în cazul bazei 106 (în pofida faptului că se operează cu cifre cam de 15 ori mai mici - având în vedere că 106 - 1 = 0xF423F, iar 65535 = 0xFFFF); 10000! a fost furnizat de programul în baza 10^6 în 220 secunde (şi mai multe click-uri 'Continue'), iar în baza 2^16 în numai 20 secunde. E drept că în primul caz am obţinut cifrele zecimale (35660 cifre), iar în al doilea doar forma hexazecimală formatată (29615 cifre hexazecimale) - ceea ce înseamnă că ar trebui să corectăm comparaţia, eliminând şi în primul program conversia la baza 10 (reducând metoda bignum_str() la bignum_str() { return this.T.reverse().join(' '); }, de exemplu); dar corecţia va fi mică, având în vedere că e vorba de conversie de la baza 10^6 la baza 10 (ceea ce nu implică operaţii de împărţire).

Aplicaţii

jsFact.zip arhivează funcţiile de mai sus (în fişierul qmin.js) şi un fişier HTML de testare care formulează următoarea aplicaţie (înscrie numărul, click Factorial, apoi click pe celelalte link-uri):

Număr: Factorial (invocă factorial_hex())

Forma hexazecimală formatată (invocă format(), v. fişierul qmin.js)

Forma zecimală (conv_dec() din qmin.js; durează, dacă n > 1000)

Verificare cu parseInt() (pentru 3..170)

Verificare calculând lg(N!) şi inversând

parseInt() poate fi de ajutor aici numai pentru valori până la 170!; aceasta, pentru că 170! are 307 cifre zecimale, iar javaScript utilizează pentru reprezentarea numerelor modelul 64bit IEEE 754 float, în care valoarea maximă reprezentabilă este (1-(1/2)^53)×2^1024 ≈ 1.797693×10^308 (deci maximum 308-309 cifre, ori 171! are deja 310 cifre zecimale).

Aplicaţia redată mai sus este o adaptare după Factoriale, unde calculul factorialului angajează (în loc de "factorial_hex()" în javaScript, cum avem aici) un program CGI a cărui sursă a fost realizată direct în limbaj de asamblare şi care poate fi încercat şi din bara de adresă a browserului, prin:

     http://docere.ro/cgi-bin/amifac.cgi?12345

obţinând o pagină care conţine pe un singur rând cifrele hexazecimale ale factorialului numărului indicat; lizibilitatea depinde de număr şi de setările browserului (de exemplu, trebuie diminuat "Text Size" pentru a vedea rezultatul apelării /amifac.cgi?70000); viteza de răspuns este de ordinul a 5 secunde pentru 100000! (care are cam 0.5 MB cifre zecimale). Selectând conţinutul şi folosind Copy&Paste - se poate obţine un fişier text conţinând cifrele respective; iar acest fişier poate fi prelucrat apoi local, cu diverse alte programe proprii.

Programul "amifac.cgi" vizat mai sus poate fi utilizat deasemenea, în orice pagină Web - incluzând în pagina respectivă un element <iframe> cu atributul src setat corespunzător. De exemplu, obţinem în această pagină, rezultatul furnizat de programul CGI menţionat:

Număr: Factorial
Număr = 3..100000, altfel se furnizează 100!

Schiţa fragmentului HTML corespunzător acestei aplicaţii cu <iframe> este următoarea:

<p>Număr: <input id="NN" value="12345" /> 
  <a href="javascript:void(0);"
     onclick = "document.getElementById('id-ifr').src='http://docere.ro/cgi-bin/amifac.cgi?' +
               document.getElementById('NN').value;">
    <b>Factorial</b>
  </a>
</p>

<iframe src="" id="id-ifr" width="95%" height="50px"></iframe>

Linkul 'Factorial' are setat "handlerul de click" onclick, prin care se determină elementul care are ID='id-ifr' (elementul <iframe>) şi i se înscrie atributul src cu valoarea HTTP necesară accesării programului "amifac.cgi", adăugând ca parametru "Query-String" valoarea existentă în elementul <input> cu atributul ID='NN'.

Înscriind acest fragment în fişierul HTML al unei pagini Web oarecare - se va obţine drept conţinut al elementului <iframe> valoarea hexazecimală a factorialului numărului tastat în elementul <input>.

vezi Cărţile mele (de programare)

docerpro | Prev | Next