Distribuirea calculului factorialului: CGI şi Javascript
Anterior (a vedea "Hello World!" şi Subrutină performantă pentru calculul factorialelor) am realizat o subrutină în limbaj de asamblare pentru n!. Î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ă. Forma binară se obţine în 0-5 secunde (n <= 100000); însă conversia la forma zecimală durează cam de cinci ori mai mult.
Este posibilă optimizarea secvenţei de conversie… dar de ce să se ocupe serverul de conversie? (şi nu browserul). Serverul trebuie să returneze rezultatul - punct! Iar rezultatul este în cazul de faţă o valoare numerică brută, în formă binară (cel mult, hexazecimală). Cel care l-a cerut (nu serverul), trebuie să ştie ce vrea să facă cu rezultatul obţinut - să-l afişeze treaba lui cum, sau să-l utilizeze ca atare (ca valoare numerică) în calcule proprii ulterioare.
Cererea http://<HOST>/cgi-bin/amifac.cgi?1234 primeşte de la server factorialul numărului 1234, în hexazecimal. Aplicaţia rezultată este pusă la dispoziţie prin Factoriale; interfaţa conţine şi o funcţie javascript de conversie la baza 10 a unui şir de cifre hexazecimale de orice lungime (folosind schema lui Horner).
Substratul problemei ("inside-out")
Atitudinea funcţionărească şi atitudinea creatoare, faţă de "probleme".
A ignora legăturile posibile înseamnă a scăpa şansa de "a reinventa roata", adică şansa de a învăţa regândind lucrurile.
Ecuaţia µ2 - µ + 1 = 0 provine din (abcd) = (acdb) sau (abcd) = (adbc); deci un raport este echianarmonic dacă şi numai dacă el se păstrează în urma unei permutări circulare între trei numere... coeficienţii sunt funcţii simetrice de a, b, c - deci se vor putea exprima prin coeficienţii ecuaţiei de gradul trei care are ca rădăcini numerele a, b, c; regăsim pe această cale elementară - "reinventând roata", aşa-i? - condiţia în care o ecuaţie de gradul trei are rădăcini reale (o teoremă a lui Joachimsthal) şi restabilim o metodă (dată de Cayley) de rezolvare a ecuaţiilor de gradul trei.
Subrutină performantă pentru calculul factorialului
Optimizări (faţă de programul în limbaj de asamblare pentru n!, realizat în "Hello World!") asupra algoritmului, asupra conversiei (baza 109) şi asupra folosirii instrucţiunii de împărţire DIV.
Se înlocuieşte înmulţirea cu fiecare factor, prin înmulţire cu produs de factori, iar operaţiile sunt modelate acum în baza 232 (în loc de modelul iniţial, bazat pe reprezentarea în baza 216). Conversia la forma zecimală este realizată acum prin intermediul bazei 109 (numerele 0..109-1 - "încap" pe 32 biţi), în loc de 104, din varianta precedentă.
Instrucţiunea microprocesorului DIV necesită cel puţin 16/24/40 tacţi pe I80486 şi 17/25/41 tacţi pe Pentium, după cum împărţitorul are 8/16/32 biţi; se rescrie programul, înlocuind împărţirea la operand (cu DIV) prin înmulţirea cu inversul operandului (MUL fiind mai rapidă ca DIV).
Extinderea funcţionalităţii serverului, prin CGI
scriere nu înseamnă neapărat "scriere pe ecran", ci comunicare (între procese); parametrii pot fi transmişi prin intermediul "variabilelor de mediu" (de ex., prin QUERY_STRING).
CGI extinde funcţionalitatea clasică a serverului; browserul cere serverului nu un anumit fişier, ci rezultatul execuţiei unui anumit program; serverul lansează programul respectiv şi transmite browserului ceea ce "scrie" la STDOUT programul executat. Acest program poate să fie cam în orice limbaj (fie ca script, fie ca "executabil"), dar trebuie să fie locat într-un anumit director (/cgi-bin/
) şi trebuie să-şi formuleze "outputul" prefixându-l cu anumite headere HTTP ('Content-type').
Se prezintă exemple de programe CGI: mimeTeX analizează o expresie matematică primită ca parametru şi returnează imaginea GIF corespunzătoare; programe în C, în perl, în limbaj de asamblare pentru lista de "environment variables".
Formulăm în diverse limbaje, soluţionarea unei aceleiaşi probleme—calculul factorialului (recursiv). Vizăm aspecte de elaborare, aspectele algoritmice necesare şi corelaţii fireşti între limbaje.
Câte cifre are n!; aplicaţie (javascript + HTML) bazată pe logaritmi. Aplicaţie pentru compararea numărului de operaţii cifră-cu-cifră necesare calculului n! în baza 10, respectiv în baza 256.
n! în limbajele bc, PHP, Python; modelare OOP în javascript folosind baza 106; program perl folosind modulul Math::BigInt; modelare OOP în perl folosind baza 106; program C folosind biblioteca GMP; modelare OOP în C++ (GCC g++) folosind baza 216 (şi conversie la baza 104); program în limbaj de asamblare GNU as şi elemente de programare în limbaj de asamblare sub Linux (transmiterea parametrilor, funcţia mmap(), folosirea apelurilor de sistem, instrucţiunea int 0x80; folosirea instrucţiunilor FPU; investigaţii asupra fişierului executabil).
vezi Cărţile mele (de programare)