Despre scopuri şi sarcini (sau despre program/aplicaţie şi subprograme)

amifac.s din Subrutină performantă pentru calculul factorialului este o subrutină în limbaj de asamblare pentru a determina factorialul numărului primit ca argument. Într-o primă etapă, factorialul se obţine în forma binară (în baza 2^32); în a doua etapă, se converteşte la baza 10^9 şi implicit la forma zecimală uzuală (care se afişează drept răspuns).

Forma binară se obţine într-un timp rezonabil: până la 5 secunde pentru valori până la 100000!; însă conversia la forma zecimală durează cam de cinci ori mai mult. Este posibilă optimizarea secvenţei de conversie, la nivelul algoritmului; dar îmbunătăţirea necesară poate să vină din altă direcţie.

În Extinderea funcţionalităţii serverului, prin CGI am arătat cum putem transforma amifac într-un program CGI; oricare client l-ar putea folosi direct din browserul său. Timpul de răspuns ar rămâne la un nivel acceptabil în cazul formei binare; dar este clar că secţiunea de conversie devine inacceptabilă, în privinţa timpului de răspuns.

Dar… de ce să se ocupe serverul de conversie?
În principiu chiar ar trebui să considerăm că după încheierea primei etape (obţinerea factorialului în baza 2^32), subrutina şi-a atins scopul (s-a obţinut factorialul cerut!); este treaba apelantului, ce face cu valoarea returnată (apelantul ar putea avea în vedere prelucrări pe care subrutina apelată nu are cum să le anticipeze: să convertească la baza 10, sau la ce bază doreşte şi să afişeze în formatul pe care-l doreşte; sau, să folosească valoarea returnată în diverse alte calcule).

Ajungem la următoarea idee de lucru şi tocmai aceasta ni se pare cea justă: eliminăm din amifac.s secvenţa de conversie la baza 10, înlocuind-o cu o secvenţă de conversie la forma hexazecimală (conversie mult mai rapidă decât la baza 10); browserul din care se apelează programul CGI va primi drept răspuns un document "text/html" conţinând reprezentarea hexazecimală a factorialului; apoi, utilizatorul va putea activa eventual, o anumită funcţie javascript prin care conţinutul hexazecimal primit să fie convertit la baza 10^k şi implicit la forma zecimală obişnuită.

Bineînţeles că şi mai just ar fi ca programul CGI respectiv să se abţină de la orice conversie (la hexazecimal? păi de ce aşa - este mai utilă forma binară, decât cea hexazecimală!), transmiţând deci nu "text/html" ci binar ("Content-type: application/octet-stream"; utilizatorul va downloada forma binară şi o va putea apoi prelucra local în orice limbaj).

În concluzie, aplicaţia ar consta din două părţi. Programul CGI amifac rulează pe server, returnând fie forma hexazecimală, fie forma binară a factorialului. La nivelul browserului, trebuie creat un formular pentru a prelua N de la utilizator; pe formular trebuie prevăzută o opţiune pentru a obţine "forma hexazecimală" (într-un anumit div din documentul HTML respectiv), sau pentru a downloada "forma binară"; deasemenea, trebuie create acele funcţii javascript care să "formateze" afişarea formei hexazecimale obţinute, sau să o convertească la forma zecimală.

"Conversie" între forma binară şi cea hexazecimală?

Să facem întâi o reparaţie, importantă aici pentru faptul că elimină opţiunea propusă mai sus, de a downloada forma binară a factorialului.

Conversia între forma binară şi cea hexazecimală - spre deosebire de conversia între binar şi zecimal, de exemplu - nu necesită operaţii pe întregul număr, ci doar pe porţiuni de câte 4 biţi - astfel că realizarea ei este aproape banală.

Obţinând forma hexazecimală, se poate obţine uşor şi forma binară, în cazul în care interesează valoarea numerică şi nu o reprezentare afişabilă; de exemplu, valoarea numerică sub forma unui tablou cu elemente de tip unsigned long se obţine transformând în binar fiecare grup de câte 8 cifre hexazecimale consecutive (astfel, pentru "1234ABCD" obţinem valoarea: 13 + 16*(12 + 16*(11 + 16*(10 + 16*(4 + 16*(3 + 16*(2 + 16*1)))))) = 305441741). Prin urmare, nu are sens să se solicite amifac şi pentru a downloada forma binară; este suficientă obţinerea formei hexazecimale.

În amifac.s am obţinut factorialul în baza 2^32, în tabloul tw[], cu nw componente (de câte 32 de biţi); următoarea secvenţă conduce la reprezentarea hexazecimală a formei binare tw[] (înlocuind secvenţa de conversie la baza 10^9; vezi articolele citate mai sus):

# amifac.s — secvenţa de conversie la forma hexazecimală a reprezentării binare din tw[]

   movl nw, %eax        # numărul de cifre hexazecimale = 8 * nw
   incl %eax
   shll $1, %eax
   pushl %eax
   call me_mmap         # alocă memorie pentru reprezentarea hexazecimală hex[]
   popl %ebx            
   movl %eax, hex
   movl %eax, %edi      # EDI = adresa de bază a tabloului hex[] alocat
   movl nw, %ecx        # ECX = nw conversii 32bit --> 8 cifre hexazecimale
   movl tw, %esi        # ESI referă cifra-32bit curentă din tw[]

FB1:
   movl (%esi), %eax    # cifra 32bit curentă din tw[]
   pushl %ecx           # câte conversii rămân de făcut

   movl $8, %ecx        # 8 cifre hexazecimale 
FB2:
   roll $4, %eax        # cei mai semnificativi 4 biţi ajung în AL (pe rangurile 3..0) 
   movb %al, %dl
   andb $0x0F, %dl      # maschează biţii de ranguri 7..4
   addb $48, %dl        # Converteşte valoarea de 4 biţi (de pe rangurile 3..0)
   cmpb $57, %dl        # la cod ASCII de cifră hexazecimală ('0'..'9', 'A'..'F')
   jna FB3
   addb $7, %dl
FB3:
   movb %dl, (%edi)     # înscrie în hex[] cifra hexazecimală rezultată
   addl $1, %edi
   loop FB2             # repetă până produce toate cele 8 cifre hexazecimale

   popl %ecx            
   addl $4, %esi        # reia conversia pentru următoarea cifră din tw[] 
   loop FB1

În secvenţa de mai sus, se citeşte din memorie (din tabloul tw[]) în registrul EAX şi - în finalul unei anumite prelucrări asupra unor porţiuni de biţi din EAX - se scrie în memorie câte un octet (cifra hexazecimală curentă). Scrierea din registru în memorie ascunde o anumită capcană, de care trebuie să ţină seama fie programatorul, fie asamblorul sau compilatorul folosit; aparent, ar fi mai rapid să cumulezi într-un registru cei 8 octeţi de scris şi să scrii în memorie (fişier) registrul respectiv (o singură scriere în memorie, în loc de 8) - numai că ordinea în care se înscriu în memorie octeţii dintr-un registru (de cel puţin 16 biţi) depinde de formatul de reprezentare (vezi endianness) al microprocesorului.

Noi avem în vedere formatul de reprezentare little endian (utilizat de microprocesoarele Intel): octetul cel mai semnificativ dintr-o valoare multi-octet standard este memorat în locaţia cu adresa mai mare. De exemplu valoarea de 4 octeţi 0xABC9DEF5 se reprezintă ca atare în regiştrii microprocesorului, dar în memorie (la scrierea din registru în memorie): 0xF5, 0xDE, 0xC9, 0xAB (indicând în ordinea crescătoare a adreselor) - spre deosebire de formatul big endian, în care ordinea octeţilor scrişi în memorie coincide cu ordinea lor din cadrul registrului.

Programul CGI amifac (dimensiune = 1.7 kB) va prelua de la server N (primit de la un browser), va testa anumite criterii pentru N, va determina N! şi va returna (după ce emite antetul HTTP "Content-type:text/html\n\n") şirul de cifre hexazecimale corespunzător (pe care serverul îl va transmite apoi browserului). Am limitat N = 3..10^5, cu timp de răspuns de până pe la 5 secunde (depinzând însă şi de trafic).

Interfaţă HTML-Javascript pentru folosirea programului CGI

Programul CGI amifac se poate apela direct de pe bara de adresă a browserului: http://sitsco.com/cgi-bin/amifac.cgi?1234 http://<HOST>/cgi-bin/amifac.cgi?1234; se obţine o pagină care conţine pe un singur rând, cifrele hexazecimale ale factorialului.

Dar este de dorit o interfaţă de lucru mai bogată în posibilităţi şi care să se integreze în contextul existent; în cazul de faţă (pe sitsco.com), pagina de bază conţine în partea dreaptă un fel de meniu; link-ul Factoriale (vezi meniul iniţial) obţine de la server pagina HTML corespunzătoare interfeţei create - redăm aici o instanţă de lucru:

Interfaţa reprodusă mai sus conţine 5-6 link-uri şi vreo trei elemente DIV. În INPUT-ul Număr s-a tastat 450; click pe link-ul factorial a determinat transmiterea către server a unei cereri de acces la programul CGI, pentru numărul tastat; răspunsul de la server a fost înscris în primul DIV (de un singur rând, cu bară de scroll orizontal). Click pe link-ul Forma hexazecimală formatată a activat o anumită funcţie javascript care a despărţit conţinutul primului DIV în grupuri de câte 8 cifre şi a înscris rezultatul pe mai multe rânduri, în al doilea DIV. Analog, click pe link-ul Forma zecimală activează funcţia javascript care converteşte la baza 10 conţinutul existent în primul DIV al paginii. Link-urile Verificare activează una sau alta dintre funcţiile javascript care permit obţinerea valorii factorialului, trunchiate la primele câteva cifre (şi cu precizarea numărului de cifre zecimale).

În esenţă (reţinând numai structura şi funcţionalitatea principală asociată), sursa HTML corespunzătoare s-ar prezenta astfel:

Număr: <input type="text" id="N" value="100"/> 
<a href="#" onclick="new Ajax.Updater('ret_ami', 
                                      'cgi-bin/amifac.cgi'+'?'+$('N').value);">
<b>Factorial</b></a> <div id="ret_ami" class="divcss1"> </div>

<a href="#" onclick="var ram = $('ret_ami'); format(ram.innerHTML, 'div_16');">
Forma hexazecimală <i>formatată</i></a> <div id="div_16" class="divcss1"> </div>

<a href="#" onclick="conv_dec($('ret_ami'), 'div_10');">
Forma zecimală</a> <div id="div_10" class="divcss1"> </div>

<a href="#" onclick="$('ver_js').innerHTML = parseInt($('ret_ami').innerHTML, 16);">
Verificare</a> <span id="ver_js"> </span>

<a href="" onclick="$('ver_lg').innerHTML = lg_factorial($('N').value)">
Verificare</a> <span id="ver_lg"> </span>

Contextul aplicaţiei include biblioteca prototype.js. Evenimentul onclick asociat link-ului Factorial lansează Ajax.Updater(container, URL) din prototype.js, prin care se trimite serverului o cerere de acces la URL (pentru executarea programului CGI menţionat), urmând ca răspunsul returnat să fie înscris în diviziunea din pagină menţionată prin parametrul "container". În esenţă, $(id) este un "shortcut" introdus de prototype.js pentru funcţia DOM getElementById(id).
În "Model JS-prototype pentru algoritmul lui Dijkstra" (Gazeta de informatică nr. 4/2007) avem un alt exemplu de folosire a bibliotecii prototype.js.
Între timp am înlocuit prototype.js cu jQuery (dar "logica" vizată aici este aceeaşi).

Funcţia javascript conv_dec(dh, dz) primeşte în dh ID-ul diviziunii care conţine şirul cifrelor hexazecimale şi în dz ID-ul diviziunii în care trebuie înscrisă forma zecimală corespunzătoare; conversia este realizată folosind schema lui Horner: valoarea zecimală parţială se înmulţeşte cu vechea bază 16 şi se cumulează cu următoarea cifră hexazecimală - având grijă ca toate calculele să fie modelate faţă de noua bază, 10.

function conv_dec(dh, dz) {
    var h = $(dh).innerHTML.split('');  // h[] = tabloul cifrelor hexazecimale
    var nx = h.length;
    var z = new Array(); z[0] = 0; var nz = 1;  // z[] = tabloul cifrelor zecimale
    var i=0, j=0, q=0;
    for(i=0; i < nx; i++) {  // Înlocuieşte codurile ASCII ale cifrelor
        switch(h[i]) {       //      prin valorile numerice.
          case 'A': h[i] = 10; break;
          case 'B': h[i] = 11; break;
          case 'C': h[i] = 12; break;
          case 'D': h[i] = 13; break;
          case 'E': h[i] = 14; break;
          case 'F': h[i] = 15; break;
          default: h[i] -= 0;
        }
    }
    for(i=0; i < nx; i++) {
        q = 0; nz = z.length;
        for(j=0; j < nz; j++) { // înmulţeşte z[]-curent cu vechea bază 16
            q += 16*z[j]; 
            z[j] = q % 10;
            q = Math.floor(q / 10);  
        }
        while(q) {      // completează (prin propagare) cu transportul final
            z[j++] = q % 10;
            q = Math.floor(q / 10);
        }
        q = z[0] + h[i];        // adaugă cifra hexazecimală curentă
        z[0] = q % 10;
        q = Math.floor(q / 10);
        j = 1;
        while(q) {      // şi completează, dacă există transport final
            if(z[j]) q += z[j];
            z[j++] = q % 10;
            q = Math.floor(q / 10);
        }
    }
    format(z.reverse().join(''), dz);  // Inversează cifrele, transformă în şir
                                       // şi apelează format().
    return z.length;  // returnează numărul de cifre zecimale
}   

Funcţia format(şir, dest) apelată în final, primeşte o referinţă la şirul de cifre (fie zecimale, fie hexazecimale), separă prin câte un spaţiu grupurile de câte 8 cifre (intercalând câte un <br> după fiecare 8 grupuri) şi înscrie rezultatul final în diviziunea "dest".

Interfaţa este completată cu două posibilităţi de verificare a rezultatului. Funcţia nativă javascript parseInt(şir, bază) transformă şirul indicat (asumând că el este scris în baza indicată) în valoare numerică; de exemplu, înscriind în bara de adresă a browserului javascript: alert( parseInt( "1B30964EC395DC24069528D", 16 ) ) se va obţine 5.2592709452685623e+26 - adică şirul de cifre hexazecimale transmis are o valoare numerică de 27 cifre zecimale ("e+26" înseamnă "*10^26"), dintre care primele 16-17 cifre sunt cele precizate în răspuns.

parseInt() poate fi de ajutor aici numai pentru valori până la 170! (pentru valori mai mari se va obţine "infinit"); 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).

O a doua funcţie de verificare se bazează pe calculul logaritmic (se însumează logaritmii cifrelor factorialului şi se inversează rezultatul - în sensul de inversare a funcţiei logaritmice); funcţia a fost prezentată deja, în "Hello world!".