Momente şi schiţe de informatică

factorial

factorial(n) = 2*3*4*...*n (notat n! - Christian Kramp, 1808)
produsul primelor n numere naturale

Extinderea funcţionalităţii serverului, prin CGI 2007 sep

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".
Subrutină performantă pentru calculul factorialului 2007 oct

Optimizări (faţă de programul în limbaj de asamblare pentru n!, realizat în "Hello World!") asupra algoritmului, asupra conversiei (baza 10⁹) ş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 2³² (în loc de modelul iniţial, bazat pe reprezentarea în baza 2¹⁶). Conversia la forma zecimală este realizată acum prin intermediul bazei 10⁹ (numerele 0..10⁹-1 - "încap" pe 32 biţi), în loc de 10⁴, 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).
Distribuirea calculului factorialului: CGI şi Javascript 2007 nov

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 on-line: click pe link-ul Factoriale din bara de meniu; 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).
Experimente cu factoriale in javaScript 2008 dec

Câte cifre are n! şi care sunt cifrele iniţiale? Câte cifre zecimale are 2²⁰⁰⁹ şi care sunt primele câteva cifre?
Există n încât n! să aibă n cifre zecimale? Există n încât n! să aibă n cifre hexazecimale?

Modelarea comparativă a calculului factorialelor în bazele 10, 10⁶, 2¹⁶ (în javaScript).

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. Rezultă că 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ă.

A vedea şi Factoriale (aplicaţie accesibilă şi de pe bara de meniu).

Media Dinamică

Drumuri

ŞahStartTemp

Localităţi

Judeţ:

Bliţuri

Load another random Bliţ

Linux şi aplicaţii Web
în 24 de ore

Orar şcolar
documentaţie Sphinx